Search

In this article, we study performance and energy saving benefits of hardware acceleration under different hardware configurations and usage scenarios for a state-of-the-art Fast Multipole Method (FMM), which is a popular N-body method. We use a dedicated Application Specific Integrated Circuit (ASIC) to accelerate General Matrix-Matrix Multiply (GEMM) operations. FMM is widely used in applications and is representative example of the workload for many HPC applications. We compare architectures that integrate the GEMM ASIC next to, in or near main memory with an on-chip coupling aimed at minimizing or avoiding repeated round-trip transfers through DRAM for communication between accelerator and CPU. We study tradeoffs using detailed and accurately calibrated x86 CPU, accelerator and DRAM simulations. Our results show that simply moving accelerators closer to the chip does not necessarily lead to performance/energy gains. We demonstrate that, while careful software blocking and on-chip placement optimizations can reduce DRAM accesses by 2X over a naive on-chip integration, these dramatic savings in DRAM traffic do not automatically translate into significant total energy or runtime savings. This is chiefly due to the application characteristics, the high idle power and effective hiding of memory latencies in modern systems. Only when more aggressive co-optimizations such as software pipelining and overlapping are applied, additional performance and energy savings can be unlocked by 37 and 35 percent respectively over baseline acceleration. When similar optimizations (pipelining and overlapping) are applied with an off-chip integration, on-chip integration delivers up to 20 percent better performance and 17 percent less total energy consumption than off-chip integration.

With the increasing complexity of the applications, there is an urgent need for solutions to improve the performance of these applications. It is noted that the loops present in some of them are responsible for up to 71% of the code execution time. So, optimizing the loop’s execution it is possible to accelerate the execution of the whole application. This performance gain can be obtained with the use of software pipelining. This work proposes RENOIR, a tool that uses software pipelining technique through the implementation of the modulo scheduling algorithm, developed in software, that acts in the generation of configurations for a coarse-grained reconfigurable architecture (CGRA). RENOIR is implemented in a compiler, which receives an application and generates a code that can run on a gem5 implementation of a CGRA that includes a RISC-V microprocessor and a thin reconfigurable array. The results show that all the applications tested achieved an improvement in performance, reaching a gain of 2,32x in certain applications.

In this article, we explore the problem of energy-aware scheduling of real-time applications modelled by conditional task graphs on NoC based MPSoC such that the total energy consumption is minimized. We propose a novel energy and memory-aware retiming conditional task graph (EMRCTG) approach that integrates task-level coarse-grained software pipelining with Dynamic Voltage and Frequency Scaling (DVFS). Our approach not only optimizes energy consumption but ensures that memory capacity constraints are satisfied. EMRCTG has two phases. In the first phase, we map tasks to processors, transform intra-period data dependencies into inter-period and generate a schedule by a Non-Linear Programming (NLP)-based algorithm assuming infinite memory capacity. The NLP-based algorithm assigns a continuous frequency and voltage to each task and each communication and uses a polynomial-time heuristic to transform the continuous frequencies and voltages to discrete frequencies and voltages. We analyse the memory consumption of the generated schedule and initiate schedule repair phase 2 if the memory capacity constraints violate. The schedule repair phase finds a set of nodes such that by reducing their retiming values the memory capacity constraints satisfy. We compare our approach against two existing approaches GeneS and JCCTS. GeneS is a genetic algorithm that first transforms the dependent task set into an independent task set and then collectively performs task mapping, ordering and voltage scaling. JCCTS is a mixed integer linear programming based approach that optimally removes inter-processor communication overhead. Our experimental result show that compared to the approach GeneS our approach can obtain an improvement in range of 1.6 to 18 percent and an average improvement of 11 percent. Compared to the approach JCCTS our approach can achieve an improvement in range of 9 to 42 percent and an average improvement of 26 percent.

Coarse-Grained Reconfigurable Arrays (CGRAs) are promising to have low power consumption and high energy-efficiency characteristics as accelerators. Recent years, many research works focus on improving the programmability of the CGRAs by enabling the fast reconfiguration during execution. The performance of these CGRAs critically hinges upon the scheduling power of the compiler. One of the critical challenges is to reduce memory access conflicts using static compilation techniques. Memory accessing conflict brings the synchronization overhead which causes the pipelining stall and reduces CGRA performance. Existing compilers usually tackle this challenge by orchestrating the data placement of the on-chip global memory (OGM) in CGRA to let the parallel memory accesses avoid the bank conflict. However, we find bank conflict is not the only reason that causes the memory access conflicts. In some CGRAs, the bandwidth of the data network between OGM and processing element array (PEA) is also limited due to the low power design principle. The unbalanced network bandwidth loads is another reason that causes memory access conflicts. Furthermore, the redundant data access across iterations is one of the primary causes of memory access conflicts. Based on these observations, we provide a comprehensive and generalized compilation flow to reduce the memory conflicts. Firstly, we develop a loop transformation model to maximize the inter-iteration data reuse of the loops to reduce the memory accessing operations under the software pipelining scheme. Secondly, we enhance the bandwidth utilization of the network between OGM and PEA and avoid the bank conflict by providing a conflict-aware spatial mapping algorithm which can be easily integrated into existing CGRA modulo scheduling compilation flow. Experimental results show our method is capable of improving performance by an average of 44% comparing with state-of-the-art CGRA compiling flow.

