{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:43:21Z","timestamp":1750308201832,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"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":[[2005,1]]},"abstract":"<jats:p>\n            Minimum area is one of the important objectives in technology mapping for lookup table-based field-progrmmable gate arrays (FPGAs). Although there is an algorithm that can find an optimal solution in polynomial time for the minimal-area FPGA technology mapping problem without gate duplication, its time complexity can grow exponentially with the number of inputs of the lookup-tables. This article proposes an algorithm with approximate to the area-optimal solution and lower time complexity. The time complexity of this algorithm is proven theoretically to be bounded by\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the total number of gates in the given circuit. It is shown that except for some cases the proposed algorithm can find an optimal solution of a given problem. We have combined the proposed algorithm with the existing postprocessing procedures which are used to find the gates that can be duplicated on a set of benchmark examples. The experimental results demonstrate the effectiveness of our algorithm.\n          <\/jats:p>","DOI":"10.1145\/1044111.1044121","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"168-186","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["An efficient algorithm for finding the minimal-area FPGA technology mapping"],"prefix":"10.1145","volume":"10","author":[{"given":"Chi-Chou","family":"Kao","sequence":"first","affiliation":[{"name":"National Pingtung Institute of Commerce, Pingtung, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yen-Tai","family":"Lai","sequence":"additional","affiliation":[{"name":"National Cheng Kung University, Tainan, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,1]]},"reference":[{"volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design. 564--567","author":"Chowdhary A.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of the ACM\/SIGDA International Symposium on Field Programmable Gate Arrays. 48--55","author":"Chen G.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.273754"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.285741"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Design. 154--158","author":"Cong J.","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the ACM International Symposium on Field Programmable Gate Arrays. 29--35","author":"Cong J.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.329262"},{"volume-title":"Proceedings of the Design Automation Conference. 613--619","author":"Francis J.","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the Design Automation Conference. 248--251","author":"Francis J.","key":"e_1_2_1_9_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design. 359--363","author":"Huang J. D.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.317471"},{"key":"e_1_2_1_12_1","article-title":"Minimization over Boolean graphs. IBM","author":"Karp R. M.","year":"1962","journal-title":"J. Res. Develop"},{"volume-title":"Proceedings of the Design Automation Conference. 240--243","year":"1991","author":"Karplus K.","key":"e_1_2_1_13_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design. 30--35","author":"Lai Y. T.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the Design Automation Conference. 642--647","author":"Lai Y. T.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.644605"},{"volume-title":"Proceedings of the Design Automation Conference. 620--625","author":"Murgai R.","key":"e_1_2_1_17_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design. 564--567","author":"Murgai R.","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design. 353--358","author":"Sawada H.","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of the Design Automation Conference. 368--373","author":"Sawkar P.","key":"e_1_2_1_20_1"},{"volume-title":"SIS: A system for sequential circuit synthesis. Tech. rep. UCB\/ERL M92\/41","year":"1992","author":"Sentovich E.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the Design Automation Conference. 65--69","author":"Shen W. Z.","key":"e_1_2_1_22_1"},{"volume-title":"Proceedings of the Design Automation Conference. 248--251","year":"1991","author":"Woo N. S.","key":"e_1_2_1_23_1"},{"volume-title":"Proceedings of the Design Automation Conference. 54--59","author":"Wurth B.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.552093"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044111.1044121","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1044111.1044121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:25:05Z","timestamp":1750263905000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044111.1044121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1145\/1044111.1044121"],"URL":"https:\/\/doi.org\/10.1145\/1044111.1044121","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2005,1]]},"assertion":[{"value":"2005-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}