Minimizing the energy consumption of computing is essential to improve efficiency and enable further performance growth. A central point where to address this is in the scheduling of tasks onto multiprocessor systems. In many previous studies the focus of static scheduling algorithms has been on the energy consumption of the processors, where techniques like Dynamic Voltage and Frequency Scaling (DVFS) have been successfully utilized. Despite the large body of work, a notable gap exists: the energy consumed by data transfer, in particular by inter-processor communication, is neglected, even though it becomes more and more significant. To address this, we introduce a revised model that incorporates the energy costs related to task communication, combining it with the existing DVFS techniques and different static energy models. Using the proposed novel energy model, we adjust existing and propose new algorithms and study their performance as influenced by the newly introduced energy parameters. The algorithms cover both major categories, namely : list-scheduling and cluster-scheduling. Using a large set of task graphs of many different structures and sizes, and different parallel systems, our evaluation offers an extensive comparison of the algorithms and provides insights into their ability to conserve energy within the new model’s framework.

Deep neural networks (DNNs) are increasingly deployed in real-time applications, yet their inference performance is often constrained by inefficient GPU utilization. While various inter-operator scheduling methods have been proposed to address this issue, many suffer from coarse-grained operator classifications, incomplete parallelism, unawareness of GPU resource contention, etc. To overcome these limitations, we propose HIOCS, a heuristic inter-operator co-scheduling framework that accelerates DNN inference on GPUs through fine-grained kernel-level scheduling. HIOCS employs a graph optimization technique at kernel granularity that reconstructs data dependencies based on memory access patterns, thereby uncovering latent parallelism. Building on this optimized graph, a heuristic co-scheduling algorithm is introduced to prioritize critical-path kernels and selectively co-locate non-critical kernels by jointly considering latency impact, resource contention, and kernel affinity to minimize makespan and maximize GPU utilization. Extensive experiments on popular DNN models across diverse domains demonstrate that HIOCS consistently achieves higher GPU utilization and better scalability. Compared to PyTorch default mode and the state-of-the-art method Opara, HIOCS achieves up to$21.19 \times$and$1.13 \times$speedup in inference latency, respectively, making it well-suited for latency-sensitive deployment scenarios.

Task scheduling for parallel computing is strongly NP-hard even without precedence constraints$P||C_{max}$. With any kind of precedence constraints and communication delays the problem becomes less manageable still. We look at the specific case of scheduling under the precedence constraints of a fork-join structure (including communication delays)$P[Q]|fork-join, c_{ij}|C_{max}$. This represents any kind of computation that divides into sub-computations with the end results being processed together. Looking at special cases where computation costs are equal, we propose polynomial time approximations and exact algorithms for them, considering homogenous and (related) heterogenous processors. Having those algorithms allows us to study the quality of heuristics in a large experimental evaluation. This demonstrates that heuristic schedulers perform well enough in most cases.

Scheduling task graphs with communication delay is a widely studied NP-hard problem. Many heuristics have been proposed, but there is no constant approximation algorithm for this classic model. In this paper, we focus on the scheduling of the important class of fork-join task graphs (describing many types of common computations) on homogeneous processors. For this sub-case, we propose a guaranteed algorithm with a $\left( {1 + \frac{m}{{m - 1}}} \right)$-approximation factor, where m is the number of processors. The algorithm is not only the first constant approximation for an important sub-domain of the classic scheduling problem, it is also a practical algorithm that can obtain shorter makespans than known heuristics. To demonstrate this, we propose adaptations of known scheduling heuristic for the specific fork-join structure. In an extensive evaluation, we then implemented these algorithms and scheduled many fork-join graphs with up to thousands of tasks and various computation time distributions on up to hundreds of processors. Comparing the obtained results demonstrates the competitive nature of the proposed approximation algorithm.

No abstract available.

Task scheduling for parallel computing is strongly NP-hard even without precedence constraints P||Cmax. With any kind of precedence constraints and communication delays the problem becomes less manageable still. We look at the specific case of scheduling under the precedence constraints of a fork-join structure (including communication delays) P|fork − join, cij|Cmax. This represents any kind of computation that divides into sub-computations with the end results being processed together, such as divide and conquer. This kind of computation is fundamental. We look at the instances where some of the computation and communication costs are constant, present polynomial time algorithms for them, and explore the boundary between tractability and NP-hardness around this problem.

Efficient architectures and implementations of median filters have been well investigated in the past. In this article, we focus on median filters for very big scientific applications with very large windows and an infinite stream of data, inspired by big data needs in the Square Kilometre Array (SKA) pulsar search engine, but transferable to other big data domains. We propose a novel approach for very large rectangular windows on an FPGA accelerator device able to support the processing of infinite streams of data. OpenCL is used for rapid parameter sweeping and design space exploration based on a pipelined model of the system. Evaluation on a host/accelerator system with an Arria 10 device surpassed 64 million values processed per second considered for the SKA real time requirement, achieving 83.4M value/s while reading from/writing to disk. These results are compared with a state-of-the-art software implementation only achieving 41M value/s for over twice the total system energy cost.

