This paper introduces a new nonblocking self-routing network, called a multi-root binary tree, which may be used to interconnect the cores in multicore chips. The multi-root binary tree network differs from other binary tree-based networks in that the cores are placed at the roots rather than the leaves or the interior nodes of the trees. The self-routing property of a multi-root binary tree is built on the concept of replication and clustering. A new replication and clustering method, called the triangular shift pairing is given to connect the cores together over dedicated paths. It is shown that connecting cores in clusters requires at least n=2 columns of pairings for an n-core network in a grid layout model and triangular shift wiring method matches this lower bound. The replication and clustering concept leads to a simple self-routing scheme that pairs cores by decoding both unicast and multicast connection requests using lg n-bit cluster address bits. In particular, it is established that cores can identify the cluster with which they pair with other cores using simple modulo addition of their own ids and addresses of the targeted cores in 2lg n single bit-decoding steps. It is also shown that, if connection requests are uniformly distributed among the cores then blocking due to target conflicts can be avoided if cores serve connection requests at a small multiple of the frequencies with which they receive them.

Quantum switching networks are derived from conventional switching networks by replacing the classical switches by quantum switches. We give the quantum circuit design and routing of an n \times m network, called a quantum concentrator that can direct quantum bit packets in arbitrary quantum states from any of its k inputs to some of its k outputs, where 1 \le k \le m \le n. Our designs are based on sparse crossbars which are rectangular grids of 2 \times 2 crosspoints. Sparse crossbar concentrator structures with theoretically minimum crosspoint complexities for any values of n and m are well known but no self-routing algorithms have been reported for such concentrators. We transform two such families of optimal concentrators, called fat-slim and banded sparse crossbars into quantum networks and provide self-routing algorithms for these families of concentrators. In this process, we extend the notion of packet concentration to a quantum network and design self-routing quantum crosspoints from quantum gates. We address issues critical to quantum operation like reversibility and localized self-routing and give a rigorous proof that quantum fat-slim and banded sparse crossbar concentrators are self-routable. The self-routing algorithms described in the paper can be used for both quantum and classical sparse crossbar concentrators by the linearity property of all quantum systems.

In many assignment problems, a set of documents such as research proposals, promotion dossiers, resumes of job applicants is assigned to a set of experts for ordinal evaluation, ranking, and classification. A desirable condition for such assignments is that every pair of documents is compared and ordered by one or more experts. This condition was modeled as an optimization problem and the number of pairs of documents was maximized for a given incidence relation between a set of documents and a set of experts using a set covering integer programming method in the literature[5]. In this paper, we use a combinatorial approach to derive lower bounds on the number of experts needed to compare all pairs of documents and describe assignments that asymptotically match these bounds. These results are not only theoretically interesting but also have practical implications in obtaining optimal assignments without using complex optimization techniques.

A frequently encountered problem in peer review systems is to facilitate pairwise comparisons of a given set of documents by as few experts as possible. In [7], it was shown that, if each expert is assigned to review k documents then ⌈n(n−1)/k(k−1)⌉ experts are necessary and ⌈n(2n−k)/k2⌉ experts are sufficient to cover all n(n−1)/2 pairs of n documents. In this paper, we show that, if √n ≤ k ≤ n/2 then the upper bound can be improved using a new assignnment method based on a particular family of balanced incomplete block designs. Specifically, the new method uses ⌈n(n+k)/k2⌉ experts where n/k is a prime power, n divides k2, and √n ≤ k ≤ n/2. When k = √n, this new method uses the minimum number of experts possible and for all other values of k, where √n ≤ k ≤ n/2, the new upper bound is tighter than the general upper bound given in [7].

