INCORPORATING INTERCONNECT, REGISTER, AND CLOCK DISTRIBUTION DELAYS INTO THE RETIMING PROCESS

A retiming algorithm is presented which includes the effects of variab le register, clock distribution, and interconnect delays, These delay components are incorporated into the retiming process by assigning reg ister electrical characteristics (REC's) to each edge in the graph rep resentation of a synchronous circuit, A matrix, called the sequential adjacency matrix (SAM), is presented that contains all path delays, Ti ming constraints for each data path are derived from this matrix. Vert ex lags are assigned ranges rather than single values as ire existing retiming algorithms. The approach used in the proposed algorithm is to initialize these ranges with unbounded values and to continuously tig hten these ranges using localized timing constraints until an optimal solution is obtained, A branch and bound method is offered for the gen eral retiming problem where the REC values are arbitrary, Certain mono tonicity constraints can be placed on the REC values to permit the use of standard linear programming methods, thereby requiring significant ly less computational time, These conditions and the feasibility of th eir application to practical circuits are presented, The algorithm is demonstrated on modified benchmark circuits and both increased clock f requencies and the elimination of all race conditions are observed.