{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:16Z","timestamp":1763468236240,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2014,10,6]],"date-time":"2014-10-06T00:00:00Z","timestamp":1412553600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"333053 (CONCERTO)"},{"name":"ERDF (European Regional Development Fund) through COMPETE (Operational Programme Thematic Factors of Competitiveness), within project FCOMP-01-0124-FEDER-037281 (CISTER)"},{"name":"FCT and the EU ARTEMIS JU funding, within project no. ARTEMIS\/0003\/2012, JU"},{"name":"National Funds through FCT (Portuguese Foundation for Science and Technology)"},{"name":"FCT and by ESF (European Social Fund) through POPH (Portuguese Human Potential Operational Program), under Ph.D.","award":["SFRH\/BD\/66771\/2009"],"award-info":[{"award-number":["SFRH\/BD\/66771\/2009"]}]},{"name":"Department of Defense under contract no. FA8721-05-C-0003 with Carnegie Mellon University for the operation of the Software Engineering Institute"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2014,12,15]]},"abstract":"<jats:p>Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 \u00d7 faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.<\/jats:p>","DOI":"10.1145\/2660495","type":"journal-article","created":{"date-parts":[[2014,10,7]],"date-time":"2014-10-07T12:57:47Z","timestamp":1412686667000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes"],"prefix":"10.1145","volume":"13","author":[{"given":"Bj\u00f6rn","family":"Andersson","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Gurulingesh","family":"Raravi","sequence":"additional","affiliation":[{"name":"Polytechnic Institute of Porto, Porto, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2014,10,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Jonah Alben. 2013. NVIDIA brings Kepler world's most advanced graphics architecture to mobile devices. http:\/\/blogs.nvidia.com\/blog\/2013\/07\/24\/kepler-to-mobile\/.  Jonah Alben. 2013. NVIDIA brings Kepler world's most advanced graphics architecture to mobile devices. http:\/\/blogs.nvidia.com\/blog\/2013\/07\/24\/kepler-to-mobile\/."},{"key":"e_1_2_1_2_1","unstructured":"AMD. 2014. AMD embedded processors. http:\/\/www.amd.com\/en-us\/products\/embedded.  AMD. 2014. AMD embedded processors. http:\/\/www.amd.com\/en-us\/products\/embedded."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1947412.1947419"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2008.9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-013-9195-z"},{"key":"e_1_2_1_6_1","unstructured":"Apple. 2012. Apple a5x: Dual-core cpu and quad-core GPU. http:\/\/www.apple.com\/ipad\/specs\/.  Apple. 2012. Apple a5x: Dual-core cpu and quad-core GPU. http:\/\/www.apple.com\/ipad\/specs\/."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018425.1020320"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/998685.1007004"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0520"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the IFIP Congress. 807--813","author":"Dertouzos Michael","year":"1974","unstructured":"Michael Dertouzos . 1974 . Control robotics: The procedural control of physical processes . In Proceedings of the IFIP Congress. 807--813 . Michael Dertouzos. 1974. Control robotics: The procedural control of physical processes. In Proceedings of the IFIP Congress. 807--813."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321951"},{"key":"e_1_2_1_12_1","unstructured":"Intel. 2013a. Bay trail: Multicore SOC family for mobile devices. http:\/\/www.intel.com\/newsroom\/kits\/idf\/2013fall\/pdfs\/bay trail fact sheet.pdf.  Intel. 2013a. Bay trail: Multicore SOC family for mobile devices. http:\/\/www.intel.com\/newsroom\/kits\/idf\/2013fall\/pdfs\/bay trail fact sheet.pdf."},{"key":"e_1_2_1_13_1","unstructured":"Intel. 2013b. Intel atom processor. http:\/\/ark.intel.com\/products\/family\/29035.  Intel. 2013b. Intel atom processor. http:\/\/ark.intel.com\/products\/family\/29035."},{"volume-title":"4th generation Intel core processor (code name Haswell). https:\/\/software.intel.com\/enus\/haswell","key":"e_1_2_1_14_1","unstructured":"Intel. 2014. 4th generation Intel core processor (code name Haswell). https:\/\/software.intel.com\/enus\/haswell . Intel. 2014. 4th generation Intel core processor (code name Haswell). https:\/\/software.intel.com\/enus\/haswell."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301361"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_1_17_1","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"Korte Bernhard","year":"2006","unstructured":"Bernhard Korte and Jens Vygen . 2006 . Combinatorial Optimization: Theory and Algorithms 3 rd Ed. Springer . Bernhard Korte and Jens Vygen. 2006. Combinatorial Optimization: Theory and Algorithms 3rd Ed. Springer.","edition":"3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2010.34"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_21_1","unstructured":"Nvidia. 2013. Tegra 4 super processors. http:\/\/www.nvidia.com\/object\/tegra.html.  Nvidia. 2013. Tegra 4 super processors. http:\/\/www.nvidia.com\/object\/tegra.html."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258570"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90009-5"},{"key":"e_1_2_1_24_1","unstructured":"Qualcomm. 2013. Quad-core for next generation devices. http:\/\/www.qualcomm.com\/snapdragon\/specs.  Qualcomm. 2013. Quad-core for next generation devices. http:\/\/www.qualcomm.com\/snapdragon\/specs."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9161-1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2012.21"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2012.64"},{"key":"e_1_2_1_28_1","unstructured":"Samsung. 2013. Samsung Exynos processor. www.samsung.com\/exynos.  Samsung. 2013. Samsung Exynos processor. www.samsung.com\/exynos."},{"key":"e_1_2_1_29_1","unstructured":"Texas Instruments. 2012. OMAP mobile processors. http:\/\/www.ti.com\/omap.  Texas Instruments. 2012. OMAP mobile processors. http:\/\/www.ti.com\/omap."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9164-y"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660495","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2660495","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:11:54Z","timestamp":1750227114000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660495"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,6]]},"references-count":30,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2014,12,15]]}},"alternative-id":["10.1145\/2660495"],"URL":"https:\/\/doi.org\/10.1145\/2660495","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2014,10,6]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}