Search

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 1/x or exp(+/-x) 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 1/x"i and exp(+/-x"i) for a vector of inputs x"i 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.

In the literature, techniques such as pipelining and wave-pipelining (WP) are proposed for increasing the operating frequency of a digital circuit. In general, use of pipelining results in higher speed at the cost of increase in the area and clock routing complexity. On the other hand, use of WP results in less clock routing complexity and less area but enables the digital circuit to be operated only at moderate speeds. In this paper, a hybrid wave-pipelining scheme is proposed to get the benefits of both pipelining and WP techniques. Major contributions of this paper are: proposal for the implementation of 2D DWT using lifting scheme by adopting the hybrid wave-pipelining and proposal for the automation of the choice of clock frequency and clock skew between the input and output registers of wave-pipelined circuit using built in self test (BIST) and system-on-chip (SOC) approaches. In the hybrid scheme, different lifting blocks are interconnected using pipelining registers and the individual blocks are implemented using WP. For the purpose of evaluating the superiority of the schemes proposed in this paper, the system for the computation of one level 2D DWT is implemented using the following techniques: pipelining, non-pipelining and hybrid wave-pipelining. The BIST approach is used for the implementation on Xilinx Spartan-II device. The SOC approach is adopted for implementation on Altera and Xilinx field programmable gate arrays (FPGAs) based SOC kits with Nios II or Micro blaze soft-core processors. From the implementation results, it is verified that the hybrid WP circuit is faster than non-pipelined circuit by a factor of 1.25–1.39. The pipelined circuit is in turn faster than the hybrid wave-pipelined circuit by a factor of 1.15–1.38 and this is achieved with the increase in the number of registers by a factor of 1.79–3.15 and increase in the number of LEs by a factor of 1.11–1.65. The soft-core processor based automation scheme has considerably reduced the effort required for the design and testing of the hybrid wave-pipelined circuit. The techniques proposed in this paper, are also applicable for ASICs. The optimization schemes proposed in this paper are also applicable for the computation of other image transforms such as DCT, DHT.

Wave-pipelining enables a digital circuit to be operated at a higher frequency. In the literature, only trial-and-error and manual procedures are adopted for the choice of the optimum value of clock frequency and clock skew between the input and output registers of wave-pipelined circuits. One of the major contributions of this paper is the proposal for automating the above procedure. A second contribution is the study of how logic depths determine the superiority of wave-pipelining over pipelining with regard to power dissipation. For the study and implementation of wave-pipelined circuits, filters using the distributed arithmetic algorithm are considered. In this paper, two automation schemes are proposed for the implementation of the wave-pipelined filters on both Xilinx and Altera field programmable gate arrays (FPGAs). In the first scheme, a self-tuning finite state machine (FSM) is used to choose the clock skew and clock period for I/O registers between the wave-pipelined blocks. In the second approach, an on-chip soft-core processor is used to choose the clock skew and clock period. To test the efficacy of the schemes proposed, filters with different taps are implemented using three schemes: synchronous pipelining, sub-optimal wave-pipelining and no pipelining (i.e. using neither synchronous pipelining nor wave-pipelining). From the implementation results, it is observed that wave-pipelined distributed arithmetic (DA) filters are faster by a factor of 1.31–1.61 compared to non-pipelined DA filters. The synchronous pipelined DA filters are in turn faster by a factor of 1.73–3.27 compared to the wave-pipelined DA filters. The increased speeds are achieved in the pipelined filters at the cost of an increase in the number of slices by 15–33% and in the number of registers by 350–530%. To compare the power dissipation, both pipelined and wave-pipelined DA filters are tested by operating them at the same frequency. For medium logic depths, the wave-pipelined DA filters dissipate less power than pipelined filters.

While multicore hardware has become ubiquitous, explicitly parallel programming models and compiler techniques for exploiting parallelism on these systems have noticeably lagged behind. Stream programming is one model that has wide applicability in the multimedia, graphics, and signal processing domains. Streaming models execute as a set of independent actors that explicitly communicate data through channels. This paper presents a compiler technique for planning and orchestrating the execution of streaming applications on multicore platforms. An integrated unfolding and partitioning step based on integer linear programming is presented that unfolds data parallel actors as needed and maximally packs actors onto cores. Next, the actors are assigned to pipeline stages in such a way that all communication is maximally overlapped with computation on the cores. To facilitate experimentation, a generalized code generation template for mapping the software pipeline onto the Cell architecture is presented. For a range of streaming applications, a geometric mean speedup of 14.7x is achieved on a 16-core Cell platform compared to a single core.

