{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:24Z","timestamp":1750308804584,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,6,1]],"date-time":"2009-06-01T00:00:00Z","timestamp":1243814400000},"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":[[2009,6]]},"abstract":"<jats:p>Multi-input addition occurs in a variety of arithmetically intensive signal processing applications. The DSP blocks embedded in high-performance FPGAs perform fixed bitwidth parallel multiplication and Multiply-ACcumulate (MAC) operations. In theory, the compressor trees contained within the multipliers could implement multi-input addition; however, they are not exposed to the programmer. To improve FPGA performance for these applications, this article introduces the Field Programmable Compressor Tree (FPCT) as an alternative to the DSP blocks. By providing just a compressor tree, the FPCT can perform multi-input addition along with parallel multiplication and MAC in conjunction with a small amount of FPGA general logic. Furthermore, the user can configure the FPCT to precisely match the bitwidths of the operands being summed. Although an FPCT cannot beat the performance of a well-designed ASIC compressor tree of fixed bitwidth, for example, 9\u00d79 and 18\u00d718-bit multipliers\/MACs in DSP blocks, its configurable bitwidth and ability to perform multi-input addition is ideal for reconfigurable devices that are used across a variety of applications.<\/jats:p>","DOI":"10.1145\/1534916.1534923","type":"journal-article","created":{"date-parts":[[2009,6,16]],"date-time":"2009-06-16T12:58:25Z","timestamp":1245157105000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Field Programmable Compressor Trees"],"prefix":"10.1145","volume":"2","author":[{"given":"Alessandro","family":"Cevrero","sequence":"first","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiotis","family":"Athanasopoulos","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadi","family":"Parandeh-Afshar","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ajay K.","family":"Verma","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hosein Seyed Attarzadeh","family":"Niaki","sequence":"additional","affiliation":[{"name":"Royal Institute of Technology, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chrysostomos","family":"Nicopoulos","sequence":"additional","affiliation":[{"name":"University of Cyprus"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank K.","family":"Gurkaynak","sequence":"additional","affiliation":[{"name":"Swiss Federal Institute of Technology, Zurich (ETHZ)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip","family":"Brisk","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yusuf","family":"Leblebici","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Ienne","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/567067.567085"},{"key":"e_1_2_1_2_1","unstructured":"Altera Corporation. 2006. Stratix II performance and logic efficiency analysis. White paper. September. http:\/\/www.altera.com\/. Altera Corporation. 2006. Stratix II performance and logic efficiency analysis. White paper. September. http:\/\/www.altera.com\/."},{"key":"e_1_2_1_3_1","unstructured":"Altera Corporation. 2008a. Stratix II device handbook. http:\/\/www.altera.com\/. Altera Corporation. 2008a. Stratix II device handbook. http:\/\/www.altera.com\/."},{"key":"e_1_2_1_4_1","unstructured":"Altera Corporation. 2008b. Stratix III device handbook. http:\/\/www.altera.com\/. Altera Corporation. 2008b. Stratix III device handbook. http:\/\/www.altera.com\/."},{"key":"e_1_2_1_5_1","unstructured":"Altera Corporation. 2008c. Stratix IV device handbook. http:\/\/www.altera.com\/. Altera Corporation. 2008c. Stratix IV device handbook. http:\/\/www.altera.com\/."},{"volume-title":"Proceedings of the 12th International Conference on Field Programmable Logic and Applications. 513--522","author":"Beuchat J.-L.","key":"e_1_2_1_6_1","unstructured":"Beuchat , J.-L. and Tisserand , A . 2002. Small multiplier-based multiplication and division operators for Virtex-II devices . In Proceedings of the 12th International Conference on Field Programmable Logic and Applications. 513--522 . Beuchat, J.-L. and Tisserand, A. 2002. Small multiplier-based multiplication and division operators for Virtex-II devices. In Proceedings of the 12th International Conference on Field Programmable Logic and Applications. 513--522."},{"volume-title":"Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications. 213--222","author":"Betz V.","key":"e_1_2_1_7_1","unstructured":"Betz , V. and Rose , J . 1997. VPR: A new packing, placement, and routing tool for FPGA research . In Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications. 213--222 . Betz, V. and Rose, J. 1997. VPR: A new packing, placement, and routing tool for FPGA research. In Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications. 213--222."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Betz V. Rose J. and Marquardt A. 1999. Architecture and CAD for Deep Submicron FPGAs. Kluwer Academic Norwell MA. Betz V. Rose J. and Marquardt A. 1999. Architecture and CAD for Deep Submicron FPGAs . Kluwer Academic Norwell MA.","DOI":"10.1007\/978-1-4615-5145-4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278480.1278565"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1344671.1344699"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2005.858488"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1155\/1996\/95942"},{"key":"e_1_2_1_13_1","unstructured":"Cosoroaba A. and Rivoallon F. 2006. Achieving higher system performance with the Virtex-5 family of FPGAs. White paper: Xilinx Corporation. July. http:\/\/www.xilinx.com\/. Cosoroaba A. and Rivoallon F. 2006. Achieving higher system performance with the Virtex-5 family of FPGAs. White paper: Xilinx Corporation. July. http:\/\/www.xilinx.com\/."},{"key":"e_1_2_1_14_1","first-page":"349","article-title":"Some schemes for parallel multipliers","volume":"34","author":"Dadda L.","year":"1965","unstructured":"Dadda , L. 1965 . Some schemes for parallel multipliers . Alta Frequenza 34 , 349 -- 356 . Dadda, L. 1965. Some schemes for parallel multipliers. Alta Frequenza 34, 349--356.","journal-title":"Alta Frequenza"},{"volume-title":"Proceedings of the 16th International Conference on Field Programmable Logic and Applications. 1--6.","author":"Frederick M. T.","key":"e_1_2_1_15_1","unstructured":"Frederick , M. T. and Somani , A. K . 2006. Multi-bit carry chains for high performance reconfigurable fabrics . In Proceedings of the 16th International Conference on Field Programmable Logic and Applications. 1--6. Frederick, M. T. and Somani, A. K. 2006. Multi-bit carry chains for high performance reconfigurable fabrics. In Proceedings of the 16th International Conference on Field Programmable Logic and Applications. 1--6."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.831434"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2006.71"},{"volume-title":"Proceedings of the IEEE Custom Integrated Circuits Conference. 261--264","author":"Kaviani A.","key":"e_1_2_1_18_1","unstructured":"Kaviani , A. , Vranisec , D. , and Brown , S . 1998. Computational field programmable architecture . In Proceedings of the IEEE Custom Integrated Circuits Conference. 261--264 . Kaviani, A., Vranisec, D., and Brown, S. 1998. Computational field programmable architecture. In Proceedings of the IEEE Custom Integrated Circuits Conference. 261--264."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.884574"},{"volume-title":"Proceedings of the 30th International Symposium on Microarchitecture. 330--335","author":"Lee C.","key":"e_1_2_1_20_1","unstructured":"Lee , C. , Potkonjak , M. , and Mangione-Smith , W. H . 1997. MediaBench: A tool for evaluating and synthesizing multimedia and communications systems . In Proceedings of the 30th International Symposium on Microarchitecture. 330--335 . Lee, C., Potkonjak, M., and Mangione-Smith, W. H. 1997. MediaBench: A tool for evaluating and synthesizing multimedia and communications systems. In Proceedings of the 30th International Symposium on Microarchitecture. 330--335."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/611817.611846"},{"volume-title":"Proceedings of the International Conference on Computer Design. 308--313","author":"Mirzaei S.","key":"e_1_2_1_22_1","unstructured":"Mirzaei , S. , Hosangadi , A. , and Kastner , R . 2006. FPGA implementation of high speed FIR filters using add and shift method . In Proceedings of the International Conference on Computer Design. 308--313 . Mirzaei, S., Hosangadi, A., and Kastner, R. 2006. FPGA implementation of high speed FIR filters using add and shift method. In Proceedings of the International Conference on Computer Design. 308--313."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.386228"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1344671.1344698"},{"volume-title":"Proceedings of the Asia-South Pacific Design Automation Conference. 138--143","author":"Parandeh-Afshar H.","key":"e_1_2_1_25_1","unstructured":"Parandeh-Afshar , H. , Brisk , P. , and Ienne , P . 2008b. Efficient synthesis of compressor trees on FPGAs . In Proceedings of the Asia-South Pacific Design Automation Conference. 138--143 . Parandeh-Afshar, H., Brisk, P., and Ienne, P. 2008b. Efficient synthesis of compressor trees on FPGAs. In Proceedings of the Asia-South Pacific Design Automation Conference. 138--143."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1403375.1403680"},{"volume-title":"Proceedings of the International Symposium on VLSI Design Automation and Test.","author":"Parandeh-Afshar H.","key":"e_1_2_1_27_1","unstructured":"Parandeh-Afshar , H. , Brisk , P. , and Ienne , P . 2009. Scalable and low cost design approach for variable block size motion estimation . In Proceedings of the International Symposium on VLSI Design Automation and Test. Parandeh-Afshar, H., Brisk, P., and Ienne, P. 2009. Scalable and low cost design approach for variable block size motion estimation. In Proceedings of the International Symposium on VLSI Design Automation and Test."},{"volume-title":"Proceedings of the 9th International Workshop on Field-Programmable Logic and Applications. 359--364","author":"Poldre J.","key":"e_1_2_1_28_1","unstructured":"Poldre , J. and Tammemae , K . 1999. Reconfigurable multiplier for Virtex FPGA family . In Proceedings of the 9th International Workshop on Field-Programmable Logic and Applications. 359--364 . Poldre, J. and Tammemae, K. 1999. Reconfigurable multiplier for Virtex FPGA family. In Proceedings of the 9th International Workshop on Field-Programmable Logic and Applications. 359--364."},{"volume-title":"Proceedings of the IEEE Custom Integrated Circuits Conference. 59--62","author":"Sriram S.","key":"e_1_2_1_29_1","unstructured":"Sriram , S. , Brown , K. , Defosseux , R. , Moerman , F. , Paviot , O. , Sundararajan , V. , and Gatherer , A . 2005. A 64 channel programmable receiver chip for 3G wireless infrastructure . In Proceedings of the IEEE Custom Integrated Circuits Conference. 59--62 . Sriram, S., Brown, K., Defosseux, R., Moerman, F., Paviot, O., Sundararajan, V., and Gatherer, A. 2005. A 64 channel programmable receiver chip for 3G wireless infrastructure. In Proceedings of the IEEE Custom Integrated Circuits Conference. 59--62."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00929625"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1977.1674730"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.2003280"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1964.263830"},{"key":"e_1_2_1_34_1","unstructured":"Xilinx Corporation. 2008a. Virtex-5 FPGA XtremeDSP design considerations. http:\/\/www.xilinx.com\/. Xilinx Corporation. 2008a. Virtex-5 FPGA XtremeDSP design considerations. http:\/\/www.xilinx.com\/."},{"key":"e_1_2_1_35_1","unstructured":"Xilinx Corporation. 2008b. Virtex-5 user guide. http:\/\/www.xilinx.com\/. Xilinx Corporation. 2008b. Virtex-5 user guide. http:\/\/www.xilinx.com\/."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774600"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1534916.1534923","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1534916.1534923","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:06Z","timestamp":1750278366000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1534916.1534923"}},"subtitle":["Acceleration of Multi-Input Addition on FPGAs"],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1145\/1534916.1534923"],"URL":"https:\/\/doi.org\/10.1145\/1534916.1534923","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2009,6]]},"assertion":[{"value":"2009-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}