{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:50:41Z","timestamp":1760151041326,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"State Key Laboratory of Complex Electromagnetic Environment Effects on Electronics and Information System; Sichuan Science and Technology Program; Fundamental Research  Funds for the Central Universities in China;","award":["CEMEE2018K0302B;2020YFG0059;ZYGX2019J128"],"award-info":[{"award-number":["CEMEE2018K0302B;2020YFG0059;ZYGX2019J128"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In order to accelerate the execution of streaming applications on multi-core systems, this article studies the scheduling problem of synchronous data flow graphs (SDFG) on homogeneous multi-core systems. To describe the data flow computation process, we propose the SDAG (Super DAG) computation model based on the DAG model combined with data-driven thoughts. Further, we analyze the current common SDFG scheduling algorithms and propose an improved SDFG scheduling algorithm, LSEFT (level-shortest-first-earliest-finish time). The LSEFT algorithm uses an inverse traversal algorithm to calculate the priority of tasks in the task-selection phase; the shortest-job-priority earliest-finish-time policy is used in the processor selection phase to replace the original long job priority policy. In the experimental part, we designed an SDFG random generator and generated 958 SDFGs with the help of the random generator as test cases to verify the scheduling algorithm. The experimental results show that our improved algorithm performs well for different numbers of processor cores, especially for 8 cores, where the speedup of our improved algorithm improves by 10.17% on average.<\/jats:p>","DOI":"10.3390\/a15020056","type":"journal-article","created":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T21:19:06Z","timestamp":1644441546000},"page":"56","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Improved Scheduling Algorithm for Synchronous Data Flow Graphs on a Homogeneous Multi-Core Systems"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9072-8446","authenticated-orcid":false,"given":"Lei","family":"Wang","sequence":"first","affiliation":[{"name":"Research Institute of Electronic Science and Technology, University of Electronic Science and Technology of China, Chengdu 611731, China"},{"name":"State Key Laboratory of Complex Electromagnetic Environment Effects on Electronics and Information System, Luoyang 471000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7859-0296","authenticated-orcid":false,"given":"Chenguang","family":"Wang","sequence":"additional","affiliation":[{"name":"Research Institute of Electronic Science and Technology, University of Electronic Science and Technology of China, Chengdu 611731, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huabing","family":"Wang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Complex Electromagnetic Environment Effects on Electronics and Information System, Luoyang 471000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1495","DOI":"10.1109\/TCAD.2013.2265852","article-title":"Schedule-Extended Synchronous Dataflow Graphs","volume":"32","author":"Damavandpeyma","year":"2013","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1109\/PROC.1987.13876","article-title":"Synchronous data flow","volume":"75","author":"Lee","year":"1987","journal-title":"Proc. IEEE"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/TC.1987.5009446","article-title":"Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing","volume":"100","author":"Lee","year":"1987","journal-title":"IEEE Trans. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1096","DOI":"10.1007\/s11390-019-1962-4","article-title":"Degree-of-node task scheduling of fine-grained parallel programs on heterogeneous systems","volume":"34","author":"Lin","year":"2019","journal-title":"J. Comput. Sci. Technol."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Cole, R., and Zajicek, O. (1989, January 18\u201321). The APRAM: Incorporating Asynchrony into the PRAM Model. Proceedings of the First Annual ACM Symposium on Parallel Algorithms and Architectures, Santa Fe, NM, USA. SPAA\u201989.","DOI":"10.1145\/72935.72954"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Suettlerlein, J., Zuckerman, S., and Gao, G.R. (2013, January 26\u201330). An implementation of the codelet model. Proceedings of the European Conference on Parallel Processing, Aachen, Germany.","DOI":"10.1007\/978-3-642-40047-6_63"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1287\/opre.9.6.841","article-title":"Parallel sequencing and assembly line problems","volume":"9","author":"Hu","year":"1961","journal-title":"Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Horspool, R.N. (2002). StreamIt: A Language for Streaming Applications. Compiler Construction, Springer.","DOI":"10.1007\/3-540-45937-5"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1993","DOI":"10.3724\/SP.J.1016.2013.01993","article-title":"COStream: A language for dataflow application and compiler","volume":"36","author":"Zhang","year":"2013","journal-title":"Chin. J. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1145\/27633.28055","article-title":"Dataflow Machine Architecture","volume":"18","author":"Veen","year":"1986","journal-title":"ACM Comput. Surv."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1109\/TC.1982.1675922","article-title":"Wavefront Array Processor: Language, Architecture, and Applications","volume":"100","author":"Kung","year":"1982","journal-title":"IEEE Trans. Comput."},{"key":"ref_12","unstructured":"J\u00e9J\u00e9, J. (1992). An Introduction to Parallel Algorithms, Addison-Wesley."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Dorostkar, F., and Mirzakuchaki, S. (2019, January 24\u201325). List Scheduling for Heterogeneous Computing Systems Introducing a Performance-Effective Definition for Critical Path. Proceedings of the 2019 9th International Conference on Computer and Knowledge Engineering (ICCKE), Mashhad, Iran.","DOI":"10.1109\/ICCKE48569.2019.8964738"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1109\/TASE.2019.2918691","article-title":"MOELS: Multiobjective Evolutionary List Scheduling for Cloud Workflows","volume":"17","author":"Wu","year":"2020","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Djigal, H., Feng, J., and Lu, J. (2020, January 11\u201314). Performance Evaluation of Security-Aware List Scheduling Algorithms in IaaS Cloud. Proceedings of the 2020 20th IEEE\/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGRID), Melbourne, Australia.","DOI":"10.1109\/CCGrid49817.2020.00-60"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Bo, Y., Benfa, Z., Feng, L., Xiaoyu, Z., Xinjuan, L., Fang, W., and Zhitao, Z. (2021, January 29\u201331). List scheduling algorithm of improved priority with considering load balance. Proceedings of the 2021 IEEE International Conference on Data Science and Computer Application (ICDSCA), Haikou, China.","DOI":"10.1109\/ICDSCA53499.2021.9650131"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Suzuki, M., Ito, M., Hashidate, R., Takahashi, K., Yada, H., and Takaya, S. (2020, January 1\u201315). Fundamental Study on Scheduling of Inspection Process for Fast Reactor Plants. Proceedings of the 2021 2020 9th International Congress on Advanced Applied Informatics (IIAI-AAI), Tokyo, Japan.","DOI":"10.1109\/IIAI-AAI50415.2020.00157"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"119082","DOI":"10.1109\/ACCESS.2019.2936004","article-title":"Parallel-Batch Scheduling with Deterioration and Group Technology","volume":"7","author":"Miao","year":"2019","journal-title":"IEEE Access"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Hu, Z., Li, D., Zhang, Y., Guo, D., and Li, Z. (2019, January 24\u201325). Branch Scheduling: DAG-Aware Scheduling for Speeding up Data-Parallel Jobs. Proceedings of the 2019 IEEE\/ACM 27th International Symposium on Quality of Service (IWQoS), Phoenix, AZ, USA.","DOI":"10.1145\/3326285.3329071"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1109\/TASE.2020.2969469","article-title":"Multiobjective Differential Evolution Algorithm for Solving Robotic Cell Scheduling Problem with Batch-Processing Machines","volume":"18","author":"Wu","year":"2021","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Moi, S.H., Yong, P.Y., and Weng, F.C. (2021, January 23\u201326). Genetic Algorithm Based Heuristic for Constrained Industry Factory Workforce Scheduling. Proceedings of the 2021 7th International Conference on Control, Automation and Robotics (ICCAR), Singapore.","DOI":"10.1109\/ICCAR52225.2021.9463323"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Yang, S., and Xu, Z. (2021, January 12\u201314). Intelligent Scheduling for Permutation Flow Shop with Dynamic Job Arrival via Deep Reinforcement Learning. Proceedings of the 2021 IEEE 5th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), Chongqing, China.","DOI":"10.1109\/IAEAC50856.2021.9390893"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"20493","DOI":"10.1109\/ACCESS.2021.3054725","article-title":"Parallel Scheduling of Multiple SDF Graphs Onto Heterogeneous Processors","volume":"9","author":"Jeong","year":"2021","journal-title":"IEEE Access"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Bonfietti, A., Benini, L., Lombardi, M., and Milano, M. (2010, January 8\u201312). An efficient and complete approach for throughput-maximal SDF allocation and scheduling on multi-core platforms. Proceedings of the 2010 Design, Automation Test in Europe Conference Exhibition (DATE 2010), Dresden, Germany.","DOI":"10.1109\/DATE.2010.5456924"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2956232","article-title":"Reducing the Complexity of Dataflow Graphs Using Slack-Based Merging","volume":"22","author":"Ali","year":"2017","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1023\/A:1020307222052","article-title":"Intermediate representations for design automation of multiprocessor DSP systems","volume":"7","author":"Bambha","year":"2002","journal-title":"Des. Autom. Embed. Syst."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2997644","article-title":"Worst-Case Response Time Analysis of a Synchronous Dataflow Graph in a Multiprocessor System with Real-Time Tasks","volume":"22","author":"Choi","year":"2017","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2997645","article-title":"Multiprocessor Scheduling of a Multi-Mode Dataflow Graph Considering Mode Transition Delay","volume":"22","author":"Jung","year":"2017","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"ref_29","first-page":"1","article-title":"Symbolic Analyses of Dataflow Graphs","volume":"22","author":"Bouakaz","year":"2017","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"ref_30","unstructured":"Stuijk, S., Geilen, M., and Basten, T. (2006, January 28\u201330). SDF3: SDF For Free. Proceedings of the Sixth International Conference on Application of Concurrency to System Design (ACSD\u201906), Turku, Finland."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"140171","DOI":"10.1109\/ACCESS.2020.3013013","article-title":"Latency Evaluation of SDFGs on Heterogeneous Processors Using Timed Automata","volume":"8","author":"Rajadurai","year":"2020","journal-title":"IEEE Access"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/56\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:16:43Z","timestamp":1760134603000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,9]]},"references-count":31,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020056"],"URL":"https:\/\/doi.org\/10.3390\/a15020056","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,2,9]]}}}