Search

In the last few decades, the concept of Wireless Network-on-chip (WiNoC) has emerged as a promising alternative for Multiprocessor Systems on Chip (MPSOC) to achieve reliable and scalable communication. Worth recalling in this regard is that our research team has already designed, verified and evaluated Multistage Interconnection Networks (MIN) in this field. With respect to the present work, we consider proceeding with further exploring our thoughts on this research area. Firstly, we propose the design and performance evaluation of a hybrid (wireless/wired) MIN, analysing how this augmented network can potentially improve not only the average delay, but also energy consumption. Secondly, we continue with examining the implementation of our advanced DELTA-based MIN architecture on Deep Neural Network (DNN) accelerators, while accounting for its potential regularity and scalability in simultaneously maintaining an effective power efficiency and lower latency throughout the DNN operating process. In this context, several metrics have been evaluated in regard to three DNN application cases through implementation of their main respective modules. [ABSTRACT FROM AUTHOR]

In the last few decades, the concept of Wireless Network-on-chip (WiNoC) has emerged as a promising alternative for Multiprocessor Systems on Chip (MPSOC) to achieve reliable and scalable communication. Worth recalling in this regard is that our research team has already designed, verified and evaluated Multistage Interconnection Networks (MIN) in this field. With respect to the present work, we consider proceeding with further exploring our thoughts on this research area. Firstly, we propose the design and performance evaluation of a hybrid (wireless/wired) MIN, analysing how this augmented network can potentially improve not only the average delay, but also energy consumption. Secondly, we continue with examining the implementation of our advanced DELTA-based MIN architecture on Deep Neural Network (DNN) accelerators, while accounting for its potential regularity and scalability in simultaneously maintaining an effective power efficiency and lower latency throughout the DNN operating process. In this context, several metrics have been evaluated in regard to three DNN application cases through implementation of their main respective modules.

In the past few decades, the demand for high-performance computing has been increasingly growing. These systems usually employ many processing elements working together via interconnection networks to solve complicated problems. Due to the efficiency and cost productivity, multistage interconnection networks (MINs) are recommended for use in such systems. At the same time, shuffle-exchange networks (SENs) have extensively been used as a suitable solution to multistage interconnection networks, given the size of their switching elements and simple configurations. In this paper, parallel SEN (PSEN) is proposed to enhance the reliability of these networks. Moreover, PSENs with one and two more stages (PSEN+ and PSEN+2) are utilized to optimize the reliability factor. The reliability analysis of the proposed network is performed through the reliability block diagram. According to the evaluation results, PSEN achieved higher reliability compared to SEN in different aspects of reliability, such as terminal, broadcast, and network. The proposed network also improves the cost-effectiveness in comparison with other MINs. [ABSTRACT FROM AUTHOR]

Terminal reliability of multistage interconnection network (MIN) is the probability of at least one fault free path between any source–destination nodes pair. MIN is used to interconnect processors and memory modules in multi-processor system. In this paper, terminal reliability is estimated and validated for existing MINs (i.e., SEN, SEN+, SEN+2, GIN, CGIN, PCGIN, 3D-GIN, 4D-GIN-1, 4D-GIN-2, 4D-GIN-3, and SEGINs). The comparison and performance analysis of MINs based on various indices are also presented. [ABSTRACT FROM AUTHOR]

Interconnection networks provide communication among processors, memory modules, and other devices in parallel computer systems. The number of stages, interconnection topology, and the types of SE used in the network configuration differentiate each interconnection network. As an illustration, there are numerous aspects that are important in the development of interconnection networks. Reliability can be considered as an important factor to measure the performance in the network. The reliability for interconnection network depends on the reliability of its components. In this paper, we examine the various topologies of interconnection, communication protocol, and discuss reliability issues related to interconnection network. [ABSTRACT FROM PUBLISHER]

We investigate the computation of mappings from a set S^n to itself with "in situ programs", that is using no extra variables than the input, and performing modifications of one component at a time, hence using no extra memory. In this paper, we survey this problem introduced in previous papers by the authors, we detail its close relation with rearrangeable multicast networks, and we provide new results for both viewpoints. A bijective mapping can be computed by 2n-1 component modifications, that is by a program of length 2n-1, a result equivalent to the rearrangeability of the concatenation of two reversed butterfly networks. For a general arbitrary mapping, we give two methods to build a program with maximal length 4n-3. Equivalently, this yields rearrangeable multicast routing methods for the network formed by four successive butterflies with alternating reversions. The first method is available for any set S and practically equivalent to a known method in network theory. The second method, a refinment of the first, described when |S| is a power of 2, is new and allows more flexibility than the known method. For a linear mapping, when S is any field, or a quotient of an Euclidean domain (e.g Z/sZ for any integer s), we build a program with maximal length 2n-1. In this case the assignments are also linear, thereby particularly efficient from the algorithmic viewpoint, and giving moreover directly a program for the inverse when it exists. This yields also a new result on matrix decompositions, and a new result on the multicast properties of two successive reversed butterflies. Results of this flavour were known only for the boolean field Z/2Z.

