# Parallelization of Array Method with Hybrid Programming: OpenMP and MPI
## 2 Basic Definitions  
Since this work is based on [6; 12], some definitions from those papers appear in this section; furthermore, other definitions are added for this research work. The proposed definitions are referenced in the explanation of the research, the proposed algorithms and the experiments performed.  
**Definition 1**.: _The target system consists of \(C_{l}\) clusters, \(C_{1},C_{2},\ldots,C_{l}\) where \(l\) is the number of clusters contained in the HPC system. Each cluster contains \(m\) heterogeneous processors with \(n\) processing cores or resources. Therefore, \(C_{l,m,n}\) is cluster \(k\), processor \(m\), processing core \(n\)._  
**Definition 2**.: _A PTG can be modeled by a Directed Acyclic Graph (DAG) \(T=(N,E)\) where: \(N=\{n_{i}:i=1,2,\ldots,N\}\) is a set of N vertices or subtasks that constitute the task, and \(E=E_{i,j}:i,j=1,2,\ldots,N\) is a set of E edges. A PTG can be characterized by_  
\[(n_{i},\{1\leq j\geq n_{i}|T_{i}\},G_{i},V_{i},W_{i}) \tag{1}\]  
_where:_  
\(n_{i}\)_: the number of subtasks in_ \(T_{i}\)_:_  
\(\{1\leq j\leq n_{i}|T_{i}\}\) _: the set of subtasks._  
\(G_{i}\)_: the set of directed relationships between the subtasks._  
\(V_{i}\)_: the number of levels of_ \(T_{i}\)_._  
\(W_{i}\)_: the width of each level_ \(T_{i}\) _represented by an array._  
_The PTG consists of a set of N nodes and a set E of edges (directed relationships). The nodes represent execution requirements of the task T. The requirement of each task is represented by \(w_{n_{i}}\). The directed relationships show the flow of execution of subtask \(\tau_{i,j}\) to subtask \(\tau_{i,k}\) of task T\({}_{i}\). Each of the terms used in this definition is explained below._  
**Definition 3**.: _PTG density is the number of links between PTG subtasks. It is represented by:_  
\[|G_{i}|. \tag{2}\]  
_The communication percentage of a task is obtained by counting the total number of edges and the number of subtasks of the PTG._  
**Definition 4**.: _A synthetic workload is constituted by a set of DAG tasks and is denoted by:_  
\[S=T_{1},T_{2},\ldots,T_{n} \tag{3}\]  
_Each \(T_{n}\) consists of a random number of subtasks and a random number of edges. \(n\) is defined in the workload generation algorithm._  
**Definition 5**.: _Let us consider Definition 2 from [12]; it follows that each PTG will request \(\eta_{i}\) resources, which must be extracted from the scheduler's resource array, then the next condition is established:_  
\[\forall\ \eta_{i}\ \exists\ R_{l,m,n}, \tag{4}\]  
_for the PTG to complete its execution._  
**Definition 6**.: _A Levy flight is a type of random walk in which the increments are distributed according to a \"large tail\" probability distribution. Specifically, the distribution used can be approximated by a power law of the form [20]:_  
\[P(l)\ \propto\ l^{-\mu}\ \text{with}\ 1<\mu\leq 3 \tag{5}\]  
_where \(\mu\) is a constant parameter of the distribution known as the exponent or scaling parameter._  
**Definition 7**.: _Consider a software agent \(SA\), which locates any idle \(R_{l,m,n}\) found in any \(C_{l}\) using Equation (2), then registers it in an array of resources, and Condition (1) is satisfied._