Detecting moving objects based on real-time video processing is considered as a challenging task. The background subtraction using the Gaussian Mixture Model (GMM) is one of the widely used technique. However, it requires high-computing power to meet real-time processing constraints. An efficient implementation of GMM algorithm on an embedded platform based on the C6678 digital signal processor (DSP) was proposed in this paper. First, an optimized GMM code has been developed for the proposed embedded platform. Then, an efficient memory management strategy has been implemented to ensure contiguous memory access. In addition, the compiler options have been enabled to take profit from loops unrolling and software pipelining to improve the computing performances. In order to evaluate the quality of our implementation, a metrics comparison have been performed based on the background truth images provided by the literature dataset references. Experimental results show important improvements over the optimized implementation of the state-of-the-art.

The increasing size of recurrent neural networks (RNNs) makes it hard to meet the growing demand for real-time AI services. For low-latency RNN serving, FPGA-based accelerators can leverage specialized architectures with optimized dataflow. However, they also suffer from severe HW under-utilization when partitioning RNNs, and thus fail to obtain the scalable performance.In this paper, we identify the performance bottlenecks of existing RNN partitioning strategies. Then, we propose a novel RNN partitioning strategy to achieve the scalable multi-FPGA acceleration for large RNNs. First, we introduce three parallelism levels and exploit them by partitioning weight matrices, matrix/vector operations, and layers. Second, we examine the performance impact of collective communications and software pipelining to derive more accurate and optimal distribution results. We prototyped an FPGA-based acceleration system using multiple Intel high-end FPGAs, and our partitioning scheme allows up to 2.4x faster inference of modern RNN workloads than conventional partitioning methods.

This paper presents a complete embedded system for segmentation of gray matter of the human brain from Positron emission tomography (PET) image using 8-bit embedded Atmel microcontroller operating at low power and a frequency of 16 MHz. Hardware implementation of the embedded system for gray matter segmentation (ESGMS) of PET image is chosen as hardware design is more efficient by adopting the principles of software development. The ideology of parallelism achieved by the sixth level of software pipelining and two levels of dedicated hardware pipelining. Using lifting technique, the wavelet function is generated and denoised the same simultaneously, generally known as second-generation wavelet. The proposed architecture reduced number of memories through in-place approach as the resultant of the operands is overwritten on the operand location. For realization, Haar wavelet is used as mother wavelet in the design which is compiled lifting technique to perform split and update. Haar mother wavelet with the lifting scheme procures the denoised image for future operations. The wavelets confer a better output image, which is established with altering different statistical measures. With our proposed system, we can obtain peak signal to noise ratio (PSNR) about 107 dB. For segmentation, unsupervised clustering algorithm (K-mean) is used and each segment is superimposed with different colors. The gray matter of the human brain in the PET image is leveled using pink color.

Processor vendors have been expanding Single Instruction Multiple Data (SIMD) extensions to exploit data-level-parallelism in their General Purpose Processors (GPPs). Each SIMD technology such as Streaming SIMD Extensions (SSE) and Advanced Vector eXtensions (AVX) has its own Instruction Set Architecture (ISA) which equipped with Special Purpose Instructions (SPIs). In order to exploit these features, many programming approaches have been developed. Intrinsic Programming Model (IPM) is a low-level concept for explicit SIMDization. Besides, Compiler’s Automatic Vectorization (CAV) has been embedded in modern compilers such as Intel C++ compiler (ICC), GNU Compiler Collections (GCC) and LLVM for implicit vectorization. Each SIMDization shows different improvements because of different SIMD ISAs, vector register width, and programming approaches. Our goal in this paper is to evaluate the performance of explicit and implicit vectorization. Our experimental results show that the behavior of explicit vectorization on different compilers is almost the same compared to implicit vectorization. IPM improves the performance more than CAVs. In general, ICC and GCC compilers can more efficiently vectorize kernels and use SPI compared to LLVM. In addition, AVX2 technology is more useful for small matrices and compute-intensive kernels compared to large matrices and data-intensive kernels because of memory bottlenecks. Furthermore, CAVs fail to vectorize kernels which have overlapping and non-consecutive memory access patterns. The way of implementation of a kernel impacts the vectorization. In order to understand what kind of scalar implementations of an algorithm is suitable for vectorization, an approach based on code modification technique is proposed. Our experimental results show that scalar implementations that have either loop collapsing, loop unrolling, software pipelining, or loop exchange techniques can be efficiently vectorized compared to straightforward implementations.

Increasing demands for energy efficiency constrain emerging hardware. These new hardware trends challenge the established assumptions in code generation and force us to rethink existing software optimization techniques. We propose a cross-layer redesign of the way compilers and the underlying microarchitecture are built and interact, to achieve both performance and high energy efficiency. In this paper, we address one of the main performance bottlenecks—level cache misses—through a software- hardware co-design. Our approach is able to hide memory latency and attain increased memory and instruction level parallelism by orchestrating a non-speculative, execute-ahead paradigm in software (SWOOP). While out-of-order (OoO) architectures attempt to hide memory latency by dynamically reordering instructions, they do so through expensive, power-hungry, speculative mechanisms. We aim to shift this complexity into software, and we build upon compilation techniques inherited from VLIW, software pipelining, mod- ulo scheduling, decoupled access-execution, and software prefetching. In contrast to previous approaches we do not rely on either software or hardware speculation that can be detrimental to efficiency. Our SWOOP compiler is enhanced with lightweight architectural support, thus being able to transform applications that include highly complex control-low and indirect memory accesses. © ACM, 2018. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions of Computing Education, https://doi.org/10.1145/3296979.3192393

