چكيده به لاتين
In this thesis, we address the critical problem of compile-time task scheduling for heterogeneous computing systems aiming to minimize the overall execution time of a parallel application. We will propose three novel list-based heuristic algorithms, which consist of two main phases namely task prioritizing and processor selection, to tackle this NP-complete problem.
In our first work, we present a critical path-oriented scheduling algorithm. It is a modification of the well-known Critical Path on a Processor (CPOP) algorithm that presented the idea of scheduling the most costly entry-exit path of tasks, commonly known as the critical path, on a single processor. Generally, this processor selection strategy has different potential impacts on computation and communication costs along a selected path in the produced schedule. However, these probably different effects are not considered in the common definition of a critical path. Differentiating between these two types of costs, we introduce a novel performance-effective definition for a critical path that is compatible with this processor selection strategy. The experimental studies prove our analysis.
The recent trend in designing list-based scheduling heuristics is introducing look-ahead features using predict-tables. The main idea is trying to make globally efficient decisions while maintaining low complexity. However, related algorithms in the literature do not fully exploit the potential of this method since they define their predict-tables based on the static concept of cost (in terms of time). Such attributes do not provide information about ensuing variations in application execution time caused by a mapping decision, and as a result, are unable to properly predict the potential processing bottlenecks of a parallel application. Also, suggested predict-tables in the literature have an inherent weakness against task parallelism since they do not consider processor availability. In our second and third works, we introduce a novel concept called optimistic saved-time and we formulate it as a predict-table called optimistic saved-time table. We define our processor selection strategy based on combinations of this new concept and cost. In the processor selection phase, each task is assigned to a processor which not only provides an early finish time for that task but also its selection is likely to result in a great saved-time in the execution of the successor tasks. The proposed predict-table also contains a novel parallelism-aware weighing approach to maintain its performance against task parallelism. The comprehensive experiments based on a wide variety of randomly generated applications and some real-world applications demonstrate the notable performance improvement of the proposed algorithm over several state-of-the-art list-based scheduling heuristics.
