{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T10:10:50Z","timestamp":1777889450641,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,1,29]],"date-time":"2008-01-29T00:00:00Z","timestamp":1201564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001774","name":"University of Sydney","doi-asserted-by":"publisher","award":["L2849 U3229"],"award-info":[{"award-number":["L2849 U3229"]}],"id":[{"id":"10.13039\/501100001774","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP 0560190"],"award-info":[{"award-number":["DP 0560190"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p>We have devised an algorithm for minimal placement of bank selections in partitioned memory architectures. This algorithm is parameterizable for a chosen metric, such as speed, space, or energy. Bank switching is a technique that increases the code and data memory in microcontrollers without extending the address buses. Given a program in which variables have been assigned to data banks, we present a novel optimization technique that minimizes the overhead of bank switching through cost-effective placement of bank selection instructions. The placement is controlled by a number of different objectives, such as runtime, low power, small code size or a combination of these parameters. We have formulated the minimal placement of bank selection instructions as a discrete optimization problem that is mapped to a partitioned boolean quadratic programming (PBQP) problem. We implemented the optimization as part of a PIC Microchip backend and evaluated the approach for several optimization objectives. Our benchmark suite comprises programs from MiBench and DSPStone plus a microcontroller real-time kernel and drivers for microcontroller hardware devices. Our optimization achieved a reduction in program memory space of between 2.7 and 18.2%, and an overall improvement with respect to instruction cycles between 5.0 and 28.8%. Our optimization achieved the minimal solution for all benchmark programs. We investigated the scalability of our approach toward the requirements of future generations of microcontrollers. This study was conducted as a worst-case analysis on the entire MiBench suite. Our results show that our optimization (1) scales well to larger numbers of memory banks, (2) scales well to the larger problem sizes that will become feasible with future microcontrollers, and (3) achieves minimal placement for more than 72% of all functions from MiBench.<\/jats:p>","DOI":"10.1145\/1331331.1331336","type":"journal-article","created":{"date-parts":[[2008,2,28]],"date-time":"2008-02-28T14:02:33Z","timestamp":1204207353000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Minimal placement of bank selection instructions for partitioned memory architectures"],"prefix":"10.1145","volume":"7","author":[{"given":"Bernhard","family":"Scholz","sequence":"first","affiliation":[{"name":"The University of Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernd","family":"Burgstaller","sequence":"additional","affiliation":[{"name":"Yonsei University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingling","family":"Xue","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,1,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/774789.774805"},{"key":"e_1_2_1_2_1","volume-title":"Computer Systems: A Programmer's Perspective","author":"Bryant R. E.","year":"2003","unstructured":"Bryant , R. E. and O'Halloran , D. R. 2003 . Computer Systems: A Programmer's Perspective . Prentice-Hall , Englewood Cliffs, NJ . Bryant, R. E. and O'Halloran, D. R. 2003. Computer Systems: A Programmer's Perspective. Prentice-Hall, Englewood Cliffs, NJ."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Symposium on Code Generation and Optimization (CGO'03)","author":"Cai Q.","unstructured":"Cai , Q. and Xue , J . 2003. Optimal and efficient speculation-based partial redundancy elimination . In Proceedings of the International Symposium on Code Generation and Optimization (CGO'03) . IEEE Computer Society, Los Alamitos, CA. 91--102. Cai, Q. and Xue, J. 2003. Optimal and efficient speculation-based partial redundancy elimination. In Proceedings of the International Symposium on Code Generation and Optimization (CGO'03). IEEE Computer Society, Los Alamitos, CA. 91--102."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/966137.966140"},{"key":"e_1_2_1_5_1","unstructured":"Dattalo T. S. 2006. The Gpsim SW simulator for PIC microcontrollers. http:\/\/www.dattalo.com\/gnupic\/gpsim.html.  Dattalo T. S. 2006. The Gpsim SW simulator for PIC microcontrollers. http:\/\/www.dattalo.com\/gnupic\/gpsim.html."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/354880.354900"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1762146.1762170"},{"key":"e_1_2_1_9_1","unstructured":"Gartner Dataquest. 2004. 2003 microcontroller market share and unit shipments.  Gartner Dataquest. 2004. 2003 microcontroller market share and unit shipments."},{"key":"e_1_2_1_10_1","unstructured":"Gartner Dataquest. 2005. Top companies revenue from shipments of 8-bit mcu---all applications.  Gartner Dataquest. 2005. Top companies revenue from shipments of 8-bit mcu---all applications."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1128020.1128563"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11860990_21"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2005.12"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176760.1176805"},{"key":"e_1_2_1_15_1","unstructured":"HI-TECH Software. 2006. PICC ANSI C Compiler. http:\/\/www.htsoft.com\/.  HI-TECH Software. 2006. PICC ANSI C Compiler. http:\/\/www.htsoft.com\/."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/165123.165160"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99)","author":"Kleinberg J. M.","unstructured":"Kleinberg , J. M. and Tardos , E . 1999. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99) . IEEE Computer Society, Los Alamitos, CA. 14--23. Kleinberg, J. M. and Tardos, E. 1999. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99). IEEE Computer Society, Los Alamitos, CA. 14--23."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/183432.183443"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2001.941118"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2005.27"},{"key":"e_1_2_1_21_1","unstructured":"Microchip Technology Inc. 1997. PICmicro mid-range MCU family reference manual.  Microchip Technology Inc. 1997. PICmicro mid-range MCU family reference manual."},{"key":"e_1_2_1_22_1","unstructured":"Microchip Technology Inc. 2003. PIC16F87XA data sheet.  Microchip Technology Inc. 2003. PIC16F87XA data sheet."},{"key":"e_1_2_1_23_1","unstructured":"Microchip Technology Inc. 2006. PIC18F97J60 family data sheet advance information.  Microchip Technology Inc. 2006. PIC18F97J60 family data sheet advance information."},{"key":"e_1_2_1_24_1","unstructured":"MicrochipC.com. 2006. PIC micros and C. http:\/\/www.microchipc.com\/.  MicrochipC.com. 2006. PIC micros and C. http:\/\/www.microchipc.com\/."},{"key":"e_1_2_1_25_1","volume-title":"Advanced Compiler Design and Implementation. Morgan Kaufmann","author":"Muchnick S. S.","unstructured":"Muchnick , S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann , San Francisco, CA . Muchnick, S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086297.1086330"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 31st Annual ACM\/IEEE International Symposium on Microarchitecture. 103--114","author":"Nystrom E.","unstructured":"Nystrom , E. and Eichenberger , A. E . 1998. Effective cluster assignment for modulo scheduling . In Proceedings of the 31st Annual ACM\/IEEE International Symposium on Microarchitecture. 103--114 . Nystrom, E. and Eichenberger, A. E. 1998. Effective cluster assignment for modulo scheduling. In Proceedings of the 31st Annual ACM\/IEEE International Symposium on Microarchitecture. 103--114."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/348019.348570"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/375977.375978"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.132"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/237090.237193"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/513829.513854"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/998300.997195"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 1995 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'95)","author":"Sudarsanam A.","unstructured":"Sudarsanam , A. and Malik , S . 1995. Memory bank and register allocation in software synthesis for ASIPs . In Proceedings of the 1995 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'95) . 388--392. Sudarsanam, A. and Malik, S. 1995. Memory bank and register allocation in software synthesis for ASIPs. In Proceedings of the 1995 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'95). 388--392."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/951710.951747"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe (DATE'04)","author":"Verma M.","unstructured":"Verma , M. , Wehmeyer , L. , and Marwedel , P . 2004. Cache-aware scratchpad allocation algorithm . In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'04) . IEEE Computer Society, Los Alamitos, CA. 1264--1269. Verma, M., Wehmeyer, L., and Marwedel, P. 2004. Cache-aware scratchpad allocation algorithm. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'04). IEEE Computer Society, Los Alamitos, CA. 1264--1269."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/645989.674319"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS'02)","author":"Zhuge Q.","unstructured":"Zhuge , Q. , Xiao , B. , and Sha , E. H . -M. 2002. Variable partitioning and scheduling of multiple memory architectures for DSP . In Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS'02) . IEEE Computer Society, Los Alamitos, CA. 332. Zhuge, Q., Xiao, B., and Sha, E. H.-M. 2002. Variable partitioning and scheduling of multiple memory architectures for DSP. In Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS'02). IEEE Computer Society, Los Alamitos, CA. 332."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1331331.1331336","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1331331.1331336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:27Z","timestamp":1750278147000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1331331.1331336"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,29]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1145\/1331331.1331336"],"URL":"https:\/\/doi.org\/10.1145\/1331331.1331336","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,29]]},"assertion":[{"value":"2006-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}