The computing continuum's actual trend is facing a growth in terms of devices with any degree of computational capability. Those devices may or may not include a full-stack, including the Operating System layer and the Application layer, or just facing pure bare-metal solutions. In either case, the reliability of the full system stack has to be guaranteed. It is crucial to provide data regarding the impact of faults at all system stack levels and potential hardening solutions to design highly resilient systems. While most of the work usually concentrates on the application reliability, the special session aims to provide a deep comprehension of the impact on the reliability of an embedded system when faults in the hardware substrate of the system stack surface at the Operating System layer. For this reason, we will cover a comparison from an application perspective when hardware faults happen in bare metal vs. real-time OS vs. general-purpose OS. Then we will go deeper within a FreeRTOS to evaluate the contribution of all parts of the OS. Eventually, the Special Session will propose some hardening techniques at the Operating System level by exploiting the scheduling capabilities.

Small satellites, such as CubeSats, have to respect time, spatial and energy constraints in the harsh space environment. To tackle this issue, this paper presents and evaluates two fault tolerant online scheduling algorithms: the algorithm scheduling all tasks as aperiodic (called ONEOFF) and the algorithm placing arriving tasks as aperiodic or periodic tasks (called ONEOFF & CYCLIC). Based on several scenarios, the results show that the performances of ordering policies are influenced by the system load and the proportions of simple and double tasks to all tasks to be executed. The “Earliest Deadline” and “Earliest Arrival Time” ordering policies for ONEOFF or the “Minimum Slack” ordering policy for ONEOFF & CYCLIC reject the least tasks in all tested scenarios. The paper also deals with the analysis of scheduling time to evaluate real-time performances of ordering policies and shows that ONEOFF requires less time to find a new schedule than ONEOFF & CYCLIC. Finally, it was found that the studied algorithms perform well also in a harsh environment.

Task scheduling with communication delays is an NP-hard problem. Some previous attempts at finding optimal solutions to this problem have used branch-and-bound state-space search, with promising results. Duplication is an extension to the task scheduling model which allows tasks to be executed multiple times within a schedule, providing benefits to schedule length where this allows a reduction in communication costs. This article proposes the first approach to state-space search for optimal task scheduling with task duplication. Also presented are new definitions for important standard bounding metrics in the context of duplication. An extensive empirical evaluation shows that the use of duplication significantly increases the difficulty of optimal scheduling, but the proposed approach also gives certainty that a large proportion of task graphs can be scheduled more effectively when duplication is allowed, and permits to quantify the exact advantage.

Summary OpenMP is a popular multiprocessing interface to parallelize different domains of applications. A previously proposed extension has made it possible for OpenMP to speedup event‐driven programs. There, a virtual target model extension is used to incrementally introduce asynchronous execution into an OpenMP program. At the same time it allows a mixture of nested parallelism with asynchronous processing. This new possibility raises the question how to use available processors/threads, for parallelism or for asynchronous execution? To investigate the best combination of asynchronization and parallelization, a performance model for measuring parallel event‐driven systems is proposed. Based on queue theory, the theoretical analysis discovers some interesting facts in an event‐driven system. Then, experiments are conducted to study the best practice of improving event‐driven programs and how to balance parallelism and asynchronous execution. By comparing it with the OpenMP tasking model, the evaluations demonstrate the effectiveness and flexibility of the virtual target model, which is able to achieve significantly better parallel event‐driven performance.

Summary Parallel computing techniques have been supported by programming languages in two major ways: either library‐based APIs or extended language constructs. Library‐based features are portable and offer fine‐grained control on parallelization details. However, they rely on individual programmer skills; thus, they may lead to inconsistent implementations and considerable code restructurings. On the contrary, language constructs promote environments that largely conceal the details of parallel programming techniques. However, they normally reduce programmer control over the granularity of parallelization and impose additional development concepts and compilation requirements that may sacrifice ease of use and portability. Therefore, approaches that balance between programmer control on parallelization details, intuitiveness of concepts, and portability can gain priority over other paradigms. In this paper, we discuss @PT (Annotation Parallel Task), a parallel computing framework that proposes Java annotations, standard Java components, as its language constructs. @PT takes an object‐oriented approach on efficient execution and management of asynchronous tasks, with a special focus on GUI‐responsive applications. This paper presents the annotation‐based programming interface of the framework and its fundamental parallelization concepts. Furthermore, it studies the usability and performance of @PT by comparisons with other Java parallelization approaches in a set of standard benchmarks. The observations suggest that @PT maintains a simple programming interface, whereas it performs efficiently in different parallel computing domains.