Interconnection networks are used for communication between nodes in multi-processor systems as well as super-systems. These systems require effective communication between the processor and memory blocks and therefore, interconnection networks are considered as the heart of the parallel processing and multi-processor systems. Multistage interconnection networks (MINs) are the main option for use in supercomputer environments that consist of thousands of processing elements. In this paper, a regular class of fault-tolerant MINs named Pars network along with its routing algorithm are presented. Analytical results demonstrate that the Pars network outperforms known regular networks, namely ABN, ASEN, EGN, and IEGN in terms of cost, fault-tolerance, terminal reliability, mean time to failure, and permutation capability. [ABSTRACT FROM AUTHOR]

Because of their cost-effectiveness, multistage interconnection networks are widely used in parallel multiprocessor systems to make a connection among the processors and memory modules. One of the most important requirements for these communication systems is reliability. Adding a number of stages to these networks is one of the main approaches to promote this issue. Despite its modest cost and ease of implementation, this approach improves the reliability only to a small extent, which is not desirable, especially for large-scale systems. In this paper, we propose a new approach to improve reliability of the networks, called reducing nodes. Extensive reliability analyses from two major perspectives, terminal and broadcast, demonstrate that this idea can achieve a tremendous advantage over the aforementioned approach. [ABSTRACT FROM AUTHOR]

In this paper, we present bi-directional data vortex interconnection network in which the packets are routed both in the forward as well as in the reverse directions. We have simulated the hardware model of a single node with data flow from the node in both the directions and routing. The cascading performance of nodes has been studied by varying the input power from -15 to 0 dBm and BER characteristics up to 70 cascaded nodes have been verified. The terminal reliability analysis of bi-directional data vortex is carried out, as reliability and fault tolerance are important parameters for any multistage interconnection network. Finally, the comparison of the terminal reliability between the proposed bidirectional architecture with two data vortex networks connected in parallel for bidirectional operation is presented. [ABSTRACT FROM PUBLISHER]

Supersystems are shown to provide enough computational power to solve complex problems on a real-time basis. In all these systems, the computational parallelism is obtained from multiple processors. Multistage interconnection networks (MINs) play a vital role on the performance of these multiprocessor systems. This paper introduces a new fault-tolerant MIN named as improved extra group network (IEGN). IEGN is designed by existing extra group (EGN) network, which is a regular multipath network with limited fault tolerance. IEGN provides four times more paths between any source-destination pairs compared with EGN. The performance of IEGN has been evaluated in terms of permutation capability, fault tolerance, reliability, path length, and cost. It has also been proved that the IEGN can achieve better results in terms of fault tolerance, reliability, path length and cost-effectiveness, in comparison to known networks, namely, EGN, augmented baseline network, augmented shuffle-exchange network, fault-tolerant double tree, Benes network, and Replicated MIN. [ABSTRACT FROM AUTHOR]

We investigate the computation of mappings from a set Sn to itself with in situ programs, that is using no extra variables than the input, and performing modifications of one component at a time, hence using no extra memory. In this paper, we survey this problem introduced in previous papers by the authors, we detail its close relation with rearrangeable multicast networks, and we provide new results for both viewpoints. A bijective mapping can be computed by 2n - 1 component modifications, that is by a program of length 2n - 1, a result equivalent to the rearrangeability of the concatenation of two reversed butterfly networks. For a general arbitrary mapping, we give two methods to build a program with maximal length 4n-3. Equivalently, this yields rearrangeable multicast routing methods for the network formed by four successive butterflies with alternating reversions. The first method is available for any set S and practically equivalent to a known method in network theory. The second method, a refinement of the first, described when ∣S∣ is a power of 2, is new and allows more flexibility than the known method. For a linear mapping, when S is any field, or a quotient of an Euclidean domain (e.g. Z/sZ for any integer s), we build a program with maximal length 2n-1. In this case the assignments are also linear, thereby particularly efficient from the algorithmic viewpoint, and giving moreover directly a program for the inverse when it exists. This yields also a new result on matrix decompositions, and a new result on the multicast properties of two successive reversed butterflies. Results of this flavour were known only for the boolean field Z/2Z. [ABSTRACT FROM AUTHOR]

This paper presents the silicon-proven design of a novel on-chip network to support guaranteed traffic permutation in multiprocessor system-on-chip applications. The proposed network employs a pipelined circuit-switching approach combined with a dynamic path-setup scheme under a multistage network topology. The dynamic path-setup scheme enables runtime path arrangement for arbitrary traffic permutations. The circuit-switching approach offers a guarantee of permuted data and its compact overhead enables the benefit of stacking multiple networks. A 0.13-\mum CMOS test-chip validates the feasibility and efficiency of the proposed design. Experimental results show that the proposed on-chip network achieves 1.9\times to 8.2\times reduction of silicon overhead compared to other design approaches. [ABSTRACT FROM AUTHOR]

