Scheduling and Behavioral Transformations for Parallel Systems (Thesis)
Report ID: TR-430-93Author: Chao, Liang-Fang
Date: 1993-10-00
Pages: 182
Download Formats: |Postscript|
Abstract:
In a parallel system, either a VLSI architecture in hardware or a parallel program in software, the quality of the final design depends on the ability of a synthesis system to exploit the parallelism hidden in the input description of applications. Since iterative or recursive algorithms are usually the most time-critical parts of an application, the parallelism embedded in the repetitive pattern of an iterative algorithm needs to be explored. This thesis studies techniques and algorithms to expose the parallelism in an iterative algorithm so that the designer can find an implementation achieving a desired execution rate. In particular, the objective is to find an efficient schedule to be executed iteratively. A form of {it data-flow graphs} is used to model the iterative part of an application, e.g. a digital signal filter or the while/for loop of a program. Nodes in the graph represent operations to be performed and edges represent both intra-iteration and inter-iteration precedence relations. A schedule of the operations is executed repeatedly with certain execution rate. Two transformation techniques, {it retiming} (pipelining) and {it unfolding} (unwinding), are combined to transform a data-flow graph into another data-flow graph while preserving the intended behavior of the application. After the interaction of retiming and unfolding is analyzed, it is shown that the order of retiming and unfolding is immaterial. Algorithms are designed to find a transformation such that tThis new technique turns out to be very useful, and can be generalized to other problems. For example, the problem of {it software pipelining} in parallel compilers is modeled as a special case of our technique. Efficient polynomial-time algorithms are derived for the scheduling on different parallel models and implementation styles. For uniform nested loops, multi-dimensional retiming and unfolding are defined and studied for nested loop scheduling. Based on the theoretical results, a novel technique, {it rotation}, is designed for loop pipelining under resource constraints. Rotation technique repeatedly transforms a schedule To a more compact schedule. The rotation scheduling gives very good performance from the experiments on many benchmarks.