Loop pipelining is an essential technique in high-level synthesis to increase the throughput and resource utilisation of field-programmable gate array--based accelerators. It relies on modulo schedulers to compute an operator schedule that allows subsequent loop iterations to overlap partially when executed while still honouring all precedence and resource constraints. Modulo schedulers face a bi-criteria problem: minimise the initiation interval (II; i.e., the number of timesteps after which new iterations are started) and minimise the schedule length. We present Moovac, a novel exact formulation that models all aspects (including the II minimisation) of the modulo scheduling problem as a single integer linear program, and discuss simple measures to prevent excessive runtimes, to challenge the old preconception that exact modulo scheduling is impractical. We substantiate this claim by conducting an experimental study covering 188 loops from two established high-level synthesis benchmark suites, four different time limits, and three bounds for the schedule length, to compare our approach against a highly tuned exact formulation and a state-of-the-art heuristic algorithm. In the fastest configuration, an accumulated runtime of under 16 minutes is spent on scheduling all loops, and proven optimal IIs are found for 179 test instances.

The Square Kilometre Array (SKA) project will be the world’s largest radio telescope array. With its large number of antennas, the number of signals that need to be processed is dramatic. One important element of the SKA’s Central Signal Processor package is pulsar search. This article focuses on the FPGA-based acceleration of the Frequency-Domain Acceleration Search module, which is a part of SKA pulsar search engine. In this module, the frequency-domain input signals have to be processed by 85 Finite Impulse response (FIR) filters within a short period of limitation and for thousands of input arrays. Because of the large scale of the input length and FIR filter size, even high-end FPGA devices cannot parallelise the task completely. We start by investigating both time-domain FIR filter (TDFIR) and frequency-domain FIR filter (FDFIR) to tackle this task. We applied the overlap-add algorithm to split the coefficient array of TDFIR and the overlap-save algorithm to split the input signals of FDFIR. To achieve fast prototyping design, we employed OpenCL, which is a high-level FPGA development technique. The performance and power consumption are evaluated using multiple FPGA devices simultaneously and compared with GPU results, which is achieved by porting FPGA-based OpenCL kernels. The experimental evaluation shows that the FDFIR solution is very competitive in terms of performance, with a clear energy consumption advantage over the GPU solution.

The Square Kilometer Array, which will be the world's largest radio telescope, will enhance and boost a large number of science projects, including the search for pulsars. The frequency-domain acceleration search is an efficient approach to search for binary pulsars. A significant part of it is the harmonic-summing module, which is the research subject of this paper. Most of the operations in the harmonic-summing module are relatively cheap operations for field-programmable gate arrays (FPGAs). The main challenge is the large number of point accesses to off-chip memory, which are not consecutive but irregular. Having the harmonic summing on the FPGA will avoid off-board communication with other pulsar search modules, which could destroy other acceleration benefits. Two types of harmonic-summing approaches are investigated in this paper: (1) storing intermediate data in off-chip memory and (2) processing the input signals directly without storing. For the second type, two approaches of caching data are proposed and evaluated: (1) preloading points that are frequently touched and (2) preloading all necessary points that are used to generate a chunk of output points. Open Computing Language (OpenCL) is adopted to implement the proposed approaches. In an extensive experimental evaluation, the same OpenCL kernel codes are evaluated on FPGA boards and GPU cards. Regarding the proposed preloading methods, preloading all necessary points method while reordering the input signals is faster than all the other methods. While in raw performance, a single-FPGA board cannot compete with a GPU. Regarding energy dissipation, GPU costs up to 2.6× times more energy than that of FPGAs in executing the same NDRange kernels.

Modulo scheduling is a key throughput optimisation when compiling for VLIW architectures, which has been applied successfully to high-level synthesis (HLS) of hardware accelerators in the past. However, problem instances in the HLS context usually have larger and denser dependence graphs and may contain many simple operations that are not subject to resource constraints, causing long runtimes with VLIW-centric modulo schedulers. We propose a complexity-reduction approach for existing exact modulo schedulers that retains their ability to compute provably optimal schedules, but shortens their runtime on typical HLS instances. The basic idea is to simplify a problem instance's dependence graph by abstracting entire subgraphs of non-critical operations with a single edge, then schedule this reduced problem comprising only the critical operations. A solution obtained for the reduced problem can be easily completed to a solution for the original problem. Applied to the well-known, originally VLIW-centric, and exact ILP formulation by Eichenberger and Davidson, we show a mean speedup of 4.37× for 21 large instances, which makes it competitive again with the recently proposed, HLS-tailored Moovac formulation. As both formulations show different problem-dependent strengths and weaknesses, these insights are a first step towards an oracle that selects the most promising scheduler for a given problem instance.

Large scale median filtering algorithms are investigated in the context of the Square Kilometre Array (SKA) pulsar search; a signal processing pipeline estimated to require more than 10POps on 60PB of search data collected per day. Real time performance is needed for rectangular median windows of 63 frequency channels across 1023 time steps, requiring at least 64 million values to be calculated and output per second. This paper proposes an algorithmic approach for large scale median filtering based on existing techniques, providing improvements for the heterogeneous system used and utilising a high-end FPGA accelerator. Taking advantage of OpenCL for rapid parameter sweeping, the design space was explored to find the best algorithmic approach. The evaluation results are promising and show output of up to 99.3 million values per second on an Arria-10 FPGA, coming close to the limits set by resources and bandwidth. These results are set into relation with GPU and CPU implementations for the same algorithm, taking advantage of the OpenCL portability, achieving up to 16.8 and 9.1Mvalue/s respectively.

