DocumentCode :
3193813
Title :
A Scratch-Pad Memory Aware Dynamic Loop Scheduling Algorithm
Author :
Ozturk, Ozcan ; Kandemir, Mahmut ; Narayanan, Sri Hari Krishna
Author_Institution :
Bilkent Univ., Ankara
fYear :
2008
fDate :
17-19 March 2008
Firstpage :
738
Lastpage :
743
Abstract :
Executing array based applications on a chip multiprocessor requires effective loop parallelization techniques. One of the critical issues that need to be tackled by an optimizing compiler in this context is loop scheduling, which distributes the iterations of a loop to be executed in parallel across the available processors. Most of the existing work in this area targets cache based execution platforms. In comparison, this paper proposes the first dynamic loop scheduler, to our knowledge, that targets scratch-pad memory (SPM) based chip multiprocessors, and presents an experimental evaluation of it. The main idea behind our approach is to identify the set of loop iterations that access the SPM and those that do not. This information is exploited at runtime to balance the loads of the processors involved in executing the loop nest at hand. Therefore, the proposed dynamic scheduler takes advantage of the SPM in performing the loop iteration-to-processor mapping. Our experimental evaluation with eight array/loop intensive applications reveals that the proposed scheduler is very effective in practice and brings between 13.7% and 41.7% performance savings over a static loop scheduling scheme, which is also tested in our experiments.
Keywords :
dynamic scheduling; iterative methods; program compilers; chip multiprocessor; dynamic loop scheduling; executing array; loop iteration to processor mapping; loop parallelization; optimizing compiler; scratch pad memory; Algorithm design and analysis; Application software; Delay; Dynamic scheduling; Memory management; Processor scheduling; Runtime; Scanning probe microscopy; Scheduling algorithm; Testing; Compilers; Multiprocessor Systems; Scheduling and Partitioning;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Quality Electronic Design, 2008. ISQED 2008. 9th International Symposium on
Conference_Location :
San Jose, CA
Print_ISBN :
978-0-7695-3117-5
Type :
conf
DOI :
10.1109/ISQED.2008.4479830
Filename :
4479830
Link To Document :
بازگشت