Internet-of-Things (IoT) is an appealing service to revolutionise Smart City (SC) initiatives across the globe. IoT interconnects a plethora of digital devices known as Sensor Nodes (SNs) to the Internet. Due to their high performance and exceptional Quality-of-Service (QoS) Multiprocessor System-on-Chip (MPSoC) computing architectures are gaining increasing popularity for the computationally extensive workloads in both IoT and consumer electronics. In this survey, we have explored balance between the IoT paradigm and its applications in SC while introducing Wireless Sensor Network (WSN), including the structure of the SN. We considered MPSoCs systems in relation to characteristics such as architecture and the communication technology involved. This provides an insight into the benefits of coupling MPSoCs with IoT. This paper, also investigates prevalent software level energy optimisation techniques and extensively reviews workload mapping and scheduling approaches since 2001 until today for energy savings using (1) Dynamic Voltage and Frequency Scaling (DVFS) and/or Dynamic Power Management (DPM) (2) Inter-processor communication reduction (3) Coarse-grained software pipelining integrated with DVFS. This paper constructively summarises the findings of these approaches and algorithms identifying insightful directions to future research avenues.

Modern high-level synthesis (HLS) tools commonly employ pipelining to achieve efficient loop acceleration by overlapping the execution of successive loop iterations. While existing HLS pipelining techniques obtain good performance with low complexity for regular loop nests, they provide inadequate support for effectively synthesizing irregular loop nests. For loop nests with dynamic-bound inner loops, current pipelining techniques require unrolling of the inner loops, which is either very expensive in resource or even inapplicable due to dynamic loop bounds. To address this major limitation, this paper proposes ElasticFlow, a novel architecture capable of dynamically distributing inner loops to an array of processing units (LPUs) in an area-efficient manner. The proposed LPUs can be either specialized to execute an individual inner loop or shared among multiple inner loops to balance the tradeoff between performance and area. A customized banked memory architecture is proposed to coordinate memory accesses among different LPUs to maximize memory bandwidth without significantly increasing memory footprint. We evaluate ElasticFlow using a variety of real-life applications and demonstrate significant performance improvements over a state-of-the-art commercial HLS tool for Xilinx FPGAs.

This work proposes several intrinsics on a reconfigurable processor intended for HEVC decoding and software pipelining algorithms with a coarse-grained array (CGA) architecture as well as the proposed intrinsic instructions. Software pipelining algorithms are developed for the CGA acceleration of inverse transform, pixel reconstruction, de-blocking filter and sample adaptive offset modules. To enable efficient software pipelining, several very-long instruction-word-based intrinsics are designed in order to maximize the parallelization rather than the computational acceleration. We found that the HEVC decoder with the proposed intrinsics yields 2.3 times faster in running clock cycle than a decoder that does not use the intrinsics. In addition, the HEVC decoder with CGA pipelining algorithms executes 10.9 times faster than that without the CGA mode.

In 2016, the MICRO ToT award was given to Dr. B. Ramakrishna (Bob) Raus seminal paper entitled Iterative Modulo Scheduling: An Algorithm for Software Pipelining Loops, which appeared at MICRO 1994, 22 years before receiving the award.

To leverage the vast parallelism of loops, embedded loop accelerators often take the form of processor arrays with many, but simple processing elements. Each processing element executes a subset of a loop's iterations in parallel using instruction- and datalevel parallelism by tightly scheduling iterations using software pipelining and packing instructions into compact, individual programs. However, loop bounds are often unknown until runtime, which complicates the static generation of programs because they influence each program's control flow.Existing solutions, like generating and storing all possible programs or full just-in-time compilation, are prohibitively expensive, especially in embedded systems. As a remedy, we propose a hybrid approach introducing a tree-like program representation, whose generation front-loads all intractable sub-problems to compile time, and from which all concrete program variants can efficiently be stitched together at runtime. The tree consists of so-called polyhedral fragments that represent concrete program parts and are annotated with iteration-dependent conditions.We show that both this representation is both space- and time-efficient: it requires polynomial space to store---whereas storing all possibly generated programs is non-polynomial---and polynomial time to evaluate---whereas just-in-time compilation requires solving NP-hard problems. In a case study, we show for a representative loop program that using a tree of polyhedral fragments saves 98.88 % of space compared to storing all program variants.

The search for better execution performance has revealed many parallelism solutions. Among them, the software pipelining technique is reported in the literature to be very promising when applied to instruction level parallelism in Superscalar and VLIW processing architectures. In this paper, we present modifications in two versions of software pipelining technique implemented natively in a general purpose non-conventional processing architecture. The objective of this proposal is to obtain better performance by exploring instruction level parallelism through this technique in an architecture that already explores task level parallelism. Simulation results show that modifications in one version increase performance by almost 3% and decrease the power consumption in 12%.

The Multiprocessor System-on-Chip (MPSoC) computing architectures are widely adopted in modern embedded systems for real-time applications due to their high performance, reliability, and Quality-of-Service (QoS). Green computing or energy-efficient task scheduling is a critical technological challenging facet in an energy constrained embedded systems because higher energy consumption limits the lifetime of the computing platform and causes an increased carbon footprint. In this paper, we investigate energy-aware task scheduling on Dynamic Voltage and Frequency Scaling (DVFS) enabled Network-on-Chip (NoC) based Heterogeneous MPSoCs (HMPSoCs). We transform the intra-data dependencies into inter-data dependencies of the tasks with precedence constraints represented by Directed Acyclic Graph (DAG). We further implement Energy-efficient Task Scheduling Heuristic (ETSH) algorithm embedded with a list scheduler to perform energy-aware task scheduling while considering the energy performance profiles of the processors and task deadlines. The observed results on 5 real-world and 5 synthetic Task Graphs (TGs) adopted from Embedded Systems Synthesis (E3S) benchmarks suit demonstrate that ETSH outperforms state-of-the-art technique. Concisely, it achieves 20% and 38% average energy-efficiency with and without using coarse-grained software pipelining respectively.

