Title: Scheduling DAG applications on multi-core processor packages architectures
Abstract: In this paper, we deal with the problem of scheduling fine grain task graph applications on multicore processor packages. We model this problem as a task scheduling problem with hierarchical communication delays. That is, we adopt the model in which the communications between cores on a processor package are much faster than those between cores belonging to different ones. This model incorporates the hierarchical nature of the communications using today’s parallel computers, as shown by many PCs where cores are grouped into processor packages. Our main contribution is to provide a scheduling algorithm based on a genetic approach that considers this model when scheduling the fine grain applications. Simulation results demonstrate the effectiveness of the proposed approach when compared with a list scheduling algorithm for hierarchical communications [1]. We consider computing architectures with a set P of M homogeneous processor packages each package containing a set of m homogeneous cores. One example of this kind of architecture could be machines with large shared memory having two 2.5 GHz Intel Xeon E5000 processor package series of two or four cores each. As stated, the computational model we adopt here is the hierarchical communication model [2]. That is the communication delay ???ij between two cores in the same package is negligible (???ij = 0), while it takes cij units of time if the two cores belong to different packages. The rational is that in multi-core processors both computation units are integrated on the same die. Thus, communication between these computation units does not have to go outside the die, and hence is independent of the die pin overhead, making intra-die communication much faster than inter-die. The application is modeled by a precedence graph G = (T,E), where the set of vertices T is a set of n tasks. Each edge e = (ti, tj) ∈ E is a precedence constraint meaning that the results of task ti must be available before tj starts its execution. To every task tj , there is an associated value pj representing its processing time. In terms of classical scheduling problems, the application has to be scheduled on P , the set of mM processor packages. The l-th processor package is denoted Pl∗ whereas the k-th core of the l-th processor is denoted Plk ∈ Pl∗. A solution of the problem of scheduling an application on the multi-cores is to determine the processor and core assignment and an execution date for each task of the application respecting scheduling constraints. The associated optimization problem is to minimize Cmax, the completion time (i.e. makespan) of the last executed task. In the 3-fields notation this problem is denoted by PM (Pm)|prec, pj , C = (cij , 0)|Cmax [2]. In terms of complexity, the problem is NP-hard as it contains NP-hard problems as particular cases [1].
Publication Year: 2010
Publication Date: 2010-10-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot