# Improved Scheduling Algorithm for Synchronous Data Flow Graphs on a Homogeneous Multi-Core Systems
## 1 Introduction  
In recent years, parallel computing has been widely popular in areas such as high-performance computing and deep learning. Streaming programs are one such class of computational tasks, which are widely popular in areas such as digital signal processing and multimedia [1]. SDFGs are an abstract representation of streaming applications. Where vertices represent tasks, directed edges represent dependencies between tasks, and vertices are also called _actors_. There is usually a directed loop structure in the SDFG, which needs to be converted into an HSDFG (Homogeneous SDFG). HSDFG is a special case of SDFG. The common scheduling algorithm for SDFG is static scheduling [2]. In static scheduling, all information in the computational graph is known at the compilation stage. Static scheduling algorithms are divided into two main categories based on the scheduling object, namely, SDFG oriented and HSDFG oriented. SDFG-oriented scheduling algorithms study how to schedule actors in the original computational graph. HSDFG-oriented scheduling algorithms study the _instances_ of actors. Instances are the execution units of an actor and have the same methods and properties as the actor, and different instances of the same actor process different data. Both SDFG-oriented and HSDFG-oriented algorithms are algorithms for scheduling SDFG. We use the algorithm in [3] to convert SDFG to HSDFG. HSDFG can be represented using the DAG model [4]. The study's object of our algorithm is HSDFG oriented. Among the shared storage computational models, the current computational model commonly used by parallel machines is APRAM [5]. The data flow model has a naturallyparallel representation compared to the APRAM computational model, which uses synchronization barriers to implement delayed waits, and must wait until all threads in a superstep have finished executing before synchronizing. A large part of the overhead in the APRAM model is in the delayed wait part, where the completion of the execution of a superstep depends on the thread with the longest execution time in that superstep. In the data-flow computing model, most methods of synchronization between tasks use peer-to-peer communication rather than using coarse-grained methods of synchronization barriers. The Codelet [6] model is a data flow execution model applied to the von Neumann model. In this model, each non-preemptive task is the basic unit of scheduling and execution and is called a \"codelet\". All codelets are connected together to form a codelet graph. In the codelet graph, each codelet plays the role of a producer and/or a consumer. Corresponding to the SDFG model, each vertex is also called an actor, which has an input and output port attribute, and a port has a rate attribute. The port rate indicates the rate at which the actor produces/consumes data per execution. In the Codelet runtime model, each codelet has three states. Codelets are called dormant when they are waiting for their dependencies to be satisfied. When all dependencies are satisfied it is called the executable state, at which point the codelet is ready to be dispatched. When the codelet is dispatched to the processor core it is called the ignition state. Although the DAG model can represent the HSDFG, the DAG model lacks a data-driven mechanism. To address this challenge, this paper adds a peer-to-peer communication and data-driven mechanism based on the DAG model, called SDAG (Super DAG), in which the communication between two instances is implemented through a specific FIFO (First-In, First-Out) queue. Further, we analyze the current HSDFG scheduling algorithm, PAPS [3] (Figure 0(b)). We propose an improved HSDFG scheduling algorithm, LSEFT (Figure 0(c)). The PAPS is a Hu-level [7] based scheduling algorithm, where each instance has a level value (Figure 0(a)) top left corner of the vertex). Level value indicates the sum of the execution times of the instances contained in the longest path from the current instance to the endpoint instance.