We implemented the H.264/AVC variable block size motion estimation (VBSME) using a very long instruction word (VLIW)---single instruction multiple data (SIMD) digital signal processor (DSP). The SAD_Reuse method which has a regular structure is chosen for VBSME not only to remove redundant sum of absolute difference (SAD) operations but also to utilize the instruction level parallelism (ILP) and data level parallelism (DLP) of the architecture. A fast mode decision algorithm is developed to reduce the number of `compare and update' operations and simplify the rate distortion optimization (RDO). The developed fast mode decision uses the difference of motion vectors and the maximum a posteriori (MAP) estimation of the rate-distortion costs. Several advanced software techniques that include software pipelining and packed-data processing are employed. Especially, memory access overhead reduction schemes including the multi-block processing and the inter-procedural scheduling are used for the software optimization. In order to reduce the `write buffer full' in the quarter pixel ME, a 4 bit quantization scheme is developed, which increases the number of arithmetic operations but decreases the stall cycles very much. The implemented variable block size ME for H.264/AVC requires an average of 9 M and 78 Mcycles per frame for QCIF and CIF size video sequences, respectively, in the TMS320C64x DSP architecture.

Kernel recognition techniques avoid the search for an appropriate initiation interval by dealing directly with a representation of the unrolled loop and its compaction. Intuitively, kernel recognition tries to achieve the effect of fully unrolling and then compacting the loop. In this chapter we present a number of kernel recognition methods that overcome the limitations of modulo scheduling in different ways, including methods that generate provably optimal schedules (in the absence of resource constraints) and handle the scheduling of tests directly, without the need for an intermediate abstraction such as hierarchical reduction.

Coarse-grained reconfigurable architecture (CGRA) is a promising platform for loop acceleration, but existing software pipelining methods cannot achieve satisfactory performance on a fair number of imperfect nested loops, especially those with sibling inner loops. To tackle this problem, this paper makes 2 contributions: 1) a 2-level pipelining method with an effective II optimization strategy for the imperfect loops with sibling inner loops; 2) a novel kernel compression method to reduce oversize kernel. Experiment results show that our approach can achieve much higher performance than the state-of-the-art approaches at acceptable costs.

Software pipelining is an efficient method of loop optimization that allows for parallelism of operations related to different loop iterations. Currently, most commercial compilers use loop pipelining methods based on modulo scheduling algorithms. This paper reviews these algorithms and considers algorithmic solutions designed for overcoming the negative effects of software pipelining of loops (a significant growth in code size and increase in the register pressure) as well as methods making it possible to use some hardware features of a target architecture. The paper considers global-scheduling mechanisms allowing one to pipeline loops containing a few basic blocks and loops in which the number of iterations is not known before the execution.

This paper presents several theoretical and fundamental results on the register need in periodic schedules, also known as MAXLIVE. Our first contribution 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 II. 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.

As CMOS feature sizes continue to shrink and traditional microarchitectural methods for delivering high performance (e.g., deep pipelining) become too expensive and power-hungry, chip multiprocessors (CMPs) become an exciting new direction by which system designers can deliver increased performance. Exploiting parallelism in such designs is the key to high performance, and we find that parallelism must be exploited at multiple levels of the system: the thread-level parallelism that has become popular in many designs fails to exploit all the levels of available parallelism in many workloads for CMP systems. We describe the Cell Broadband Engine and the multiple levels at which its architecture exploits parallelism: data-level, instruction-level, thread-level, memory-level, and compute-transfer parallelism. By taking advantage of opportunities at all levels of the system, this CMP revolutionizes parallel architectures to deliver previously unattained levels of single chip performance. We describe how the heterogeneous cores allow to achieve this performance by parallelizing and offloading computation intensive application code onto the Synergistic Processor Element (SPE) cores using a heterogeneous thread model with SPEs. We also give an example of scheduling code to be memory latency tolerant using software pipelining techniques in the SPE.

Majority of scientific and Digital Signal Processing (DSP) applications are recursive or iterative. Transformation techniques are generally applied to increase parallelism for these nested loops. Most of the existing loop transformation techniques either can not achieve maximum parallelism, or can achieve maximum parallelism but with complicated loop bounds and loop indexes calculations. This paper proposes a new technique, loop striping, that can maximize parallelism while maintaining the original row-wise execution sequence with minimum overhead. Loop striping groups iterations into stripes, where all iterations in a stripe are independent and can be executed in parallel. Theorems and efficient algorithms are proposed for loop striping transformations. The experimental results show that loop striping always achieves better iteration period than software pipelining and loop unfolding, improving average iteration period by 50 and 54% respectively.

Impulsionadas pelos constantes avanços da indústria de semicondutores, as aplicações computacionais têm evoluído consideravelmente, uma vez que podem fazer uso de circuitos eletrônicos eficientes e com alto poder computacional. Nesse sentido, a busca por maior desempenho pode ser conseguida por meio do aumento da frequência de operação, o que permite instruções executarem em tempo menor, ou pela execução concorrente das operações, por meio de técnicas de paralelismo. Este artigo apresenta a implementação da técnica de paralelismo chamada software pipelining em uma arquitetura de processamento não convencional. Adicionalmente, são mostrados resultados de simulação, que comprovam a eficiência da técnica quando o desempenho é medido em versões da arquitetura com e sem a implementação do software pipelining.

