Parallel Tasks On Distributed Memory Multiprocessor Static Scheduling

In distributed memory multiprocessor(DMM) systems, the communication overhead involved among different processors is still not trivial for medium/fine granularity parallel programs which even offsets the advantages brought by multiprocessor parallelism. In order to execute a parallel application efficiently, it is essential to assign tasks to processors properly using an appropriate static task scheduling technology. The final goal of static task scheduling is to minimize the execution time of a parallel program.Static task scheduling can be implemented by hand or by algorithms. For regular applications or those applications whose topologies coincide with that of multiprocessor system, it is feasible to assign tasks to processors by hand. However, dedicated scheduling algorithms should be used when applications are rather irregular and their sizes are large. This paper focuses on the research of static task scheduling using algorithms. Main contributions achieved in this paper are as follows:1. For completely interconnected systems, a scheduling algorithm CNF based on dynamic critical path is proposed. The three features of this algorithm include : 1). The dynamic critical path is adjusted according to scheduling process. 2). The task nodes on the critical path are scheduled first, and 3). For a task to be scheduled, if it has only one child. then a try-and-scheduling method is adopted to select processor for it, otherwise, only the processor on which it can be executed the earliest is considered. The performance comparison results indicate that algorithm CNF outperforms three recently reported algorithms in respect of average schedule length. In addition. an effective method is exploited to cut down processors needed to be used in scheduling.2. The formal description of static task scheduling for incompletely interconnected systems is presented. For some typical interconnecting topologies, such as linear array, ring, star, 2D mesh and hyperoube, a general scheduling algorithm is proposed. In this algorithm, links between different processors are also treated as...