{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:59:46Z","timestamp":1759147186733,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"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":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>Horizontal Microcoded Architecture (HMA) is a paradigm for designing programmable high-performance processing elements (PEs). However, it suffers from large code size, which can be addressed by compression. In this article, we study the code size of one of the new HMA-based technologies called No-Instruction-Set Computer (NISC). We show that NISC code size can be several times larger than a typical RISC processor, and we propose several low-overhead dictionary-based code compression techniques to reduce its code size. Our compression algorithm leverages the knowledge of \u201cdon't care\u201d values in the control words and can reduce the code size by 3.3 times, on average. Despite such good results, as shown in this article, these compression techniques lead to poor FPGA implementations because they require many on-chip RAMs. To address this issue, we introduce an FPGA-aware dictionary-based technique that uses the dual-port feature of on-chip RAMs to reduce the number of utilized block RAMs by half. Additionally, we propose cascading two-levels of dictionaries for code size and block RAM reduction of large programs. For an MP3 application, a merged, cascaded, three-dictionary implementation reduces the number of utilized block RAMs by 4.3 times (76%) compared to a NISC without compression. This corresponds to 20% additional savings over the best single level dictionary-based compression.<\/jats:p>","DOI":"10.1145\/1371579.1371583","type":"journal-article","created":{"date-parts":[[2009,1,13]],"date-time":"2009-01-13T13:15:48Z","timestamp":1231852548000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Merged Dictionary Code Compression for FPGA Implementation of Custom Microcoded PEs"],"prefix":"10.1145","volume":"1","author":[{"given":"Bita","family":"Gorjiara","sequence":"first","affiliation":[{"name":"University of California, Irvine"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mehrdad","family":"Reshadi","sequence":"additional","affiliation":[{"name":"University of California, Irvine"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Gajski","sequence":"additional","affiliation":[{"name":"University of California, Irvine"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Agrawala A. and Rauscher T. 1976. Foundations of Microprogramming: Architecture Software and Applications. Academic Press. Agrawala A. and Rauscher T. 1976. Foundations of Microprogramming: Architecture Software and Applications . Academic Press.","DOI":"10.1016\/B978-0-12-045150-0.50014-2"},{"key":"e_1_2_1_2_1","first-page":"4","article-title":"A VLIW architecture for a trace scheduling compiler","volume":"21","author":"Codwell R.","year":"1987","journal-title":"ACM SIGOPS Operat. Syst. Rev."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/859618.859660"},{"key":"e_1_2_1_4_1","unstructured":"Fraser C. 2002. An instruction for direct interpretation of LZ77-compressed programs. Tech. rep. MSR-TR-2002-90 Microsoft Research Microsoft Corporation. Fraser C. 2002. An instruction for direct interpretation of LZ77-compressed programs. Tech. rep. MSR-TR-2002-90 Microsoft Research Microsoft Corporation."},{"key":"e_1_2_1_5_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W.H. Freeman."},{"key":"e_1_2_1_6_1","unstructured":"Gorjiara B. 2007. Synthesis and optimization of custom low-power NISC processors. Ph.D. dissertation University of California Irvine. Gorjiara B. 2007. Synthesis and optimization of custom low-power NISC processors. Ph.D. dissertation University of California Irvine."},{"volume-title":"Proceedings of the IEEE Workshop on Embedded Systems for Real-Time Multimedia (ESTIMedia).","author":"Gorjiara B.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the International Conference on Computer Design (ICCD).","author":"Gorjiara B.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391571"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176254.1176323"},{"key":"e_1_2_1_11_1","unstructured":"Grehan R. 1997. 16-bit: The good the bad your options. Embed. Syst. Prog. Grehan R. 1997. 16-bit: The good the bad your options. Embed. Syst. Prog."},{"volume-title":"Proceedings of the International Conference on Synthesis and System Integration of Mixed Information System (SASIMI).","author":"Ishiura N.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Jensen T. and Toft B. 1995. Graph Coloring Problems. Wiley-Interscience. New York. Jensen T. and Toft B. 1995. Graph Coloring Problems . Wiley-Interscience. New York.","DOI":"10.1002\/9781118032497"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.426.0807"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/951710.951724"},{"volume-title":"Proceedings of the International Symposium on Microarchitecture.","author":"Lefurgy C.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/513918.513929"},{"volume-title":"Proceedings of the Data Compression Conference.","author":"Prakash J.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","unstructured":"Rafail K. 1994. Universal Compression and Retrieval. Kluwer Academic. Publishing. Rafail K. 1994. Universal Compression and Retrieval . Kluwer Academic. Publishing."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.19820"},{"key":"e_1_2_1_21_1","unstructured":"Reshadi M. 2007. No-instruction-set-computer (NISC) technology modeling and compilation. Ph.D. thesis University of California Irvine. Reshadi M. 2007. No-instruction-set-computer (NISC) technology modeling and compilation. Ph.D. thesis University of California Irvine."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1084834.1084845"},{"volume-title":"Proceedings of the Design Automation and Test in Europe (DATE).","author":"Reshadi M.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2005.112"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391489"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1023833.1023853"},{"key":"e_1_2_1_27_1","unstructured":"Saghir M. 1998. Application-specific instruction-set architectures for embedded SDP applications. Ph.D. thesis University of Toronto. Saghir M. 1998. Application-specific instruction-set architectures for embedded SDP applications. Ph.D. thesis University of Toronto."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.464580"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2006.7"},{"key":"e_1_2_1_30_1","unstructured":"Wang K. 2001. Code compaction for VLIW instructions. M.S. thesis University of Toronto. Wang K. 2001. Code compaction for VLIW instructions. M.S. thesis University of Toronto."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1084834.1084854"},{"volume-title":"Proceedings of the International Symposium on Microarchitecture.","author":"Wolfe A.","key":"e_1_2_1_32_1"},{"volume-title":"Proceedings of the International Symposium on Microarchitecture.","author":"Xie Y.","key":"e_1_2_1_33_1"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1371579.1371583","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1371579.1371583","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:21Z","timestamp":1750254981000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1371579.1371583"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1371579.1371583"],"URL":"https:\/\/doi.org\/10.1145\/1371579.1371583","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2008,6]]},"assertion":[{"value":"2007-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}