Vicki H. Allan, Reese B. Jones, Randall M. Lee et al. · ACM Computing Surveys · 1995
Utilizing parallelism at the instruction level is an important way to improve performance. Because the time spent in loop execution dominates total execution time, a large body of optimizations focuses on decreasing the time to execute each iteration. Software pipelining is a technique that reforms the loop so that a faster execution rate is realized. Iterations are executed in overlapped fashion to increase parallelism. Let { ABC } n represent a loop containing operations A, B, C that is executed n times. Although the operations of a single iteration can be parallelized, more parallelism may be achieved if the entire loop is considered rather than a single iteration. The software pipelining transformation utilizes the fact that a loop { ABC } n is equivalent to A { BCA } n −1 BC . Although the operations contained in the loop do not change, the operations are from different iterations of the original loop. Various algorithms for software pipelining exist. A comparison of the alternative methods for software pipelining is presented. The relationships between the methods are explored and possibilities for improvement highlighted.
Cited by 344Open access
John C. Ruttenberg, Guang R. Gao, Arthur Stoutchinin et al. · 1996
This paper is a scientific comparison of two code generation techniques with identical goals --- generation of the best possible software pipelined code for computers with instruction level parallelism. Both are variants of modulo scheduling, a framework for generation of software pipelines pioneered by Rau and Glaser [RaG181], but are otherwise quite dissimilar.One technique was developed at Silicon Graphics and is used in the MIPSpro compiler. This is the production compiler for SGI's systems which are based on the MIPS R8000 processor [Hsu94]. It is essentially a branch--and--bound enumeration of possible schedules with extensive pruning. This method is heuristic because of the way it prunes and also because of the interaction between register allocation and scheduling.The second technique aims to produce optimal results by formulating the scheduling and register allocation problem as an integrated integer linear programming (ILP1) problem. This idea has received much recent exposure in the literature [AlGoGa95, Feautrier94, GoAlGa94a, GoAlGa94b, Eichenberger95], but to our knowledge all previous implementations have been too preliminary for detailed measurement and evaluation. In particular, we believe this to be the first published measurement of runtime performance for ILP based generation of software pipelines.A particularly valuable result of this study was evaluation of the heuristic pipelining technology in the SGI compiler. One of the motivations behind the McGill research was the hope that optimal software pipelining, while not in itself practical for use in production compilers, would be useful for their evaluation and validation. Our comparison has indeed provided a quantitative validation of the SGI compiler's pipeliner, leading us to increased confidence in both techniques.
Cited by 94
Copyright Reese, B. Jones, Reese B. Jones · 1991
Considerable research has been done in the area of parallelization. In machines that have many synchronous functional units, the extraction of fine-grain parallelism is an important topic.
Cited by 0
Alexander Aiken, Alexandru Nicolau, Steven Novack · 1995
This paper presents a software pipelining algorithm for the automatic extraction of ne-grain parallelism in general loops. The algorithm accounts for machine resource constraints in a way that smoothly integrates the management of resource constraints with software pipelining. Furthermore, generality in the software pipelining algorithm is not sacriced to handle resource constraints, and scheduling choices are made with truly global information. Proofs of correctness and the results of experiments with an implementation are also presented. 1
Cited by 0
2008
Cited by 0
Cristina Barrado, Eduard Ayguadé, Jesús Labarta · 1998
Software pipelining is becoming widely used as a loop execution model for microprocessors supporting a high instruction level parallelism. In this paper we describe a heuristic method for software pipelining, named Graph Traverse Software Pipelining (GTSP), that divides the scheduling problem in two phases: scheduling on a graph and code generation. The first phase encapsulates the NP-complete part of the problem. The scheduling is represented on the data dependence graph (DDG) through a set of scheduling recurrences composed of scheduling edges, representing a partial ordering between statements in the each recurrence. A heuristic is given to include such edges in order to generate efficient schedules. It improves previous software pipelining techniques achieving the maximum throughput for 98% of a benchmark set composed of more than 500 innermost loops from the SpecFP95. The second phase is a fast and automatic algorithm that transforms the scheduling generated on the DDG into VLIW-l...
Cited by 0
Neil Vachharajani, Ram Rangan, Easwaran Raman et al. · Proceedings of the ... Conference on Parallel Architectures and Compilation Techniques/Proceedings of the Conference on Parallel Architectures and Compilation Techniques · 2007
In recent years, microprocessor manufacturers have shifted their focus from single-core to multi-core processors. To avoid burdening programmers with the responsibility of parallelizing their applications, some researchers have advocated automatic thread extraction. A recently proposed technique, Decoupled software pipelining (DSWP), has demonstrated promise by partitioning loops into long-running, fine-grained threads organized into a pipeline. Using a pipeline organization and execution decoupled by inter-core communication queues, DSWP offers increased execution efficiency that is largely independent of inter-core communication latency. This paper proposes adding speculation to DSWP and evaluates an automatic approach for its implementation. By speculating past infrequent dependences, the benefit of DSWP is increased by making it applicable to more loops, facilitating better balanced threads, and enabling parallelized loops to be run on more cores. Unlike prior speculative threading proposals, speculative DSWP focuses on breaking dependence recurrences. By speculatively breaking these recurrences, instructions that were formerly restricted to a single thread to ensure decoupling are now free to span multiple threads. Using an initial automatic compiler implementation and a validated processor model, this paper demonstrates significant gains using speculation for 4-core chip multiprocessor models running a variety of codes.
Cited by 58
Wolfgang Thaller · 2006
Software Pipelining is a method of instruction scheduling where loops are scheduled more efficiently by executing operations from more than one iteration of the loop in parallel. Finding an optimal software pipelined schedule is NP-complete, but many heuristic algorithms exist. In iteration i, a software pipelined loop will execute, in parallel, ”stage” 1 of iteration i, stage 2 of iteration i − 1 and so on until stage k of iteration i − k + 1. We present a new approach to software pipelining based on using a heuristic algorithm to explicitly assign each operation to its stage before the actual scheduling. This explicit assignment allows us to implement control flow mechanisms that are hard to implement with traditional methods of software pipelining, which do not give us direct control over what stages instructions are assigned to.
Cited by 4
Amod K. Dani, V. Janaki Ramanan, R. Govindarajan · 2002
We propose an integrated approach for register-sensitive software pipelining. In this approach, the heuristics proposed in the stage scheduling method of A.E. Eichenberger and E.S. Davidson (1995) are integrated with the iterative scheduling method to obtain schedules with high initiation rate and low register requirements. The performance of our integrated software pipelining method was analyzed for a large number of loops taken from a variety of scientific benchmark programs. Our studies reveal that the stage scheduling heuristics facilitate better performance benefits when applied at the scheduling time, resulting in significant performance improvement over both the stage scheduling method and the slack scheduling method.
Cited by 1
Jian Wang, Andreas Krall, M. Anton Ertl · 2015
Although it is well-known that a strong interaction exists between software pipelining and register allocation, simultaneous software pipelining and register allocation is still less understood and remains an open problem. In this paper, we first analyze the influence of the reuse of registers on the loop data dependence graph and model the problem of software pipelining to reduce register requirement based on the concepts of row-number and column-number of decomposed software pipelining. Given the row-numbers of all operations in the loop, generating the column-numbers to obtain the minimum register requirement can be modelled as the integer programming problem which can be solved in polynomial time. Then, a solution is presented to the special case without resource constraints and an approximate solution is presented to the general case with resource constraints. Register spilling and register coloring are considered to further reduce the number of actually needed registers. The preliminary experimental results are presented to indicate the efficiency of our new approach.
Cited by 0
Alex Aiken, A. Nicolau, Steven Novack · IEEE Transactions on Parallel and Distributed Systems · 1995
This paper presents a software pipelining algorithm for the automatic extraction of fine-grain parallelism in general loops. The algorithm accounts for machine resource constraints in a way that smoothly integrates the management of resource constraints with software pipelining. Furthermore, generality in the software pipelining algorithm is not sacrificed to handle resource constraints, and scheduling choices are made with truly global information. Proofs of correctness and the results of experiments with an implementation are also presented.
Cited by 71
J. Ramanujam · 1994
This paper presents an approach to software pipelining of nested loops. While several papers have addressed software pipelining of inner loops, little work has been done in the area of extending it to nested loops. This paper solves the problem of finding the minimum iteration initiation interval (in the absence of resource constraints) for each level of a nested loop. The problem is formulated as one of finding a rational quasi-affine schedule for each statement in the body of a perfectly nested loop which is then solved using linear programming. This allows us to treat iteration-dependent statement reordering and multidimensional loop unrolling in the same framework. Unlike most work in scheduling nested loops, we treat each statement in the body as a unit of scheduling. Thus, the schedules derived allow for instances of statements from different iterations to be scheduled at the same time. Optimal schedules derived here subsume extant work on software pipelining of inner loops, in t...
Cited by 0
Guang R. Gao, Qi Ning, Vincent Van Dongen · 1993
In this paper, we present a novel framework of software pipelining for nested loops. Under this framework, a periodic scheduling function, called r-periodic schedule, is associated with each operation of the loop body in the entire iteration space. We present a simple problem formulation as well as efficient solutions which gives provable asymptotically time-optimal schedule for nested loops under our program model. It also provides some useful insights on the interplay between unimodular loop transformation and fine-grain scheduling under a unified framework. The main results are: ffl We show that, for nested loops under our program model, software pipelining problem can be formulated into a very simple linear programming problem based on r-periodic schedules. ffl We prove that the r-periodic scheduling is asymptotically time-optimal, that is, it is asymptotically as good as the best schedule --- the free schedule where statements can be freely scheduled as early as possible subjec...
Cited by 0
Raya Leviathan · 2008
The paper presents a method for translation validation of a specific optimization, software pipelining optimization, used to increase the instruction level parallelism in EPIC type of architectures. Using a methodology as in [15] to establish simulation relation between source and target based on computational induction, we describe an algorithm that automatically produces a set of decidable proof obligations. The paper also describes SPV, a prototype translation validator that automatically produces verification conditions for software pipelining optimizations of the SGI Pro-64 compiler. These verification conditions are further checked automatically by the CVC [12] checker.
Cited by 0
Hongbo Rong, Zhizhong Tang · 2000
Software pipelining is an effective approach to loop scheduling. A common problem is that, if some paths are severely constrained by dependence cycles while others are not, how to find an optimal schedule without splitting paths. By removing control dependencies, speculation provides a general but limited answer. This paper provides another answer: removing data dependencies. Although a data dependency is a must-follow relationship, that does not mean it always has instances. By data dependence relaxation, a (near) optimal schedule with self-adaptable initiation interval is achieved.
Cited by 1
Chikako Nakanishi, Hideki Ando, Tetsuya Hara et al. · Systems and Computers in Japan · 1998
Software pipelining is an efficient scheduling technique for VLIW and superscalar processors. Performance improvement by using conventional algorithms has been restricted due to resource occupation by infrequently executed control paths and long data-dependent paths because all the control paths in a loop are pipelined. In this paper, we propose an algorithm that performs pipelining by selecting frequently executed paths in a loop. This algorithm provides for the possibility to optimally pipeline, not only frequently executed paths, but also non-innermost loops. This has been difficult in the past. We performed a comparative evaluation of this algorithm against conventional algorithms using benchmark programs for non-numerical application, and verified its high efficiency. © 1998 Scripta Technica, Syst Comp Jpn, 29(9): 74–86, 1998
Cited by 0
鼎超 李, 直宏 石井 · Medical Entomology and Zoology · 1998
Cited by 0
Yoshiyuki Yamashita, Masato Tsuru · Lecture notes in computer science · 2007
Cited by 3
Masataka Katahira, T. Sasaki, Hong Shen et al. · Proceedings of the ... International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN) · 2002
High performance processors based on pipeline processing play an important role in scientific computation. We have proposed a hybrid pipeline architecture named Jetpipeline in our former work. The concept of Jetpipeline comes from the integration of superscalar, VLIW and vector architectures. Jetpipeline has multiple instruction pipelines, which execute multiple instructions like superscalar architectures. Instructions to be executed simultaneously are statically scheduled by a compiler like VLIW architectures. Therefore, parallelism derivation and instruction scheduling are very important for Jetpipeline. Software pipelining is one of the well-known techniques to achieve high throughput when processing loop programs. In this paper, we propose software pipelining for Jetpipeline. Firstly, the overview of the Jetpipeline architecture is described. Then the banked register configuration of Jetpipeline for reducing hardware complexity and supporting software pipelining is presented. Finally, the effectiveness of software pipelining for Jetpipeline is discussed by simulation.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 2
Easwaran Raman, Guilherme Ottoni, Arun Raman et al. · 2008
In recent years, the microprocessor industry has embraced chip multiprocessors (CMPs), also known as multi-core architectures, as the dominant design paradigm. For existing and new applications to make effective use of CMPs, it is desirable that compilers automatically extract thread-level parallelism from single-threaded applications. DOALL is a popular automatic technique for loop-level parallelization employed successfully in the domains of scientific and numeric computing. While DOALL generally scales well with the number of iterations of the loop, its applicability is limited by the presence of loop-carried dependences. A parallelization technique with greater applicability is decoupled software pipelining (DSWP), which parallelizes loops even in the presence of loop-carried dependences. However, the scalability of DSWP is limited by the size of the loop body and the number of recurrences it contains, which are usually smaller than the loop iteration count.
Cited by 140