# Improved Scheduling Algorithm for Synchronous Data Flow Graphs on a Homogeneous Multi-Core Systems
## 4 SDAG Model and HSDFG Scheduling
### HSDFG Scheduling  
#### 4.3.1 Problem Definition  
HSDFG scheduling is a static scheduling, which allows all tasks to be scheduled during the compilation phase, and therefore HSDFG scheduling simulates the process of execution. First, we introduce the basic notations related to hardware and software, as shown in Table 1.  
A data flow application consists of a series of periodic instances. These instances are represented using the HSDFG and we only consider instance scheduling per unit period. The HSDFG is denoted by a tuple \((V,E)\), \(V=\{\alpha_{1},\alpha_{2},\ldots,\alpha_{n}\}\) denoting the set containing \(n\) instances, \(\alpha_{i}\) is the instance ID, \(i=1,\ldots,n\), and \(W(\alpha_{i})\) is the size of \(\alpha_{i}\). \(\alpha_{i}\) has the set of input channels \(IN(\alpha_{i})\) and the set of output channels \(OUT(\alpha_{i})\), where \(IN(\alpha_{i})=\{I_{1}^{\alpha_{i}},I_{2}^{\alpha_{i}},\ldots\}\), \(I_{j}^{\alpha_{i}}\) is the ID of the input channel of \(\alpha_{i}\), \(j=1,2,\ldots,r(I_{j}^{\alpha_{i}})\) denotes the tokens consumption rate of \(I_{j}^{\alpha_{i}}\), and \(OUT(\alpha_{i})=\{O_{1}^{\alpha_{i}},O_{2}^{\alpha_{i}},\ldots\}\), \(O_{j}^{\alpha_{i}}\) is the ID of the output channel of \(\alpha_{i}\), \(s(O_{j}^{\alpha_{i}})\) denotes the tokens production rate of \(O_{j}^{\alpha_{i}}\). From the SDAG model, the total number of tokens consumed \(sum(tokens)\) per unit period and the minimum space of the FIFO cache queue \(min(FIFO)\) are defined as follows. \[sum(tokens)=\sum_{i=1}^{n}\sum_{I^{\alpha_{i}}\in IN(\alpha_{i})}r(I^{\alpha_ {i}}) \tag{12}\] \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Description** \\ \hline \(\alpha\) & An instance in set \(V\) \\ \(W(\alpha)\) & The size of the instance \(\alpha\) \\ \(IN(\alpha)\) & The set of input channels of the instance \(\alpha\) \\ \(OUT(\alpha)\) & The set of output channels of the instance \(\alpha\) \\ \(I^{\alpha}\) & The ID of input channel of the instance \(\alpha\) \\ \(O^{\alpha}\) & The ID of output channel of the instance \(\alpha\) \\ \(r(I^{\alpha})\) & The token producing rate of instance \(\alpha\) of channel \(I^{\alpha}\) \\ \(s(O^{\alpha})\) & The token consuming rate of instance \(\alpha\) of channel \(O^{\alpha}\) \\ \(et(\alpha)\) & The execution time of the instance \(\alpha\) \\ \(e\) & A channel in set \(E\) \\ C & A set of all processing cores \\ c & A processing core in \(C\) \\ \(p(c)\) & The performance of processing core \(c\) \\ \(M\) & The number of processing cores \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Basic Notations. \[min(FIFO)=\sum_{i=1}^{n}\sum_{O^{i}\in OUT(\alpha_{i})}s(O^{\alpha_{i}}) \tag{13}\]  
\(E=\{e_{1},e_{2},\ldots,e_{k}\}\in V\times V\) denotes the set containing \(k\) directed edges and \(e_{i}\) is the directed edge ID, \(i=1,\ldots,k\). We use \(c_{i}(i=1,2,\ldots)\) to denote the ID of the processor cores. For homogeneous multi-core systems, each ID is associated with a logical core. \(p(c_{i})\) denotes the performance of the processor core \(c_{i}\), and since the processor cores are homogeneous, we use \(p(c)\) denote the performance of the processor. \(et(\alpha_{i})\) denotes the execution time of the instance \(\alpha_{i}\) at the processor core, including the FIFO queue operation time \(L\), which is defined as follows. \[et(\alpha_{i})=\frac{W(\alpha_{i})}{p(c)}+L \tag{14}\]  
As instances communicate with each other in shared memory and instances are created sequentially, the FIFO queue operation time and \"pass lock\" time are very short compared to the execution time of instance \(\alpha_{i}\), so we use a constant \(L\) to represent the FIFO queue operation time for all instances. \(U(c_{i})\) denotes all instances of \(c_{i}\) assigned to the processor. \(cl(c_{i})\) denotes the finish time at which processor \(c_{i}\) has executed all instances in \(U(c_{i})\).