DocumentCode :
1349539
Title :
On the complexity of designing optimal branch-and-combine clock networks
Author :
El-Amawy, Ahmed ; Kulasinghe, Priyalal
Author_Institution :
Dept. of Electr. & Comput. Eng., Louisiana State Univ., Baton Rouge, LA, USA
Volume :
47
Issue :
2
fYear :
1998
fDate :
2/1/1998 12:00:00 AM
Firstpage :
264
Lastpage :
269
Abstract :
Recently, an unconventional clock distribution scheme, called Branch-and-Combine (BaC) was proposed. The scheme is the first to guarantee constant skew upper bound irrespective of the clocked network´s size. In BaC clocking, a set of interconnected nodes perform simple processing on clock signals such that the path from the source to any node is automatically and adaptively selected such that it is the shortest delay path. The graph underlying a BaC network is constrained by the requirement that each pair of adjacent nodes is in a cycle of length ⩽k, where k is the feature cycle length. The graph representing such a network is called a BaC(k) graph. The feature cycle length (k) is an important parameter upon which skew bound and node function depend. We study the complexity of the general problem of designing a minimum cost BaC network for clocking a data processing network of arbitrary topology so that a certain feature cycle length is satisfied. We define two versions of the problem, differing in the way we are allowed to place edges in the graph representing the BaC network. We show that, in both cases, the general optimization problem is NP hard. We also provide efficient heuristic algorithms for both versions of the optimization problem. When k=2, the two versions of the optimization problem become the same and can be solved in polynomial time. For k=3, the complexity is still unknown
Keywords :
circuit CAD; circuit optimisation; clocks; computational complexity; directed graphs; heuristic programming; BaC network; NP hard; adjacent nodes; arbitrary topology; clock signals; complexity; constant skew upper bound; data processing network; feature cycle length; general optimization problem; heuristic algorithms; interconnected nodes; minimum cost BaC network; node function; optimal branch-and-combine clock network design; polynomial time; shortest delay path; skew bound; unconventional clock distribution scheme; Clocks; Costs; Data processing; Delay; Heuristic algorithms; Network topology; Polynomials; Signal processing; Timing; Upper bound;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.664212
Filename :
664212
Link To Document :
بازگشت