In this paper, we analyze ways of realizing permutations in a class of 2log/sub 2/N- or (2log/sub 2/N-1)-stage rearrangeable networks. The analysis is based on the newly developed inside-out routing algorithm and we derive the upper and lower bounds on the number of possible realizations of a permutation. It is shown that the algorithm can provide us with comparable degrees of freedom in realizing a given permutation as the well-known looping algorithm, while it can be more generally applied to a class of 2log/sub 2/N- or (2log/sub 2/N-1)-stage rearrangeable networks. In finding a set of complete assignments for the center-stage cycles, alternate realizations of a permutation can be obtained by changing the initial position, changing the assigning direction, or even interchanging the first-level decompositions of the permutation. We also show that these numerable alternate realizations can be utilized to make the networks tolerate some sets of faults, i.e., control faults of SEs including stuck-at-straight and stuck-at-cross. Various cases of single control faults at the center stages and other stages are examined through examples. These new approaches originate from routing outward from center stages to outer stages; therefore, the center stages and two half networks may be treated separately.

A new multipath multistage interconnection network called the Augmented Composite Banyan Network (ACBN) is proposed. The ACBN is created by adding a link to each SE of the Composite Banyan Network (CBN), which is a multipath network with at least two disjoint paths and was originally proposed in (Seo and Feng, 1995). Therefore, the basic building blocks in the ACBN are 4/spl times/4 SEs with log/sub 2/N stages. The ACBN inherits the favorable features of the CBN such as regularity, symmetry and easy rerouting capability under faults and conflicts. The ACBN also has an efficient and fast control algorithm that can easily generate a primary routing tag and alternative routing tags as in the CBN. A major improvement of the ACBN over the CBN is the higher connectivity with four disjoint paths between any source and destination pair. Moreover the ACBN can generate alternative routing tags in a much simpler way i.e., by a simple binary operation not by the conversion table as in the CBN. To compare the ACBN with other networks in connectivity, we introduce the definition of a degree of connectivity as a new connectivity measure function. The comparison results show that due to high connectivity the ACBN can resolve more random connection requests than other networks by using only a small amount of additional hardware.

A new multipath multistage interconnection network called the composite banyan network is proposed. The network incorporates both the banyan and the reverse banyan networks and is constructed by superimposing the two. The basic building blocks in the composite banyan network are 3/spl times/3 switching elements with log/sub 2/N stages. A major advantage of the composite banyan network over existing networks with 3/spl times/3 SEs is an efficient and fast control algorithm that sets up a path between any source and destination pair. Instead of complex numerical calculations, the network can easily generate a primary routing tag and alternate tags through simple binary operations. Also, the network has a lot of favorable features, including regularity, symmetry, and easy rerouting capability under faults and conflicts. It is shown that at least two totally disjoint paths exist between any source and destination pair, which increase the degree of fault-tolerance. A deterministic permutation routing algorithm is also developed for the 8/spl times/8 composite banyan network, Using a simple tabular method, it is shown that the algorithm always finds a set of conflict-free tags.>

This paper introduces a new tag scheme having a flexibility and a bidirectionality for an N x N k-stage shuffle-exchange network where k > log2N. Based on the interstage correlations for a path, the EB-tag generating rules are presented. In addition, an elegant and simple graphical representation called a N-leaf Dual Complete Binary tree (N-leaf DCB-tree) for a given permutation is proposed and its characteristics are discussed. Then the universal necessary condition for a conflict-free connection pattern is given. Due to this condition, the conflict-free routing problem can be transformed to the perfect assignment problem.

In this paper, we present a generalized version of the routing algorithm[1] for a class of 2log_2 N-stage networks which are made by concatenating two log_2 Nstage blocking networks. We show that the generalized algorithm can also cover a class of(2log_2 N - 1)-stage networks. It is shown that the inside-out algorithm is a more general algorithm which covers a large class of inherently symmetric rearrangeable networks, including the Benes and its equivalent networks. Moreover, it is shown that the time complexity of the algorithm is in O(N), which is superior to that of the looping algorithm. The algorithm is discussed using a graph representation of the network and its connectivity properties are shown by a graph describing rule. To show that the algorithm covers a class of 2log_2 N-stage networks, we introduce the concept of a base-network. These base-networks satisfy some common connectivity properties, and we show that any concatenation of two base-networks can be routed by our new algorithm.

