Search

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

QR decomposition (QRD) is one of the most widely used numerical linear algebra (NLA) kernels in several signal processing applications. Its implementation has a considerable and an important impact on the system performance. As processor architectures continue to gain ground in the high-performance computing world, QRD algorithms have to be redesigned in order to take advantage of the architectural features on these new processors. However, in some processor architectures like very large instruction word (VLIW), compiler efficiency is not enough to make an effective use of available computational resources. This paper presents an efficient and optimized approach to implement Givens QRD in a low-power platform based on VLIW architecture. To overcome the compiler efficiency limits to parallelize the most of Givens arithmetic operations, we propose a low-level instruction scheme that could maximize the parallelism rate and minimize clock cycles. The key contributions of this work are as follows: (i) New parallel and fast version design of Givens algorithm based on the VLIW features (i.e., instruction-level parallelism (ILP) and data-level parallelism (DLP)) including the cache memory properties. (ii) Efficient data management approach to avoid cache misses and memory bank conflicts. Two DSP platforms C6678 and AK2H12 were used as targets for implementation. The introduced parallel QR implementation method achieves, in average, more than 12 and 6 speedups over the standard algorithm version and the optimized QR routine implementations, respectively. Compared to the state of the art, the proposed scheme implementation is at least 3.65 and 2.5 times faster than the recent CPU and DSP implementations, respectively. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The graphic processing unit (GPU) is becoming increasingly popular as a performance accelerator in various applications requiring high-performance parallel computing capability. In a central processing unit (CPU) or GPU hybrid system, software pipelining is a major task in order to deliver accelerated performance, where hiding CPU–GPU communication overheads by splitting a large task into small units is the key challenge. In this paper, we carry out a systematic investigation into task partitioning in order to achieve maximum performance gain. We first validate the advantage of even partition strategy, and then propose the optimal scheduling, with detailed study into how to achieve optimal unit size (data granularity) in an analytical framework. Experiments on AMD and NVIDIA GPU platforms demonstrate that our approaches achieve around 31 – 59% performance improvement using software pipelining. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

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\texts 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. [ABSTRACT FROM PUBLISHER]

The fast Fourier transform (FFT) is perhaps today's most ubiquitous algorithm used with digital data; hence, it is still being studied extensively. Besides the benefit of reducing the arithmetic count in the FFT algorithm, memory references and scheme's projection on processor's architecture are critical for a fast and efficient implementation. One of the main bottlenecks is in the long latency memory accesses to butterflies' legs and in the redundant references to twiddle factors. In this paper, we describe a new FFT implementation on high-end very long instruction word (VLIW) digital signal processors (DSP), which presents improved performance in terms of clock cycles due to the resulting low-level resource balance and to the reduced memory accesses of twiddle factors. The method introduces a tradeoff parameter between accuracy and speed. Additionally, we suggest a cache-efficient implementation methodology for the FFT, dependently on the provided VLIW hardware resources and cache structure. Experimental results on a TI VLIW DSP show that our method reduces the number of clock cycles by an average of 51 % (2 times acceleration) when compared to the most assembly-optimized and vendor-tuned FFT libraries. The FFT was generated using an instruction-level scheduling heuristic. It is a modulo-based register-sensitive scheduling algorithm, which is able to compute an aggressively efficient sequence of VLIW instructions for the FFT, maximizing the parallelism rate and minimizing clock cycles and register usage. [ABSTRACT FROM AUTHOR]

We study the trade-off between throughput and memory footprint of embedded software that is synthesized from acyclic static dataflow (task graph) specifications targeting distributed memory multiprocessors. We identify iteration overlapping as a knob in the synthesis process by which one can trade application throughput for its memory requirement. Given an initial processor assignment and non-overlapped task schedule, we formally present underlying properties of the problem, such as constraints on a valid iteration overlapping, maximum possible throughput, and minimum memory footprint. Moreover, we develop an effective algorithm for generation of a rich set of design points that provide a range of trade-off options. Experimental results on a number of applications and architectures validate the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

