Making contention aware of identical data

Abstract

In scheduling algorithms for parallel computing, communication between tasks plays an important role for the achievable performance. When a task needs to send the same data to more than one target tasks, this data is called identical data. Identical data will be sent many times to different target tasks but without changing it. If some of the target tasks are on the same processor, the processor needs to only receive the identical data once. Based on this property, this work considers identical data in scheduling algorithms in order to reduce the schedule length for task scheduling. Unfortunately, when the communication costs and data transmission contention are considered in the parallel system, it is difficult to find an effcient schedule for tasks. After investigating the two most important scheduling heuristics: list scheduling and clustering, this thesis separately suggests a list scheduling algorithm and a clustering algorithm under the contention model. Both of them can consider identical data and the communication contentions. Further more, the weakness of the two proposed algorithms are studied and a third algorithm that combines both clustering and list scheduling algorithms, abbreviated as cluster list algorithm (CLA), is proposed to overcome the weakness of them. In the CLA, the clustering algorithm is used to decide which edges are needed to be zeroed. The list algorithm is used to get the scheduling length in each steps of the clustering algorithm. In order to reduce the complexity, the list scheduling is simplified without needing to find the processors for the nodes. This CLA has a time complexity of O(E (V + E)), where lVl represents the number of tasks and lEl represents the number of edges in the task graph.