This paper presents a routing algorithm for a class of multistage interconnection networks. Specifically, the concatenation of two Omega networks which has 2 log/sub 2/ N stages is treated. It is shown that this kind of asymmetric Omega+Omega network can be converted into a symmetric Omega/sup -1spl times/Omega network or a symmetric Omega/spl times/Omega/sup -1/ network. However, they have butterfly connections between the two center stages. A general algorithm is developed which routes a class of symmetric networks. The algorithm routes the network from center stages to outer stages at both the input and the output sides simultaneously. The algorithm presented is simpler and more flexible than the well-known looping algorithm in that it can be applied adaptively according to the structure of the network. It can be applied to routing the Omega-based networks regardless of the center-stage connection patterns, i.e., straight, skewed straight, simple butterfly or skewed butterfly as long as the networks are symmetric. The sufficient conditions for proper routing are shown and proved. In addition, an example is shown to demonstrate the algorithm.>

A queueing model for performance evaluation of cluster-based multiprocessors is proposed. Most system components are modeled as M/D/1/L queues to capture deterministic service time and finite buffer behavior. Various subsystems are analyzed independently and then integrated for the system level analysis. Average delay, throughput, and processor utilization are the performance parameters studied in this analysis. The analytical results are first validated via simulation. Next, several design alternatives are discussed using the model. These include the effect of buffer length and identification of bottleneck centers for various design configurations.>

Benes networks are nonblocking rearrangeable networks that can realize arbitrary permutations without conflict. A class of 2 log/sub b/ N stage networks which are equivalent to the Benes networks is introduced. Networks in this class can be either symmetric or asymmetric in their structure, regular or irregular in their interstage connections, and even, 2 log/sub b/ N or 2 log/sub b/ N-1 stages. All networks in this class are nonblocking rearrangeable. A switch labeling scheme is proposed to provide testing of the topological and functional equivalency for this class of networks. This switch labeling scheme can also provide a novel matrix representation for network configuration. This representation introduces a portability concept for the routing scheme on this class of networks. With this representation, a general routing scheme is also developed. This routing scheme can realize arbitrary permutation for the whole class of 2 log/sub b/ N stage networks.>

A conflict-free routing scheme is presented for a class of parallel and distributed computing systems. The core of the scheme is a quadtree communication structure. The quadtree structure suggests a general approach to mapping a class of parallel algorithms with intensive communication requirements for selecting data from many different sources and distributing data from a single source. By properly merging messages and efficiently replicating data, the quadtree structure can complete required communications in O(log/sub 4/ M) parallel steps, where M is the network size. It is shown that the size of a quadtree communication structure can be contracted and stretched by adjusting the number of descendent nodes without affecting its conflict-free property. The relationship between the computation/communication ratio of various parallel algorithms and the number of tree levels is presented, and finally, their joint effect on the response time of combining and distributing data messages is examined. This analysis helps determine the optimal adaptation of the quadtree for minimizing the overall algorithm execution time.>

Overall architecture of a local computer network, Star, is described. The objective is to accomplish a cost-effective system which provides multiple users a real-time service of manipulating very large volume imagery information and data. Star consists of a reconfigurable communication subnet (Starnet), heterogeneous resource units, and distributed-control software entities. Architectural aspects of a fault-tolerant communication subnet, distributed database management, and a distributed scheduling strategy for configuring desirable computation topology are exploited. A model for comparing cost-effectiveness among Starnet, crossbar, and multiple buses is included. It is concluded that Starnet outperforms the other two when the number of units to be connected is larger than 64. This project serves as a research tool for using current and projected technology to innovate better schemes for parallel image processing.

To study the fault-diagnosis method for a class of multistage interconnection networks a general fault model is first constructed. Specific steps for diagnosing single faults and detecting multiple faults in interconnection networks such as the indirect binary n-cube network and the flip network are then developed. The following results are derived in this study: 1) independent of the network size, only four tests are required for detecting a single fault; 2) the number of tests required for locating a single fault and determining the fault type ranges from 4 to max(12, 6 + 2 ⌈log2(log2N)⌉) except for four types of single faults in the switching elements which cannot be pinpointed at the switching element level where N is the number of inputs/outputs; 3) only four tests are required for locating a single fault if the switching element is designed in such a way that any physical defection of the switching element causes both outputs of the related switching element to be faulty; and 4) multiple faults can be detected by 2(1 + log2N) tests.

