Certain investigations Into Optimization of multi loop problems for reconfigurable VLSI Design

Abstract

The high integration density of very large scale integrated (VLSI) circuits has made system on chip design (SoC) become a reality. With increasing complexity of SoC, it becomes important to raise the design abstraction to a behavioral level in order to enable the development of new design methodologies to tap the full potential of reconfigurable SoC platforms for various compute bound applications. The focus here is on mapping of computationally intensive multi-loop nest algorithms (termed as n-dimensional) onto parallel array architectures where the target architecture considered is a systolic array comprising of locally interconnected grid of processing elements (PEs). The problem of determining the configuration of PE array for mapping of the n-dimensional (n-D) nested loop problems has been receiving considerable attention in the recent years. The mapping methodologies, which have been used in systolic array design, use the set of dependencies in the n-D nested loop problems represented by dependence vectors (DV) and determine the projection matrix constituted of the processor space matrix (P) and the timing function or vector (S). Heuristic approaches have been used to search for the projection matrices, but the complexity of search procedure grows with the loop nest size and hence these methods need a large computational effort. The mapping methodology proposed in this thesis identifies that for multidimensional problems, the compute sub-space lies strictly in a lower dimension. The computational expression and the subspace in which it lies are defined as the computational trail vector (CTV) and (n-x)-D compute sub-space respectively. The PE array is allocated to each point in this subspace.