NDLI: Applying array contraction to a sequence of DOALL loops

Content Provider	IEEE Xplore Digital Library
Author	Yonghong Song Zhiyuan Li
Copyright Year	2004
Description	Author affiliation: Sun MicroSysterms Inc., Santa Clara, CA, USA (Yonghong Song)
Abstract	Efficient program execution on multiprocessor computers requires both sufficient parallelism and good data locality. Recent research found that, using a combination of loop shifting, loop fusion, and array contraction, one can reduce the memory required to execute a sequence of serial loops, thereby to improve the cache locality. This paper studies how to extend such a memory-reduction scheme to a sequence of DOALL loops, which are executed in parallel on multiprocessors. Two methods are proposed to overcome difficulties caused by loop-carried dependences. Data copy-in is performed to remove anti-dependences between different parallel threads, and computation duplication is performed to remove flow dependences. Experiments performed on a number of benchmark programs show that the proposed technique improves both cache locality and parallel execution speed for the DOALL loops. The scheme achieves an average speedup of 1.41 for 17 programs on a 4-processor SUN machine.
Starting Page	46
Ending Page	53
File Size	349168
Page Count	8
File Format	PDF
ISBN	0769521975
ISSN	01903918
DOI	10.1109/ICPP.2004.1327903
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-08-15
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Yarn Concurrent computing Sun Computer networks Parallel processing Intelligent networks Data flow computing
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

Applying Array Contraction to A Sequence of DOALL Loops

Speculative parallelism of intelligent interactive systems

MigThread: thread migration in DSM systems

Exploiting pipelined executions in OpenMP

From distributed sequential computing to distributed parallel computing

Parallel computing with distributed shared data

Nets and data flow interpreters

Run-time parallelization for partially parallel loops

Implementation of an efficient parallel BDD package

Applying array contraction to a sequence of DOALL loops

Similar Documents

Applying Array Contraction to A Sequence of DOALL Loops

Speculative parallelism of intelligent interactive systems

MigThread: thread migration in DSM systems

Exploiting pipelined executions in OpenMP

From distributed sequential computing to distributed parallel computing

Parallel computing with distributed shared data

Nets and data flow interpreters

Run-time parallelization for partially parallel loops

Implementation of an efficient parallel BDD package

Applying array contraction to a sequence of DOALL loops