Optimal Register Assignment with Minimum-Path Delay Compensation for Variation-Aware Datapaths

Keisuke INOUE  Mineo KANEKO  Tsuyoshi IWAGAKI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.4   pp.1096-1105
Publication Date: 2009/04/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.1096
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Advanced Technologies Emerging Mainly from the 21st Workshop on Circuits and Systems in Karuizawa)
datapath synthesis,  delay variation,  register assignment,  setup and hold constraints,  minimum delay compensation,  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 constraint, as well as the setup constraint, becomes critical for latching a correct signal under delay variations. This paper treats the hold constraint in a datapath circuit, and discusses a register assignment in high level synthesis considering delay variations. Our approach to ensure the hold constraint under delay variations is to enlarge the minimum-path delay between registers, which is called minimum-path delay compensation (MDC) in this paper. MDC can be done by inserting delay elements mainly in non-critical paths of a functional unit (FU). One of our contributions is to show that the minimization of the number of minimum-path delay compensated FUs is NP-hard in general, and it is in the class P if the number of FUs is a constant. A polynomial time algorithm for the latter is also shown in this paper. In addition, an integer linear programming (ILP) formulation is also presented. The proposed method generates a datapath having (1) robustness against delay variations, which is ensured partly by MDC technique and partly by SRV-based register assignment, and (2) the minimum possible numbers of MDCs and registers.