Name
Abstract | ||
|---|---|---|
Clock skew scheduling is a useful sequential circuit optimization method. The run time efficiency of this problem becomes crucial if it must be repeated iteratively in a higher level optimization. The widely recognized Burns' algorithm proposed to solve this problem suffers from high runtime complexity, which makes it unsuitable to be deployed in iterative optimization loops. This algorithm is based on the general concept of primal-dual optimization. In this paper, we demonstrate that a more efficient approach to the clock skew scheduling problem can be developed by designing a new algorithm using the same primal-dual optimization concept. The basic idea of the algorithm is to avoid creating new admissible graph and recalculating ¿ values for each iteration of the primal-dual optimization. The asymptotic runtime efficiency of our algorithm is of O(|V||E| + |V|2log|V|), which is improved from O(|V|2|E|) thanks to the heap data structure used in our proposed algorithm. The experimental results show that our algorithm is on average 95 times faster than Burns' implementation. In best case, we can observe as much as 189 times speedup. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/ISQED.2010.5450492 | ISQED |
Keywords | Field | DocType |
primal-dual optimization concept,sequential circuits,optimization,clock skew scheduling,asymptotic runtime efficiency,circuit optimisation,heap data structure,sequential circuit,iterative optimization loops,primal-dual,primal-dual based clock skew scheduling algorithm,burns algorithm,circuit optimization method,high runtime complexity,iterative methods,data structure,registers,scheduling,clock skew,scheduling algorithm,scheduling problem,data structures,algorithm design and analysis,design optimization | Mathematical optimization,Algorithm design,Sequential logic,Scheduling (computing),Iterative method,Computer science,Meta-optimization,Algorithm,Real-time computing,Heap (data structure),Population-based incremental learning,Speedup | Conference |
ISSN | ISBN | Citations |
1948-3287 | 978-1-4244-6454-8 | 2 |
PageRank | References | Authors |
0.41 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Ni | 1 | 69 | 4.46 |
| Seda Öǧrenci Memik | 2 | 488 | 42.57 |