High-level approaches to hardware development can expedite the design process, allowing for rapid design space exploration. However, in order to generate optimised solutions expert intervention is often still required. This work seeks to explore the relationship between high-level descriptions and the resulting hardware architecture. This aims to reduce the barrier to entry for software developers (without hardware expertise) to produce optimised hardware designs through application of classical loop optimisation techniques. An algorithm from the Square Kilometre Array (SKA) is chosen to demonstrate the effects of such changes in a real world, real-time application requiring high throughput and low power consumption, taking a systematic approach in order to achieve an optimised result. A systolic array design is also discussed and compared with the software style changes. The Intel FPGA SDK for OpenCL (AOCL) Offline Compiler (AOC) is used here for verification and synthesis of the designs being examined, targeting an Arria-10 FPGA accelerator.

Pulsar search is one of the main tasks for the Square Kilometre Array (SKA) central signal processor (CSP) sub-element. Because most of the pulsar details are unknown, many pulsar search approaches are employed. The main compute-intensive application of the pulsar search modules is the matched filter group, which convolves the input signals with a group of filters. High-performance designs on FPGAs have been proposed that can process multiple large filters efficiently. But given that in many applications, including the here targeted pulsar search, filters have different sizes, there is a high potential for optimisation. This paper investigates the optimisation of general matched filtering design for the SKA pulsar search engine. The influence of changing the number of filters and the difference in sizes is analysed. The general implementations in time-domain (TD) and frequency-domain (FD) are optimised, employing the longest processing time (LPT) first rule to distribute filter templates across filter processing pipelines. The proposed design is employed to implement the matched filter groups in two SKA pulsar modules. The results show that the optimisation can provide up to 2.1× speedup in TD and 1.2× speedup in FD.

The sophisticated nature of parallel computing concepts makes parallel programming challenging. This has encouraged investigations for higher-level frameworks that conceal much of the complications behind abstraction layers. Paradigms in this category are mostly performance centric, and do not share the same sentiments for the robustness of asynchronous executions. This is while current applications demand consistency and soundness in addition to fast performance. Therefore, programming environments that offer high-level support for asynchronous exception handling will have higher chances for popularity. This paper discusses our latest enhancements to @PT, a parallel computing environment that is based on Java annotations. The proposed concept promotes the robustness of parallelized programs by adhering to the familiar exception handling standards of sequential codes, and reducing the asynchronous execution concerns in the API level. This study suggests that the concept simplifies efficient management of asynchronous exception handling concepts that appears to be challenging in parallel programming.

This paper is aimed at studying fault-tolerant design of the realtime multi-processor systems and is in particular concerned with the dynamic mapping and scheduling of tasks on embedded systems. The effort is concentrated on scheduling strategy having reduced complexity and guaranteeing that, when a task is input into the system and accepted, then it is correctly executed prior to the task deadline. The chosen method makes use of the primary/backup approach and this paper describes its refinement based on reduction of windows within which the primary and the backup copies can be scheduled. The results show that the use of restricted scheduling windows reduces the algorithm complexity by up to 15%.

Scientific workloads are often described by Directed Acyclic task Graphs. Indeed, DAGs represent both a theoretical model and the structure employed by dynamic runtime schedulers to handle HPC applications. A natural problem is then to compute a makespan-minimizing schedule of a given graph. In this paper, we are motivated by task graphs arising from multifrontal factorizations of sparse matrices and therefore work under the following practical model. Tasks are malleable (i.e., a single task can be allotted a time-varying number of processors) and their speedup behaves perfectly up to a first threshold, then speedup increases linearly, but not perfectly, up to a second threshold where the speedup levels off and remains constant. After proving the NP-hardness of minimizing the makespan of DAGs under this model, we study several heuristics. We propose model-optimized variants for PROPSCHEDULING, widely used in linear algebra application scheduling, and FLOWFLEX. GREEDYFILLING is proposed, a novel heuristic designed for our speedup model, and we demonstrate that PROPSCHEDULING and GREEDYFILLING are 2-approximation algorithms. In the evaluation, employing synthetic data sets and task graphs arising from multifrontal factorization, the proposed optimized variants and GREEDYFILLING significantly outperform the traditional algorithms, whereby GREEDYFILLING demonstrates a particular strength for balanced graphs.

In scheduling theory and parallel computing practice, programs are often represented as directed acyclic graphs. Finding a makespan-minimising schedule for such a graph on a given number of homogenous processors (PIprec; cijICmax) is an NP-hard optimisation problem. Among the many proposed heuristics, the two dominant approaches are list-scheduling and cluster-scheduling (based on clustering), whereby clustering targets an unlimited number of processors at its core. Given their heuristic nature, many experimental comparisons exist. However, their overwhelming majority compares algorithms within but not across categories. Hence it is not clear how cluster-scheduling, for a limited number of processors, performs relative to list-scheduling or how list-scheduling, for an unlimited number of processors, performs against clustering. This study addresses these open questions by comparing a large set of representative algorithms from the two approaches in an extensive experimental evaluation. The algorithms are discussed and studied in a modular nature, categorizing algorithms into components. Some of the included algorithms are previously unpublished combinations of these techniques. This approach also permits to study the separate merit of techniques like task insertion or lookahead. The results show that simple low-complexity algorithms are surprisingly competitive and that more sophisticated algorithms only exhibit their strengths under certain conditions.

