NDLI: Efficient algorithms for block-cyclic array redistribution between processor sets

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

Efficient algorithms for block-cyclic array redistribution between processor sets

Content Provider	IEEE Xplore Digital Library
Author	Neungsoo Park Prasanna, V.K. Raghavendra, C.S.
Copyright Year	1990
Abstract	Run-time array redistribution is necessary to enhance the performance of parallel programs on distributed memory supercomputers. In this paper, we present an efficient algorithm for array redistribution from cyclic(x) on P processors to cyclic(Kx) on Q processors. The algorithm reduces the overall time for communication by considering the data transfer, communication schedule, and index computation costs. The proposed algorithm is based on a generalized circulant matrix formalism. Our algorithm generates a schedule that minimizes the number of communication steps and eliminates node contention in each communication step. The network bandwidth is fully utilized by ensuring that equal-sized messages are transferred in each communication step. Furthermore, the time to compute the schedule and the index sets is significantly smaller. It takes O(max(P, Q)) time and is less than 1 percent of the data transfer time. In comparison, the schedule computation time using the state-of-the-art scheme (which is based on the bipartite matching scheme) is 10 to 50 percent of the data transfer time for similar problem sizes. Therefore, our proposed algorithm is suitable for run-time array redistribution. To evaluate the performance of our scheme, we have implemented the algorithm using C and MPI on an IBM SP2. Results show that our algorithm performs better than the previous algorithms with respect to the total redistribution time, which includes the time for data transfer, schedule, and index computation.
Sponsorship	IEEE Computer Society
Starting Page	1217
Ending Page	1240
Page Count	24
File Size	1319765
File Format	PDF
ISSN	10459219
Volume Number	10
Issue Number	12
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1999-12-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Signal processing algorithms Processor scheduling Scheduling algorithm Costs Runtime Concurrent computing Multidimensional signal processing Distributed computing Computer Society Supercomputers
Content Type	Text
Resource Type	Article
Subject	Signal Processing Computational Theory and Mathematics Hardware and Architecture

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

Efficient Algorithms for Block-Cyclic Array Redistribution between Processor Sets

Scheduling block-cyclic array redistribution

Efficient local search far DAG scheduling

Efficient algorithms for array redistribution

Efficient algorithms for block-cyclic array redistribution between processor sets

Efficient algorithms for multi-dimensional block-cyclic redistribution of arrays

On runtime parallel scheduling for processor load balancing

Optimal scheduling of compute-intensive tasks on a network of workstations

Contention-free communication scheduling for array redistribution

Efficient algorithms for block-cyclic array redistribution between processor sets

Similar Documents

Efficient Algorithms for Block-Cyclic Array Redistribution between Processor Sets

Scheduling block-cyclic array redistribution

Efficient local search far DAG scheduling

Efficient algorithms for array redistribution

Efficient algorithms for block-cyclic array redistribution between processor sets

Efficient algorithms for multi-dimensional block-cyclic redistribution of arrays

On runtime parallel scheduling for processor load balancing

Optimal scheduling of compute-intensive tasks on a network of workstations

Contention-free communication scheduling for array redistribution

Efficient algorithms for block-cyclic array redistribution between processor sets