This paper represents the architecture of an embedded system for Early Started Hybrid Denoising Technology for Medical Images (ESHDT) using a very popular embedded processor, ATmega processor, which is inexpensive in terms of computation. Embedded implementation of the ESHDT algorithm is chosen because hardware presents a good scope of parallelism and pipelining over software. The Proposed System can work efficiently in a noisy environment. The proposed embedded system architecture has less space complexity because the number of memories is used here. The system starts performing the algorithmic task as soon as two-pixel values are received, and parallelism is achieved by the sixth level of software pipelining and two levels of dedicated hardware pipelining. Due to the design simplicity of our algorithm, it used very few memory resources. Here we used the 8-bit AVR processor which run on low power, and we optimized SD card access so we can say the power consumption by our system is low. Instead of the set of filters, simple predict and update mechanism is introduced. ESHDT provides very good-quality denoised output image with respect to PSNR, UIQI, and MSE.

Trends in processor and system architecture, driven by power and complexity, point super-computing landscape toward very high and heterogeneous core count designs. As the number of cores inevitably increase traditional ways of performing large scale computations will also need to evolve from legacy models like OpenMP & MPI. However, such models are very much wedded to a control-flow vision of parallel programs, making it difficult to express asynchrony in programs. To address these challenges, codelet model was developed which is fine-grained, event-driven asynchronous program execution model. In-spite of its initial design goals, the Codelet model is rife with opportunities for further improvements to provide high-performance for both data and control regular applications. The major inspiration behind this work is to leverage the decades of research done to exploit instruction level parallelism (ILP) for the machine instructions inside codelet while build upon the dataflow software pipelining principals at codelet graph level to further enhance performance. In this paper, we propose hardware assisted extensions to the original codelet program execution model in order to implement efficient dataflow software pipelining and extend capabilities of the codelet model. This hardware-software co-design focuses on efficient implementation of data FIFO buffers leveraging proposed optimizations like - FIFO ring buffers and multiple-head FIFO buffers and single owner FIFO buffers to further exploit advantages of dataflow software pipelining. The wide range of scientific, machine learning and specially streaming applications should be able to take advantage of techniques proposed in this paper. Identifying these kernels and bench-marking them are the next anticipated steps for us.

Network Functions Virtualization emphasizes the importance of performance in software-based network functions and in-network computing on general-purpose computers. Efficient resource utilization is challenging to run multiple network functions at high performance. This paper proposes a generalized performance optimization technique for chains of network functions on commodity CPUs, named deep pipelining. The key idea of deep pipelining is the combination of software pipelining and coroutines to reduce the overhead of high latency instructions such as memory access of network algorithms. Coroutines are used to schedule the execution of multiple pipelines of chained network functions. Microbenchmark and synthetic benchmark results shed light on both the effectiveness and the small overhead of deep pipelining. By taking the advantage of deep pipelining, we prove the effectiveness in chaining network functions with software-based layer-3 switch implementation consisting of Ethernet switching and IP routing on our operating system. The evaluation demonstrates that deep pipelining improves packet switching and routing performance by 0.11-78% compared to the existing batching-with-prefetch approach.