In this paper, we present a quantum multicasting network, called a generalized quantum connector (n-GQC), which can be used to multicast quantum information from n inputs to n outputs. This network is recursively constructed using n/2-GQCs and consists of O(n log2n) quantum gates. The key component of the n-GQC is another network, called an n-quantum concentrator (n-QC). This concentrator is also an n × n quantum network, and can route arbitrary quantum states on any m of its inputs to its top m outputs, for any m, 1 ¿ m ¿ n. Its quantum gate complexity is O(n log n). The quantum gate-level depths of n-QC and n-GQC are O(log2n) and O(log3n), respectively. Both n-QC and n-GQC are based on the classical self-routing concentrators and generalized connection networks given by Lee and Oruc [1]. While these networks work for multicasting classical packets, they cannot be used to multicast quantum packets as they employ balancer switches with both forward and backward propagation of packets. We introduce a quantum balancer switch that works using a forward propagation of packets only, thereby facilitating the n-QC and n-GQC designs presented in the paper.

A bipartite concentrator is a single stage sparse crossbar switching device that can connect any m of its n/spl ges/m inputs to its m outputs, possibly without the ability to distinguish their order. Fat-and-slim crossbars were introduced recently to show that bipartite concentrators can be constructed with a minimum number of crosspoints for any number of inputs and outputs. We generalize these graphs to obtain bipartite concentrators with nearly a fixed fanout without altering their (n-m+1)m crosspoint complexity. We also present an O(log n)-time algorithm to route arbitrary concentration assignments on this new family of fat-and-slim crossbars.

This paper introduces a new concept by which it is possible to design and implement arithmetic processors using permutation networks. To demonstrate this concept, several optoelectronic arithmetic units combining optical directional coupler switches and cyclic permutation networks are designed. The designs show that addition, subtraction, and multiplication can all be performed in O(log n) time in residue code domain and using O(n/sup 2/) directional coupler switches and gates, where n=log M, and M is the integer range of interest. These arithmetic units also have the capability of concurrent error detection and fault-tolerance, and they can be used to construct constant time inner product processors.

A sparse crossbar (n,m,c)-concentrator is a bipartite graph with n inputs and m outputs in which any c or fewer inputs can be matched with an equal number of outputs, where c is called its capacity. We present a number of new results on the crosspoint complexity of such concentrators. First, we describe a sparse crossbar (n, m, m)-concentrator whose crosspoint complexity matches Nakamura-Masson's (1982, 1977) lower bound for any given n and m. Second, we present a sparse crossbar (2m, m, m)-concentrator with crosspoint complexity also matching Nakamura-Masson's lower bound, and with fixed fan-in and nearly fixed fan-out. Third, we derive an easily computable lower bound on the crosspoint complexity of sparse crossbar (n, m, c)-concentrators. Finally, we show that this bound is attainable within a factor of two when n-m/spl les/c/spl les/[m/c].

This paper presents a new generalized connector with a very simple self-routing scheme. Unlike some of the recently reported generalized connectors, this generalized connector does not rely on an explicit use of a copy network; rather it replicates packets as it routes them through its stages to their destinations. In addition to its attractive routing scheme, this generalized connector can be constructed with O(n lg/sup 2/ n) bit-level constant fanin logic gates, O(lg/sup 2/ n) bit-level depth, and can realize any multicast assignment in O(lg/sup 3/ n) bit-level time.>

This paper presents a new parallel algorithm for routing unicast (one-to-one) assignments in Benes networks. Parallel routing algorithms for such networks were reported earlier, but these algorithms were designed primarily to route permutation assignments. The routing algorithm presented in this paper removes this restriction without an increase in the order of routing cost or routing time. We realize this new routing algorithm on two different topologies. The algorithm routes a unicast assignment involving O(k) pairs of inputs and outputs in O(lg/sup 2/ k+lg n) time on a completely connected network of n processors and in O(lg/sup 4/ k+lg/sup 2/ k lg n) time on an extended shuffle-exchange network of n processors. Using O(n lg n) professors, the same algorithm can be pipelined to route /spl alpha/ unicast assignments each involving O(k) pairs of inputs and outputs, in O(lg/sup 2/ k+lg n+(/spl alpha/-1) lg k) time on a completely connected network and in O(lg/sup 4/ k+lg/sup 2/ k lg n+(/spl alpha/-1)(lg/sup 3/ k+lg k lg n)) time on the extended shuffle-exchange network. These yield an average routing time of O(lg k) in the first case, and O(lg/sup 3/ k+1g k lg n) in the second case, for all /spl alpha/spl ges/lg n. These complexities indicate that the algorithm given in this paper is as fast as Nassimi and Sahni's algorithm for unicast assignments, and with pipelining, it is faster than the same algorithm at least by a factor of O(lg n) on both topologies. Furthermore, for sparse assignments, i.e., when k=O(1), it is the first algorithm which has an average routing time of O(1g n) on a topology with O(n) links.>

