Awards

The Best Paper Award

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

Keisuke Inoue　・　Mineo Kaneko　・　Tsuyoshi Iwagaki

（英文論文誌A　平成23年4月号掲載）

　The history of VLSI (very large scale integration) is the history of technology scaling down, and the design of VLSI is the continuing challenge of overcoming ``variation.’’ In particular, the delay uncertainty caused by process variations has become increasingly pronounced in the nano-scale era, which will limit the operating speed of future digital VLSI circuits. This paper opens a new view of high-level synthesis to deal with such delay variations, which completely differs from statistical-based analysis and optimization.
　High-level synthesis is a critical design stage which receives an application algorithm to be implemented and determines its datapath structure, i.e., the structure of signal propagation paths between registers, and its cycle-level timing of signal propagations customized for the algorithm. In the authors' previous work ``Novel register sharing in datapaths for structural robustness against delay variation (IEICE Trans. Vol. E91-A, No.4, 2008),’’ they proposed a novel basic concept of variation-aware high-level synthesis. They, then, focused on a certain robustness against variations achieved by invariable structure of signal propagation paths, invariable temporal order of events, etc., and discussed it separately from the timing closure depending on variable process parameters. The former was named ``SRV (structural robustness against delay variation).’’ The paper recommended here discusses a practical and important class of SRV achieved by introducing a kind of order relation on registers, and proposes a design method for it. ``BDD (backward data direction clocking)’’ considered in this paper is such a clocking scheme that a destination register in data propagation always receives the clock signal earlier than a source register in the presence of delay variations. Since the necessity of BDD for an individual operation in an application algorithm depends on a cycle-level operation schedule and binding of data to registers, and also the source-destination register pair for each operation may change depending on register binding, their BDD-aware high-level synthesis proposed in this paper is the simultaneous optimization of register binding and register ordering. Their contributions are threefold: (1) to show SRV property achieved by BDD and its relation to scheduling and binding, (2) to prove that the problem is NP-hard, and (3) to present an ILP (Integer Linear Programming)-based solution for this simultaneous optimization problem.
　In conclusion, this paper provides a completely new and valuable viewpoint to variation-aware VLSI design, and their contributions are greatly appreciated.