2-SAT Based Linear Time Optimum Two-Domain Clock Skew Scheduling in General-Synchronous Framework

Yukihide KOHIRA  Atsushi TAKAHASHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.12   pp.2459-2466
Publication Date: 2014/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.2459
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Logic Synthesis, Test and Verification
Keyword: 
general-synchronous framework,  multi-domain clock skew scheduling,  two-domain clock skew scheduling,  2-SAT,  

Full Text: PDF>>
Buy this Article




Summary: 
Multi-domain clock skew scheduling in general-synchronous framework is an effective technique to improve the performance of sequential circuits by using practical clock distribution network. Although the upper bound of performance of a circuit increases as the number of clock domains increases in multi-domain clock skew scheduling, the improvement of the performance becomes smaller while the cost of clock distribution network increases much. In this paper, a linear time algorithm that finds an optimum two-domain clock skew schedule in general-synchronous framework is proposed. Experimental results on ISCAS89 benchmark circuits and artificial data show that optimum circuits are efficiently obtained by our method in short time.