# Improved Scheduling Algorithm for Synchronous Data Flow Graphs on a Homogeneous Multi-Core Systems
## 2 SDFG Background  
As shown in Figure 2, an SDFG can be represented by a directed graph. Where the vertices represent computational tasks, also called _actors_. The actors have input and output ports, and the ports have data block processing rates, which are called _tokens_. The number of tokens consumed by the input port once the actor is executed is called _consumption rate_, similarly, the output port corresponds to _production rate_. In the synchronous data flow computational mode [2], the port rate of the actor is determined. The memory where the tokens are stored is called the _data buffer_ (or called _channel_) and is implemented as a FIFO queue, which also specifies the data dependencies between the two actors, with the head of the queue connecting the actor's input port and the tail of the queue connecting the actor's output port. Assume that the precursor actor is \(A\), the successor actor is \(B\), \(B\) depends only on \(A\), and both \(A\) and \(B\) have only one port. _Minimum execution period_ indicates that all actors in the SDFG are executed at least once. In a minimum execution period, the number of executions of \(A\) is \(q_{A}\), the number of executions of \(B\) is \(q_{B}\), the production rate of port \(A\) is \(s(A)\), the consumption rate of port \(B\) is \(r(B)\), the balancing equation of Equation (1) can be constructed. \[q_{A}s(A)=q_{B}r(B) \tag{1}\]  
where \(s(A)\) and \(r(B)\) are known and \(s(A),r(B)\in\mathbb{N}^{+}\), then an infinite number of solutions \((q_{A},q_{B})\) can be solved. With the minimum execution period, we take the minimum positive integer solution as the number of executions for actor \(A\) and actor \(B\). In SDFG, each of the two actors with data dependencies constructs a balancing equation, and we represent the solution obtained for each actor in SDFG by a solution vector \(q=(q_{1},q_{2},q_{3},\ldots)\). If there is no solution, or if a positive integer solution cannot exist, the SDFG is said not to satisfy the consistency condition and cannot be scheduled for execution. Otherwise, we take the minimum positive integer solution as the number of times each actor has to be executed at its minimum period, which is referred to as the unit period in the following. Figure 2: An example of SDFG. We represent an SDFG using the tuple \((V,E)\), where \(V=\alpha_{1},\alpha_{2},\ldots,\alpha_{n}\) denotes the set containing \(n\) actors, \(\alpha_{i}\), \(i=1\ldots n\) denotes actor \(i\), \(E=e_{1},e_{2},\ldots,e_{k}\subseteq V\times V\) denotes the set containing \(k\) directed edges, and \(e_{i},i=1,\ldots,k\) denotes the \(i\)-th directed edge. Use \(src(e_{i})\) to denote the production rate of directed edge \(e_{i}\) arc-tailed actors and \(des(e_{i})\) to denote the consumption rate of directed edge \(e_{i}\) arc-headed actors. The SDFG is represented using a topological matrix similar to the correlation matrix [3], where the rows represent directed edges and the columns represent actors, generating a \(k\times n\) matrix with \(k\) directed edges and \(n\) actors. The topological matrix element \((i,j)\) is given the value rule as in Equation (2). \[(i,j)=\left\{ \begin{array}{ll}\text{src}(e_{i}),\text{ if the actor of arc tail of }e_{i}\text{ is }\alpha_{j}\\ -\text{des}(e_{i}),\text{ if the actor of arc head of }e_{i}\text{ is }\alpha_{j}\\ 0,\text{ other}\end{array} \right. \tag{2}\]  
Thus, the topological matrix \(\Gamma\) for the example in Figure 1 can be obtained as (3):  
\[\Gamma=\left[ \begin{array}{ccc}c&-e&0\\ d&0&-f\\ 0&i&-g\end{array} \right] \tag{3}\]  
With the help of the topological matrix \(\Gamma\), we use Equation (4) to solve for the vector \(q\). \[\Gamma q=0 \tag{4}\]  
The sufficient condition for the existence of a minimum positive integer solution to Equation (4) is \(rank(\Gamma)=n-1\), where \(n\) is the number of actors in the SDFG. The corresponding number of instances of actors is created based on the \(q\) vector, and these instances are then constructed as an HSDFG.