Parameterized dependence graph and its applications to multi-stage systolic mapping procedure

A systolic mapping procedure is proposed. A unified representation, the parameterized dependence graph (PDG), is proposed to faithfully represent the possible implementations of a given computing algorithm. A multistage mapping procedure, taking advantage of the PDG, is developed to map a multistage algorithm to a systolic array. Specifically, the multistage mapping problem is formulated as an NP-hard optimization problem. A heuristic best first search method then is devised to efficiently exploit the design space for a design which minimizes a heuristic cost function