{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:39:50Z","timestamp":1750307990854,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2004,6,7]],"date-time":"2004-06-07T00:00:00Z","timestamp":1086566400000},"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. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            Clustering, duplication, and placement are critical steps in a cluster-based FPGA design flow. Clustering has a great impact on the wirelength, timing, and routability of a circuit. Logic duplication is an effective method for improving performance while maintaining the logic equivalence of a circuit. Based on several novel algorithmic contributions, we present an efficient and effective algorithm named\n            <jats:italic>SPCD<\/jats:italic>\n            (simultaneous placement with clustering and duplication) which performs clustering and duplication\n            <jats:italic>during<\/jats:italic>\n            placement for wirelength and timing minimization. First, we incorporate a path counting-based net weighting scheme for more effective timing optimization. Secondly, we introduce a novel method of moving a fragment of a cluster (called a\n            <jats:italic>fragment level move<\/jats:italic>\n            ) during placement to optimize the clustering structure. To reduce the critical path detour during legalization from a more global perspective, we also introduce the notions of a\n            <jats:italic>monotone region<\/jats:italic>\n            and a\n            <jats:italic>global monotone region<\/jats:italic>\n            in which improvement to the local\/global path detour is guaranteed. Furthermore, we introduce a notion of a\n            <jats:italic>constrained gain graph<\/jats:italic>\n            to embed all complex FPGA clustering constraints, and implement an optimal incremental legalization algorithm under such constraints. Finally, in order to reduce the circuit area, we formulate a timing-constrained global\n            <jats:italic>redundancy removal<\/jats:italic>\n            problem and propose a heuristic solution. Our SPCD algorithm outperforms a widely used academic FPGA placement flow,\n            <jats:italic>T-VPack + VPR<\/jats:italic>\n            , with an average reduction of 31% in the longest path estimate delay and 18% in the routed delay. We also apply our SPCD algorithm to Altera's Stratix architecture in a commercial FPGA implementation flow (\n            <jats:italic>Quartus II<\/jats:italic>\n            4.0). The routed result achieved by our SPCD algorithm outperforms\n            <jats:italic>VPR<\/jats:italic>\n            by 20% and outperforms\n            <jats:italic>Quartus II<\/jats:italic>\n            4.0 by 4%.\n          <\/jats:p>","DOI":"10.1145\/1142980.1142989","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"740-772","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Simultaneous placement with clustering and duplication"],"prefix":"10.1145","volume":"11","author":[{"given":"Gang","family":"Chen","sequence":"first","affiliation":[{"name":"Magma Design Automation, Santa Clara, CA"}]},{"given":"Jason","family":"Cong","sequence":"additional","affiliation":[{"name":"UCLA, Los Angeles, CA"}]}],"member":"320","published-online":{"date-parts":[[2004,6,7]]},"reference":[{"volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference, 196--201","author":"Beraudo G.","key":"e_1_2_1_1_1","unstructured":"Beraudo , G. and Lillis , J . 2003. Timing optimization of FPGA placements by logic replication . In Proceedings of the ACM\/IEEE Design Automation Conference, 196--201 . 10.1145\/775832.775885 Beraudo, G. and Lillis, J. 2003. Timing optimization of FPGA placements by logic replication. In Proceedings of the ACM\/IEEE Design Automation Conference, 196--201. 10.1145\/775832.775885"},{"volume-title":"Proceedings of the International Workshop on Field Programmable Logic and Application, 213--222","author":"Betz V.","key":"e_1_2_1_2_1","unstructured":"Betz , V. and Rose , J . 1997. VPR: A new packing, placement and routing tool for FPGA research . In Proceedings of the International Workshop on Field Programmable Logic and Application, 213--222 . Betz, V. and Rose, J. 1997. VPR: A new packing, placement and routing tool for FPGA research. In Proceedings of the International Workshop on Field Programmable Logic and Application, 213--222."},{"volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference","author":"Bozorgzadeh E.","key":"e_1_2_1_3_1","unstructured":"Bozorgzadeh , E. , Ogrenci , S. , and Sarrafzadeh , M . 2001. Routability-Driven packing for cluster-based FPGAs . In Proceedings of the Asia and South Pacific Design Automation Conference ( Yokohama, Japan). 629--634. 10.1145\/370155.370567 Bozorgzadeh, E., Ogrenci, S., and Sarrafzadeh, M. 2001. Routability-Driven packing for cluster-based FPGAs. In Proceedings of the Asia and South Pacific Design Automation Conference (Yokohama, Japan). 629--634. 10.1145\/370155.370567"},{"volume-title":"Proceedings of the International Conference on Field Programmable Logic and Its Applications","author":"Chen G.","key":"e_1_2_1_4_1","unstructured":"Chen , G. and Cong , J . 2004. Simultaneous timing driven clustering and placement for FPGAs . In Proceedings of the International Conference on Field Programmable Logic and Its Applications ( Antwerp, Belgium). 158--167. Chen, G. and Cong, J. 2004. Simultaneous timing driven clustering and placement for FPGAs. In Proceedings of the International Conference on Field Programmable Logic and Its Applications (Antwerp, Belgium). 158--167."},{"volume-title":"Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 51--59","author":"Chen G.","key":"e_1_2_1_5_1","unstructured":"Chen , G. and Cong , J . 2005. Simultaneous timing-driven placement and duplication . In Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 51--59 . 10.1145\/1046192.1046200 Chen, G. and Cong, J. 2005. Simultaneous timing-driven placement and duplication. In Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 51--59. 10.1145\/1046192.1046200"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/43.273754","article-title":"FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs","volume":"13","author":"Cong J.","year":"1994","unstructured":"Cong , J. and Ding , Y. 1994 . FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs . IEEE Trans. Compute.-Aided Des. 13 , 1 (Jan.), 1--12. Cong, J. and Ding, Y. 1994. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Trans. Compute.-Aided Des. 13, 1 (Jan.), 1--12.","journal-title":"IEEE Trans. Compute.-Aided Des."},{"volume-title":"Proceedings of the 36th ACM\/IEEE Design Automation Conference (New Orleans, La.). 460--465","author":"Cong J.","key":"e_1_2_1_7_1","unstructured":"Cong , J. , Li , H. , and Wu , C . 1999. Simultaneous circuit partitioning\/clustering with retiming for performance optimization . In Proceedings of the 36th ACM\/IEEE Design Automation Conference (New Orleans, La.). 460--465 . 10.1145\/309847.309980 Cong, J., Li, H., and Wu, C. 1999. Simultaneous circuit partitioning\/clustering with retiming for performance optimization. In Proceedings of the 36th ACM\/IEEE Design Automation Conference (New Orleans, La.). 460--465. 10.1145\/309847.309980"},{"volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference","author":"Hrkic M.","key":"e_1_2_1_8_1","unstructured":"Hrkic , M. , Lillis , J. , and Beraudo , G . 2004. An approach to placement-coupled logic replication . In Proceedings of the ACM\/IEEE Design Automation Conference ( San Diego, Calif.). 711--716. 10.1145\/996566.996761 Hrkic, M., Lillis, J., and Beraudo, G. 2004. An approach to placement-coupled logic replication. In Proceedings of the ACM\/IEEE Design Automation Conference (San Diego, Calif.). 711--716. 10.1145\/996566.996761"},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design","author":"Hur S.-W.","key":"e_1_2_1_9_1","unstructured":"Hur , S.-W. and Lillis , J . 2000. Mongrel: Hybrid techniques for standard cell placement . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design ( San Jose, Calif.). 165--170. Hur, S.-W. and Lillis, J. 2000. Mongrel: Hybrid techniques for standard cell placement. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (San Jose, Calif.). 165--170."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design","author":"Kong T.","year":"2002","unstructured":"Kong , T. 2002 . A novel net weighting algorithm for timing-driven placement . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design ( San Jose, Calif.). 172--176. 10.1145\/774572.774597 Kong, T. 2002. A novel net weighting algorithm for timing-driven placement. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (San Jose, Calif.). 172--176. 10.1145\/774572.774597"},{"volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems, 196--201","author":"Lillis J.","key":"e_1_2_1_11_1","unstructured":"Lillis , J. , Cheng , C.-K. , and Lin , T . -T. Y. 1996. Algorithms for optimal introduction of redundant logic for timing and area optimization . In Proceedings of the IEEE International Symposium on Circuits and Systems, 196--201 . Lillis, J., Cheng, C.-K., and Lin, T.-T. Y. 1996. Algorithms for optimal introduction of redundant logic for timing and area optimization. In Proceedings of the IEEE International Symposium on Circuits and Systems, 196--201."},{"volume-title":"Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 37--46","author":"Marquardt A.","key":"e_1_2_1_12_1","unstructured":"Marquardt , A. , Betz , V. , and Rose , J . 1999. Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density . In Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 37--46 . 10.1145\/296399.296426 Marquardt, A., Betz, V., and Rose, J. 1999. Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density. In Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 37--46. 10.1145\/296399.296426"},{"volume-title":"Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 203--213","author":"Marquardt A.","key":"e_1_2_1_13_1","unstructured":"Marquardt , A. , Betz , V. , and Rose , J . 2000. Timing-driven placement for FPGAs . In Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 203--213 . 10.1145\/329166.329208 Marquardt, A., Betz, V., and Rose, J. 2000. Timing-driven placement for FPGAs. In Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays (Monterey, Calif.). 203--213. 10.1145\/329166.329208"},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design","author":"Neumann I.","key":"e_1_2_1_14_1","unstructured":"Neumann , I. , Stoffel , D. , Hartje , H. , and Kunz , W . 1999. Cell replication and redundancy elimination during placement for cycle time optimization . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design ( San Jose, Calif.). 25--30. Neumann, I., Stoffel, D., Hartje, H., and Kunz, W. 1999. Cell replication and redundancy elimination during placement for cycle time optimization. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (San Jose, Calif.). 25--30."},{"key":"e_1_2_1_15_1","volume-title":"SIS: A system for sequential circuit synthesis. Electronics Research Laboratory. Memorandum No. UCB\/ERL M92\/41.","author":"Sentovich E.","year":"1992","unstructured":"Sentovich , E. , Singh , K. , Lavagno , L. , Moon , C. , Murgai , R. , Saldanha , A. , Savoj , Stephan, P., Brayton , R. , and Sangiovanni-Vincentelli , A. 1992 . SIS: A system for sequential circuit synthesis. Electronics Research Laboratory. Memorandum No. UCB\/ERL M92\/41. Sentovich, E., Singh, K., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, Stephan, P., Brayton, R., and Sangiovanni-Vincentelli, A. 1992. SIS: A system for sequential circuit synthesis. Electronics Research Laboratory. Memorandum No. UCB\/ERL M92\/41."},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design","author":"Srivastava A.","key":"e_1_2_1_16_1","unstructured":"Srivastava , A. , Kastner , R. , and Sarrafzadeh , M . 2000. Timing driven gate duplication: Complexity issues and algorithms . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design ( San Jose, Calif.). 447--450. Srivastava, A., Kastner, R., and Sarrafzadeh, M. 2000. Timing driven gate duplication: Complexity issues and algorithms. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (San Jose, Calif.). 447--450."},{"key":"e_1_2_1_17_1","unstructured":"The FPGA Place-and-Route Challenge. http:\/\/www.eecg.toronto.edu\/&sim;vaughn\/challenge\/challenge.html.  The FPGA Place-and-Route Challenge. http:\/\/www.eecg.toronto.edu\/&sim;vaughn\/challenge\/challenge.html."},{"key":"e_1_2_1_18_1","unstructured":"Stratix Device Handbook. http:\/\/www.altera.com\/literature\/lit-stx.jsp.  Stratix Device Handbook. http:\/\/www.altera.com\/literature\/lit-stx.jsp."},{"key":"e_1_2_1_19_1","unstructured":"Simultaneous Placement with Clustering and Duplication for LUT-based FPGA Designs. http:\/\/ballade.cs.ucla.edu\/&sim;chg\/spcd.  Simultaneous Placement with Clustering and Duplication for LUT-based FPGA Designs. http:\/\/ballade.cs.ucla.edu\/&sim;chg\/spcd."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1142980.1142989","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1142980.1142989","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:16Z","timestamp":1750259176000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1142980.1142989"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6,7]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1142980.1142989"],"URL":"https:\/\/doi.org\/10.1145\/1142980.1142989","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2004,6,7]]},"assertion":[{"value":"2004-06-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}