NDLI: On the shuffle-exchange permutation network

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

2012 12th International Symposium on Pervasive Systems, Algorithms and Networks

2009 10th International Symposium on Pervasive Systems, Algorithms, and Networks

2008 International Symposium on Parallel Architectures, Algorithms, and Networks (i-span 2008)

8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05)

7th International Symposium on Parallel Architectures, Algorithms and Networks, 2004. Proceedings.

Proceedings International Symposium on Parallel Architectures, Algorithms and Networks. I-SPAN'02

Proceedings International Symposium on Parallel Architectures, Algorithms and Networks. I-SPAN 2000

Proceedings Fourth International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN'99)

Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)

Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)

Deep Blue: One Small Step For A Computer

A new general purpose parallel database system

A parallel pipelined renderer for time-varying volume data

A polynomial time algorithm for reconfiguring the 1 1/2 track-switch model with PE and bus faults

BaLinda: a simple parallel programming model with active objects

Wavelength division multiple access ring: virtual topology on a simple ring network

Features of optical interconnects in distributed-shared memory organized MIMD architectures: the ultimate goal

Optimal realization of hypercubes by three-dimensional space-invariant optical interconnections

A pipelined TDM optical bus with improved performance

Critical sections and producer/consumer queues in weak memory systems

A scalable cache coherent architecture for large-scale mesh-connected multiprocessors

The architecture of OCMP and its evaluation

Exploiting global data locality in non-blocking multithreaded architectures

A fast algorithm for complete subcube recognition

An implementable dynamic automatic self-stabilizing protocol

Cover model: a framework for design and execution of distributed applications

An NC parallel algorithm for generalized vertex-rankings of partial k-trees

Hamiltonian-laceability of star graphs

The horizontal rotate crossed cube: HCQ interconnection network

A new shortest path routing algorithm and embedding cycles of crossed cube

Algorithms and lower bounds for p-gossiping in circulant networks

Fiber-ribbon pipeline ring network for high-performance distributed computing systems

On deciding granularity for optimal speedup for solving data parallel problems with clustered distributed computing

A high performance dynamic token-based distributed synchronization algorithm

Hardware synchronization of massively parallel processes in distributed systems

On the shuffle-exchange permutation network

On the power of the mesh with hybrid buses

Fault-tolerant hypercubes with small degree

UHC-a massively parallel and distributed realisation of hierarchical classifier networks

Efficiency of remote access caches in future SMP-based CC-NUMA multiprocessors: initial results

Efficient implementation of software release consistency on asymmetric distributed shared memory

Pleiades: a prototype of inter-processor network generation system

WWW-oriented system for visualization, animation and investigation of mapping algorithms

Processor allocation in k-ary n-cube multiprocessors

A parallel algorithm for embedding large pyramids into smaller hypercubes with load balancing

A parallel algorithm with embedded load balancing for autocorrelation matrix computation

RMESH algorithms for parallel string matching

Collecting cyclic garbage in distributed systems

Approximation Algorithms

New partitioning schemes for parallel modified Gram-Schmidt orthogonalization

An efficient parallel algorithm for the planar mincut linear arrangement problem for trees

Parallel implementation of branch and bound algorithm for solving vehicle routing problem on NOWs

Parallel approaches for discovering functional dependencies from data for information system design recovery

Supporting parallel processing on the RHODOS cluster of workstations

Minimizing communication conflicts with load-skewing task assignment techniques on network of workstations

Research on cluster of workstations

Speech support in wireless, multihop networks

CASS: an efficient task management system for distributed memory architectures

An adaptive processor allocation strategy for mesh-connected systems

Design and evaluation of a submesh allocation scheme for two-dimensional mesh-connected parallel computers

Processor allocation in the star graph using Sg-lattice model

Color optimal self-stabilizing depth-first token circulation

Clock snooping and its application in on-the-fly data race detection

A knowledge base for the optimization of parallel query execution plans

Efficient parallel multiselection on hypercubes

A genetic algorithm for optimal 3-connected telecommunication network designs

A fast approximation algorithm for maximum-leaf spanning tree

Effects of chromosome migration on a parallel and distributed genetic algorithm

Modular design of a large sorting network

An evolutionary approach for scheduling in parallel processor systems

A method for estimating optimal unrolling times for nested loops

A simulation study of dynamic load balancing for network-based parallel processing

An operation placement and scheduling scheme for cache and communication localities in fine-grain parallel architectures

A fair congestion control scheme for LAN interconnection via ATM

Node-to-node cluster fault tolerant routing in hypercubes

An efficient class of SEC-DED-AUED codes

Wide-diameter of generalized undirected de Bruijn graph UG/sub B/(n, n/sup 2/)

The diameter of the generalized de Bruijn graph UG/sub B/(n,n(n/sup 2/+1))

Radix R parallel FFT algorithms with a global interconnection networks and its evaluation

The barrier synchronization impact on the MPI-programs performance using a cluster of workstations

Optimal software multicast on wormhole switch-based networks

Toward more advanced usage of instruction level parallelism by a very large data path processor architecture

Fast nearest neighbor algorithms on a linear array with a reconfigurable pipelined bus system

Performance analysis for dynamic tree embedding in k-partite networks by random walk

A built-in self-reconfigurable scheme for 3D mesh arrays

A tampering protocol for reducing the coherence transactions in regular computation

Reliable broadcasting and secure distributing in channel networks

Bit-parallel selfrouting optoelectronic switching fabrics for massively parallel wide-format data processing: principle and optical architecture

A decentralised scheme for multi-node broadcasting on hypercubes

Efficient tree-based multicast in wormhole-routed 2D meshes

Index of authors

Proceedings Second International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN'96)

Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN)

On the shuffle-exchange permutation network

Content Provider	IEEE Xplore Digital Library
Author	Bass, D.W. Sudborough, I.H.
Copyright Year	1997
Description	Author affiliation: Comput. Sci. Program, Texas Univ., Dallas, TX, USA (Bass, D.W.)
Abstract	The shuffle-exchange permutation network (SEP/sub n/) is a fixed degree Cayley graph which has been proposed as a basis for massively parallel systems. We propose a routing algorithm with an upper bound of (5/8)n/sup 2/+O(n), where n is the length of the permutation. (This improves on a (9/8)n/sup 2/ routing algorithm described earlier (Latifi and Srimani, 1996)). Thus, the diameter of SEP/sub n/ is at most (5/8) n/sup 2/+O(n). We also show that the diameter is at least n/sup 2//2-O(n). We demonstrate that SEP/sub n/ has a Hamilton cycle, for n/spl ges/3, and describe embeddings of variable-degree Cayley networks, such as bubble-sort networks, star networks and pancake networks into SEP/sub n/. Our embeddings for these networks are substantial improvement of earlier results stated in Latifi and Srimani (1996).
Starting Page	165
Ending Page	171
File Size	637039
Page Count	7
File Format	PDF
ISBN	0818682596
ISSN	10874089
DOI	10.1109/ISPAN.1997.645088
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1997-12-20
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing Multiprocessor interconnection networks Upper bound Hypercubes Sorting
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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