West Home

West Team --- MRmin

MRmin: Multidimensional Ring as a Multiprocessor Interconnection Network

A collaboration with M.-Tahar Kechadi, University College Dublin Belfield, Ireland.

The interconnection network is an important and complex component in the design and implementation of parallel computer architectures. Interconnection network design requires good understanding of network conflicts and the data transfer capacity between different sets of modules, and depends on the cost of building and integrate it as part the machine architecture. In parallel computers, interconnection networks are often exploited to realise the required communication between processors and memories. The communication overheads depend to a great extent on the underlying interconnection network. A good interconnection network should match as closely as possible the general communication patterns of various practical parallel applications to achieve low network latency and high throughput. In addition, the interconnection network should not be very costly compared with the total machine cost.

Existing interconnection networks are mostly members of the class of multistage cubes. The main shortcoming of multistage cube networks is the existence of a single path of each source-destination pair of nodes. As a result, the network is susceptible to a link or a node failure. Among them are the entire class of multidimensional access networks, which includes the MDA (Multidimensional Access Memories) and OMP (Orthogonal multiprocessor), the class of bi-delta networks like the Omega, flip, and indirect binary cube, and the baseline and reverse baseline networks.

This project consists of studying a new type of interconnection networks based on multi-dimensional ring topology.

Multi-dimensional ring networks (MR) are defined with regard to a base (radix) r and the number of nodes N to be connected, where the base r is between 2 and N/2, (2£ r£ ë N/2û). The network MR(r, n) is a graph G(N, E), where V is a set of nodes labeled from 0 to N-1 and E is a set of links defined by E={(x,y);x,yÎ V | y-x+kN = ± rⁱ}, k is an integer and 0£ i£ log_r(N). Each i value constitutes a dimension of the MR(R, N) network.

A new multistage interconnection network based on the MR topology has been carried out in a preliminary study . The interconnection network based on MR(r,N) uses the shortest path to connect the source node to the destination node. This path is given by expressing the distance d(x,y) in base r, where x is the source node and y is the destination node. The distance between any two nodes d(x,y) is given by the equation

One of the important characteristics of this interconnection network is that each stage implements one dimension of the MR(r, N) network.

This research project we want to pursue will be carried out on two complementary aspects:

• The theoretical model of this network which consists of developing different types of routing strategies, other types of network architectures based on the MR topology, and also continue developing all theoretical aspects of the analysis of the MIN network made so far.
• The simulation model consists of implementing the MIN network in its current version and its extended version (new interconnection network architecture based on hierarchical MIN that could include cube and hypercube networks) in a shared or distributed memory multiprocessor environment. The simulation model will allow the validation theoretical results and also the optimisation the parameters of the theoretical model for an efficient implementation.

Main Publications

M.-Tahar Kechadi, A Study of a New Processor-Memory Interconnection Network for Multiprocessor Systems, to be published in IEEE Transactions on Parallel and Distributed Systems, 2000.

Copyright © 2000-2008 LIFL.

Nov 20 2000, 12:08.