Power management is a major concern for computer architects and system designers. As reported by the International Technology Roadmap for Semiconductors (ITRS), energy consumption has become one of the most dominant issues for the semiconductor industry when the size of transistors scales down from 22 to 11 nm nodes. In this regard, current existing techniques such as dynamic voltage scaling, clock gating, and the Complementary metal-oxide semiconductor technology have shown their physical limits; therefore, scaling will no longer be a valid strategy for achieving power-performance improvement. To overcome this critical issue in energy-efficient processor design, there is a clear demand for alternative solution. In this paper, an approach that provides a promising solution for energy reduction is proposed, by using a micro-architectural technique referred to as variable stage pipelining, which can be further validated and extended to different application domains such as mobile and desktop. An analytical model for evaluating the relationship between the number of cores and the pipeline stage depth in a chip multi-processor is also proposed, based on which the optimal pipeline depth for various metrics are calculated.

Pipelining is a common method to implement high speed FIR filters. While the efficient pipelining of multiplications is well understood, no attention has been paid on the pipelining of structural adders so far. The delay of structural adders becomes crucial in high speed designs as they have the largest word size in non-truncated FIR filters and typically lie in the critical path. The common pipelining method results in an excessive overhead in registers when applied to the structural adders as many additional paths have to be delayed. An efficient method for pipelining structural adders using a partially redundant number representation is proposed in this paper. With a very little area overhead of 5.4%, the throughput of the structural adders can be doubled while a speedup factor of up to 7 can be achieved with an area overhead of 26.7%.

This paper presents an accelerating face detection algorithm using Coarse Grained Reconfigurable Architectures (CGRA). Face detection algorithms usually use several stages of cascaded face detectors and require large amount of feature data, while general processors have small internal memory. Since the latency from external memory is much longer than internal memory, efficient use of memory is important to make face detection faster. In this paper, we do the first-stage of cascaded face detection process for every line using the feature data in the internal memory, and then do next stages for the candidates that pass the first-stage. In addition, by efficient use of software pipelining and vectorization, face detection process can be accelerated. The proposed method was implemented into CGRA@400MHz, and can run at 15.1@800×600 frame per second.

This paper presents a compiler flow to map Deep Convolutional Networks (ConvNets) to a highly specialized VLIW accelerator core targeting the low-power embedded market. Earlier works have focused on energy efficient accelerators for this class of algorithms, but none of them provides a complete and practical programming model. Due to the large parameter set of a ConvNet it is essential that the user can abstract from the accelerator architecture and does not have to rely on an error prone and ad-hoc assembly programming model. By using modulo scheduling for software pipelining we demonstrate that our automatic generated code achieves equal or within 5-20% less hardware utilization w.r.t. code written manually by experts. Our compiler removes the huge manual workload to efficiently map ConvNets to an energy-efficient core for the next-generation mobile and wearable devices.

Stream programming based on the synchronous data flow (SDF) model naturally exposes data, task and pipeline parallelism. Statically scheduling stream programs for homogeneous architectures has been an area of extensive research. With graphic processing units (GPUs) now emerging as general purpose co-processors, scheduling and distribution of these stream programs onto heterogeneous architectures (having both GPUs and CPUs) provides for challenging research. Exploiting this abundant parallelism in hardware, and providing a scalable solution is a hard problem.In this paper we describe a coarse-grained software pipelined scheduling algorithm for stream programs which statically schedules a stream graph onto heterogeneous architectures. We formulate the problem of partitioning the work between the CPU cores and the GPU as a model-checking problem. The partitioning process takes into account the costs of the required buffer layout transformations associated with the partitioning and the distribution of the stream graph. The solution trace result from the model checking provides a map for the distribution of actors across different processors/-cores. This solution is then divided into stages, and then a coarse grained software-pipelined code is generated. We use CUDA streams to map these programs synergistically onto the CPU and GPUs. We use a performance model for data transfers to determine the optimal number of CUDA streams on GPUs. Our software-pipelined schedule yields a speedup of upto 55.86X and a geometric mean speedup of 9.62X over a single threaded CPU.

Recently, researchers have shown an increased interest in using task-level pipelining to accelerate the overall execution of applications mainly consisting of producer-consumer tasks. This paper proposes optimization techniques for enhancing our approach to pipeline the execution of producer-consumer tasks in FPGA-based multicore architectures with reductions in the number of accesses to external memory. Our approach is able to speedup the overall execution of successive, data-dependent tasks, by using multiple cores and specific customization features provided by FPGAs. We evaluate the impact in the performance of task-level pipelining when using different hash functions and optimization schemes in the inter stage buffer (ISB). The optimizations proposed in this paper were evaluated with FPGA implementations. The experimental results show the efficiency of a simple scheme to reduce external memory accesses and the suitability of the hash function being used. Furthermore, the results reveal noticeable performance improvements for the set of benchmarks being used.

