# PHEFT: Pessimistic Image Processing Workflow Scheduling for DSP Clusters
## 2 Model
### DSP Cluster  
DSP-clusters consist of \(m\) integrated modules (\(IM\)). Each \(IM_{i}\) contains \(k_{i}\) DPS-processors with their own local memory. Data exchange between DPS-processors of the same \(IM\) is performed through local ports. The exchange of data between DPS-processors from different \(IM\) is performed via external memory, which needs a longer transmission time than through the local ports. The speed of data transfer between processors depends on their mutual arrangement in the cluster.  
Let \(f_{ij}\) be the data rate coefficient from the processor of the \(IM_{i}\) to the processor of \(IM_{j}\). We neglect the communication delay \(\varepsilon\) inside DSP; however, we take into account the communication delay between DSP-processors of the same \(IM\). Data rate coefficients of this communication are represented as a matrix \(D\) of the size \(k_{i}\times\ k_{i}\). We assume that the transmission rates between different \(IM\) are equal to \(\alpha\gg\varepsilon\). Table 1 shows a complete matrix of data rate coefficients for a DSP-cluster with four \(IM\)s.  
The values of the matrix \(D\) depend on the specific communication topology of the \(1M\)s. In Figure 2, we consider three examples of the \(1M_{i}\) communication topology for \(k_{i}=4\).  
Figure 2a shows uni-directional DSP communication. Let us assume that the transfer rate between processors connected by an internal link port is equal to \(\alpha=1\). The corresponding matrix of data rate coefficients is presented in Table 2a. Figure 2b shows bi-directional DSP communication. The corresponding matrix of data rate coefficients is presented in Table 2b. Figure 2c shows all-to-all communication of DSP. Table 2c shows the corresponding data rate coefficients.  
For the experiments, we take into account two models of the cluster (Figure 3). In the cluster \(A\), ports connect only neighboring DSPs, as shown in Figure 3a. In the cluster \(B\), DSPs are connected to each other, as shown in Figure 3b.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**IM** & **1** & **2** & **3** & **4** \\ \hline
1 & \(\varepsilon\) & \(\alpha\) & \(\alpha\) & \(\alpha\) \\
2 & \(\alpha\) & \(\varepsilon\) & \(\alpha\) & \(\alpha\) \\
3 & \(\alpha\) & \(\alpha\) & \(\varepsilon\) & \(\alpha\) \\
4 & \(\alpha\) & \(\alpha\) & \(\alpha\) & \(\varepsilon\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Data rate coefficients of the cluster of DSP with four integrated modules (IMs).  
\begin{table}
\begin{tabular}{c c c c|c c c|c c c c} \hline \hline \multicolumn{2}{c|}{**(a) Uni-Directional**} & \multicolumn{4}{c|}{**(b) Bi-Directional**} & \multicolumn{4}{c}{**(c) All to All**} \\ \hline
1 & 2 & 3 & 0 & 1 & 2 & 1 & 0 & 1 & 1 & 1 & 0 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Data rate coefficient matrix \(D\) for three communication topologies between DSP-processors.  
Figure 3: DSP cluster configuration. (**a**) Cluster \(A\); (**b**) Cluster \(B\).  
Figure 2: Examples of communication topology of DSP-processors: (**a**) uni-directional; (**b**) bi-directional; (**c**) all to all.  
_IM_s are interconnected by a bus. In the current model, for each connection, different data transmission coefficients are used. Data transfer within the same DSP has a coefficient of 0, between adjacent DSPs in a single \(IM\) has a coefficient of 1, and between \(IM\)s, has a data transmission coefficient of 10.