Algorithm transformations for parallel processing and VLSI architecture design
J.A.B. Fortes · University of Southern California Digital Library · 2015
This dissertation describes a methodology for the systematic design of algorithmically specified (VLSI) array processors. The basic idea behind our approach is to transform the original algorithm, which can hardly be mapped into an array processor, into an equivalent algorithm for which an easy mapping exists and it allows for maximum parallelism using a minimum number of processors. We introduce an algorithm model that is simple and powerful enough to represent most algorithms described in a conventional programming language. In this model, the set of data dependencies is the most important component for our VLSI design procedure based on algorithm transformations. By inspecting the matricial representation of the dependencies of an algorithm we can easily find orderings of execution that explore parallelism. Knowing the desirable form of the dependencies, we can devise algorithm transformations that yield an equivalent algorithm with that desired set of dependencies. Algorithm transformations are composed of a time and space transformation. We give methods for optimally selecting both transformations when they are described by linear functions and they preserve syntactical algorithm equivalence. The optimal time transformation is obtained by solving a non trivial nonlinear integer programming problem. The transformed algorithms can be executed in near-optimal time. We show how to select space and time transformations so that data communication does not degrade unnecessarily the execution time of an algorithm and broadcasts are eliminated or reduced to easily implementable local broadcasts. VLSI architectures will have restricted use unless they can execute algorithms of arbitrary size. We show how to design VLSI arrays so that algorithms can be partitioned with minimal side effects, i.e., without destroying correctness, increasing the complexity of the cells of the array or unnecessarily degrading execution time. Algorithm transformations that preserve forms of algorithm equivalence that are weaker than syntactical equivalence are also discussed. (Copies available exclusively from Micrographics Department, Doheny Library, USC, Los Angeles, CA 90089.)