Loop pipelining is probably the most important optimization method in high-level synthesis (HLS), allowing multiple loop iterations to execute in a pipeline. In this paper, we extend the capability of loop pipelining in HLS to handle loops with uncertain memory behaviours. We extend polyhedral synthesis techniques to the parametric case, offloading the uncertainty to parameter values determined at run time. Our technique then synthesizes lightweight runtime checks to detect the case where a low initiation interval (II) is achievable, resulting in a run-time switch between aggressive (fast) and conservative (slow) execution modes. This optimization is implemented into an automated source-to-source code transformation framework with Xilinx Vivado HLS as one RTL generation backend. Over a suite of benchmarks, experiments show that our optimization can implement transformed pipelines at almost same clock frequency as that generated directly with Vivado HLS, but with approximately 10× faster initiation interval in the fast case, while consuming approximately 60% more resource.

In this paper, we discuss efficient implementation of machine learning algorithms on DSPs. Specifically, we implement OCR and speech recognition on DSP and show how they can be optimized using fixed point routines. We illustrate the optimal usage of DSP resources like MAC units, shifters and software pipelining through assembly code structuring which massively reduces the MIPS consumed by the processor. We also describe how floating point overheads can be reduced by equivalent fixed point routines for real time implementations. Though the Blackfin-533 DSP is chosen for this illustration, the ideas presented here apply to other fixed point DSPs as well.

Multiple constant multiplication (MCM) is widely used in several digital signal processing applications. Recently, pipelining techniques have been applied to accelerate the computation of the MCM blocks. The existing pipelining techniques consider the adder stage pipelining, i.e., inserting registers between two adjacent adder stages, to reduce the adder depth. However, the critical path may be still long, even though the adder depth is minimized. In this paper, the adder stage pipelining method is analyzed at bit-level and a novel pipelining method is proposed for pipelining the adders in the MCM block. Experimental results show that the proposed pipelining method provides nearly 32% reduction of critical path over the traditional adder stage pipelining in average for several benchmark MCM blocks, while the area and power consumption are maintained.

Coarse Grained Reconfigurable Arrays (CGRAs) offer improved energy efficiency and performance over conventional architectures. However, modulo counter based control of these devices limits efficiency for applications with multiple execution modes. This work presents a new type of architecture that adds support for branching control flow to CGRAs. The pipelined program counter CGRA framework blends the high parallelism of traditional CGRAs with the flexibility of commodity processors. Offset Pipelined Scheduling (OPS) is the basis of an enhanced CGRA tool chain targeting these devices. OPS is shown to provide an average 1.94x speed up for benchmarks that are resource limited when modulo scheduled.

In this paper a multiplexer based S-box architecture with 5 stage pipelining is proposed The proposed AES S-box were implemented on Xilinx device XC5VLX20T Virtex-5 FPGA. The results are compared with modular design architecture. This implementation gives 10.55 ns path delay with the slice area of 52 without pipelining and 1.74 ns path delay with the slice area of 36 by introducing 5 stage pipelining. The results show that the pipelined modified structure reduces the critical path so the through put is increased to 4.5Gbps.

As multicore architectures enter the mainstream, there is a pressing demand for high-level programming models that can effectively map to them. Stream programming offers an attractive way to expose coarse-grained parallelism, as streaming applications (image, video, DSP, etc.) are naturally represented by independent filters that communicate over explicit data channels.In this paper, we demonstrate an end-to-end stream compiler that attains robust multicore performance in the face of varying application characteristics. As benchmarks exhibit different amounts of task, data, and pipeline parallelism, we exploit all types of parallelism in a unified manner in order to achieve this generality. Our compiler, which maps from the StreamIt language to the 16-core Raw architecture, attains a 11.2x mean speedup over a single-core baseline, and a 1.84x speedup over our previous work.

This brief presents a high-speed parallel cyclic redundancy check (CRC) implementation based on unfolding, pipelining, and retiming algorithms. CRC architectures are first pipelined to reduce the iteration bound by using novel look-ahead pipelining methods and then unfolded and retimed to design high-speed parallel circuits. A comparison on commonly used generator polynomials between the proposed design and previously proposed parallel CRC algorithms shows that the proposed design can increase the speed by up to 25% and control or even reduce hardware cost

