Backward-Data-Direction Clocking and Relevant Optimal Register Assignment in Datapath Synthesis

Keisuke INOUE  Mineo KANEKO  Tsuyoshi IWAGAKI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.4   pp.1067-1081
Publication Date: 2011/04/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.1067
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
datapath synthesis,  delay variation,  register assignment,  hold timing constraint,  backward-data-direction clocking,  integer linear programming,  

Full Text: PDF>>
Buy this Article

For recent and future nanometer-technology VLSIs, static and dynamic delay variations become a serious problem. In many cases, the hold timing constraint, as well as the setup timing constraint, becomes critical for latching a correct signal under delay variations. While the timing violation due to the fail of the setup timing constraint can be fixed by tuning a clock frequency or using a delayed latch, the timing violation due to the fail of the hold timing constraint cannot be fixed by those methods in general. Our approach to delay variations (in particular, the hold timing constraint) proposed in this paper is a novel register assignment strategy in high-level synthesis, which guarantees safe clocking by Backward-Data-Direction (BDD) clocking. One of the drawbacks of the proposed register assignment is the increase in the number of required registers. After the formulation of this new register minimization problem, we prove NP-hardness of the problem, and then derive an integer linear programming formulation for the problem. The proposed method receives a scheduled data flow graph, and generates a datapath having (1) robustness against delay variations, which is ensured by BDD-based register assignment, and (2) the minimum possible number of registers. Experimental results show the effectiveness of the proposed method for some benchmark circuits.