Sparse matrix-vector multiplication (shortly SpM×V) is an important building block in algorithms solving sparse systems of linear equations, e.g., FEM. Due to matrix sparsity, the memory access patterns are irregular and utilization of the cache can suffer from low spatial or temporal locality. Approaches to improve the performance of SpM×V are based on matrix reordering and register blocking [1, 2], sometimes combined with software-pipelining [3]. Due to its overhead, register blocking achieves good speedups only for a large number of executions of SpM×V with the same matrix A.We have investigated the impact of two simple SW transformation techniques (software-pipelining and loop unrolling) on the performance of SpM×V, and have compared it with several implementation modifications aimed at reducing computational and memory complexity and improving the spatial locality. We investigate performance gains of these modifications on four CPU platforms.

We address the problem of generating compact code from software pipelined loops. Although software pipelining is a powerful technique to extract fine-grain parallelism, it generates lifetime intervals spanning multiple loop iterations. These intervals require periodic register allocation (also called variable expansion), which in turn yields a code generation challenge. We are looking for the minimal unrolling factor enabling the periodic register allocation of software pipelined kernels. This challenge is generally addressed through one of: (1) hardware support in the form of rotating register files, which solve the unrolling problem but are expensive in hardware; (2) register renaming by inserting register moves, which increase the number of operations in the loop, and may damage the schedule of the software pipeline and reduce throughput; (3) post-pass loop unrolling that does not compromise throughput but often leads to impractical code growth. The latter approach relies on the proof that MAXLIVE registers (maximal number of values simultaneously alive) are sufficient for periodic register allocation (Eisenbeis et al. in PACT '95: Proceedings of the IFIP WG10.3 working conference on Parallel Architectures and Compilation Techniques, pages 264-267, Manchester, UK, ; Hendren et al. in CC '92: Proceedings of the 4th International Conference on Compiler Construction, pages 176-191, London, UK, ). However, the best existing heuristic for controlling this code growth-modulo variable expansion (Lam in SIGPLAN Not 23(7):318-328, )-may not apply the correct amount of loop unrolling to guarantee that MAXLIVE registers are enough, which may result in register spills Eisenbeis et al. in PACT '95: Proceedings of the IFIP WG10.3 working conference on Parallel Architectures and Compilation Techniques, pages 264-267, Manchester, UK, . This paper presents our research results on the open problem of minimal loop unrolling, allowing a software-only code generation that does not trade the optimality of the initiation interval ( II) for the compactness of the generated code. Our novel idea is to use the remaining free registers after periodic register allocation to relax the constraints on register reuse. The problem of minimal loop unrolling arises either before or after software pipelining, either with a single or with multiple register types (classes). We provide a formal problem definition for each scenario, and we propose and study a dedicated algorithm for each problem. Our solutions are implemented within an industrial-strength compiler for a VLIW embedded processor from STMicroelectronics, and validated on multiple benchmarks suites. [ABSTRACT FROM AUTHOR]

Stream programming model has been productively applied to a number of important application domains. Software pipelining is an important code scheduling technique for stream programs. However, the multicore evolution has presented a new dimension of challenges: that is how to orchestrate the best software pipelining schedule in the face of resource constrained architectures (e.g., number of cores, available memory, and bandwidth)? In this paper, we proposed a new solution methodology to address the problem above. Our main contributions include the following. A unified Integer Linear Programming (ILP) formulation has been proposed that combines the requirement of both rate-optimal software pipelining and the minimization of intercore communication overhead. Next, an extended formulation has been proposed to formulate the schedule under memory size constrained systems. It orchestrates the rate-optimal software pipelining execution for stream programs with strict memory, processor cores, and communication constraints. A solution testbed has been implemented for the proposed problem formulations. This has been realized by extending the Brook programming environment with our software pipelining support—named DFBrook. An experimental study has been conducted to verify the effectiveness of the proposed solutions. [ABSTRACT FROM PUBLISHER]

Stream programming languages have become popular owing to their representations that enable parallelization of applications via static analysis. Several research groups have proposed approaches to software pipeline streaming applications onto multi/many-core architectures, such as CELL BE processors and NVIDIA GPUs. In this paper, we present a novel scheduling algorithm that software-pipelines streaming applications onto multi/many core architectures. The algorithm generates software pipeline schedules by formulating and solving MILP (Mixed Integer Linear Programming) problems. Experimental results show that compared to previous works, our approach generates schedules that use up to a 71% smaller amount of buffers needed for communication between kernels. [ABSTRACT FROM AUTHOR]

