Publication

Abstract : Many computationally intensive algorithms are often represented as n-dimensional (n-D) nested loop algorithms. Systolic-array-based projections and their modifications involving multidimensional vector space representations have been used to realise the optimal VLSI design of deeply nested loop problems. The approaches employed so far involve an extensive search of the feasible solution space through heuristic methods and yield near optimal solutions. This paper presents a method of identifying the optimal solution directly and through a logical procedure. The new allocation method is shown to evolve around the computational expression and the sub-space in which it lies. The array of processing elements termed as the PE array is allocated to the indentified computational sub-space which is strictly of lower dimension than the n-D problem space. The proposed new optimal allocation procedure is first explained using the 3-D matrix/matrix multiplication (MMM) problem. The effectiveness of the method for higher dimensional problem is demonstrated through the illustrative example flow of 6-D full search block motion (FSBM) algorithm. The various design possibilities of the above mapping procedure are explored analytically and the cost constraints termed the figure of merit (FoM) of the design are evolved for the various design trade-offs for MMM and 6-D FSBM problem. An experimental methodology is developed using a hyper-graph model to represent the PE allocation to a particular sub-space of the n-D problem space. The advantage of our mapping procedure is illustrated by considering two cases namely, first an allocation represented by a vertex cover that covers the nodes of the identified computational (n - x)-D sub-space, where x lt; n, and in the second case as a random cover of group of nodes in the n-D problem space to model an allocation of PE array to a random sub-space. The design space exploration (DSE) results for the same are presented for the 6-D (FSBM) estimation algorithm using the high level synthesis tool 'GAUT' to compare the allocation of resources and utilisation in our method with the random PE array allocation and utilisation. It is found that our methodology leads to optimal number of resource allocation and their optimal utilisation for the various design possibilities using the timing constraint given as input to the HLS tool. Also the complexity of our approach is compared with that of existing methods which shows that the complexity of our approach does not grow with the n-D problem size. © 2013 Elsevier B.V. All rights reserved.