## 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|^{2}log|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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010 |

Pages | 755-764 |

Number of pages | 10 |

DOIs | |

State | Published - May 28 2010 |

Event | 11th International Symposium on Quality Electronic Design, ISQED 2010 - San Jose, CA, United States Duration: Mar 22 2010 → Mar 24 2010 |

### Other

Other | 11th International Symposium on Quality Electronic Design, ISQED 2010 |
---|---|

Country | United States |

City | San Jose, CA |

Period | 3/22/10 → 3/24/10 |

## Keywords

- Clock skew scheduling
- Optimization
- Primal-dual
- Sequential circuit

## ASJC Scopus subject areas

- Electrical and Electronic Engineering