The performance of a multiprocessor system depends heavily on its ability to provide conflict free paths among its processors. In this paper, we explore the possibility of using a nonblocking network with O(N log N) edges (crosspoints) to interconnect the processors of an N processor system, We combine Bassalygo and Pinsker's implicit design of strictly nonblocking networks with an explicit construction of expanders to obtain a strictly nonblocking network with -765.18N+352.8N log N edges and 2+log(N/5) depth. We present an efficient parallel algorithm for routing connection requests on this network and implement it on three parallel processor topologies. The implementation on a parallel processor whose processing elements are interconnected as in the Bassalygo-Pinsker network requires O(N log N) processing elements, O(N log N) interprocessor links and it takes O(log N) steps to route any single connection request where each step involves a small number (/spl ap/72) of bit-level operations. A contracted or folded version of the same implementation reduces the processing element count to O(N) without increasing the link count or the routing time. Finally, we establish that the same algorithm takes O(log/sup 3/ N) steps on a perfect shuffle processor with O(N) processing elements. These results improve the crosspoint, depth and routing time complexities of the previously reported strictly nonblocking networks.>

Strictly nonblocking networks may hold the key for high performance multiprocessor systems. While a number of strictly nonblocking networks have been reported in the literature, their use in multiprocessors is hampered by a lack of efficient distributed routing at algorithms to set paths in these networks. As a step in this direction, the paper presents two distributed routing algorithms for D.G. Cantor's (1971) strictly nonblocking network. For N inputs, the first routing algorithm takes O(t)+O(logt log N) steps/sup 1/ to routing t requests in parallel. While this algorithm performs quite well for i=O(log/sup 2/ N), for larger valves of t, we present a randomized version of the same algorithm with an expected time complexity of O(log/sup 2/ N) for any number of requests. These results, when combined with the crosspoints and depth complexities of a Cantor network, give a strictly nonblocking network with O(N log/sup 2/ N) crosspoints, O(logN) depth and O(log/sup 2/N) routing time.

Abstract Rearrangeable Clos networks have been studied in the literature in connection with telephone switching and communication networks. This paper examines the applicability of matching and edge‐coloring in bipartite graphs to the rearrangement problem in these networks. A survey of various matching and edge‐coloring algorithms is given, and these algorithms are evaluated for their suitability and effectiveness. It is shown that no single matching or edge‐coloring algorithm reported in the literature performs well over all Clos networks. It is further shown that the time complexity of the looping algorithm for Beneš networks is at least as good as any routing algorithm that can be obtained from matching or edge‐coloring. © 1994 by John Wiley & Sons, Inc.

Inner product and matrix operations find extensive use in algebraic computations. In this brief contribution, we introduce a new parallel computation model, called a permutation network processor, to carry out these computations efficiently. Unlike the traditional parallel computer architectures, computations on this model are carried out by composing permutations on permutation networks. We show that the sum of N algebraic numbers on this model can be computed in O(1) time using N processors. We further show that the inner product and matrix multiplication can both be computed on this model in O(1) time at the cost of O(N) and O(N/sup 3/), respectively, for N element vectors, and N/spl times/N matrices. These results compare well with the time and cost complexities of other high level parallel computer models such as PRAM and CRCW PRAM.>