In this paper, we address a cyclic scheduling problem of finding a periodic schedule with minimal period for the unitary resource constrained cyclic scheduling problem. The main originality is in being able to cope with both precedence delays and complex resource settings which make the problem $\mathcal{NP}$-complete, in general. A guaranteed approach, called Decomposed Software Pipelining, has been proposed by Gasperoni and Schwiegelshohn (Parallel Process. Lett. 4:391-403, ), followed by the retiming method by Calland et al. (IEEE Trans. Parallel Distrib. Syst. 9(1):24-35, ) to solve the problem assuming parallel identical processors and ordinary precedence constraints. In this paper, an extension of this approach to unitary resource-constrained cyclic scheduling problems with precedence delays, is analyzed and its worst case performance ratio is provided. [ABSTRACT FROM AUTHOR]

semi-conductor technologies move down to the nanometer scale, leakage power has become a significant component of the total power consumption. In this paper, we present a leakage-aware modulo scheduling algorithm to achieve leakage energy saving for applications with loops on Very Long Instruction Word (VLIW) architectures. The proposed algorithm is designed to maximize the idleness of function units integrated with the dual-threshold domino logic, and reduce the number of transitions between the active and sleep modes. We have implemented our technique in the Trimaran compiler and conducted experiments using a set of embedded benchmarks from DSPstone and Mibench on the cycle-accurate VLIW simulator of Trimaran. The results show that our technique achieves significant leakage energy saving compared with a previously published DAG-based (Directed Acyclic Graph) leakage-aware scheduling algorithm. [ABSTRACT FROM AUTHOR]

Abstract: This article treats register constraints in high performance codes and embedded VLIW computing, aiming to decouple register constraints from instruction scheduling. It extends the register saturation (RS) concept to periodic instruction schedules, i.e., software pipelining (SWP). We formally study an approach which consists in computing the exact upper-bound of the register need for all the valid SWP schedules of an innermost loop (without overestimation), independently of the functional unit constraints. We call this upper-limit the periodic register saturation (PRS) of the data dependence graph (DDG). PRS is well adapted to situations where spilling is not a favourite solution for reducing register pressure compared to ILP scheduling: spill operations request memory data with a higher energy consumption. Also, spill code introduces unpredictable cache effects and makes Worst-Case-Execution-Time (WCET) estimation less accurate. PRS is a computer science concept that has many possible applications. First, it provides compiler designers new ways to generate better codes regarding register optimisation by avoiding useless spilling. Second, its computation can help architectural designers to decide about the most suitable number of available registers inside an embedded VLIW processor; such architectural decision can be done with full respect to instruction level parallelism extraction, independently of the chosen functional units configuration. Third, it can be used to verify prior to instruction scheduling that a code does not require spilling. In this paper, we write an appropriate mathematical formalism for the problem of PRS computation and reduction in the case of loops where data dependence graphs may be cyclic. We prove that PRS reduction is NP-hard and we provide optimal and approximate methods. We have implemented our methods, and our experimental results demonstrate the practical usefulness and efficiency of the PRS approach. [Copyright &y& Elsevier]

Abstract: The modern microprocessors have become more sophisticated, the performance of software on modern architectures has grown more and more difficult to dissect and prognosticate. The execution of a program nowadays entails the complex interaction of code, compiler and processor micro-architecture. The built-in functions to compute or of math library and hardware are often incapable of achieving the challenging performance of high-performance numerical computing. To meet this demand, the current trend in constructing high-performance numerical computing for specific processors Alpha 21264 & 21364, and IA-64 has been optimized for and for a vector of inputs which is significantly faster than optimized library routines. A detailed deliberation of how the processor micro-architecture as well as the manual optimization techniques improve the computing performance has been developed. [Copyright &y& Elsevier]

