{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T16:24:50Z","timestamp":1649003090723},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J CIRCUIT SYST COMP"],"published-print":{"date-parts":[[2015,7]]},"abstract":"<jats:p> The segmented channel routing problem is fundamental to the routing of row-based field programmable gate arrays (FPGAs) and is proven to be nondeterministic polynomial time (NP) complete. In this paper, we capitalize on the compelling advancements in satisfiability (SAT) solvers to propose a multilevel pseudo-Boolean SAT-based approach. We construct several levels of hierarchy amongst the nets and the routing problem of each level is formulated as a pseudo-Boolean optimization (PBO) problem. Moreover, an optimization technique of reducing the number of variables in PBO problems is described to improve the scalability of the proposed method. Similar to the SAT-based routing, the unroutability of a given circuit can be proved by the approach. Experimental results show that the proposed method compares very favorably with existing algorithms and achieves the best convergence rate. <\/jats:p>","DOI":"10.1142\/s0218126615500838","type":"journal-article","created":{"date-parts":[[2015,3,12]],"date-time":"2015-03-12T22:36:46Z","timestamp":1426199806000},"page":"1550083","source":"Crossref","is-referenced-by-count":0,"title":["A Multilevel Pseudo-Boolean Satisfiability-Based Approach for Segmented Channel Routing"],"prefix":"10.1142","volume":"24","author":[{"given":"Dahua","family":"Zhang","sequence":"first","affiliation":[{"name":"State Key Laboratory of Electronic Thin Films and Integrated Devices, University of Electronic Science and Technology of China, Chengdu 610054, P. R. China"}]},{"given":"Wei","family":"Li","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Electronic Thin Films and Integrated Devices, University of Electronic Science and Technology of China, Chengdu 610054, P. R. China"}]},{"given":"Tao","family":"Du","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Electronic Thin Films and Integrated Devices, University of Electronic Science and Technology of China, Chengdu 610054, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2015,5,26]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1109\/43.184845"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1109\/43.248080"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1109\/3477.775264"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1080\/00207217.2012.751324"},{"key":"rf10","first-page":"59","volume":"7","author":"Berre D. L.","year":"2010","journal-title":"J. Sat. Bool. Model. Comput."},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2002.1004311"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.1"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2011.2169259"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2275254"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1145\/1027084.1027090"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1080\/00207210701650661"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1145\/348019.348574"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1109\/4.18600"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1109\/43.331404"}],"container-title":["Journal of Circuits, Systems and Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218126615500838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T23:39:20Z","timestamp":1565134760000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218126615500838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,26]]},"references-count":14,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2015,5,26]]},"published-print":{"date-parts":[[2015,7]]}},"alternative-id":["10.1142\/S0218126615500838"],"URL":"https:\/\/doi.org\/10.1142\/s0218126615500838","relation":{},"ISSN":["0218-1266","1793-6454"],"issn-type":[{"value":"0218-1266","type":"print"},{"value":"1793-6454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,26]]}}}