The complexity of many embedded software applications and their stringent performance requirements have reached a point where they can no longer be supported by conventional embedded-system architectures based on a single general-purpose processor. Nanometer fabrication technologies have made it feasible to integrate several embedded processors on a single chip to create multiprocessor systems-on-chip (MPSoCs) for a wide range of applications. It is already well known that, for embedded systems, customizing the processor to the application can significantly increase performance and energy efficiency. Single-chip heterogeneous multiprocessors, where the different processors are customized to the tasks they perform, are thus attracting attention. Despite their significant potential, a primary bottleneck to their adoption remains the development of programming paradigms and tools to alleviate the design complexity. Some advances have been made in the areas of custom multiprocessor architecture, tool support, and design methodology in order to reduce the design turnaround time. However, because of the heterogeneity of the custom processors, the designers are still required to manually map the application tasks to the different processors and, at the same time, customize each processor so that the overall performance requirements are satisfied. A multilevel custom multiprocessor-synthesis methodology to perform the assignment and scheduling of the application tasks on the various processors together with processor customization in an integrated manner is proposed. This paper focuses on extensible processors, which provide a good tradeoff between efficiency, flexibility, and design turnaround time, by combining a configurable base processor with hardware that implements custom instructions to extend its instruction set. This paper motivates the need for such an integrated approach by demonstrating that custom-instruction selection has complex interdependencies with task assignment and scheduling, and performing these steps independently often results in significant degradation in the quality of the synthesized multiprocessor architecture. The methodology presented here uses an iterative improvement algorithm to first assign and schedule tasks on processors and then select custom instructions along the critical path. It utilizes the concept of "expected execution time" to connect these two steps. It not only considers the currently selected custom instructions for the current task assignment and schedule, but also the possibility of better custom instructions being selected in future iterations. The methodology presented here is also enhanced to integrate task-level software pipelining to further increase the parallelism in the task graph and provide opportunities for multiprocessing. In this paper, the proposed heterogeneous multiprocessor-synthesis methodology is implemented in the context of a commercial extensible-processor design flow, using the Xtensa platform from Tensilica Inc. The presented tool was evaluated by automatically generating custom multiprocessor architectures for several complex embedded software benchmarks. The results show that architectures synthesized by the proposed methodology demonstrate an average speedup of 2.0times (up to 2.9times) compared to symmetric multiprocessor architectures in which the processors have not been augmented with custom instructions. To the best of the authors' knowledge, this is the first tool for the synthesis of custom MPSoCs using extensible processors

The increasingly complicated DSP processors and applications with strict timing and code size constraints require design automation tools to consider multiple optimizations such as software pipelining and loop unfolding, and their effects on multiple design parameters. This paper presents an Integrated Framework for Design Optimization and Space Minimization (IDOM) toward finding the minimum configuration satisfying timing and code size constraints. We show an effective way to reduce the design space to be explored through the study of the fundamental properties and relationships among retiming function, unfolding factor, timing, and code size. We present theorems to show that a small set of feasible unfolding factors can be obtained effectively to produce high-quality designs. The IDOM algorithm is proposed to generate a minimal configuration of the design by integrating software pipelining, unfolding, and code size reduction techniques. The experimental results on a set of DSP benchmarks show the efficiency and effectiveness of our technique.

Microprocessors exploit instruction-level parallelism and tolerate memory-access latencies to achieve high-performance. Out-of-order microprocessors do this by dynamically scheduling instruction execution, but require power-hungry hardware structures. This article describes multipass pipelining, a microarchitectural model that provides an alternative to out-of-order execution for tolerating memory access latencies. We call our approach "flea-flicker" multipass pipelining because it uses two (or more) passes of preexecution or execution to achieve performance efficacy. Multipass pipelining assumes compile-time scheduling for lower-power and lower-complexity exploitation of instruction-level parallelism

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

We propose a systematic pipelining method for a linear system to minimize power and maximize throughput, given a constraint on the number of pipeline stages and a set of resource constraints. Unlike most existing pipelining approaches, our method takes the number of pipeline stages as one of the constraints and considers the pipelining as an aspect of power minimization. Operations are retimed so that as many operations as possible take common operands as their inputs, using a novel technique called force-directed retiming; operand sharing is then determined, based on list scheduling. Experimental results show that the proposed approach reduces the power consumption of functional units by 27.8% on average and by more than 50% in some cases, compared to the state-of-the-art pipelining and operand sharing techniques.

Software pipelining is a critical optimization for producing efficient code for VLIW/EPIC and superscalar processors in high-performance embedded applications such as digital signal processing. Software thread integration (STI) can often improve the performance of looping code in cases where software pipelining performs poorly or fails. This paper examines both situations, presenting methods to determine what and when to integrate.We evaluate our methods on C-language image and digital signal processing libraries and synthetic loop kernels. We compile them for a very long instruction word (VLIW) digital signal processor (DSP) -- the Texas Instruments (TI) C64x architecture. Loops which benefit little from software pipelining (SWP-Poor) speed up by 26% (harmonic mean, HM). Loops for which software pipelining fails (SWP-Fail) due to conditionals and calls speed up by 16% (HM). Combining SWP-Good and SWP-Poor loops leads to a speedup of 55% (HM).