The automotive industry is embracing new challenges to deliver self-driving cars, and this in turn requires increasingly complex hardware and software. Software developers are leveraging artificial intelligence, and in particular machine learning, to deliver the capabilities required for an autonomous vehicle to operate. This has driven automotive systems to become increasingly heterogeneous offering multi-core processors and custom co-processors capable of performing the intense algorithms required for artificial intelligence and machine learning. These new processors can be used to vastly speed up common operations used in AI (Artificial Intelligence) and machine learning algorithms.The R-Car V3H system-on-chip (SoC) from the Renesas AutonomyâDc platform for ADAS (Advanced Driver Assistance Systems) and automated driving supports Level 3 and above (as defined by SAE's automation level definitions). It follows the heterogeneous IP concept of the Renesas Autonomy platformâDc, giving the developer the choice of high performance computer vision at low power consumption, as well as flexibility to implement the latest algorithms such as those used in machine learning.By examining the architecture of the R-Car hardware we can understand how this differs from HPC and desktop heterogeneous systems, and how this can be mapped to the SYCL and OpenCL programming models. When both power consumption and performance are important, as is the case in the automotive industry, the focus for implementing OpenCL and SYCL on these hardware platforms must be a balanced approach. The memory capacity and layout must be used in the most optimum way to build a pipeline that provides the best throughput. The R-Car hardware provides DMA and on-chip memory where these are used to facilitate efficient data transfer on the device. The memory hierarchy layers can be seen on how it is efficiently mapped to OpenCL paradigm.The R-Car hardware also offers many fixed function IP blocks, each performing a specific function like convolution for deep neural networks, optical flow and more, beyond the programmable processor. The flexibility of OpenCL enables the development of built in kernels so that developers can take advantage of these architecture designs.The OpenCL model enables extensive usage of the heterogenous hardware, including fully programmable IP, efficient data transfer using the DMA to the on-chip device memory via OpenCL extension, and fixed function IP block, such as CNN for enabling high throughput convolution operations, via OpenCL builtin kernels, device triggered DMA using partial subgroups. We examine the memory mapping to bring in efficiency and the software pipelining & parallelism. These hardware architectures include AI accelerator processors specifically designed to be used in the next generation of vehicles. In particular, the processors are designed to tackle complex algorithms whilst limiting the overall consumption of power. Benchmarks will be presented to show how portable code can also deliver performance for developers using this hardware.As well as enabling developers to choose OpenCL or SYCL, we will talk about how these standards enable additional high-level frameworks that can be used to target this hardware. These include libraries for deep neural networks and linear algebra operations.

Modified Gram Schmidt (MGS) is one of the well-known forms of QR decomposition (QRD) algorithms. It has been used in many signal and image processing applications to solve least square problem, linear equations or to invert matrices. Nevertheless, QRD is considered a computationally expensive operation, and its sequential implementation doesn't meet the requirements of many real time applications. In this paper, we propose an optimized MGS algorithm version based on software pipelining and loop unrolling techniques. The suggested MGS version is parallel and well suited for VLIW architectures. The implementation is done under TI C6678 VLIW DSP and the obtained results show great improvements against the standard MGS and the optimized vendor QRD implementations.

Coarse-grained reconfigurable architecture (CGRA) is a promising parallel computing platform that provides high performance, high power efficiency and flexibility. However, for imperfect nested loops, the existing loop mapping methods often result in low execution performance and poor hardware utilization. To tackle this problem, this paper makes three contributions: 1) a highly effective and general approach to map imperfect loops on CGRA; 2) a global optimization strategy to search the optimal initiation intervals (IIs); 3) a powerful kernel compression method to reduce the oversized kernel. Experiment results show that our approach can reduce the total computing latency by 20.5, 58.5 and 73.2 percent compared to the state-of-the-art approaches on $2 \times 2$ , $4 \times 4$ and $8 \times 8$ CGRA respectively. Moreover, the compilation time and configuration context size is acceptable in practice.

In recent years, there has been increasing interest in using task-level pipelining to accelerate the overall execution of applications mainly consisting of producer/consumer tasks. This paper proposes fine- and coarse-grained data synchronization approaches to achieve pipelining execution of producer/consumer tasks in FPGA-based multicore architectures. Our approaches are able to speedup the overall execution of successive, data-dependent tasks, by using multiple cores and specific customization features provided by FPGAs. An important component of our approach is the use of customized inter-stage buffer schemes to communicate data and to synchronize the cores associated with the producer/consumer tasks. We propose techniques to reduce the number of accesses to external memory in our fine-grained data synchronization approach. The experimental results show the feasibility of the approach in both in-order and out-of-order producer/consumer tasks. Moreover, the results using our approach reveal noticeable performance improvements for a number of benchmarks over a single core implementation without using task-level pipelining.

Strategies to parallelize applications is one way to increase performance in computer architectures. In addition to the hardware organization, some techniques are adopted, maintaining its architecture or instruction set, in order to increase the flow of processing instructions, such as pipeline and software pipelining. This paper presents a version of the software pipelining technique in IPNoSys, an unconventional architecture, for improved performance in the execution of applications containing loops. The new version was compared with an already implemented version of the software pipelining technique to IPNoSys and was two times more efficient than the old version.

Motion control systems require an isochronal real-time guarantee that each control task should periodically produce outputs with no jitters. However, it is difficult to build up such a tight isochronal system with a multicore architecture and a general-purpose operating system, because the inherent resource sharing principle leads to large jitters to the control tasks. This paper proposes a software pipelining framework for an EtherCAT-based motion controller that achieves a tight isochronal guarantee with that combination. The tight guarantee is possible by multicore partitioning and reservation-aware task phasing, which reduce resource contentions between the tasks on each stage of the pipeline. Through experiments, we show that the proposed pipelining framework gives a tight isochronal guarantee with high scalability in terms of the number of motion transactions. On a real 8-axis motion control platform with two processor cores dedicated to the pipeline and a slight modification of the Linux operating system, it achieves a maximum jitter of $10\ \upmu\text{s} $ for four motion transactions with a common period of 1.6 ms, whereas a priority-driven method gives a maximum jitter of a few hundreds of microsecond under the same condition.

Coarse-grained reconfigurable architecture (CGRA) is a promising architecture with high performance, high power efficiency, and attraction of flexibility. The computation-intensive portions of applications, i.e., loops, are often implemented on CGRAs for acceleration. The loop pipelining techniques are usually used to exploit the parallelism of loops. However, for nested loops, the existing loop pipelining methods often result in poor hardware utilization and low execution performance. To tackle this problem, this paper makes three contributions: 1) we propose the use of affine transformation to facilitate nested loop pipelining; 2) based on polyhedral model, we present a precise and general formulation of the nested loop pipelining problem on a CGRA; and 3) using the insights from problem formulation, we design a joint affine transformation and multipipeline merging approach to improve the performance of nested loop on CGRA. The experimental results show that our approach can improve the performance of nested loops up to 35% on average, compared with the state-of-the-art techniques.

