Title :
Scheduling of tiled nested loops onto a cluster with a fixed number of SMP nodes
Author :
Athanasaki, Maria ; Koukis, Evangelos ; Koziris, Nectarios
Author_Institution :
Comput. Syst. Lab., Nat. Tech. Univ. of Athens, Greece
Abstract :
We propose several alternative methods for the compile time scheduling of tiled nested loops onto a fixed size parallel architecture. We investigate the distribution of tiles among processors, provided that we have chosen either a nonoverlapping communication mode, which involves successive computation and communication steps, or an overlapping communication mode, which supposes a pipelined, concurrent execution of communication and computations. In order to utilize the available processors as efficiently as possible, we can either adopt a cyclic assignment schedule, or assign neighboring tiles to the same CPU, or adapt the size and shape of tiles, so that the required number of processors is exactly equal to the number of the available ones. We theoretically and experimentally compare the proposed schedules, so as to design one which achieves the minimum total execution time, depending on the cluster configuration, (i.e. number and type of nodes, interconnect bandwidth, etc) the internal characteristics of the underlying architecture (i.e. NIC and DMA latencies, etc) and the iteration space size and shape.
Keywords :
parallel architectures; pipeline processing; processor scheduling; program control structures; workstation clusters; CPU; DMA latencies; cluster configuration; compile time scheduling; cyclic assignment schedule; nonoverlapping communication mode; parallel architecture; symmetric multiprocessor nodes; tiled nested loops; Concurrent computing; Distributed computing; Electronic mail; Laboratories; Network interfaces; Parallel architectures; Processor scheduling; Shape; Systems engineering and theory; Tiles;
Conference_Titel :
Parallel, Distributed and Network-Based Processing, 2004. Proceedings. 12th Euromicro Conference on
Print_ISBN :
0-7695-2083-9
DOI :
10.1109/EMPDP.2004.1271475