## 2 Basic Definitions  
This section defines a set of terms to help understand the following sections in this paper. It considers the definitions contained in [8; 13] and other definitions arising from the extension of this research. An additional subsection to explain the UMDA is provided. Definition 1: The target system is constituted by \(\mathbb{C}_{k}\) clusters \(C_{1},C_{2},...C_{k}\), where \(k\) is the number of clusters of the HDCS. Each cluster contains \(m\) heterogeneous processors with \(n\) processing cores. Therefore, \(C_{k,n,m}\) denotes the core \(k\) processor \(n\) processing core \(m\). Definition 2: A PTG can be modeled by a directed acyclic graph (DAG) \(T=(N,E)\), where \(N=\{\eta_{i}:i=1,...,N\}\) is a set of \(N\) nodes or sub-tasks and \(E=\{E_{i,j}:i,j=1,...,N\}\) is a set of \(E\) edges. Parallel task graph \(T\) can be characterized by \((\eta_{i},\{1\leq j\leq\eta_{i}|\tau_{i,j}\},G_{i},V_{i},W_{i})\), where \(\eta_{i}\) is the number of sub-tasks of \(T_{i}\), the second parameter is the set of sub-tasks, \(G_{i}\) is the set of relations directed between the sub-tasks, \(V_{i}\) is the number of levels of \(\tau_{i}\), and \(W_{i}\) the width of each level of \(\tau_{i}\) (represented by a vector). The PTG consists of a set of nodes and edges (directed relationships). The nodes represent the execution requirements of the task, whereas the directed relationships show the execution flow. Definition 3: A directed relationship from sub-task \(\tau_{i,j}\) to \(\tau_{i,k}\) means that \(\tau_{i,k}\) can start its execution only if \(\tau_{i,j}\) completes its own. In this case, we call \(\tau_{i,j}\) a parent sub-task of \(\tau_{i,k}\) and \(\tau_{i,k}\) the child of \(\tau_{i,j}\). Each sub-task in a given DAG task can have several parents and children. An initial sub-task is a sub-task without parents, whereas a final sub-task is a sub-task without children. A PTG has a start sub-task and a finish sub-task. **Definition 4**. : _Layering. Given \(T\), where each \(n\in N\) node has a positive width \(W_{i}\), a division by layers or levels of \(T_{i}\) (also called stratification of \(T_{i}\)) is a partition of its set of nodes \(V\) within disjointed subsets \(V1,V2,...,Vh\), such that if \((u,v)\in E\), where \(u\in V_{i}\) and \(v\in V_{j}\), then \(i>j\). A DAG with a stratification or division by levels is called a stratified digraph._  
**Definition 5**. : _The width of a level \(V_{k}\) is traditionally defined as \(w(V)=\sum_{v\in V_{k}}\), and the width of a stratified digraph (divided into layers or levels) is defined by the equation \(w=max_{1\leq k\leq h}w(V_{k})\)_  
**Definition 6**. : _The height of a vertex is denoted by [6]:_  
\[height(n_{i})=\left\{ \begin{array}{l}0\ if\ PRED(n_{i})=\emptyset\\ \\ 1+max(height(n_{j}))\forall n_{j}\in PRED(n_{i})\text{otherwise}\end{array} \right. \tag{1}\]  
**Definition 7**. : _The set of DAG tasks that represents a synthetic load is denoted by \(\tau=\{\tau_{1},...,\tau_{n}\}\)._  
**Definition 8**. : _The length of the critical path of a DAG task [6], is denoted by_  
\[M=\lceil\frac{\sum W_{n_{i}}}{\text{cp length}}\rceil\]  
_where \(M\) is the minimum number of processors and \(W_{n_{i}}\) is the processing time of task \(i\)._  
**Definition 9**. : _The cost of calculating an execution cost (EC) of a sub-task represented by a node expressed in flops is the cost of executing a sub-task once it is assigned to a processor. The cost of executing the total of the sub-tasks of task \(i\) is expressed as_  
\[\sum_{\forall\tau_{i,j}\in\tau_{i}}EC_{i,j}. \tag{2}\]  
**Definition 10**. : _The cost of communication represented by \(CC_{\tau_{i,j}\rightarrow\tau_{i,k}}\) between sub-tasks \(\tau_{i,j}\) and \(\tau_{i,k}\) is expressed in bytes._  
**Definition 11**. : _Makespan, the length of the scheduling produced by the algorithm, is expressed as_  
\[\text{makespan}=max(FT(n_{i})). \tag{3}\]  
**Definition 12**.