PRESAGE, a tool for the design of low-cost systolic circuits

The theory behind PRESAGE is described. Given a set of uniform recurrences, PRESAGE finds the linear timing and the linear allocation functions that minimize the number of time steps and the number of processors in the circuit. Depending on the specifications, pure or semisystolic circuit designs are generated. Specifications on the connections are used to derive circuits with unidirectional data flow. Finally, when both directions of pipelining are allowed, PRESAGE finds the one that minimizes the cost of the circuit. The essence of the tool is an algorithm that solves some particular integer programming problems. The method used by the algorithm is briefly summarized