Cost measures in VLSI array design

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 ν for processing during step τ(ν) on processor π(ν). The range of π also is a convex polyhedron (usually k-1 dimensions). In general, the designer is interested in determining the best τ and π 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