NDLI: Just-In-Time Scheduling for Loop-based Speculative Parallelization

Content Provider	IEEE Xplore Digital Library
Author	Llanos, D.R. Orden, D. Palop, B.
Copyright Year	2008
Description	Author affiliation: Univ. de Valladolid, Valladolid (Llanos, D.R.)
Abstract	Scheduling for speculative parallelization is a problem that remained unsolved despite its importance. Simple methods such as Fixed-Size Chunking (FSC) need several 'dry-runs' before an acceptable chunk size is found. Other traditional scheduling methods were originally designed for loops with no dependences, so they are primarily focused in the problem of load balancing. In general, all these methods perform poorly when used for speculative parallelization, where loops may present unexpected dependences that adversely affect performance. In this work we address the problem of scheduling loops with and without dependences for speculative execution. We have found that a trade-off between minimizing the number of re-executions and reducing overheads can be found if the size of the scheduled block of iterations is calculated at runtime. We introduce here a scheduling method called Just-In- Time (JIT) scheduling that uses the information available during the execution of the loop in order to dynamically compute the size of the next block to be scheduled. The results show a 10% to 26% speedup improvement in real applications with dependences with respect to a carefully- tuned FSC strategy, and a 9% to 39% speedup improvement in real applications without dependences. With our proposal, the number of dependence violations that lead to squashes can be reduced by up to 62%. Moreover, in applications where the cost of dependence violations is too high to obtain speedups with FSC, our runtime scheduling mechanism avoids performance degradation.
Starting Page	334
Ending Page	342
File Size	661486
Page Count	9
File Format	PDF
ISBN	9780769530895
ISSN	10666192
DOI	10.1109/PDP.2008.13
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-02-13
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Processor scheduling Power capacitors Yarn Dynamic scheduling Runtime Costs Shape Scheduling algorithm Design methodology Load management scheduling Speculative parallelization loop-based speculation speculative multithreading
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

Meseta: a new scheduling strategy for speculative parallelization of randomized incremental algorithms

P-slice based efficient speculative multithreading

IPLS: an intelligent parallel loop scheduling for multiprocessor systems

Just-in-time scheduling for loop-based speculative parallelization.

A cost-driven compilation framework for speculative parallelization of sequential programs

A load-balancing algorithm for N-cubes

Thread-based software synthesis for embedded system design

Exclusive squashing for thread-level speculation

The Parallel State Processor

Just-In-Time Scheduling for Loop-based Speculative Parallelization

Similar Documents

Meseta: a new scheduling strategy for speculative parallelization of randomized incremental algorithms

P-slice based efficient speculative multithreading

IPLS: an intelligent parallel loop scheduling for multiprocessor systems

Just-in-time scheduling for loop-based speculative parallelization.

A cost-driven compilation framework for speculative parallelization of sequential programs

A load-balancing algorithm for N-cubes

Thread-based software synthesis for embedded system design

Exclusive squashing for thread-level speculation

The Parallel State Processor

Just-In-Time Scheduling for Loop-based Speculative Parallelization