Name
Abstract | ||
|---|---|---|
In the most general form, clock skew scheduling (CSS) generates a dedicated clock delay for each individual sequential component in the clock distribution network in order to minimize the clock period. Multidomain CSS (MDCSS) relieves this requirement. Instead, sequential components are grouped into several clusters (called clock domains), each of which has a uniform clock delay for all registers within that domain. The skew values of clock domains are provided by a set of deskew buffers with electrically programmable phase shifts and injected after the chip is manufactured. This technique is attractive since, due to process variations, it is becoming overwhelmingly difficult to create precise clock network delays for all sequential elements in a design globally. In this paper, we present a fast algorithm for determining the minimum number of clock domains to be used by MDCSS. The exact solution to this problem cannot be found within a reasonable time if the number of clock domains increases beyond three domains. We show that, even with a small-size circuit, in order to obtain the minimum clock period, more than three clock domains may be required. Therefore, a fast heuristic algorithm is needed to identify these domains. To the best of our knowledge, we present the first efficient heuristic algorithm for this problem. For large benchmark circuits, we solve the problem within 14.7 min on average (as high as 31.7 min for the worst case), while a commercial mixed-integer linear program solver cannot finish in over 5 h. Furthermore, our results show that, for 19 out of 21 small- and medium-size benchmarks, our algorithm yields the optimal solution. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/TVLSI.2009.2014069 | IEEE Transactions on Very Large Scale Integration (VLSI) Systems |
Keywords | Field | DocType |
sequential circuits,scheduling,dedicated clock delay,clock distribution network,time 31.7 min,clock period,clock skew scheduling (css),sequential elements,multidomain clock skew scheduling,clock skew domain,fast heuristic algorithm,minimum clock period,clock skew scheduling,delays,clocks,clock domains increase,clock domain,time 14.7 min,uniform clock delay,algorithm yield,precise clock network delay,sequential circuit optimization,time 5 h,clock delay,mixed-integer linear program solver,cascading style sheets,scheduling algorithm,exact solution,chip,phase shift,clustering algorithms,circuits,heuristic algorithm,manufacturing,network delay,process variation,clock skew,job shop scheduling,registers | Vector clock,Clock gating,Clock network,Clock drift,Computer science,Clock domain crossing,Algorithm,Real-time computing,Electronic engineering,Clock skew,Digital clock manager,Clock angle problem | Journal |
Volume | Issue | ISSN |
18 | 4 | 1063-8210 |
Citations | PageRank | References |
5 | 0.48 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Ni | 1 | 69 | 4.46 |
| Seda Öǧrenci Memik | 2 | 488 | 42.57 |