## 4 Array Method
### Task Scheduling Phase
#### 4.1.3 The Allocation Matrix  
**Definition 17**. : _The allocation matrix is a dynamic matrix that grows or decreases as the search for resources for the PTGs is carried out._  
This array is composed of the following columns. * System processors with their number of cores, according to Definition 1 in Section 2. * PTG sub-task identifier according to Definition 2 in Section 2. The procedure for filling the allocation matrix is as follows. With the characteristics matrix of the PTGs, it is possible to start the process of searching for the resources in the HDCS, which performs the filling of the characteristics matrix. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**DAG ID** & **DAG Paths** & **Path Nodes** & **Number Level** & **Nodes Per Level** & **DAG Density** \\ \hline
1 & 1 & ABDF & 1 & 2 & 0-1 \(\rightarrow\) 2 \\
1 & 2 & ABEF & 2 & 2 & 1-2 \(\rightarrow\) 3 \\
1 & 3 & ACF & & & 2-3 \(\rightarrow\) 2 \\
2 & 1 & ABF & 1 & 4 & 0-1 \(\rightarrow\) 4 \\
2 & 2 & ABCF & & & 1-2 \(\rightarrow\) 4 \\
2 & 3 & ABCDF & & & \\
2 & 4 & ABCDEF & & & \\
2 & 5 & ACF & & & \\
2 & 6 & ACDF & & & \\
2 & 7 & ACDEF & & & \\
2 & 8 & ADF & & & \\
2 & 9 & ADEF & & & \\
2 & 10 & AEF & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Characteristics matrix of the Parallel Task Graphs (PTGs) from Figures 2 and 3. Figure 3: A second six-node DAG task. Figure 2: A first six-node Directed Acyclic Graph (DAG) task. The sub-task to a resource is allocated based on the characteristics of the PTGs, which, in the execution of the algorithm, are called search criteria. The following paragraphs describe in detail how the algorithm proceeds to search the resources in the HDCS. The first search criterion is the PTG paths. The resource allocation process is started using each of the routes in the DAG considering the first path in the characteristics matrix (column 2 DAG paths, Table 2) as the critical path with the highest allocation priority; the rest of the paths are considered subcritical paths by the algorithm. The vertices of the PTG that constitute the critical path are trimmed, and then each of the subcritical paths is trimmed. The algorithm checks the processing cores in each processor with the number of nodes in each path. Depending on the number of nodes in the path, it looks for a processor with a number equal to or less than the number of nodes in the path. If the number of nodes in the path is greater than the maximum number of cores than one (or more) of the system processors, then it applies the divide and conquer method: it divides the number of nodes in the path by two, rounds down to the lowest number, and then looks again for a processor with the number of nodes obtained with the division. If, with this division, it is not possible to cover the number of nodes in the path again, the two results are again divided by two. This condition ends when it obtains a number of nodes that can be covered by the number of processor cores in the system. When a PTG sub-task is likely to be allocated to the resource in the row, the column is marked with a value of 1, indicating the processor as a candidate to contain the sub-task. The algorithm seeks to allocate one sub-task per processing core, which avoids overloading threads or processes in each core. The allocation matrix is updated if a processor is located for the sub-task; the update occurs with the PTG sub-tasks and the cores of each processor as follows. If a processor meets the condition of the number of cores equal to or less than the number of nodes in the path, then this processor is placed in the allocation matrix, indicating which DAG nodes will be allocated to that processor. This allocation of cores to nodes indicates how many nodes of the DAG will remain in the same cluster for processing and how many nodes of the DAG must be placed in other clusters. With the diversity of clusters where the nodes are allocated, the distance is calculated to determine the communication load. Definition 10 (overhead) is used to generate the task during its processing.