Micro-architecture designers are very cautious about expanding the number of architected registers (also the register field), because increasing the register field adds to the code size, raises I-cache and memory pressure, complicates processor pipeline. Especially for low-end processors, encoding space could be extremely limited due to area and power considerations. On the other hand, the number of architected registers exposed to the compiler could directly affect the effectiveness of compiler analysis and optimization. For high performance computers, register pressure can be higher than the available registers in some regions, e.g. due to optimizations like aggressive function inlining, software pipelining etc. The compiler cannot effectively perform compilation and optimization if only a small number of registers are exposed through the ISA. Therefore, it is crucial that more architected registers are available at the compiler's disposal without expanding the code size significantly.In this paper, we look at a new register encoding scheme called differential encoding that allows more registers to be addressed in the operand field of instructions than the direct encoding currently being used. We show it can be implemented with very low overhead. Based upon differential encoding, we apply it in several ways such that the extra architected registers can benefit the performance. Three schemes are devised to integrate differential encoding with register allocation. We demonstrate that differential register allocation is helpful in improving the performance of both high-end and low-end processors. Moreover, We can combine it with software pipelining to provide more registers and reduce spills.Our results show that differential encoding significantly reduces the number of spills and speeds up program execution. For a low-end configuration, we achieve over 12% speedup while keeping code size almost unaffected. For optimization on loops, it significantly speeds up loops with high register pressure (over 70% speedup).

Data dependency constraints constitute a lower bound P on the minimal clock period of single-phase clocked sequential circuits. In contrast to methods based on basic retiming, clocked sequential circuits with clock period P can always be obtained using software pipelining techniques. Such circuits can be derived by any method that can be framed in the following four-step process: Step 1, determine P; Step 2, compute a valid periodic schedule of the computational elements; Step 3, place registers back to the circuit; Step 4, assign the clock signals to control registers.Methods with polynomial run-time to implement this process are proposed in the literature. They implement these steps sequentially, starting with Step 1. These methods do not know how to optimally place registers which leads to an unnecessary number of registers. In this article, we address the problem of how to simultaneously implement Steps 2 and 3 in order to minimize the total number of registers. We conjecture that the problem is NP-hard in its general form. We formulate the problem for the first time in the literature, and devise a Mixed Integer Linear Program (MILP) to solve it. From this MILP, we derive a linear program to determine approximate solutions to the problem for large general circuits. We show that the proposed approach can handle nonzero clock skew. Experimental results confirm the effectiveness of the approach and show that significant reductions of the number of registers can be obtained although register sharing is not used. When the schedule is given, the proposed approach provides solutions to the problem of how to place the minimal number of registers in Step 3.

Application-specific instruction set processor (ASIP) design is a promising approach for meeting the performance and cost goals of embedded systems. We have developed a new microarchitecture, called a wide counterflow pipeline (WCFP), for automatically constructing ASIPs. Our ASIP synthesis technique uses software pipelining and design-space exploration to generate a custom WCFP and instruction set for an embedded application. This paper describes an innovative methodology and framework for WCFP synthesis and the lessons learned from designing and building the infrastructure. These lessons can be applied to other automated design tools for application-specific processors. The framework includes a user-supplied design database, intermediate representations for pipeline organization and custom instruction set architecture, and a reconfigurable simulator and performance analysis tool. The paper describes how the requirements and needs of automatic architectural design for WCFPs influenced the synthesis methodology and framework. To demonstrate the framework, we show its usefulness in refining the organization of custom WCFPs to better match the execution behavior of an application.

This paper introduces a compiler orchestrated prefetching system as a unified framework geared toward ameliorating the gap between processing speeds and memory access latencies. We focus the scope of the optimization on specific subsets of the program dependence graph that succinctly characterize the memory access pattern of both regular array-based applications and irregular pointer-intensive programs. We illustrate how program embedded precomputation via speculative execution can accurately predict and effectively prefetch future memory references with negligible overhead. The proposed techniques reduce the total running time of seven SPEC benchmarks and two OLDEN benchmarks by 27% on an Itanium 2 processor. The improvements are in addition to several state-of-the-art optimizations including software pipelining and data prefetching. In addition, we use cycle-accurate simulations to identify important and lightweight architectural innovations that further mitigate the memory system bottleneck. In particular, we focus on the notoriously challenging class of pointer-chasing applications, and demonstrate how they may benefit from a novel scheme of it sentineled prefetching . Our results for twelve SPEC benchmarks demonstrate that 45% of the processor stalls that are caused by the memory system are avoidable. The techniques in this paper can effectively mask long memory latencies with little instruction overhead, and can readily contribute to the performance of processors today.

