Cost measures in VLSI array design
Peter R. Cappello, Sanjay V. Rajopadhye · 2002
The authors consider parameterized families of directed acyclic graphs (DAGs) whose nodes can be labeled with integral index points in a k-dimensional index space, and whose node set consists of all the integral points inside a convex polyhedron in k-space. Given a DAG, a multiprocessor schedule assigns node nu for processing during step tau ( nu ) on processor pi ( nu ). The range of pi also is a convex polyhedron (usually k-1 dimensions). In general, the designer is interested in determining the best tau and pi for a given DAG, and a number of different cost functions have been used. The authors attempt to develop a unified view of these measures. They first define these measures, study some relationships between them, and discuss how they can be defined. By investigating the costs associated with linear mappings, the authors propose guidelines for practical mappings. From the complexity viewpoint, the authors are interested in the best that one can do for a given DAG, regardless of the mapping chosen. They investigate some intrinsic properties of the DAG.>