{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:09:38Z","timestamp":1750306178473,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,8,2]],"date-time":"2016-08-02T00:00:00Z","timestamp":1470096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Chongqing High-Tech Research Programs","award":["cstc2015jcyjA40042 and cstc2014yykfB40007"],"award-info":[{"award-number":["cstc2015jcyjA40042 and cstc2014yykfB40007"]}]},{"name":"National 863 Programs","award":["2013AA013202 and 2015AA015304"],"award-info":[{"award-number":["2013AA013202 and 2015AA015304"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61402060"],"award-info":[{"award-number":["61402060"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>Multiprocessor systems are becoming ubiquitous in today\u2019s embedded systems design. In this article, we address the problem of mapping an application represented by a Homogeneous Synchronous Dataflow (HSDF) graph onto a real-time multiprocessor platform with the objective of maximizing total throughput. We propose that the optimal solution to the problem is composed of three components: actor-to-processor mapping, retiming, and actor ordering on each processor. The entire problem is systematically modeled into a Boolean Satisfiability (SAT) problem such that the optimal solution can be guaranteed theoretically. In order to explore the vast solution space more efficiently, we develop a specific HSDF theory solver based on the special characteristics of the timed HSDF, and integrate it into the general search framework of the SAT solver. Two alternative integration methods based on branch-and-bound are presented to achieve early branch pruning in the search space; thus, the scalability is greatly improved. Extensive performance evaluation on synthetic examples and a case study on the realistic H.264 Video Decoder show that our approach provides as much as 76.9% throughput improvement, and is scalable to industry-sized applications.<\/jats:p>","DOI":"10.1145\/2950051","type":"journal-article","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T13:26:34Z","timestamp":1470317194000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["An Efficient Technique of Application Mapping and Scheduling on Real-Time Multiprocessor Systems for Throughput Optimization"],"prefix":"10.1145","volume":"15","author":[{"given":"Weichen","family":"Liu","sequence":"first","affiliation":[{"name":"Key Laboratory of Dependable Service Computing in Cyber Physical Society (Chongqing University) of Ministry of Education, and College of Computer Science, Chongqing University, Chongqing, China"}]},{"given":"Chunhua","family":"Xiao","sequence":"additional","affiliation":[{"name":"Key Laboratory of Dependable Service Computing in Cyber Physical Society (Chongqing University) of Ministry of Education, and College of Computer Science, Chongqing University, Chongqing, China"}]}],"member":"320","published-online":{"date-parts":[[2016,8,2]]},"reference":[{"volume-title":"Proceedings of the 4th Colombian Computing Conference (4CCC\u201909)","year":"2009","author":"Alvarez Mauricio","key":"e_1_2_1_1_1"},{"volume-title":"Automation Test in Europe Conference Exhibition (DATE\u201910)","author":"Bonfietti A.","key":"e_1_2_1_2_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/1216919.1216934"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1109\/43.728912"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1109\/82.700929"},{"volume-title":"SAT, Lecture Notes in Computer Science","author":"E\u00e9n Niklas","key":"e_1_2_1_6_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.5555\/1622655.1622656"},{"unstructured":"J. N. Hooker and Hong Yan. 1995. Logic circuit verification by Benders decomposition. Principles and Practice of Constraint Programming: The Newport Papers 267C288.  J. N. Hooker and Hong Yan. 1995. Logic circuit verification by Benders decomposition. Principles and Practice of Constraint Programming: The Newport Papers 267C288.","key":"e_1_2_1_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1109\/TC.1987.5009446"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1629435.1629445"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.5555\/2830689.2830706"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1109\/ISVLSI.2011.49"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1109\/RTSS.2008.49"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1109\/ASPDAC.2007.358032"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1109\/RTSS.2006.44"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1109\/TC.2009.155"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/1289927.1289941"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/158511.158519"},{"unstructured":"Object Management Group. MDA--The architecture of choice for a changing world. Retrieved July 1 2016 from http:\/\/www.omg.org\/mda.  Object Management Group. MDA--The architecture of choice for a changing world. Retrieved July 1 2016 from http:\/\/www.omg.org\/mda.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1109\/12.73588"},{"volume-title":"Proceedings of Asilomar Conference on Signals, Systems and Computers (ACSSC\u201995)","author":"Parks Thomas M.","key":"e_1_2_1_21_1"},{"doi-asserted-by":"crossref","unstructured":"Nadathur Satish Kaushik Ravindran and Kurt Keutzer. 2007. A decomposition-based constraint optimization approach for statically scheduling task graphs with communication delays to multiprocessors. In DATE Rudy Lauwereins and Jan Madsen (Eds.). ACM 57--62.   Nadathur Satish Kaushik Ravindran and Kurt Keutzer. 2007. A decomposition-based constraint optimization approach for statically scheduling task graphs with communication delays to multiprocessors. In DATE Rudy Lauwereins and Jan Madsen (Eds.). ACM 57--62.","key":"e_1_2_1_22_1","DOI":"10.1109\/DATE.2007.364567"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1007\/11814948_1"},{"volume-title":"Embedded Multiprocessors: Scheduling and Synchronization","year":"2000","author":"Sriram S.","key":"e_1_2_1_24_1"},{"unstructured":"Sander Stuijk. 2007. Predictable Mapping of Streaming Applications on Multiprocessors. Ph.D. Dissertation. Technical University of Eindhoven Eindhoven The Netherlands.  Sander Stuijk. 2007. Predictable Mapping of Streaming Applications on Multiprocessors. Ph.D. Dissertation. Technical University of Eindhoven Eindhoven The Netherlands.","key":"e_1_2_1_25_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/1278480.1278674"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1109\/ACSD.2006.23"},{"volume-title":"Automation Test in Europe Conference Exhibition (DATE\u201909)","year":"2009","author":"Yang Hoeseok","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","first-page":"1","article-title":"Application mapping and scheduling for network-on-chip-based multiprocessor system-on-chip with fine-grain communication optimization","volume":"99","author":"Yang L.","year":"2016","journal-title":"IEEE Transactions on Very Large Scale Integration (VLSI) Systems PP"},{"volume-title":"IEEE 20th International Conference on Embedded and Real-Time Computing Systems and Applications. 1--8. DOI:http:\/\/dx.doi.org\/10","year":"2014","author":"Yang Lei","key":"e_1_2_1_30_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1109\/HPCC-CSS-ICESS.2015.60"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1109\/TCAD.2011.2182352"},{"volume-title":"Automation and Test in Europe Conference and Exhibition (DATE\u201914)","year":"2014","author":"Zhu Xue-Yang","key":"e_1_2_1_33_1"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2950051","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2950051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:49:55Z","timestamp":1750218595000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2950051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,2]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1145\/2950051"],"URL":"https:\/\/doi.org\/10.1145\/2950051","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2016,8,2]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}