NDLI: Reduced distance routing in single-state shuffle-exchange interconnection networks

Please wait, while we are loading the content...

A view of database system performance measures

A performance comparison of multi-micro and mainframe database architectures

Packet routing algorithms for integrated switching networks

Performance of the Expressnet with voice/data traffic

Analysis of the resequencing delay for M/M/m systems

Parallel discrete event simulation: a shared memory approach

A close look at vector performance of register-to-register vector computers and a new model

Memory access patterns of parallel scientific programs

Disk scheduling in System V

Multi-disk management algorithms

A unified operational treatment of RPS reconnect delays

Performance analysis of parallel processing systems

Reduced distance routing in single-state shuffle-exchange interconnection networks

Queueing delays in buffered multistage interconnection networks

Performance through memory

Predicting performance of concurrency control designs

Performance analysis of a fault detection scheme in multiprocessor systems

A statistical approach to computer performance modeling

Monit: a performance monitoring tool for parallel and pseudo-parallel programs

Modeling the software architecture of a prototype parallel machine

A workload characterization pipeline for models of parallel systems

Transformation between different levels of workload characterization for capacity planning: fundamentals and case study

Performance analysis of file replication schemes in distributed systems

Network measurement of the VMTP request-response protocol in the V distributed system

Performance evaluation of LAN sorting algorithms

Delay analysis of a window tree conflict resolution algorithm in a local area network environment

Some conjectures on the behavior of acknowledgement-based transmission control of random access communication channels

The effect of channel-exit protocols on the performance of finite population radom-access systems

Reduced distance routing in single-state shuffle-exchange interconnection networks

Content Provider	ACM Digital Library
Author	Tan, Ziao-Nan Sevcik, Kenneth C.
Abstract	In multiprocessor architectures, it is frequently necessary to provide parallel communication among a potentially large number of processors and memories. Among the many interconnection schemes that have been proposed and analyzed, shuffle-exchange networks have received much attention due to their ability to allow a message to pass from any node to any other node in a number of steps that grows only logarithmically with the number of interconnected nodes (in the absence of contention) while keeping the number of hardware connections per node independent of the number of nodes.Straight-forward use of shuffle-exchange networks to interconnect &Ngr; nodes involves having every packet pass through log2 &Ngr; stages enroute to its destination. By exploiting common structure in the addresses of the source and destination nodes, however, more sophisticated routing can reduce the average number of steps per message below log2 &Ngr;. In this paper, we describe and evaluate three levels of improvements to basic single-stage shuffle-exchange routing. Each one yields successively more benefit at the cost of more complexity. Using simulation, we show that the use of routing schemes that reduce the average distance can substantially reduce average message delay times and increase interconnection network capacity. We quantify the performance gains only in the case where messages from one node are destined with uniform probability over all nodes. However, it is clear that the advantage of the new schemes we propose would be still greater if there is some “locality” of communication that can be exploited by having the most frequent communication occur between pairs of nodes with shorter distances separating them.
Starting Page	95
Ending Page	110
Page Count	16
File Format	PDF
ISBN	089791225X
DOI	10.1145/29903.29917
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1987-08-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Reduced distance routing in single-state shuffle-exchange interconnection networks

On shortest path routing in single stage shuffle-exchange networks

Constructing transition matrices for routing BPC permutations on shuffle-exchange recirculating networks

Algebraic Models for the Cube Connected Cycles and Shuffle Exchange Graphs

On the shuffle-exchange permutation network

Rearrangeability of 2 log N-1 shuffle/exchange network

Switch adjusting on hierarchical shuffle-exchange networks for all-to-all personalized exchange

A New Tag Scheme and Its Tree Representation for a Shuffle-Exchange Network

A New Fault Tolerant Routing Algorithm for Advance Irregular Augmented Shuffle Exchange Network

Reduced distance routing in single-state shuffle-exchange interconnection networks

Similar Documents

Reduced distance routing in single-state shuffle-exchange interconnection networks

On shortest path routing in single stage shuffle-exchange networks

Constructing transition matrices for routing BPC permutations on shuffle-exchange recirculating networks

Algebraic Models for the Cube Connected Cycles and Shuffle Exchange Graphs

On the shuffle-exchange permutation network

Rearrangeability of 2 log N-1 shuffle/exchange network

Switch adjusting on hierarchical shuffle-exchange networks for all-to-all personalized exchange

A New Tag Scheme and Its Tree Representation for a Shuffle-Exchange Network

A New Fault Tolerant Routing Algorithm for Advance Irregular Augmented Shuffle Exchange Network

Reduced distance routing in single-state shuffle-exchange interconnection networks