Multiple on-chip memory modules are attractive to many high-performance digital signal processing (DSP) applications. This architectural feature supports higher memory bandwidth by allowing multiple data memory accesses to be executed in parallel. However, making effective use of multiple memory modules remains difficult. The performance gain in this kind of architecture strongly depends on variable partitioning and scheduling techniques. In this paper, we propose a graph model known as the variable independence graph (VIG) and algorithms to tackle the variable partitioning problem. Our results show that VIG is more effective than interference graph for solving variable partitioning problem. Then, we present a scheduling algorithm known as the rotation scheduling with variable repartition (RSVR) to improve the schedule lengths efficiently on a multiple memory module architecture. This algorithm adjusts the variable partitions during scheduling and generates a compact schedule based on retiming and software pipelining. The experimental results show that the average improvement on schedule lengths is 44.8% by using RSVR with VIG. We also propose a design space exploration algorithm using RSVR to find the minimum number of memory modules and functional units satisfying a schedule length requirement. The algorithm produces more feasible solutions with equal or fewer number of functional units compared with the method using interference graph.

The PRIMEPOWER HPC is a new Fujitsu HPC server, which combines the vector parallel processing technology of the VPP Series with the symmetric multi-processor (SMP) technology of the PRIMEPOWER UNIX server. The PRIMEPOWER HPC enables an SMP node configuration consisting of up to 128 high-speed (5.2 GFLOPS) scalar CPUs to be built. As up to 128 processing nodes can be crossbar-connected via a high-speed optical interconnection unit, the maximum configuration of the parallel multi-node system attains a logical performance of 85.2TFLOPS and 64 Tbytes of main memory. Features for high performance include high-speed CPUs, high-speed (133 gigabytes per second) snoop performance, and a barrier synchronization unit, while features for high reliability include redundancy of the node crossbar switch units and partitioning. This paper describes the parallel processing method and hardware features of the PRIMEPOWER HPC., 資料番号: AA0047427009, レポート番号: JAXA-SP-03-002

Software pipelining technique is extensively used to exploit instruction-level parallelism of loops, but also significantly expands the code size. For embedded systems with very limited on-chip memory resources, code size becomes one of the most important optimization concerns. This paper presents the theoretical foundation of code size reduction for software-pipelined loops based on retiming concept. We propose a general Code-size REDuction technique (CRED) for various kinds of processors. Our CRED algorithms integrate the code size reduction with software pipelining. The experimental results show the effectiveness of the CRED technique on both code size reduction and code size/performance trade-off space exploration.

Wave pipelining offers faster clock rates than conventional pipelining; however, wave-pipelined circuit design is time-consuming and requires a high level of expertise. Wave pipelining is especially vulnerable to delay changes due to variations in process, voltage, and temperature (PVT) and in the operating environment. Wave pipelining's performance is also affected by the minimum-delay path. Thus, minimum delay is also a concern for wave-pipelined circuits. Automating wave-pipelined circuit design, especially generating a design netlist, is therefore challenging. To automate the generation of wave-pipelined design netlists, we use a commercial synthesis tool, the synopsys design compiler, and delay-balancing scripts.

Software pipelining increases the loop execution throughput by overlapping the execution of successive iterations in a pipelined fashion. For loops with control flows, however, software pipelining is not straightforward because we need to consider the overlap of more than one execution path. Modulo scheduling simply transforms them into straightline loops through if-conversion which, in effect, achieves a fixed, worst-case initiation interval (/spl par/) among all paths. On the other hand, all-path pipelining (APP) and enhanced pipeline scheduling (EPS) can achieve a variable /spl par/ depending on the path that is taken at execution time. Unfortunately, APP concentrates only on the overlap within the same path, entirely losing the overlap between different paths, whereas EPS attempts to overlap all paths together, failing to produce a tight schedule for each individual path, especially when resource constraints are tight. In this paper, we propose a new approach to EPS called split-path EPS (SP-EPS), which first splits each individual path via tail duplication and then performs EPS in a way to guarantee a tight schedule for each path, while producing a competitive cross-path schedule. We also extend SP-EPS to outer loops such that frequent paths that bypass the inner loop are split and then scheduled by SP-EPS. Our experimental results on nontrivial integer benchmarks show that SP-EPS can achieve as much as a geometric mean of 10 percent speedup over EPS when innermost loops are scheduled by SP-EPS, while it can achieve a geometric mean of 11.9 percent speedup when outer loops are also scheduled by SP-EPS.

We address the problem of minimizing dynamic power consumption under performance constraints by scaling down the supply voltage of computational elements off critical paths. We assume that the number of possible supply voltages and their values are known for each computational element. We focus on solving this problem on cyclic and acyclic graphs corresponding to synchronous designs. We consider multiphase clocked sequential circuits derived using software pipelining techniques. In this paper, we present exact and heuristic methods to solve the problem. The proposed methods take the form of mathematical programming formulations and their associated solution algorithms. The exact methods are based on a mixed integer linear programming formulation of the problem. The heuristic methods are based on linear programming formulations derived from the exact problem formulation. Solution methods are analyzed experimentally in terms of their run time and effectiveness in finding designs with lower dynamic power using circuits from the ISCAS89 benchmark suite. Power reduction factors as high as 69.75% were obtained compared to designs using the highest supply voltages. One of the heuristic methods leads to solutions that are near optimal, typically within 5% from the optimal solution. Low dynamic-power designs with no or a small number of level converters, are also obtained.

