# Improved Scheduling Algorithm for Synchronous Data Flow Graphs on a Homogeneous Multi-Core Systems
## 4 SDAG Model and HSDFG Scheduling  
### SDAG Computational Model  
We have added a communication method and a data-driven mechanism to the DAG model, i.e., SDAG, which not only has the architecture-independent advantages of DAG, but also the data-driven advantages of the data flow computational model. In this subsection, we focus on the communication approach and the data-driven mechanism. There are two actors \(A\) and \(B\), and an SDFG consisting of a directed edge, as shown in Figure 2(a). The production rate of port \(A\) is \(s(A)=1\), and the consumption rate of port \(B\) is \(r(B)=2\). According to the balancing Equation (1), at the minimum period, \(A\) needs to execute 2 times to satisfy the data demand of \(B\). A needs to create 2 instances (\(A_{1}\) and \(A_{2}\)) and \(B\) needs to create only 1 instance (\(B_{1}\)) to construct the HSDFG as shown in Figure 3(b). In SDAG, each directed edge in the SDFG corresponds to a FIFO queue of finite capacity. We assume that there are two instances of \(\alpha_{1}\) and \(\alpha_{2}\), and a directed edge connecting these two instances. The predecessor instance is \(\alpha_{1}\), and the successor instance is \(\alpha_{2}\), and the directed edge is a FIFO queue with a shared memory area. Both \(\alpha_{1}\) and \(\alpha_{2}\) have only one port, the output port rate of \(\alpha_{1}\) is \(s(\alpha_{1})\), the input port rate of \(\alpha_{2}\) is \(r(\alpha_{2})\). Data communication between \(\alpha_{1}\) and \(\alpha_{2}\) is achieved through a FIFO queue with the following constraints on the operation of the FIFO queue. \(\alpha_{1}\) performs an _enqueue_ operation on the FIFO queue after execution is complete, and \(\alpha_{2}\) performs a _dequeue_ operation on the FIFO queue during execution. The data-driven mechanism is based on the FIFO queue. We set a threshold constant \(thd\) and a queue capacity variable \(caps\) for the FIFO queue, with the \(caps\) variable being jointly maintained by \(\alpha_{1}\) and \(\alpha_{2}\). The threshold constant \(thd\) and the queue capacity variable \(caps\) are defined as follows:  
\[thd=r(\alpha_{2}) \tag{6}\]  
\[caps=caps+s(\alpha_{1}) \tag{7}\]  
\[caps=caps-r(\alpha_{2}) \tag{8}\]  
After \(\alpha_{1}\) has finished updating the \(caps\) variable, when Equation (9) is satisfied, \(\alpha_{1}\) will access the waiting queue (Figure 5) to see if \(\alpha_{2}\) has been created. If not, \(\alpha_{2}\) is created, the  
Figure 4: (**a**) SDFG, (**b**) HSDFG converted form (**a**). status of the port corresponding to \(\alpha_{2}\) is set to available and \(\alpha_{2}\) is placed in the waiting queue. After each instance is created, a status variable is also created for each input port of the instance and initialised to unavailable. If so, the state of the port corresponding to \(\alpha_{2}\) is updated. If \(\alpha_{2}\) has more than one input port, \(\alpha_{2}\) is created whenever one of them satisfies Equation (9). \[caps\geqslant thd \tag{9}\]  
The memory overhead can be excessive when creating a FIFO queue for each directed edge in the HSDFG. Therefore, we specify that instances created by the same actor share a FIFO queue, e.g., \(A_{1}\) and \(A_{2}\) in Figure 2b share a FIFO queue. To ensure consistency in reading data from the FIFO queue, a \"pass lock\" is set for both the enqueue and dequeue operations. The \"pass lock\" specifies the instance that can open the lock, and the instance cannot perform an enqueue or dequeue operation until the \"pass lock\" is opened. After the current instance has completed its queuing operation, the lock is set to be opened by the next instance in order of instance number, i.e., passed to the next instance. The last instance passes the lock to the first instance. The \"pass lock\" defaults to the first instance being able to open it at the initial stage. An overview of the SDAG model is shown in Figure 5, where instance \(B_{1}\) is created using a data-driven mechanism and then \(B_{1}\) is added to the waiting queue.