Accession Number:

ADA172144

Title:

Retiming Synchronous Circuitry.

Descriptive Note:

Interim research rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

• Leiserson,Charles E.
• Saxe,James B.

Report Date:

1986-05-01

Pagination or Media Count:

33.0

Abstract:

This paper shows how the technique of retiming can be used to transform a given synchronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph, and we give an OV ElgV algorithm for determining an equivalent circuit with the smallest possible clock period. We show that the problem of determining an equivalent retimed circuit with minimum state total number of registers is polynomial-time solvable. This result yields a polynomial-time optimal solution to the problem of pipelining combinational circuitry with minimum register cost. We also give a characterization of optimal retiming based on an efficiently solvable mixed-integer linear programming problem. Author

Descriptors:

• *EQUIVALENT CIRCUITS
• *REGISTERS(CIRCUITS)
• ALGORITHMS
• GRAPHS
• COSTS

Subject Categories:

• Electrical and Electronic Equipment

Distribution Statement:

APPROVED FOR PUBLIC RELEASE