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.

This paper addresses the problem of mapping a feedforward ANN onto a multiple bus system, MBS, with p processors and b buses so as to minimize the total execution time. We present an algorithm which assigns the nodes of a given computational layer (c-layer) to processors such that the computation lower bound [N/sup l//p]t/sub p//sup l/ and the communication lower bound [N/sup l//b]t/sub c/ are achieved simultaneously, where N/sup l/ is the number of nodes in the mapped c-layer l and t/sub p//sup l/ and t/sub c/ are the computation and communication times, respectively, associated with a node in the layer. When computation and communication are not overlapped, we show that the optimal number of processors needed is either 1 or p, depending on the ratio t/sub p//sup l//t/sub c/. When computation and communication are overlapped, we show that the optimal number of processors needed is either 1 or ([t/sub p//sup l//t/sub c/])b. We show that there is a unique arrangement of interfaces such that the total number of interfaces is minimum and the optimal time is reached. Finally, we compare the relative merits of the MBS simulating ANNs over the recently introduced checkerboarding scheme.

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.

We describe a new technique for achieving maximum performance in pipelines which allows task initiations to follow any arbitrary cycle provided that the average time between initiations is /spl les/M, where M is the maximum number of reservations of any stage. This is not possible with the existing methods. The idea behind the proposed scheme is to allow different initiations to follow different reservation tables. This contrasts existing methods which require all initiations in a cycle to follow the same reservation table. We describe an algorithm for systematic construction of the reservation tables for different initiations in any cycle whose performance does not exceed the theoretical upper bound on throughput. We formally prove that the algorithm is correct and that it will always succeed in constructing the tables.>

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.>

In a recent development a new clock distribution scheme has been introduced. The scheme called Branch-and-Combine or BaC, is the first to guarantee constant skew bound regardless of network size. In this paper we generalize and extend the work on BaC networks. Our study takes the approach of defining a general graph theoretic model which is then utilized to define a general network model taking into account node function. We use the models to establish some interesting results on clocking paths, node input sequences, node inputs' relative timings, and skew bound. We prove that a network adhering to our general model is stable (will not oscillate) despite its cyclic nature. We also prove that no tree of any kind can be used to distribute the clock in two or more dimensions such that skew bound is constant. The paper then exploits the derived properties to describe the inherent interplay between topology, timing, node function, and skew bound.>

Branch-and-Combine (BaC) clock distribution has recently been introduced. The most interesting aspect of the new scheme is its ability to bound skew by a constant irrespective of network size. In this paper, we introduce algorithms for systematic synthesis of BaC networks for clocking meshes, tori, and hypercubes of different dimensionalities. For meshes our approach relies on filing techniques. We start with the identification of basic proper tiles satisfying certain criteria. We define a set of valid transformations on tiles. By appropriately applying a sequence of transformations on a basic proper tile, one could synthesize a valid BaC network. We formally introduce methods and procedures for applying the above steps to systematically construct different valid BaC network designs for 2D and 3D meshes. To construct BaC networks for clocking hypercubes of any dimensionality we describe a formal methodology. In this case, we utilize an approach called replication which is based on constructing larger hypercube clocking networks from smaller ones. We combine the techniques for 2D, 3D meshes with replication techniques to formulate a methodology applicable to meshes and tori of dimensionality greater than three. We provide proofs of correctness for the algorithms we introduce. Besides, we formally define an optimality criterion based on link costs which is utilized to check the optimality of the synthesized network designs. In the case of meshes, we show that the majority of synthesized networks are optimal with respect to our defined criterion. For those suboptimal networks, we describe a procedure for identifying and removing unnecessary (redundant) links. The procedure is guaranteed to optimize the network without changing its behavioral parameters.

In a recent development a new clock distribution scheme, called Branch-and-Combine or BaC, has been introduced. The scheme is the first to guarantee constant skew bound regardless of network size. In this paper we generalize and extend the work on BaC networks. We establish some interesting results on clocking paths, node input sequences, node inputs' relative timing, network stability, and skew bound. Furthermore, this study establishes an upper bound on maximum clocking rates for BaC networks which is about double that predicted by earlier studies.

The effects of redundancy and masking on the reliability of synchronizer circuits in the presence of metastability are considered. It is shown that in the jitter model developed by L. Kleeman (1990), in which circuit noise effects are considered, redundancy improves the probability of metastable failure of synchronizers, contrary to Kleeman's claim. A stochastic model that relates the noise model to the absorbing barrier problem for such noise effects is presented. It is demonstrated analytically that under considerably general conditions on the (masking) (Bcombinational circuit, clock delay, voter delay, and aperture alignment and width, the probability of metastable failure of the redundant synchronizer tends to zero with L, the number of component synchronizers. If the component synchronizers are identical, this probability of metastable failure decreases monotonically with L. Furthermore, the best combinational circuits to use in the general redundant synchronizer are the L-input AND and OR functions. Conditions are derived under which the majority voter function may or may not be effective in a general redundant synchronizer.>

A scheme for global synchronization of arbitrarily large computing structures such that clock skew between any two communicating cells is bounded above by a constant is described. The scheme utilizes clock nodes that perform simple processing on clock signals to maintain a constant skew bound irrespective of the size of the computing structure. Among the salient features of the scheme is the interdependence between network topology, skew upper bound, and maximum clocking rate achievable. A 2-D mesh framework is used to present the concepts, introduce three network designs, and to prove some basic results. For each network the (constant) upper bound on clock skew between any two communicating processors, is established, and its independence of network size is shown. Simulations were carried out to verify correctness and to check the workability of the scheme. A 4*4 network was built and successfully tested for stability. Such issues as node design, clocking of nonplanar structures such as hypercubes, and the concept of fuse programmed clock networks are addressed.>

A new hypercube-type structure, the folded hypercube (FHC), which is basically a standard hypercube with some extra links established between its nodes, is proposed and analyzed. The hardware overhead is almost 1/n, n being the dimensionality of the hypercube, which is negligible for large n. For this new design, optimal routing algorithms are developed and proven to be remarkably more efficient than those of the conventional n-cube. For one-to-one communication, each node can reach any other node in the network in at most (n/2) hops (each hop corresponds to the traversal of a single link), as opposed to n hops in the standard hypercube. One-to-all communication (broadcasting) can also be performed in only (n/2) steps, yielding a 50% improvement in broadcasting time over that of the standard hypercube. All routing algorithms are simple and easy to implement. Correctness proofs for the algorithms are given. For the proposed architecture, communication parameters such as average distance, message traffic density, and communication time delay are derived. In addition, some fault tolerance capabilities of this architecture are quantified and compared to those of the standard cube. It is shown that this structure offers substantial improvement over existing hypercube-type networks in terms of the above-mentioned network parameters.>

An array that inverts an n*n dense matrix in 5n-1 time units, including I/O time, is presented. The inversion algorithm consists of three phases and assumes that Gaussian elimination without pivoting can be applied. The array, which consists of 2n/sup 2/-n simple processing elements, implements and overlaps the execution of all three phases without any need for intermediate I/O or reconfiguration. An efficient data-steering technique which is well suited for feedback recurrences is utilized.>

It is claimed in the above-mentioned work (ibid., vol.C-35, p.643-6, July 1986) that redundancy and masking techniques are ineffective in improving synchronizer performance due to metastable behavior. This claim is based on an input model that is not always valid, particularly in reliability analysis. The commenter points out the weakness in the assumed model and provides an alternative input model which can be used to analyze redundant synchronizer reliability. Based on the proposed alternative model it is shown that, under certain conditions, redundancy and masking can indeed improve synchronizer reliability. The authors reply that their original paper was the first to examine the question and naturally adopts the simplest modeling approach based on a deterministic model. They note that the differences in conclusion derive from the modeling assumptions for metastability, and asset that these need to be examined further by researchers. Some initial comments are given.>