The problem of task scheduling with communication delays is NP-hard. State-space search algorithms such as A* have been shown to be a promising approach to solving this problem optimally. A recently proposed state-space model for task scheduling, known as Allocation-Ordering (AO), allows state-space search methods to be applied to the problem of optimal task scheduling without the need for duplicate avoidance mechanisms. This paper examines the performance of two parallel search algorithms when applied to both the AO model and the older ELS state-space model. This suggests that its use may provide an advantage with many different variations on state-space search. This paper explores the application of AO to some of these variants, namely depth-first branch-and-bound (DFBnB) and parallel search. We also present an update to the formulation of AO that prevents invalid states from being considered during a search. An evaluation shows that AO gives a clear advantage to DFBnB and allows greater scalability for parallel search algorithms. The update to AO's formulation has no significant impact on performance either way.

In high-level synthesis, loop pipelining is a technique to improve the throughput and utilisation of hardware datapaths by starting new loop iterations after a fixed amount of time, called the initiation interval (II), allowing to overlap subsequent iterations. The problem is to find the smallest II and corresponding operation schedule that fulfils all data dependencies and resource constraints, both of which are usually found by modulo scheduling.

The Square Kilometre Array (SKA) project will be the world largest radio telescope array. With the growth of the number of antennas, the signals that need to be processed increase dramatically. One import element of the SKA central signal processor (CSP) package is pulsar search. This paper focuses on the FPGA-based acceleration of the frequency-domain acceleration search (FDAS) module, part of SKA pulsar search. In FDAS, the frequency-domain input signals have to be processed by 85 421-tap FIR filters within a short time limit and for thousands of input arrays. Because of the large scale of input length and FIR filter size, even high-end FPGA devices cannot parallelize the task completely. We start by investigating both time-domain FIR filter (TDFIR) and frequency-domain FIR filter (FDFIR) to tackle the FDAS task. We applied the overlap-add algorithm (OLA) to split the coefficient array of TDFIR and the overlap-save algorithm (OLS) to split the input signals of FDFIR. To achieve fast prototyping design, we applied OpenCL, which is a high-level FPGA development technique, to develop high-end FPGAs. The performance and power consumption are evaluated and compared with GPU results, which is achieved by porting FPGA-based OpenCL kernels. The experimental evaluation shows that the FD solution is very competitive in terms of performance, with a clear energy consumption advantage over the GPU solution.

Summary Biomedical modelling that is mathematically described by ordinary differential equations (ODEs) is often one of the most computationally intensive parts of simulations. With high inherent parallelism, hardware acceleration based on field programmable gate array has great potential to increase the computational performance of the ODE model integration while being very power efficient. ODE‐based Domain‐specific Synthesis Tool is a tool we proposed previously to automatically generate the complete hardware/software co‐design framework for computing biomedical models based on CellML. Although it provides remarkable performance improvement and high energy efficiency compared with CPUs and GPUs, there is still a great potential for optimisation. In this paper, we investigate a set of optimisation strategies including compiler optimisation, resource fitting and balancing, and multiple pipelines. They all have in common that they can be performed automatically and hence can be integrated in our domain‐specific high level synthesis tool. We evaluate the optimised hardware accelerator modules generated by ODE‐based Domain‐specific Synthesis Tool on real hardware based on their resource usage, processing speed and power consumption. The results are compared with single threaded and multi‐core CPUs with/without Streaming SIMD Extension (SSE) optimisation and a graphics card. The results show that the proposed optimisation strategies provide significant performance improvement and result in even more energy‐efficient hardware accelerator modules. Furthermore, the resources of the target field programmable gate array device can be more efficiently utilised in order to fit larger biomedical models than before. Copyright © 2015 John Wiley & Sons, Ltd.

Dynamic biomedical systems are mathematically described by Ordinary Differential Equations (ODEs) and their solution is often one of the most computationally intensive parts in biomedical simulations. With high inherent parallelism, hardware acceleration based on Field-Programmable Gate Arrays (FPGAs) has great potential to increase the computational performance of the model simulations, while being very power-efficient. However, the manual hardware implementation is complex and time consuming. The advantages of FPGA designs can only be realised if there is a general solution to automate the process. In this article, we propose a domain-specific high-level synthesis tool called ODoST that automatically generates an FPGA-based Hardware Accelerator Module (HAM) from a high-level description. In this direct approach, ODE equations are directly mapped to processing pipelines without any intermediate architecture layer of processing elements. We evaluate the generated HAMs on real hardware based on their resource usage, processing speed, and power consumption, and compare them with CPUs and a GPU. The results show that FPGA implementations can achieve 15.3 times more speedup compared to a single core CPU solution and perform similarly to an auto-generated GPU solution, while the FPGA implementations can achieve 14.5 times more power efficiency than the CPU and 3.1 times compared to the optimised GPU solution. Improved speedups are foreseeable based on further optimisations.

