{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:30Z","timestamp":1750306110781,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,5,26]],"date-time":"2017-05-26T00:00:00Z","timestamp":1495756800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Polish Ministry of Science and Higher Education with a scholarship for outstanding young scientists"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2017,11,30]]},"abstract":"<jats:p>Switching active memory banks at runtime allows a processor with a narrow address bus to access memory that exceeds ranges normally addressable via the bus. Switching code memory banks is regaining interest in microcontrollers for the Internet of Things (IoT), which have to run continuously growing software, while at the same time consuming ultra-small amounts of energy. To make use of bank switching, such software must be partitioned among the available banks and augmented with bank-switching instructions. In contrast to the augmenting, which is done automatically by a compiler, today the partitioning is normally done manually by programmers. However, since IoT software is cross-compiled on much more powerful machines than its target microcontrollers, it becomes possible to partition it automatically during compilation.<\/jats:p>\n          <jats:p>\n            In this article, we thus study the problem of partitioning program code among banks such that the resulting runtime performance of the program is maximized. We prove that the problem is\n            <jats:italic>NP<\/jats:italic>\n            -hard and propose a heuristic algorithm with a low complexity, so it enables fast compilation and hence interactive software development. The algorithm decomposes the problem into three subproblems and introduces a heuristic for each of them: (1) which pieces of code to partition, (2) which of them to assign to permanently mapped banks, and (3) how to divide the remaining ones among switchable banks. We integrate the algorithm, together with earlier ones, in an open-source compiler and test the resulting solution on synthetic as well as actual commercial IoT software bases, thereby demonstrating its advantages and drawbacks. In particular, the results show that the performance of partitions produced by our algorithm comes close to that of partitions created manually by programmers with expert knowledge on the partitioned code.\n          <\/jats:p>","DOI":"10.1145\/3055511","type":"journal-article","created":{"date-parts":[[2017,5,31]],"date-time":"2017-05-31T19:32:40Z","timestamp":1496259160000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Automated Code Partitioning for Microcontrollers with Switchable Memory Banks"],"prefix":"10.1145","volume":"16","author":[{"given":"Michal","family":"Ciszewski","sequence":"first","affiliation":[{"name":"University of Warsaw, Warszawa, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5380-6337","authenticated-orcid":false,"given":"Konrad","family":"Iwanicki","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warszawa, Poland"}]}],"member":"320","published-online":{"date-parts":[[2017,5,26]]},"reference":[{"volume-title":"Amstrad PLC","author":"Manual ZX","key":"e_1_2_1_1_1"},{"volume-title":"ARM DDI 0432C (ID113009). (Nov.","year":"2009","author":"Limited ARM","key":"e_1_2_1_2_1"},{"volume-title":"ARM DDI 0337H (ID032710). (Feb.","year":"2010","author":"Limited ARM","key":"e_1_2_1_3_1"},{"volume-title":"ARM DDI 0484B (ID041812). (April","year":"2012","author":"Limited ARM","key":"e_1_2_1_4_1"},{"volume-title":"Computer Structures: Readings and Examples","year":"1971","author":"Gordon Bell C.","key":"e_1_2_1_5_1"},{"volume-title":"Holmes","year":"1983","author":"Bray Andrew C.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","unstructured":"Stephane Carrez. 2003. GNU Development Chain for 68HC11868HC12. Retrieved from http:\/\/www.gnu.org\/software\/m68hc11\/m68hc11_doc.html.  Stephane Carrez. 2003. GNU Development Chain for 68HC11868HC12. Retrieved from http:\/\/www.gnu.org\/software\/m68hc11\/m68hc11_doc.html."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2008.05.014"},{"edition":"3","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629479"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1460412.1460483"},{"volume-title":"SDCC Compiler User Guide (SDCC 3.5.1). Revision 929. (Aug","year":"2015","author":"Dutta Sandeep","key":"e_1_2_1_12_1"},{"volume-title":"Johnson","year":"1979","author":"Garey Michael R.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781133"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCCN.2015.7288377"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1460412.1460415"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPSN.2016.7460720"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629422"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17520-6_6"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SECON.2010.5508223"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2001.941118"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2005.27"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSTE.2010.5608834"},{"key":"e_1_2_1_27_1","unstructured":"Lotus Development Corporation Intel Corporation and Microsoft Corporation. 1987. Expanded Memory Specification (Version 4.0). 300275-005. Retrieved from http:\/\/www.phatcode.net\/res\/218\/files\/limems 40.txt.  Lotus Development Corporation Intel Corporation and Microsoft Corporation. 1987. Expanded Memory Specification (Version 4.0). 300275-005. Retrieved from http:\/\/www.phatcode.net\/res\/218\/files\/limems 40.txt."},{"key":"e_1_2_1_28_1","unstructured":"Lotus Development Corporation Intel Corporation and Microsoft Corporationand AST Research Inc. 1988. eXtended Memory Specification (XMS) ver 2.0. Retrieved from http:\/\/www.phatcode.net\/res\/219\/files\/xms20.txt.  Lotus Development Corporation Intel Corporation and Microsoft Corporationand AST Research Inc. 1988. eXtended Memory Specification (XMS) ver 2.0. Retrieved from http:\/\/www.phatcode.net\/res\/219\/files\/xms20.txt."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/CASES.2013.6662516"},{"key":"e_1_2_1_31_1","unstructured":"Microchip Technology Inc. 2002. PIC16F7X: 28\/40-pin 8-bit CMOS FLASH Microcontrollers. Data Sheet DS30325B. (2002).  Microchip Technology Inc. 2002. PIC16F7X: 28\/40-pin 8-bit CMOS FLASH Microcontrollers. Data Sheet DS30325B. (2002)."},{"volume-title":"Extended Memory Access Using IAR v3.42A and CCE v2. Texas Instruments","year":"2007","author":"Nisarga Bhargavi","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/375977.375978"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1345206.1345220"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/237090.237193"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176760.1176786"},{"key":"e_1_2_1_37_1","unstructured":"Paul Sokolovsky. 2013. 8051 Code Banking in ContikiOS. Retrieved from https:\/\/github.com\/contiki-os\/contiki\/wiki\/8051-Code-Banking.  Paul Sokolovsky. 2013. 8051 Code Banking in ContikiOS. Retrieved from https:\/\/github.com\/contiki-os\/contiki\/wiki\/8051-Code-Banking."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"volume-title":"Family: User\u2019s Guide. SLAU144J.","year":"2013","author":"Instruments Texas","key":"e_1_2_1_39_1"},{"volume-title":"Applications: User\u2019s Guide. Data Sheet, no. SWRU191F. (April","year":"2014","author":"Instruments Texas","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/951710.951747"},{"volume-title":"Interconnecting Smart Objects with IP: The Next Internet. Morgan Kaufmann","author":"Vasseur Jean-Philippe","key":"e_1_2_1_42_1"},{"volume-title":"Programming the Commodore 64: The Definitive Guide. COMPUTE! Publications","author":"West Raeto C.","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2002.1106005"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055511","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055511","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:20Z","timestamp":1750217780000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,26]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.1145\/3055511"],"URL":"https:\/\/doi.org\/10.1145\/3055511","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2017,5,26]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}