Search

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 /spl les/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.

We develop a formal and systematic methodology for designing an optimal multiple bus system (MBS) realizing a set of interconnection functions whose graphical representation (denoted as IFG) is symmetric. The problem of constructing an optimal MBS for a given IFG is NP-hard. In this paper, we show that polynomial time solutions exist when the IFG is vertex symmetric. This is the case of interest for the vast majority of important interconnection function sets. We present a particular partition (which can be found in polynomial time) on the edge set of a vertex symmetric IFG, that produces a symmetric MBS with minimum number of buses as well as minimum number of interfaces. We demonstrate several advantages of such an MBS over a direct-link architecture realizing the same IFG, in terms of the number of ports per processor, number of neighbors per processors, and the diameter.

The recently introduced interconnection network, crossed cube, has attracted much attention in the parallel processing area due to its many attractive features. Like the ordinary hypercube, the n-dimensional crossed cube is a regular graph with 2/sup n/ vertices and n2/sup n-1/ edges. The diameter of the crossed cube is approximately half that of the ordinary hypercube. These advantages of the crossed cube motivated the study of how well it can simulate other networks such as the complete binary tree. We show that the (2/sup n/-1) node complete binary tree can be embedded into the n-dimensional crossed cube with dilation 1. >

This paper addresses the combinatorial problem of constructing a minimal cost, bused, interconnection among a set of modules (or processors). Although some work has been reported on bused interconnection between modules, the compuational complexity of the problem has not been previously addressed. We show that the optimization problem of finding a minimal cost interconnection among modules to realize a certain set of data transfers is NP-Hard. >