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

Keisuke INOUE  Mineo KANEKO  Tsuyoshi IWAGAKI 

Publication
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
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)
Category: 
Keyword: 
datapath synthesis,  delay variation,  register assignment,  setup and hold constraints,  minimum delay compensation,  integer linear programming, 

Full Text: PDF(343.8KB)

Summary: 
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.