The simulation of biomedical models often requires the numerical integration of ordinary differential equation systems, a computationally intensive task that can be accelerated well by deeply-pipelined FPGA-based accelerators. Since the main design target is throughput, larger FPGA devices can easily be exploited by scaling-up the number of parallel datapath instances on a chip. To this end, reducing the area of each datapath becomes a key optimisation. High-level synthesis can be employed to generate custom simulation accelerators from standardised cell descriptions in CellML. In this work, we improve this process by inserting LLVM into the flow to pre-optimise the simulation models generated from CellML for hardware synthesis. This is achieved not only by the selective application of general-purpose optimisation passes, but also by adding new domain-specific optimisations, including unsafe floating-point transformations, to the optimisation flow. We investigate their effect on the quality-of-results and show that a novel strategy using our optimisations outperforms standard strategies, such as LLVM's -Oz (aggressive size reduction), when applied for hardware synthesis in 99 out of 146 example models. Our approach, which reduces area by up to 25%, leads to the smallest implementations for four models examined in detail, and allows a particularly complex cell model to fit on the target FPGA device for the first time.

The Square Kilometre Array (SKA), currently in the pre-construction phase, will be the world largest telescope array for radio astronomy. The Fourier domain acceleration search (FDAS) is a sub-module of the Non-imaging Processing Pulsar Search Sub-element (NIP PSS) of SKA-MID Central Signal Processor (CSP) element. The total performance needed for FDAS module of up to 2000 beams is over 14Poperations/s. The huge scale of it is a strong computing challenge. In this work, the use of FPGAs to accelerate the FDAS module is studied, due to their high inherent parallelism and power efficiency. We study the impact of the relaxation of a number of FDAS factors and test them using a Terasic DE5 board. By applying all the relaxation methods, up to 93% FPGAs can be saved. Further, several optimization techniques are introduced to reduce the number of needed FPGAs.

Summary Task parallelism is an approach to parallel programming that has recently gained traction because of its compatibility with the predominant object‐oriented languages and its low overhead compared to threading approaches. Parallel Task is an Open Source task‐parallel compiler and runtime system for object‐oriented languages, in particular Java. It is very flexible and expressive, demonstrated by the fact that it can be directly employed to implement most parallel computing patterns. The only notable exception has been the pipeline pattern where many data items are streamed through a number of processing stages. This is not surprising, as task parallelism is generally not compatible with the pipeline pattern. In this paper, we investigate how the pipeline pattern can be elegantly and efficiently implemented in a task‐parallel environment. To do so, we extend Parallel Task with the concept of implicit futures to allow creating pipelines in an intuitive and object‐oriented manner. Our experimental evaluation uses the extended Parallel Task to implement pipelines of different lengths and characteristics and compares with manual implementations. The evaluation demonstrates very good performance and scalability of the proposed task‐parallel pipeline approach. Copyright © 2014 John Wiley & Sons, Ltd.

To fully benefit from a multiprocessor system, the tasks of a program are to be carefully assigned and scheduled on the processors of the system such that the overall execution time is minimal. The associated task scheduling problem with communication delays, Plprec; cijlCmax, is a well known NP-hard problem. We propose a novel mixed integer linear programming (MILP) solution to this scheduling problem, despite the fact that scheduling problems are often difficult to handle by MILP solvers. The proposed MILP solution uses problem specific knowledge to eliminate the need to linearise the bi-linear equations arising out of communication delays. Further, the size of the proposed formulation in terms of variables is independent of the number of processors. We analyse and discuss the influence of the different MILP components in respect to characteristics of the task graph such as structure and communication to computation ratio. The proposed MILP formulation is experimentally compared with previous MILP formulations used to solve this scheduling problem. The proposed formulation displays a drastic improvement in performance, which allows to solve larger problems optimally. We also observe strengths and weaknesses of the formulation related to the input characteristics.

Directives based incremental parallelism is an uncomplicated and expressive parallelisation practice and has led to wide adoption of OpenMP. However, the OpenMP specification does not present a binding for the Java language and the OpenMP threading model finds limited use for GUI (Graphical User Interface) application development. This paper focuses on the study of a semantic interpretation of OpenMP in the context of an object orientated environment. It proposes novel concepts to extend OpenMP for applications with a Graphical User Interface (GUI), based on the distinction between parallelism and concurrency. We present a compiler-runtime system for OpenMP-like directives in Java, enhanced with GUI related constructs. Acknowledging the productivity gains of the incremental parallelism approach of OpenMP, the GUI related constructs enable the developer to incrementally introduce concurrency. We present and discuss the performance of programs written using our system by comparing them with previous attempts and traditional ways of parallelisation-concurrency, using the parallel Java Grande Forum (JGF) benchmarks and a set of GUI applications.

