MINIMIZING THE NUMBER OF DELAY BUFFERS IN THE SYNCHRONIZATION OF PIPELINED SYSTEMS

When designing a pipelined digital system, delay buffers (often implem ented as shift registers) are usually introduced into the system in or der to synchronize the various signals impinging on each and every pro cessing element. By thus insuring that all related inputs to each proc essing element arrive at precisely the same time, additional memory fo r this purpose need not be included within the processing elements the mselves. The design of these elements may therefore be carried out ind ependently of the topologies of the systems within which they will ult imately appear. Clearly, any solution to this synchronization problem is not likely to be unique; that is, there will usually exist many com binations of buffer locations and lengths that can produce overall inp ut data synchronization in a typical pipelined network. When selecting one solution from many available solutions, it is natural to observe that it would be beneficial to implement a solution that makes use of the minimum number of total delay buffer stages necessary to produce s ynchronization in order that the system hardware cost and complexity m ay be reduced. In this paper, we present a technique to solve this del ay buffer problem in polynomial time. Unlike other polynomial-time met hods, this approach solves both the pipeline synchronization and buffe r minimization problems within a single formulation. Furthermore, this technique is readily extended to handle pipelined systems containing feedback loops as well as processing elements whose fanout loads are g reater than one. It has been used in a synthesis design environment de scribed in [1].