A theory of mapping program graphs onto linear arrays
Iyer Venkateshwaran Ramakrishnan · 1983
This thesis presents a formal model of linear array processors suitable for VLSI implementation as well as a graph representation of programs suitable for execution on such array processors. A distinction is made between correct mapping and correct execution of such graphs on this model. A complete characterization of the structure of the class of graphs that is correctly mappable is obtained. It is shown that some limited knowledge of the computation performed by these graphs in addition to their structural properties is important for their correct execution. Without such knowledge it is shown that the class of correctly executable graphs is very limited. A practical consequence of this theory is the development of an algorithm synthesis technique for this model. Syntheses of some existing algorithms as well as some novel algorithms are provided as examples.