{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:25:13Z","timestamp":1750307113991,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,9,1]],"date-time":"2011-09-01T00:00:00Z","timestamp":1314835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGBED Rev."],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a heterogeneous multiprocessor platform. We consider a restricted case where the maximum utilization of any task on any processor in the system is no greater than one. We use an algorithm proposed in [1] (we refer to it as LP-EE) from state-of-the-art for assigning tasks to heterogeneous multi-processor platform and (re-)prove its performance guarantee for this restricted case but for a stronger adversary. We show that if a task set can be scheduled to meet deadlines on a heterogeneous multiprocessor platform by an optimal task assignment scheme that allows task migrations then LP-EE meets deadlines as well with no migrations if given processors twice as fast.<\/jats:p>","DOI":"10.1145\/2038617.2038621","type":"journal-article","created":{"date-parts":[[2011,10,4]],"date-time":"2011-10-04T13:24:18Z","timestamp":1317734658000},"page":"19-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Provably good task assignment on heterogeneous multiprocessor platforms for a restricted case but with a stronger adversary"],"prefix":"10.1145","volume":"8","author":[{"given":"Gurulingesh","family":"Raravi","sequence":"first","affiliation":[{"name":"CISTER-ISEP Research Center, Polytechnic Institute of Porto, Portugal"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bj\u00f6rn","family":"Andersson","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh and CISTER-ISEP Research Center, Polytechnic Institute of Porto, Portugal"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantinos","family":"Bletsas","sequence":"additional","affiliation":[{"name":"CISTER-ISEP Research Center, Polytechnic Institute of Porto, Portugal"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"S. Baruah \"Task partitioning upon heterogeneous multiprocessor platforms \" in Proceedings of the 10th IEEE International Real-Time and Embedded Technology and Applications Symposium 2004 pp. 536--543. S. Baruah \"Task partitioning upon heterogeneous multiprocessor platforms \" in Proceedings of the 10th IEEE International Real-Time and Embedded Technology and Applications Symposium 2004 pp. 536--543.","DOI":"10.1109\/RTTAS.2004.1317301"},{"key":"e_1_2_1_2_1","unstructured":"IBM Corp. \"The Cell Project at IBM Research \" http:\/\/www.research.ibm.com\/cell\/. IBM Corp. \"The Cell Project at IBM Research \" http:\/\/www.research.ibm.com\/cell\/."},{"key":"e_1_2_1_3_1","unstructured":"NVIDIA \"Dell and NVIDIA Workstation Solutions \" http:\/\/www.nvidia.com\/object\/IO_16084.html. NVIDIA \"Dell and NVIDIA Workstation Solutions \" http:\/\/www.nvidia.com\/object\/IO_16084.html."},{"key":"e_1_2_1_4_1","unstructured":"Intel Corporation \"The 2nd generation Intel Core processor family \" http:\/\/www.intel.com\/consumer\/products\/processors\/core-family.htm. Intel Corporation \"The 2nd generation Intel Core processor family \" http:\/\/www.intel.com\/consumer\/products\/processors\/core-family.htm."},{"key":"e_1_2_1_5_1","unstructured":"AMD Inc. \"AMD Embedded G-Series Platform \" http:\/\/www.amd.com\/us\/products\/embedded\/processors\/Pages\/g-series.aspx. AMD Inc. \"AMD Embedded G-Series Platform \" http:\/\/www.amd.com\/us\/products\/embedded\/processors\/Pages\/g-series.aspx."},{"key":"e_1_2_1_6_1","unstructured":"AMD Inc. \"The AMD Fusion Family of APUs \" http:\/\/sites.amd.com\/us\/fusion\/apu\/Pages\/fusion.aspx. AMD Inc. \"The AMD Fusion Family of APUs \" http:\/\/sites.amd.com\/us\/fusion\/apu\/Pages\/fusion.aspx."},{"key":"e_1_2_1_7_1","unstructured":"IEEE Spectrum \"With Denver Project NVIDIA and ARM Join CPU-GPU Integration Race \" http:\/\/spectrum.ieee.org\/tech-talk\/semiconductors\/processors\/with-denver-project-nvidia-and-arm-join-cpugpu-integration-race. IEEE Spectrum \"With Denver Project NVIDIA and ARM Join CPU-GPU Integration Race \" http:\/\/spectrum.ieee.org\/tech-talk\/semiconductors\/processors\/with-denver-project-nvidia-and-arm-join-cpugpu-integration-race."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2004.20"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2004.56"},{"key":"e_1_2_1_11_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman & Co , 1979 . M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co, 1979."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90009-5"},{"key":"e_1_2_1_13_1","unstructured":"IBM \"IBM ILOG CPLEX Optimizer \" http:\/\/www-01.ibm.com\/software\/integration\/optimization\/cplex-optimizer\/. IBM \"IBM ILOG CPLEX Optimizer \" http:\/\/www-01.ibm.com\/software\/integration\/optimization\/cplex-optimizer\/."}],"container-title":["ACM SIGBED Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2038617.2038621","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2038617.2038621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:48:14Z","timestamp":1750240094000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2038617.2038621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1145\/2038617.2038621"],"URL":"https:\/\/doi.org\/10.1145\/2038617.2038621","relation":{},"ISSN":["1551-3688"],"issn-type":[{"type":"electronic","value":"1551-3688"}],"subject":[],"published":{"date-parts":[[2011,9]]},"assertion":[{"value":"2011-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}