Title :
Scheduling of wavefront parallelism on scalable shared-memory multiprocessors
Author :
Manjikian, Naraig ; Abdelrahman, Tarek S.
Author_Institution :
Dept. of Electr. & Comput. Eng., Toronto Univ., Ont., Canada
Abstract :
Tiling exploits temporal reuse carried by an outer loop of a loop nest to enhance cache locality. Loop skewing is typically required to make tiling legal. This restricts parallelism to wavefronts in the tiled iteration space. For a small number of processors, wavefront parallelism can be efficiently exploited using dynamic self-scheduling with a large tile size. Such a strategy enhances intratile locality, but does not necessarily enhance intertile locality. We show that dynamic self-scheduling performs poorly on scalable shared-memory multiprocessors where smaller tiles are necessary to provide sufficient parallelism-smaller tiles place greater importance on intertile locality. We propose static scheduling strategies which enhance intertile locality for small tiles. Results of experiments on a Convex SPP1000 multiprocessor demonstrate that our strategies outperform dynamic self-scheduling by a factor of up to 2.3 on 30 processors
Keywords :
cache storage; processor scheduling; reconfigurable architectures; shared memory systems; Convex SPP1000 multiprocessor; cache locality; dynamic self-scheduling; intertile locality; intratile locality; loop nest; loop skewing; parallelism; scalable shared-memory multiprocessors; static scheduling strategies; temporal reuse; tiled iteration space; tiling; wavefront parallelism scheduling; Delay; Dynamic scheduling; Hardware; High performance computing; Law; Legal factors; Parallel processing; Processor scheduling; Scalability; Tiles;
Conference_Titel :
Parallel Processing, 1996. Vol.3. Software., Proceedings of the 1996 International Conference on
Conference_Location :
Ithaca, NY
Print_ISBN :
0-8186-7623-X
DOI :
10.1109/ICPP.1996.538567