## 5 The PMOD Scheduler
### Transforming the Class Table into a Scheduling Matrix  
This transformation requires two steps. **Step 1: Transform CT to a Single Index Matrix**  
The first step transforms the CT to a single-index matrix (\(SIM\)). Each row of \(SIM\) describes a communication step based entirely on a single class. The communicating pairs of each class \(k\) reside in row \(k\) of the CT. We simply pick each communicating node pair \((n,q)\) found in row \(k\) and place the value of \(q\) in column \(n\) of \(SIM\). In our example, the CT will be transformed into the following \(SIM\) matrix. \[ \begin{array}{ccccccccc}\textbf{Communicating Step}&N_{0}&N_{1}&N_{2}&N_{3}&N_{4}&N_{5}\\ 0&0&2&4&0&2&4\\ 1&1&3&5&1&3&5\\ 2&2&4&0&2&4&0\\ 3&3&5&1&3&5&1\\ 4&4&0&2&4&0&2\\ 5&5&1&3&5&1&3\\ \end{array} \]  
**Step 2: Mix Class Elements to Define Communicating Steps**  
Our scheduler requires that each communicating step requires \(Q\) communications. If each class includes \(\alpha\) communications towards different destinations, we have to mix elements between \(Q/\alpha\) homogeneous classes, \(\alpha\geq 2\). To mix class elements, we simply interchange \(\alpha\) elements of homogeneous classes that reside in corresponding columns. In our example, \(\alpha=3\); thus, we interchange three elements in columns \(N_{3}-N_{5}\) of the homogeneous classes 0; 1, 2 and 3; and 4 and 5. This will produce the following scheduling matrix, \((SM)\): \begin{tabular}{c c c c c c c c}
**Communicating Step** & \(N_{0}\) & \(N_{1}\) & \(N_{2}\) & \(N_{3}\) & \(N_{4}\) & \(N_{5}\) & **Communication Cost** \\
0 & 0 & 2 & 4 & 1 & 3 & 5 & **2** \\
1 & 1 & 3 & 5 & 0 & 2 & 4 & **3** \\
2 & 2 & 4 & 0 & 3 & 5 & 1 & **4** \\
3 & 3 & 5 & 1 & 2 & 4 & 0 & **5** \\
4 & 4 & 0 & 2 & 5 & 1 & 3 & **4** \\
5 & 5 & 1 & 3 & 4 & 0 & 2 & **5** \\ \end{tabular}   
The communication cost for each step is computed based on the maximum cost, \(\ell_{\max}\), found between the the communicating pairs. For example, in step 0, there is a communication between nodes 2 and 4 and between nodes 3 and 1. Thus, \(\ell_{max}=|2-4|=|3-1|=2\). The remaining \(\ell\) values are \(|0-0|=0\), \(|1-2|=1\), \(|4-3|=1\) and \(|5-5|=0\) (internal communication between tasks residing in node 5). Since all the communications start simultaneously, the latency of this step is dictated by \(\ell_{\max}\), so it equals 2. Similarly, we obtain all the costs for the other communication steps. Thus, the total communication cost for all the steps is the sum of the communication costs of the six communication steps, which is 23. Our third scheduling step aims to reduce this cost. The following proposition gives the theoretical approximation of the communication costs that exist within the \(SM\). Proposition 2: _The total cost of the communications, \(\mathcal{C}_{SM}\), which are defined in the \(SM\) can be approximated by the following equation:_  
\[\mathcal{C}_{SM}=2(Q-1)+2(Q-2)+\chi_{1}(Q-3)+\chi_{2}(Q-4)+\dots+\chi_{\
u}(Q-1) \tag{11}\]  
Proof: By mixing class elements (Step 2), we guarantee that all the communications are performed between different source and target nodes (see the \(SM\) matrix). We know that, in a set of \(Q^{2}\) communications, the latency values \(\ell_{q},\ q\in[0,\dots,Q-1]\), and the number of communicating pairs that are characterized by \(\ell_{q}\) are as shown in Table 2:  
For example, with \(Q=6\), there are two pairs with a cost of \(Q-1=5\) ((5,0) and (0,5)) and six pairs with a cost of 0 (internal node communications; (0,0), (1,1), (2,2), (3,3), (4,4), and (5,5)). Additionally, there are 10 pairs with a cost of 1, eight pairs with a cost of 2, six pairs with a cost of 3 and four pairs with a cost of 4. Because of the way the \(SM\) is generated (different source and target indices per communication step), these pairs are, on average, equally distributed in the initial scheduling matrix. Specifically, each row of the \(SM\) has \(\alpha\) elements from \(Q/\alpha\) classes.