Rendering programs use ray tracing to artificially create photo-realistic scenes that would otherwise be too dangerous, too costly or physically impossible to fabricate. Acceleration of the rendering process can be achieved through spatial or object hierarchy structures, which aim to restrict the number of expensive ray-object intersection calculations along a ray path by trading them for traversal of the structure. With extensive inherent parallelism, ray tracing benefits from GPU acceleration but may also benefit from the more flexible control flow and memory architecture available with FPGAs. We present a flexible FPGA based ray tracing platform capable of traversing varying widths and types of acceleration hierarchies to evaluate their efficiency. The platform consists of four main controllers for communication, traversal, intersection and memory. The platform interfaces with LuxRays, an open-source C++ renderer, over PCIexpress to transfer data for computation to onboard memory. We implement a configuration of the platform at 250MHz on our target device that shows promising results compared to CPU and GPU renders.

OpenCMISS is a mathematical modeling environment designed to solve field based equations and link subcellular and tissue-level biophysical processes to organ-level processes. It employs a general purpose parallel design, in particular distributed memory, for its computations. CellML is a mark up language based on XML that is designed to encode lumped parameter biophysically based systems of ordinary differential equations and nonlinear algebraic equations. OpenCMISS allows CellML models to be evaluated and integrated into models at various spatial and temporal scales. With good inherent parallelism, hardware acceleration based on FPGAs has a great potential to increase the computational performance and to reduce the energy consumption of computations with CellML models integrated in OpenCMISS. However, with several hundred CellML models, manual hardware implementation for each CellML model is complex and time consuming. The advantages of FPGA designs will only be realised if there is a general solution or a tool to automatically convert CellML models into hardware description languages such as VHDL. In this paper we describe the architecture for the FPGA hardware implementation of CellML models and evaluate the first results related to performance and resource usage based on a variety of criteria.

This paper investigates the execution of tree-shaped task graphs using multiple processors. Each edge of such a tree represents a large IO file. A task can only be executed if all input and output files fit into memory, and a file can only be removed from memory after it has been consumed. Such trees arise, for instance, in the multifrontal method of sparse matrix factorization. The maximum amount of memory needed depends on the execution order of the tasks. With one processor the objective of the tree traversal is to minimize the required memory. This problem was well studied and optimal polynomial algorithms were proposed. Here, we extend the problem by considering multiple processors, which is of obvious interest in the application area of matrix factorization. With the multiple processors comes the additional objective to minimize the time needed to traverse the tree, i.e., to minimize the makespan. Not surprisingly, this problem proves to be much harder than the sequential one. We study the computational complexity of this problem and provide an inapproximability result even for unit weight trees. Several heuristics are proposed, each with a different optimization focus, and they are analyzed in an extensive experimental evaluation using realistic trees.

Currently C-to-hardware (C2H) compilation tools have the potential to generate high-performing and efficient hardware functions from application source code. But often this is not realised without expensive manual code modifications to massage the input source code into a form whereby the compiler can extract maximum meaning from it, thus improving the quality of generated hardware. These modifications represent a significant hurdle for software developers; to improve this we present our work towards a semi-automated compilation framework that attempts to streamline this design flow. The proposed framework consists of an extensible analysis phase of input source code and automated generation of code-mutations that serve as trial candidates. These are then automatically combined within the greater SoPC environment and passed through a parallel compilation stage through the C2H tool. Based on the compilation results the process can be refined and re-executed after manually-assisted candidate pruning. In experimental results, a significant performance speedup has been demonstrated when applying these techniques to simple examples which were compiled out-of-the-box with the same C2H tool. Moreover, minimal extra development effort was necessary to achieve these results. Open challenges still remain, but we believe the promise of such an augmented approach to tool-generated SoPC designs is clear.

Mapping and scheduling an application onto the processors of a parallel system is a difficult problem. This is true when performance is the only objective, but becomes worse when a second optimization criterion like reliability is involved. In this paper we investigate the problem of mapping an application consisting of several consecutive stages, i.e., a pipeline, onto heterogeneous processors, while considering both the performance, measured as throughput, and the reliability. The mechanism of replication, which refers to the mapping of an application stage onto more than one processor, can be used to increase throughput but also to increase reliability. Finding the right replication trade-off plays a pivotal role for this bi-criteria optimization problem. Our formal model includes heterogeneous processors, both in terms of execution speed as well as in terms of reliability. We study the complexity of the various sub problems and show how a solution can be obtained for the polynomial cases. For the general NP-hard problem, heuristics are presented and experimentally evaluated. We further propose the design of an exact algorithm based on A* state space search which allows us to evaluate the performance of our heuristics for small problem instances.

With the advent of multi-core processors, desktop application developers must finally face parallel computing and its challenges. A large portion of the computational load in a program rests within iterative computations. In object-oriented languages these are commonly handled using iterators which are inadequate for parallel programming. Consequently, the powerful Parallel Iterator concept was developed. This paper presents various developments of the Parallel Iterator, such as parallel traversal of complex collections with partial ordering (such as a tree). Other features include reductions, parallel remove semantics and exception handling. Along with the ease of use, the results reveal great speedup in comparison to traditional Java parallelism approaches.