In this paper, a method for fast processing of data stream tuples in parallel execution of continuous queries over a multiprocessing environment is proposed. A copy of the query plan is assigned to each of processing units in the multiprocessing environment. Dynamic and continuous routing of input data stream tuples among the graph constructed by these copies (called the Query Mega Graph) for each input tuple determines that, after getting processed by each processing unit (e.g., processor), to which next processor it should be forwarded. Selection of the proper next processor is performed such that the destination processor imposes the minimum tuple latency to the corresponding tuple, among all of the alternative processors. The tuple latency is derived from processing, buffering and communication time delay which varies in different practical parallel systems. Parallel system architectures that would be suitable as the desired multiprocessing environment for employing the proposed Dynamic Tuple Routing ( DTR) method are considered and analyzed. Also, practical challenges and issues for the proper parallel underlying system are discussed. Implementation of the desired parallel system on multi-core systems is provided and used for evaluating the proposed DTR method. Evaluation results show that the proposed DTR method outperforms similar method such as the Eddies in terms of tuple latency, throughput and tuple loss. [ABSTRACT FROM AUTHOR]

A multistage interconnection network (MIN) consisting of 2 x 2 nodes constructs a nonblocking switch if the network is rearrangeable. When a x 2n x 2n bit-permuting network is rearrangeable with the minimum depth of 2n - 1, the initial (resp. final) n stages of the network form a banyan-type network and hence the network is equivalent to the tandem connection between two banyan-type networks. Let γ denote the guide permutation of a 2n x 2n banyan-type network and τ the trace permutation of another. These are permutations on numbers from 1 to n. This paper proves that, when the permutation γτ-1 is the transposition between the number n and some number k < n, the tandem connection between the two networks is rearrangeable. This sufficient condition for rearrangeability covers a wide class of tandem connections. For example, the first network in tandem can be the omega network appended with the banyan exchange of any rank while the second is the reversed omega network. [ABSTRACT FROM AUTHOR]

In this paper regular and irregular MINs are analyzed and compared in terms of performance parameters namely Bandwidth, Cost and Bandwidth per unit Cost. Regular networks considered are Extra Stage Cube (ESC) and Augmented Shuffle Exchange (ASEN-2), and Irregular networks are Four Tree (FT) Network and Modified Four Tree Network (MFT). [ABSTRACT FROM AUTHOR]

This paper proposes the multistage interconnection network (MIN) R-Clos, with a hierarchical structure in which locality of communications can be utilized. In R-Clos, a Clos network, which is a three-stage MIN, is used as the local network. By interconnecting multiple Clos networks through the intermediate stage of the hierarchical structure, a large-scale system can be constructed with a smaller hardware requirement than that for a Clos network. On the other hand, due to the use of the Clos network, with great transfer power, as the network for nearby data communications, low latency and wide bandwidth can be provided for nearby access. The latency and throughput of the proposed configuration are evaluated by a simulation using a stochastic model. Although the performance is lowered for traffic with a uniform access pattern, the transfer performance is improved for a data distribution with high locality, compared to the recursive (2s-1)-stage Clos. © 2006 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 89(11): 30–39, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20280 [ABSTRACT FROM AUTHOR]

Although cache control mechanisms for use in multiprocessors that use a multistage interconnection network (MIN) as the interconnecting network have been proposed in which a directory or the cache itself is built into the switches in the MIN, the structure of the switches in these methods have been complex and there therefore remains room for improvement. Our research group has therefore proposed a MIN with directory cache switch (MINDIC) that implements cache control by only building small- capacity directory caches into the switches. This paper reports on the results of evaluating MINDIC using a clock level simulator. The results reveal that MINDIC is able to achieve a level of cache control efficiency that is equal to that of a full map directory management scheme by setting the number of entries in the MINDIC directory caches to approximately 2048 entries. The results also show that the amount of memory required for the directory can be greatly reduced by MINDIC. © 2006 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 89(9): 11–23, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20301 [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we introduce the concept of routing grid as a tool for analyzing realizability of permutations on bit permutation networks (BPNs). We extend a result by Linial and Tarsi which characterizes permutations realizable on shuffle-exchange networks to any BPNs. A necessary condition for a BPN to be rearrangeable is given, and the rearrangeability of two families of BPNs are explored. Finally, we present a method which may help to tackle one kind of balanced matrix problems whose solution implies an answer to Benes conjecture. Hopefully, our treatment brings some new insight into the problem of permutation routing. [Copyright &y& Elsevier]