This paper presents several theoretical and fundamental results on the register need in periodic schedules, also known as MAXLIVE. Our first computation is a novel formula for computing the exact number of registers needed by a scheduled loop. This formula has two advantages: Its computation can be done by using a polynomial algorithm with O(n lg n) complexity (n is the number of instructions in the loop) and it allows the generalization of a previous result [13]. Second, during software pipelining, we show that the minimal number of registers needed may increase when incrementing the initiation interval (II), which is contrary to intuition. For the case of zero architectural delays in accessing registers, we provide a sufficient condition for keeping the minimal number of registers from increasing when incrementing the II. Third, we prove an interesting property that enables us to optimally compute the minimal periodic register sufficiency of a loop for all its valid periodic schedules, irrespective of H. Fourth and last, we prove that the problem of optimal stage scheduling under register constraints is polynomially solvable for a subclass of data dependence graphs, whereas this problem is known to be NP-complete for arbitrary dependence graphs [7]. Our latter result generalizes a previous achievement [13] which addressed data dependence trees and forest of trees. In this study, we consider cyclic data dependence graphs without taking into account any resource constraints. The aim of our theoretical results on the periodic register need is to help current and future software pipeliners achieve significant performance improvements by making better (if not the best) use of the available resources. [ABSTRACT FROM AUTHOR]

Improved Enhanced Modulo Scheduling (Improved EMS) is proposed as an efficient software pipelining method for loops with conditional branches. In EMS and Improved EMS, multiple pipeline kernels are generated, depending on the truth value of the condition, and the appropriate one is selected on execution at each iteration. Since these kernels have variables that live for the number of stages with different conditions mixed together, register allocation becomes difficult. In this paper, the authors discuss register allocation methods using interference graphs for EMS and improved EMS. The first method is a register allocation method using conventional interference graph which is applied to the deployed kernels. Because the interference graph becomes very large, however, in proportion to the number of kernels deployed in the method, the proposed method reduces the size of the interference graph by overlapping the graphs and improves the results of register allocation. These two methods were evaluated with approximating coloring algorithms. It was clear that allocation could be performed rapidly, and in a manner in no way inferior to the conventional method for the number of registers by the method by overlapping and reducing the size of the graphs. © 2006 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 89(12): 59– 69, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20290 [ABSTRACT FROM AUTHOR]

Register allocation in loops is generally performed after or during the software pipelining process. This is because doing a conventional register allocation as a first step without assuming a schedule lacks the information of interferences between values live ranges. Thus, the register allocator may introduce an excessive amount of false dependences that dramatically reduce the ILP (Instruction Level Parallelism). We present a new theoretical framework for controlling the register pressure before software pipelining. Thus is based on inserting some anti-dependence edges (register reuse edges) labeled with reuse distances, directly on the data dependence graph. In this new graph, we are able to fix the register pressure, measured as the number of simultaneously alive variables in any schedule. The determination of register and distance reuse is parameterized by the desired minimum initiation interval (MII) as well as by the register pressure constraints - either can be minimized while the other one is fixed. After scheduling, register allocation is done on conventional register sets or on rotating register files. We give an optimal exact model, and an approximation that generalizes the Ning-Gao [22] buffer optimization method. We provide experimental results which show good improvement compared to [22]. Our theoretical model considers superscalar, VLIW and EPIC/IA64 processors. [ABSTRACT FROM AUTHOR]

Although the hardware platform is often seen as the most important element of real-time imaging systems, software optimization can also provide remarkable reduction of overall computational costs. The recommended code development flow for digital signal processors based on the TMS320C6000TM architecture usually involves three phases: development of C code, refinement of C code, and programming linear assembly code. Each step requires a different level of knowledge of processor internals. The developer is not directly involved in the automatic scheduling process. In some cases, however, this may result in unacceptable code performance. A better solution can be achieved by scheduling the assembly code by hand. Unfortunately, scheduling of software pipelines by hand not only requires expert skills but is also time consuming, and moreover, prone to errors. To overcome these drawbacks we have designed an innovative development tool—the Software Pipeline Optimization Tool (SPOTTM). The SPOT is based on visualization of the scheduled assembly code by a two-dimensional interactive schedule editor, which is equipped with feedback mechanisms deduced from analysis of data dependencies and resource allocation conflicts. The paper addresses optimization techniques available by the application of the SPOT. Furthermore, the benefit of the SPOT is documented by more than 20 optimized image processing algorithms. [Copyright &y& Elsevier]