# Improved Scheduling Algorithm for Synchronous Data Flow Graphs on a Homogeneous Multi-Core Systems
## 2 SDFG Background
#### Construction of the HSDFG Algorithm  
In an SDFG, there is a directed cyclic structure, such as Figure 2(a), where there is a directed cyclic ring in the directed graph. To avoid deadlocks, a cache of data, denoted \"1D\", is placed on the directed edge between actor B and actor C. Similarly, 2 caches of data, denoted \"2D\", are placed between actor C and actor A. In order to break this ring structure and to more naturally represent the parallelism between instances, we transform the SDFG into an HSDFG, i.e., a DAG, which in turn transforms the object of our study into a vertex in the DAG, without taking into account some of the properties of the SDFG.  
Dataflow programs are periodic programs, so in converting to HSDFG we can consider the HSDFG constructed by all instances under a unit period, and we can also consider instances under multiple periods. We denote this variable by \(J\). If \(J=1\), it denotes the HSDFG constructed by all instances under the unit period, as in Figure 2(b). If \(J=2\), it denotes the HSDFG constructed for all instances under two periods, as in Figure 2(c).  
To describe the construction of the HSDFG algorithm, we first define some notation. \(j\) values, a repeat execution vector \(p\), a random sequence of actors \(node\_r\), a set of predecessor actors for each actor, and a topology matrix \(\Gamma\). b(0) then denotes the state of the cache queue at the initial moment. \(j_{p}\) denotes the scheduling count vector for all actors, where \(j_{-}p_{\alpha}\) denotes the scheduling count for the actor \(\alpha\). \(count_{t}\) denotes the vector of instantiation counts for all actors, where \(count\_{t}\_{\alpha}\) denotes the number of instantiations of the actor \(\alpha\). A detailed description is shown in Algorithm 1.  
```
Input:SDFG Output: HSDFG
1:\(j\_p=j*p\), \(count_{t}=O\), \(O\) is zero vector.
2: Iterate over the actor \(\alpha\) in the sequence \(node\_r\)
3: IF \(count\_t_{\alpha}==j\_p_{\alpha}\), then perform Step 2, else perform Step 4.
4: Calculate \(b+\Gamma v_{\alpha}\) to judge whether the actor \(\alpha\) can be executed. If not, perform Step 2. If so, \(count\_t_{\alpha}\gets count\_t_{\alpha}+1\), and create the \(count\_t_{\alpha}\)-th instance \(ins\_{-\alpha}\). Then add to the instance sequence \(apg\_ins\).
5: Check whether the precursor set of the actor \(\alpha\) has elements. If not, perform Step 9. Else perform Step 6.
6: Iterate through the precursor actor set of the actor \(\alpha\) to obtain the precursor actor \(\eta\) and the connected directed edge \(a\).
7: Calculate \(d\) value, using \(d=\left\lceil\frac{-j\Gamma_{\alpha}-b(0)_{\alpha}}{\Gamma_{\alpha}}\right\rceil\). If \(d<0\), then \(d=0\). Establish a precursor relationship between the first \(d\) instances of actor \(\eta\) and instance \(ins\_{-\alpha}\).
8: Update \(b\gets b+\Gamma v_{\alpha}\). If the current traversal is not complete, perform Step 2; else, preform Step 9.
9: For all actors, if \(count\_t==j\_p\), then algorithm is terminated. Else perform Step 2 and start a new round of traversal.
```  
**Algorithm 1**Constructing the HSDFG