A. Elamawy et P. Kulasinghe, ON THE COMPLEXITY OF DESIGNING OPTIMAL BRANCH-AND-COMBINE CLOCK NETWORKS, I.E.E.E. transactions on computers, 47(2), 1998, pp. 264-269
Recently, an unconventional clock distribution scheme, called Branch-a
nd-Combine (BaC), has been proposed. The scheme is the first to guaran
tee constant skew upper bound irrespective of the clocked network's si
ze. in BaC clocking, a set of interconnected nodes perform simple proc
essing 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 l
ess than or equal to k, where k is the feature cycle length. The graph
representing such a network is called a BaC(k) graph. The feature cyc
le length (k) is an important parameter upon which skew bound and node
function depend. In this paper, we study the complexity of the genera
l problem of designing a minimum cost BaC network for clocking a data
processing network of arbitrary topology such that a certain feature c
ycle length is satisfied. We define two versions of the problem, diffe
ring in the way we are allowed to place edges in the graph representin
g the BaC network. We show that, in both cases, the general optimizati
on problem is NP-hard. We also provide efficient heuristic algorithms
for both versions of the optimization problem. When k = 2, the two ver
sions of the optimization problem become the same and can he solved in
polynomial time. For k = 3, the complexity is still unknown.