Concentrators are used to interface and combine together low speed communication channels onto higher speed transmission links to alleviate transmission costs. They are also used to construct more powerful switching fabrics such as permutation and broadcast networks. Using an adaptive binary sorting network model, this paper constructs new concentrators and superconcentrators. Unlike the previously reported concentrators and superconcentrators, these new constructions are fast, and ran easily be implemented using simple switching devices. More specifically, for n inputs, they can be constructed with O(n lg lg n) constant fanin bit-level multiplexers and demultiplexers, and can be routed in O(lg/sup 2/ n) bit-level time.>

A lower bound on the amount of information necessary to compute the switch settings for a three-stage Clos network is derived. The bound is derived by considering the effect of a family of permutations, called balanced multiloops, on the settings of the switches of a Clos network. By carefully selecting these permutations, it is proven that there exists at least one switch in each stage whose setting depends upon at least (k/spl minus/3)(m/2+1)/2 assignments in the permutations to be routed for k/spl ges/4 where m is the number of center-stage switches and k is the number of input and output-stage switches. It is also proven that the setting of the input stage depends on at least m/spl minus/1 assignments. Lower bounds on the routing time of a three-stage Clos network on a variety of machine models follow immediately from these results. In particular, any constant fan-in implementation of any routing algorithm for such a network should have a time lower bound of /spl Omega/(log mk).>

Many routing problems in parallel processing, such as concentration and permutation problems, can be cast as sorting problems. In this paper, we consider the problem of sorting on a new model, called an adaptive sorting network. We show that any sequence of n bits can be sorted on this model in O(lg/sup 2/ n) bit-level delay using O(n) constant fanin gates. This improves the cost complexity of K.E. Batcher's binary sorters (1968) by a factor of O(lg/sup 2/ n) while matching their sorting time. The only other network that can sort binary sequences in O(n) cost is the network version of columnsort algorithm, but this requires excessive pipelining. In addition, using binary sorters, we construct permutation networks with O(n lg n) bit-level cost and O(lg/sup 3/ n) bit-level delay. These results provide the asymptotically least-cost practical concentrators and permutation networks to date. We note, of course, that the well-known AKS sorting network has O(lg n) sorting time and O(n lg n) cost, but the constants hidden in these complexities are so large that our complexities outperform those of the AKS sorting network until n becomes extremely large.>

Conventional fault-tolerant modulo arithmetic processors rely on the properties of a residue number system with L redundant moduli to detect up to L/2 errors. In this paper, we propose a new scheme that combines r-out-of-s residue codes with Berger codes to concurrently detect any number of module errors without any redundant moduli. In addition, this scheme can tolerate L faults if L redundant moduli are used, and has the property of graceful degradation when the number of faulty moduli exceeds L. Finally, it is shown that the added cost for fault tolerance is much less than those were reported earlier in the literature.>

This paper presents new results on routing unicast (one-to-one) assignments over Benes networks. Parallel routing algorithms with polylogarithmic routing times have been reported earlier [10,8], but these algorithms can only route permutation assignments unless unused inputs are assigned to dummy outputs. This restriction is removed in this paper by using techniques taht permit bypassing idle or unused inputs without any increase in the order of routing cost or routing time.

A self-routing permutation network with O((n lg n)) switches and O(lg/sup 2/n) routing time, where lg denotes log/sub 2/, is presented. More generally, a permutation network with O(kn/sup 1+1/k/) cost and O(k lg n) routing time for any k, 1>

A number of matrix decomposition schemes have been previously reported for routing on Clos switching networks. These schemes occasionally fail to find the right decomposition, unless backtracking is used. It is shown that a partition may occur during the decomposition process, and that this is the underlying reason these algorithms fail for some decompositions. A parallel algorithm which can recognize when a partition exists and set up the Clos network without backtracking is given.>