Scheduling is the most important task in high-level synthesis process, while pipelining is highly important for realising high-performance digital components. This paper presents a pipeline list-based scheduling algorithm, which performs forward and backward pipelining. The forward priority function is based on incorporating some information extracted from data flow graph (DFG) structure to guide the scheduler to find near-optimal/optimal schedules quickly. The algorithm has a flexible procedure cycle, which allow designers to make efficient area-performance trade-offs by using different strategies employed. Designers can choose between doing forward / backward pipelining with or without resource sharing combined with clock cycle selection, pipe stage delay determination. Experimental results with standard benchmarks show the effectiveness of the proposed algorithm.

Software pipelining is widely used as a compiler optimization technique to achieve high performance in machines that exploit instruction-level parallelism. However, surprisingly, there have been few theoretical or empirical results on time optimal software pipelining of loops with control flows. In this paper, we present three new theoretical and practical contributions for this under-investigated problem. First, we propose a necessary and sufficient condition for a loop with control flows to have an optimally software-pipelined program. We also present a decision procedure to compute the condition. As part of the formal treatment of software pipelining, we propose a new formalization of software pipelining. Second, we present two software pipelining algorithms. The first algorithm computes an optimal solution for every loop satisfying the condition, but may run in exponential time. The second algorithm computes optimal solutions efficiently for most (but not all) loops satisfying the condition. The former one proves the sufficiency of the condition and the latter one suggests a practical optimal software pipelining algorithm. Third, we present experimental results which strongly indicate that achieving the time optimality in the software-pipelined programs is a viable goal in practice with reasonable hardware support.

This paper describes our experiments comparing multiple scalar replacement algorithms to evaluate their effectiveness on entire scientific application benchmarks within the context of a production-level compiler. We investigate at what point aggressive scalar replacement becomes detrimental and which dependence tests are necessary to give scalar replacement enough information to be effective. As many commercial optimizing compilers may include some version of scalar replacement as an optimization, it is important to determine how aggressive these algorithms need to be.Previously, no study has examined 'how much' scalar replacement is sufficient and effective within the context of an existing highly optimizing compiler. Our experiments show that, on whole programs, simple algorithms and simple dependence analysis capture nearly all opportunities for scalar replacement found in scientific application benchmarks. While additional aggressiveness may lead to some performance gain in some individual loops, it also leads to performance degradation too often to be worth the risk when considering entire applications. Algorithms restricted to value reuse over at most one loop iteration and to fully redundant array references give the best results.Our experiment further shows that scalar replacement is not only an effective optimization, but also a feasible one for commercial optimizers since the simple algorithms are not computationally expensive. Based upon our findings, we conclude that scalar replacement ought to be a part of any highly optimizing compiler because of its low cost and significant potential gain.

Software-pipelining is an important technique for increasing the instruction level parallelism of loops during compilation. Currently, the LLVM compiler infrastructure does not offer this optimization although some target specific implementations do exist. We have implemented a high-level method for software-pipelining within the LLVM framework. By implementing this within LLVM's optimization layer we have taken the first steps towards a target independent software-pipelining method.

Design automation has been one of the main propellers of the semiconductor industry with logic synthesis being one of the core technologies in this field. This article reviews the evolution of logic synthesis until the advent of techniques for automatic pipelining based on elastic timing, either synchronous or asynchronous. The emergence of these techniques can enable a productive interaction with tools that can do microarchitectural exploration of complex designs.

International audience; — Multidimensional retiming is an efficient optimization approach that ensures increasing a parallelism level in order to optimize the execution time. Two existing techniques called incremental and chained multidimensional retiming are based on this approach, which aim at achieving a full parallelism on loop body in order to schedule applications with a minimum cycle period. However, the cycle number increases in terms of parallelism level which presents a limiting factor to respect the execution time constraint of real-time applications. In this paper, we show how the minimal cycle period is achieved in multidimensional applications without applying a full parallelism. We present the theory of a novel technique, called delayed multidimensional retiming. Firstly, two efficient algorithms are presented where the first one insures the extraction of timing and data dependency properties of the application and the second one selects the set of data path for retiming. Then, we propose theorems to deduce a retiming function for the selected paths. Finally, a third algorithm describing the optimization approach is introduced. The experimental results show that our technique improves execution times in comparison to existing techniques. It achieves average improvements on the execution time of 41.57% compared to the Incremental technique and 11.55% compared to the Chained technique.