This paper has focused on the realization of every arbitrary permutation with the shuffle-exchange network. Permutation properties of shuffle-exchange networks are studied and are used to demonstrate several universal networks. It is concluded that 3(log2 N) –1 passes through a single-stage regular shuffle exchange network are sufficient to realize every arbitrary permutation where N is network size. A routing algorithm is also developed to calculate control settings of the shuffle-exchange switches for the permutation realization. Three optimal universal networks, namely, expanded direct- connection shuffle-exchange network, multiple-pass omega network, and modified shuffle-exchange network are then exploited for better interconnection purposes. In addition, this work specifies the inherent relationship between the shuffle-exchange network and the Benes binary network so that designers can have a broad prospect.

A baseline network and a configuration concept are introduced to evaluate relationships among some proposed multistage interconnection networks. It is proven that the data manipulator (modified version), flip network, omega network, indirect binary n-cube network, and regular SW banyan network (S = F = 2) are topologically equivalent. The configuration concept facilitates developing a homogeneous routing algorithm which allows one-to-one and one- to-many connections from an arbitrary side of a network to the other side. This routing algorithm is extended to full communication which allows connections between terminals on the same side of a network. A conflict resolution scheme is also included. Some practical implications of our results are presented for further research.

Properties of the reverse-exchange interconnection network are used to develop a reconfiguration scheme and a two-pass structure for enhancing the efficiency of a class of multistage interconnection networks. Functional relationships among a class of multistage interconnection networks are first derived. According to the functional relationships, we propose a reconfiguration scheme which enables a network to accomplish various interconnection functions of other networks. Then the admissible permutations along with related recursive control algorithms of the reverse-exchange interconnection network are specified through a set of theorems. Using the reverse-exchange property, we also prove that the algorithms actually work. Finally, we prove that arbitrary permutations can be realized in two passes (or 2 · 1og2N switching steps where N is the network size). By taking advantage of Benes network control algorithms, a way to control the two-pass structure is also developed.

This paper describes an asynchronous circuit switching network for multiple-processor systems. Several circuit switching networks for various applications have been proposed and constructed. However, there are problems associated with these networks. The asynchronous circuit switching network possesses several features that can solve these problems. A three-stage fully connected topology is utilized to construct the network. Each switching element is functionally and physically identical and this facilitates a cost-effective LSI implementation and software development. The control structure of the switching element and the routing algorithm are re-organized to fit the asynchronous operation. The network takes advantage of low-cost microcomputers to do the distributed routing control and to implement the communication protocols. The graceful degradation characteristic in the network is provided by independent multiple paths existing between any pair of the source and the destination. A network monitor is incorporated to facilitate an adaptive routing strategy and to have the fault diagnostic capability. Three alternatives for the switching element implementation are described to demonstrate the hardware and software tradeoffs.

Application of associative processors to the solution of the maximal flow problem is investigated. To take maximum advantage of the capability of associative processors, a new algorithm based on matrix representation is developed. The new algorithm is then compared with the associative version of the Ford and Fulkerson labeling method. The comparison is made on the total associative memory access time required for problem solution by each algorithm running on an associate processor. Results show that the ratio of the labeling algorithm to the new algorithm is about 3 for a dense network with 5 nodes. This ratio increases as the number of nodes increases, and decreases as the density of the network decreases.

In this paper, various Communication Processor Systems (CPS) architectures are reviewed and classified according to their interconnection organizations. The evolution and future development of the CPS architectures are discussed and the intercommunication subsystem requirement, interconnection networks structure, network hardware and software design aspects are carefully examined. The functional baseline for the processing unit of the CPS is identified and a comparative study of various existing and proposed processing units is included. The critical review is based on the important features such as the reliability improvement, the interrupt handling, the priority encoding, and the optimized repertoire, etc. Finally, general software considerations are also outlined.

This paper shows that there exists a class of functions called data manipulating functions (DMF's), in sequential as well as paralel processors. The circuits used to achieve these functions can be considered to form an independent functional block, called a data manipulator. A basic organization applicable to both sequential and parallel processors is then suggested. The main deviation of a parallel processor orgaization from the conventional Von Neumann organization is seen to be in the bit-slice (bis) manipulating functions. A comprehensive set of bis manipulating functions from the categories of permuting, replicating, spacing and masking is given. Implementation of the last category, the masking functions, is usually through a mask register by defining its content (mask pattern). It is found that for many operations the required mask patterns are periodic and/or monotonic. The upper bounds of generating these patterns are found. The techniques and designs of two data manipulators for the first three categories of DMF's (permuting, replicating, spacing) are given. Periodic and monotonic mask patterns are also used to help in implementing some of these functions. In addition, it is shown that the data manipulator designs presented in this paper are extremely flexible to suit the requirements of various parallel processors.