Parallel programming is notoriously difficult. This becomes even more critical as multicore processors bring parallel computing into the mainstream. In order to ease the difficulty, tools have been designed that help the programmer with some aspects of parallelisation. Unfortunately, the programmer is mostly left along when it comes to the difficult task of dependence analysis among the subtasks to be executed concurrently. This paper presents a new visual tool that supports the programmer with the dependence analysis in loops. This is very useful in combination with an automatically parallelising compiler or when loops are parallelised with OpenMP. The tool displays on-the-fly the dependences between the statements of the loop nest on which the developer is currently working. To maximise the usefulness of the tool, it is unobtrusive, customisable and flexible, and based on dependence analysis theory. A prototype was implemented for the Eclipse IDE as a plug-in that seamlessly integrates into the normal development process. The evaluation of the tool, including an evaluation against cognitive dimensions, demonstrates the usability and usefulness of the tool.

The need to parallelise desktop applications is becoming increasingly essential with the mainstream adoption of multi-cores. In object-oriented languages, sequential iterators handle iterative computations of a sequential program; similarly, the parallel iterator was developed to handle the iterative computations of a parallel program. This paper presents the progress of the parallel iterator concept. New features, such as support for reductions and global break semantics, allow the parallel iterator to undertake more situations. With a slight contract modification, the parallel iterator interface now imitates that of the sequential iterator. All these features combine together to promote minimal, if any, code restructuring. The reduction frequently outperforms related work and the importance of providing simple and flexible fine-tuning capability is affirmed.

This paper describes a new task scheduling algorithm based on clustering. In this new approach, clustering of the tasks is achieved by applying a force model to the task graph. From an initial configuration of the task graph, forces act upon the nodes to manoeuvre them into a low energy or equilibrium state. Clusters are created from the equilibrium state and scheduled for an unlimited number of processors. This algorithm is compared in an extensive experimental evaluation to three other clustering algorithms namely, linear, single edge and dominant sequence clustering. By keeping the mapping and scheduling phases of the algorithms identical, we compare only the difference in clustering between all algorithms. Results show that force directed clustering is very promising, especially for a limited number of processors.

Scheduling tasks onto the processors of a parallel system is a crucial part of program parallelisation. Due to the NP-hard nature of the task scheduling problem, scheduling algorithms are based on heuristics that try to produce good rather than optimal schedules. Nevertheless, in certain situations it is desirable to have optimal schedules, for example for time critical systems or to evaluate scheduling heuristics. This paper investigates the task scheduling problem using A* search algorithm. The A* scheduling algorithm implemented can produce optimal schedules in reasonable time for small to medium sized task graphs. In comparison to a previous approach, the here presented A* scheduling algorithm has a significantly reduced search space due to a much improved cost function f(s) and additional pruning techniques. Last but not least, the experimental results show that the proposed A* scheduling algorithm significantly outperforms the previous approach.

Task scheduling is an important aspect of parallel programming. Most of the heuristics for this NP-hard problem are based on a very simple system model of the target parallel system. Experiments revealed the inappropriateness of this classic model to obtain accurate and efficient schedules for real-systems. In order to overcome this shortcoming, a new scheduling model was proposed that considers the contention for communication resources. Even though the accuracy and efficiency improved with the consideration of contention, the new contention model is still not good enough. The crucial aspect is the involvement of the processor in communication. This paper investigates the involvement of the processor in communication and its impact on task scheduling. A new system model is proposed based on the contention model that is aware of the processor involvement. The challenges for the scheduling techniques are analyzed and two scheduling algorithms are proposed. Experiments on real parallel systems show the significantly improved accuracy and efficiency of the new model and algorithms.

A novel strategy for employing schedules obtained using standard static scheduling algorithms in a battery powered multiprocessor environment is investigated. The strategy is able to dynamically respond to deteriorating batteries and operate with fewer processors according to the battery levels of the system. The nature of the proposed approach allows poorly performing batteries to recover through self charge. The strategy therefore maximizes the battery life and the operation time of the device.

Task scheduling is an essential aspect of parallel programming. Most heuristics for this NP-hard problem are based on a simple system model that assumes fully connected processors and concurrent interprocessor communication. Hence, contention for communication resources is not considered in task scheduling, yet it has a strong influence on the execution time of a parallel program. This paper investigates the incorporation of contention awareness into task scheduling. A new system model for task scheduling is proposed, allowing us to capture both end-point and network contention. To achieve this, the communication network is reflected by a topology graph for the representation of arbitrary static and dynamic networks. The contention awareness is accomplished by scheduling the communications, represented by the edges in the task graph, onto the links of the topology graph. Edge scheduling is theoretically analyzed, including aspects like heterogeneity, routing, and causality. The proposed contention-aware scheduling preserves the theoretical basis of task scheduling. It is shown how classic list scheduling is easily extended to this more accurate system model. Experimental results show the significantly improved accuracy and efficiency of the produced schedules.