A self-routing connection network is a switching device where the routing of each switch can be determined in terms of the destination addresses of its inputs alone, i.e. independent of the routing information regarding the other switches in the network. One family of connection networks that were considered in the literature for self-routing are Clos networks. Earlier studies indicate that some Clos networks can be self-routed for certain permutations. In this paper, it is proved that the only category of Clos networks that can be self-routed for all permutations are those with at most two switches in their outer stages.>

Optimal setup procedures for cube-connected networks are described. The setup patterns include paths, transpositions, cycles, and one-pass permutations. It is shown that for an N-input cube-connected network, the procedure for paths requires O(log/sub 2/ N) steps and O(N) space, the procedure for transportations and cycles requires O(N) steps and O(N) space, and the procedure for permutations takes O(N log/sub 2/ N) steps and O(N) space. It is also shown that the time complexities of the setup procedures for transpositions, cycles, and permutations can be improved as O(log/sub 2/ N) by using O(N) processors.>

A parametrized design technique is presented of cellular permutation arrays based on coset decompositions of symmetric groups. A type of permutation cell referred to as a coset generator is introduced to customize the propagation delay, fan-in, fan-out, and number of edges in the target network. To aid in the design process, a cost function is derived expressing the number of edges in terms of the number of inputs and the sizes of cells. The results provide a spectrum of networks which vary with the size of the coset generator used and range from a simple bipartite graph to several cellular permutation arrays reported in the literature.>

A variant of the mapping problem, namely, systolic contractions of program graphs, is considered. The notion of time links is introduced to mechanize the contraction process; the timing of information flow between processors is modeled in terms of fundamental loop and path equations of delays and is optimized using linear programming. While the results apply primarily to systolic contractions, they can be extended to other types of graph contractions by relaxing the time constraints imposed by delay equations. Such contractions can, in principle, lead to faster execution of program graphics, since they may do away with the delays imposed on the links between the processors by systolic contractions. Clearly, storage is traded for time since extra storage may be necessary to hold some operands temporarily until a processor acquires all of its operands for a computation.>

A fundamental problem in interconnection network theory is to design permutation networks with as few cells as possible and a small programming or setup time. The well-known networks of Benes and Waksman have asymptotically optimal cell counts, but the best setup algorithm available for such networks with n inputs requires O(n log2 n) sequential time. As an alternative, this paper considers another class of permutation networks which are collectively referred to as cellular permutation arrays. Using a group theoretic formulation, a natural correspondence is established between such permutation networks and iterative decompositions of symmetric groups through cosets. Based on this correspondence, the setup problem is reduced to iteratively determining the leaders of the cosets to which the permutation to be realized belongs. This, in turn, leads to linear-time setup algorithms for cellular permutation arrays. The paper describes these algorithms in detail for two families of cellular permutation arrays reported in the literature.

The problem of constructing equivalence maps between two multistage permutation networks is considered. A branch-and-bound algorithm is given to test whether two such networks are equivalent in polynomial time. Whenever they are, the algorithm also determines a map that conjugates one network onto the other.

The correspondence examines the functional relations within a class of multistage interconnection networks. It is known that these networks are not rearrangeable. This fact has led to some research on interconnection network relations. The correspondence deals with one aspect of this research, namely, that of constructing an equivalence map between two interconnection networks. Procedures are given to test whether two such networks are equivalent. Whenever they are, these procedures also produce a map to conjugate one network onto the other.

The correspondence presents three classes of cube-connected networks with individual stage control based on a group theoretic modeling of interconnection networks. It is shown that these classes of networks retain nonisomorphic groups of permutations. Although the permutations realizable by such networks are rather limited in number, the simplicity of their control scheme makes them attractive. Moreover, the interconnection power of these networks can be enhanced by simulating the networks which belong to one class by any member of that class.

The paper describes an algebraic model which provides a means for realizing an arbitrary permutation through various cellular-array-type networks. The model views a cellular array as an ordered set of transposition maps where each transposition corresponds to a permutation cell of the array. A permutation realizable by such an array is then expressed as a composition of the transpositions where the rules for the composition are determined by the topology of the array.