Modified Gram–Schmidt (MGS) algorithm is one of the most-known forms of QR decomposition (QRD) algorithms. It has been used in many signal and image processing applications to solve least square problem and linear equations or to invert matrices. However, QRD is well-thought-out as a computationally expensive technique, and its sequential implementation fails to meet the requirements of many real-time applications. In this paper, we suggest a new parallel version of MGS algorithm that uses VLIW (Very Long Instruction Word) resources in an efficient way to get more performance. The presented parallel MGS is based on compact VLIW kernels that have been designed for each algorithm step taking into account architectural and algorithmic constraints. Based on instruction scheduling and software pipelining techniques, the proposed kernels exploit efficiently data, instruction and loop levels parallelism. Additionally, cache memory properties were used efficiently to enhance parallel memory access and to avoid cache misses. The robustness, accuracy and rapidity of the introduced parallel MGS implementation on VLIW enhance significantly the performance of systems under severe rea-time and low power constraints. Experimental results show great improvements over the optimized vendor QRD implementation and the state of art.

Iterators prescribe the traversal of data structures and determine loop termination, and many loop analyses and transformations require their exact identification. While recognition of iterators is a straight-forward task for affine loops, the situation is different for loops iterating over dynamic data structures or involving control flow dependent computations to determine the next data element. In this paper we propose a compiler analysis for recognizing loop iterators code for a wide class of loops. We initially develop a static analysis, which is then enhanced with profiling information to support speculative code optimizations. We have prototyped our analysis in the LLVM framework and demonstrate its capabilities using the SPEC CPU2006 benchmarks. Our approach is applicable to all loops and we show that we can recognize iterators in, on average, 88.1% of over 75,000 loops using static analysis alone, and up to 94.9% using additional profiling information. Existing techniques perform substantially worse, especially for C and C++ applications, and cover only 35–44% of the loops. Our analysis enables advanced loop optimizations such as decoupled software pipelining, commutativity analysis and source code rejuvenation for real-world applications, which escape analysis and transformation if loop iterators are not recognized accurately.

To improve the overall performance of computer systems, instruction-level parallelism (ILP) has been widely exploited. However, branch hazards, conditional and unconditional, still limit the efficiency of most ILP techniques. Compiler techniques such as loop unrolling, software pipelining, and trace scheduling are being used to increase the amount of parallelism available in systems with fairly predictable branches, while predicated instructions have been useful in eliminating branch hazards in specific cases. The limitations imposed on ILP by branch hazards, however, are significant in large blocks of codes or, at best, hidden at the expense of processor resources. As a result, researchers are exploring the techniques of approximate computing, which when applied, would be suitable for only fault-tolerant systems. Some are also working on the methods of code approximation, which mainly involves hazard minimization by distribution over specific parts of code segments. In this work, we propose and demonstrate a novel branch hazard distribution technique — Symbolic Execution using Approximate Computing (SEAC). We applied the proposed technique to a test program and ran simulation experiments using the Detailed CPU model in gem5 simulator. Simulation results show that SEAC is 3.57, 1.95 and 1.32 times better than the best, among the tested conventional ILP techniques, based on speedup, energy saving, and branch hazard distribution coefficient respectively.

This paper proposes a DSP optimization solution of rain detection and removal algorithm. We propose rain detection and removal algorithms considering camera motion, and also presents optimization results in algorithm level and DSP level. At algorithm level, this paper utilizes a block level binary pattern analysis, and reduces the operation time by using the fast motion estimation algorithm. Also, the algorithm is optimized at DSP level through inter memory optimization, EDMA, and software pipelining for real-time operation. Experiment results show that the proposed algorithm is superior to the other algorithms in terms of visual quality as well as processing speed.

This paper provides an extended description of the design and implementation of the Time Iterated Dependency Flow (TIDeFlow) execution model. TIDeFlow is a dataflow-inspired model that simplifies the scheduling of shared resources on many-core processors. To accomplish this, programs are specified as directed graphs and the dataflow model is extended through the introduction of intrinsic constructs for parallel loops and the arbitrary pipelining of operations. The main contributions of this paper are: (1) a formal description of the TIDeFlow execution model and its programming model, (2) a description of the TIDeFlow implementation and its strengths over previous execution models, such as the ability to natively express parallel loops and task pipelining, (3) an analysis of experimental results showing the advantages of TIDeFlow with respect to expressing parallel programs on many-core architectures and (4) a presentation of the implementation of a low overhead runtime system for TIDeFlow.

Pipelining is a popularly used technique to achieve higher frequency of operation of digital signal processing (DSP) applications, by reducing the critical path of circuits. But conventionally critical path is estimated by the discrete component timing model in terms of the times required for the computation of additions and multiplications, where arithmetic circuits are considered as discrete components. Pipeline registers are inserted in between arithmetic circuits to reduce the estimated critical path. In this paper, we show that very often the architecture-level pipelining, based on the discrete component timing model, does not result in significant reduction in critical path, but on the other hand increases the latency and register complexity. In order to derive greater advantage of pipelining, propagation delays of different combinational sections could be evaluated precisely at gate level or at least at the level of one-bit adders, and based on that, the critical path could be reduced by placing the pipeline registers seamlessly across the combinational datapath without restricting them to be placed only in between arithmetic circuits. In this paper, we present adequately precise evaluation of propagation delays across combinational path as a network of arithmetic circuits based on seamless view of signal propagation. Using the precise information of propagation delay of combinational sections, we identify the best possible locations of pipeline registers in order to reduce the critical path up to the desired limit. The proposed seamless pipelining approach is found to achieve the desired acceleration of DSP applications without significant pipeline overhead in terms of latency and register complexity.

