{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:18:59Z","timestamp":1672291139424},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2006,8]]},"abstract":"<jats:p>Many modern embedded processors such as DSPs support partitioned memory banks (also called X--Y memory or dual-bank memory) along with parallel load\/store instructions to achieve higher code density and performance. In order to effectively utilize the parallel load\/store instructions, the compiler must partition the memory-resident values and assign them to X or Y bank. This paper gives a postregister allocation solution to merge the generated load\/store instructions into their parallel counterparts. Simultaneously, our framework performs allocation of values to X or Y memory banks. We first remove as many load\/stores and register--register moves as possible through an excellent iterated coalescing based register allocator by Appel and George [1996]. We then attempt to parallelize the generated load\/stores using a multipass approach. The basic phase of our approach attempts the merger of load\/stores without duplication and web splitting. We model this problem as a graph-coloring problem in which each value is colored as either X or Y. We then construct a motion scheduling graph (MSG), based on the range of motion for each load\/store instruction. MSG reflects potential instructions that could be merged. We propose a notion of pseudofixed boundaries so that the load\/store movement is less affected by register dependencies. We prove that the coloring problem for MSG is NP-complete and solve it with two different heuristic algorithms with different complexity. We then propose a two-level iterative process to attempt instruction duplication, variable duplication, web splitting, and local conflict elimination to effectively merge the remaining load\/stores. Finally, we clean up some multiple-aliased load\/stores. To improve the performance, we combine profiling information with each stage coupled with some modifications to the algorithm. We show that our framework results in parallelization of a large number of load\/stores without much growth in data and code segments. The average speedup for our optimization pass reaches roughly 13% if no profile information is available and 17% with profile information. The average code and data segment growth is controlled within 13%.<\/jats:p>","DOI":"10.1145\/1165780.1165784","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"613-657","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallelizing load\/stores on dual-bank memory embedded processors"],"prefix":"10.1145","volume":"5","author":[{"given":"Xiaotong","family":"Zhuang","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, Georgia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Santosh","family":"Pande","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, Georgia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Aarts E. and Korst K. 1989. Simulated annealing and Boltzmann Machines Courier Int'l.   Aarts E. and Korst K. 1989. Simulated annealing and Boltzmann Machines Courier Int'l.","DOI":"10.1111\/j.1467-9574.1989.tb01245.x"},{"key":"e_1_2_1_2_1","unstructured":"Aho A. V. Sethi R. and Ullman J. D. 1986. Compilers Principles Techniques and Tools Addison-Wesley Reading MA.   Aho A. V. Sethi R. and Ullman J. D. 1986. Compilers Principles Techniques and Tools Addison-Wesley Reading MA."},{"key":"e_1_2_1_3_1","unstructured":"Briggs P. Cooper K. and Torczon L. 1994. Improvements to graph coloring register allocation. ACM Transactions on Programming Languages and Systems. 10.1145\/177492.177575   Briggs P. Cooper K. and Torczon L. 1994. Improvements to graph coloring register allocation. ACM Transactions on Programming Languages and Systems. 10.1145\/177492.177575"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","article-title":"Register allocation via coloring","volume":"6","author":"Chaitin G.J.","year":"1981","journal-title":"Computer Language"},{"key":"e_1_2_1_5_1","volume-title":"Proc. of LCTES'02 (June), 130--138","author":"Cho J."},{"key":"e_1_2_1_6_1","unstructured":"Cooper K. D. and Harvey T. J. 1998. Compiler-controlled memory. In 8th ASPLOS (Oct.) 10.1145\/291069.291010   Cooper K. D. and Harvey T. J. 1998. Compiler-controlled memory. In 8th ASPLOS (Oct.) 10.1145\/291069.291010"},{"key":"e_1_2_1_7_1","volume-title":"Proc. SIGPLAN '1999 Conf. Programming Language Design and Implementation (May), 139--149","author":"Cooper K. D."},{"key":"e_1_2_1_8_1","volume-title":"Proc. SIGPLAN '94 Conf. Programming Language Design and Implementation (June) 186--195","author":"Davidson J. W."},{"key":"e_1_2_1_9_1","volume-title":"Proc. SIGPLAN '96 Conf. Programming Language Design and Implementation. 10","author":"George L."},{"key":"e_1_2_1_10_1","unstructured":"Gross J. and Yellen J. 1999. Graph theory and its applications. CRC Press. Boca Raton FL.   Gross J. and Yellen J. 1999. Graph theory and its applications. CRC Press. Boca Raton FL."},{"key":"e_1_2_1_11_1","volume-title":"Proc. SIGPLAN '1992 Conf. Programming Language Design and Implementation (July). 10","author":"Knoop J."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2001.941118"},{"key":"e_1_2_1_13_1","unstructured":"Mach-SUIF Backend Compiler 2000. The Machine-SUIF 2.1 compiler documentation set. Harvard University Sept. http:\/\/ececs.harvard.edu\/hube\/research\/machsuif.html.  Mach-SUIF Backend Compiler 2000. The Machine-SUIF 2.1 compiler documentation set. Harvard University Sept. http:\/\/ececs.harvard.edu\/hube\/research\/machsuif.html."},{"key":"e_1_2_1_14_1","volume-title":"Dover Publications","author":"Papadimitriou C.H.","year":"1998"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings International Conference on Acoustics, Speech, and Signal Processing. 553--556","author":"Powell B."},{"key":"e_1_2_1_16_1","volume-title":"Proc. of the 8th International Conference on Architectural Support for Programming Languages and Operation Systems, 234--243","author":"Saghir M. A. R."},{"key":"e_1_2_1_17_1","unstructured":"Stanford SUIF Compiler Infrastructure 2000. The SUIF 2 Compiler Documentation Set Stanford University Sep. http:\/\/suif.stanford.edu\/suif\/index.html.  Stanford SUIF Compiler Infrastructure 2000. The SUIF 2 Compiler Documentation Set Stanford University Sep. http:\/\/suif.stanford.edu\/suif\/index.html."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/335043.335047"},{"key":"e_1_2_1_19_1","volume-title":"Proc. of International Conference on Parallel Architectures and Compilation Techniques, 68--70 (Sep.).","author":"Zhuang X."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1165780.1165784","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:45:09Z","timestamp":1672260309000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1165780.1165784"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,8]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,8]]}},"alternative-id":["10.1145\/1165780.1165784"],"URL":"https:\/\/doi.org\/10.1145\/1165780.1165784","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,8]]},"assertion":[{"value":"2006-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}