We describe an automated pipelining approach for optimally balanced pipeline implementation that achieves low area cost as well as meeting timing requirements. Most previous automatic pipelining methods have focused on Instruction Set Architecture (ISA)-based designs and the main goal of such methods generally has been maximizing performance as measured in terms of instructions per clock (IPC). By contrast, we focus on datapath-oriented designs (e.g., DSP filters for image or communication processing applications) in ASIC design flows. The goal of the proposed pipelining approach is to find the optimally pipelined design that not only meets the user-specified target clock frequency, but also seeks to minimize area cost of a given design. Unlike most previous approaches, the proposed methods incorporate the use of accurate area and timing information (iteratively achieved by synthesizing every interim pipelined design) to achieve higher accuracy during design exploration. When compared with exhaustive design exploration that considers all possible pipeline patterns, the two heuristic pipelining methods presented here involve only a small area penalty (typically under 5%) while offering dramatically reduced computational complexity. Experimental validation is performed with commercial ASIC design tools and described for applications including polynomial function evaluation, FIR filters, matrix multiplication, and discrete wavelet transform filter designs with a 90nm standard cell library.

In the past years, many works have demonstrated the applicability of Coarse-Grained Reconfigurable Array (CGRA) accelerators to optimize loops by using software pipelining approaches. They are proven to be effective in reducing the total execution time of multimedia and signal processing applications. However, the run-time reconfigurability of CGRAs is hampered overheads introduced by the needed translation and mapping steps. In this work, we present a novel run-time translation technique for the modulo scheduling approach that can convert binary code on-the-fly to run on a CGRA. We propose a greedy approach, since the modulo scheduling for CGRA is an NP-complete problem. In addition to read-after-write dependencies, the dynamic modulo scheduling faces new challenges, such as register insertion to solve recurrence dependences and to balance the pipelining paths. Our results demonstrate that the greedy run-time algorithm can reach a near-optimal ILP rate, better than an off-line compiler approach for a 16-issue VLIW processor. The proposed mechanism ensures software compatibility as it supports different source ISAs. As proof of concept of scaling, a change in the memory bandwidth has been evaluated. In this analysis it is demonstrated that when changing from one memory access per cycle to two memory accesses per cycle, the modulo scheduling algorithm is able to exploit this increase in memory bandwidth and enhance performance accordingly. Additionally, to measure area and performance, the proposed CGRA was prototyped on an FPGA. The area comparisons show that a crossbar CGRA (with 16 processing elements and including an 4-issue VLIW host processor) is only 1.11 × bigger than a standalone 8-issue VLIW softcore processor.

Increased complexity of computer hardware makes close to impossible to rely on hand-coding at the-level of HDLs for digital hardware design. High-level synthesis can be employed instead, in order to automatically obtain HDL codes from highlevel language functional descriptions. With high-level synthesis it becomes easier to design coprocessors, accelerators, and other special-purpose hardware. Nonetheless, compiler optimizations can improve efficiency of automatically generated hardware descriptions and make high-level synthesis to become the dominant technology to build more complicated hardware as well. Compilers, well known and explored software tools, can allow programmers to use their software skills on hardware programming, without any language compromises. Furthermore, compiler optimizations transform the input code, in order to produce a high-quality high-performance output hardware description. In this paper, we discuss compiler issues for high-level synthesis, and in particular, the incorporation of loop pipelining in the C language front end of the CCC high-level synthesis tool. We also present a novel pipelining technique that minimizes the area used for the pipeline prologue and epilogue. Results from experiments on the Livermore loops and Mpeg2 open-source codes validate our technique.

For the next generations of Processor-Arrays-on-Chip (e. g., coarse-grained reconfigurable or programmable arrays)—including more than 100s to 1000s of processing elements—it is very important to keep the on-chip configuration/instruction memories as small as possible. Hence, compilers must take into account the scarceness of available instruction memory and create the code as compact as possible [1]. However, Very Long Instruction Word (VLIW) processors have the well-known problem that compilers typically produce lengthy codes. A lot of unnecessary code is produced due to unused Functional Units (FUs) or repeating operations for single FUs in instruction sequences. Techniques like software pipelining can be used to improve the utilization of the FUs, yet with the risk of code explosion [2] due to the overlapped scheduling of multiple loop iterations or other control flow statements. This is, where our proposed Orthogonal Instruction Processing (OIP) architecture (see Fig. 1) shows benefits in reducing the code size of compute-intensive loop programs. The idea is, contrary to lightweight VLIW processors used in arrays like Tightly Coupled Processor Arrays (TCPAs) [4], to equip each FU with its own instruction memory, branch unit, and program counter, but still let the FUs share the register files as well as input and output signals. This enables a processor to orthogonally execute a loop program. Each FU can execute its own sub-program while exchanging data over the register files. The branch unit and its instruction format have to be slightly changed by introducing a counter to each instruction that determines how often the instruction is repeated until the specified branch is executed. This enables repeating instructions without repeating them in the code. Those kind of processors have to be carefully programmed, e. g., to not run into data dependency problems while optimizing throughput. For solving this resource-constrained modulo scheduling problem, we use techniques based on mixed integer linear programming [5], [3].

High-Level Synthesis (HLS) has been widely recognized as an efficient compilation process targeting FPGAs for algorithm evaluation and product prototyping. However, the massively parallel memory access demands and the extremely expensive cost of single-bank memory with multi-port have impeded loop pipelining performance. Thus, based on an alternative multi-bank memory architecture, a joint approach that employs memory-aware force directed scheduling and multi-cycle memory partitioning is formally proposed to achieve legitimate pipelining kernel and valid bank mapping with less resource consumption and optimal pipelining performance. The experimental results over a variety of benchmarks show that our approach can achieve the optimal pipelining performance and meanwhile reduce the number of multiple independent memory banks by 55.1% on average, compared with the state-of-the-art approaches.

High-Level Synthesis (HLS) has been widely recognized and accepted as an efficient compilation process targeting FPGAs for algorithm evaluation and product prototyping. However, the massively parallel memory access demands and the extremely expensive cost of single-bank memory with multi-port have impeded loop pipelining performance. Thus, based on an alternative multi-bank memory architecture, a joint approach that employs memory-aware force directed scheduling and multi-cycle memory partitioning is formally proposed to achieve legitimate pipelining kernel and valid bank mapping with less resource consumption and optimal pipelining performance. The experimental results over a variety of benchmarks show that our approach can achieve the optimal pipelining performance and meanwhile reduce the number of multiple independent memory banks by 55.1% on average, compared with the state-of-the-art approaches.

Current pipelining approach in high-level synthesis (HLS) achieves high performance for applications with regular and statically analyzable memory access patterns. However, it cannot effectively handle infrequent data-dependent structural and data hazards because they are conservatively assumed to always occur in the synthesized pipeline. To enable high-throughput pipelining of irregular loops, we study the problem of augmenting HLS with application-specific dynamic hazard resolution, and examine its implications on scheduling and quality of results. We propose to generate an aggressive pipeline at compile-time while resolving hazards with memory port arbitration and squash-and-replay at run-time. Our experiments targeting a Xilinx FPGA demonstrate promising performance improvement across a suite of representative benchmarks.

In modern computing, multitasking is the most favorable aspect. An un-pipelined instruction cycle (fetch-execute cycle) CPU processes instructions one after another increasing duration at lesser speed in completing tasks. With pipelined computer architecture, unprecedented improvement in size and speed are achievable. This work investigates the possibility of a better improvement to computer architecture through understanding the inner workings of instruction pipelining in operating system. A design of a 5 stage pipelined architecture simulator for RiSC-16 processors using Visual Basic programming has been achieved contrary to the common available four stage simulators. The simulator also future two most common pipeline instruction hazards generally missing in most available simulators. Thus, the designed simulator becomes an appropriate tool for understanding the concept of pipelining on a step-by-step visualization based instructioncycle processors hence facilitating a more efficient design in computer architecture. The simulator has been evaluated based on its closeness to real time pipelined computer architecture and through execution of all 8 basic RiSC-16 instruction set with data dependency and control hazard.

The increasing gap between plentiful computing elements and limited memory bandwidth makes it increasingly difficult and sometimes even infeasible for HPC community to port more applications onto many-core processor architectures. The Sunway many-core processor SW26010 used to build the Sunway TaihuLight System contains a total of 260 heterogeneous cores. All these cores can be divided into 4 core groups (CGs). Each CG includes a Management Processing Element (MPE) core and 64 Computing Processing Elements (CPEs) cores. In this paper, we refactor an important molecular dynamics (MD) application GROMACS on the Sunway Taihulight system. By rewriting the compute-intensive kernel of GROMACS, we exploit a suitable parallelism for CPE cluster and implement pipelining computation between MPE and CPE cluster. Optimization strategies including the efficient use of scratchpad, the software-emulated cache and a hybrid parallel algorithm are adopted to solve the challenging memory bandwidth limitation. When comparing the refactored version using MPE and 64 CPEs with the original ported version using only MPE, we achieve a 16x speedup for the compute-intensive kernel. For simulating a molecule with 3 million atoms, we currently have managed to scale to 798,720 cores. Moreover, we analyze the adaptability of our mapping and optimization strategies for solving the memory bandwidth limitation when refactoring a real-world application on the Sunway heterogeneous many-core processor system.

The purpose of this chapter is to introduce asynchronous programming with OpenACC, particularly in regards to a technique known as pipelining. This chapter will accelerate an existing OpenACC code by enabling the overlap of computation and data transfers. At the end of this chapter the reader will have an understanding of: • Asynchronous execution within OpenACC • Pipelining as a technique to overlap data transfers with computation • How to use the OpenACC routine directive.

The method of optimal partitioning of subscriber messages into protocol data units by the transport layer according to the criterion of delays in the multi-hop transmission path is proposed. The terms of the appropriateness of the fragmentation of messages into packets during its transmission over multi-hop virtual channel are obtained. Analytical dependences for the optimal packet size from the structure of network traffic and settings of the virtual connections are obtained.

International audience; Cyclic scheduling has been widely studied because of the importance of applications in manufacturing systems and in computer science. For this class of problems, a finite set of tasks with precedence relations and resource constraints must be executed repetitively while maximizing the throughput. Many applications also require that execution schedules be periodic i.e. the execution of each task is repeated with a fixed global period w.The present paper develops a new method to build periodic schedules with cumulative resource constraints, periodic release dates and deadlines. The main idea is to fix the period w, to unwind the cyclic scheduling problem for some number of iterations, and to add precedence relations so that the minimum time lag between two successive executions of any task equals w. Then, using any usual (not cyclic) scheduling algorithm to compute task starting times for the unwound problem, we prove that either the method converges to a periodic schedule of period w or it fails to compute a schedule. A non-polynomial upper bound on the number of iterations to unwind in order to guarantee that cyclic precedence relations and resource constraints are fulfilled is also provided. This method is successfully applied to a real-life problem, namely the software pipelining of inner loops on an embedded VLIW processor core by using a Graham list scheduling algorithm.