{"links":{},"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00228917","sets":["1164:2036:11089:11372"]},"path":["11372"],"owner":"44499","recid":"228917","title":["集合対間配線問題に対するSATを用いた配線手法の改良"],"pubdate":{"attribute_name":"公開日","attribute_value":"2023-11-10"},"_buckets":{"deposit":"68282c0e-9634-4b3f-b7f2-699e6fdecffa"},"_deposit":{"id":"228917","pid":{"type":"depid","value":"228917","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"集合対間配線問題に対するSATを用いた配線手法の改良","author_link":["614748","614750","614751","614749"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"集合対間配線問題に対するSATを用いた配線手法の改良"},{"subitem_title":"An Improved Routing Method by SAT for Set-Pair Routing Problem","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"アルゴリズム，VLSI試作・実用化","subitem_subject_scheme":"Other"}]},"item_type_id":"4","publish_date":"2023-11-10","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"東京農工大学大学院工学府電気電子工学専攻"},{"subitem_text_value":"東京農工大学大学院工学府電気電子工学専攻"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Electrical and Electronic Engineering, Tokyo Univercity of Agriculture and  Technology","subitem_text_language":"en"},{"subitem_text_value":"Department of Electrical and Electronic Engineering, Tokyo Univercity of Agriculture and Technology","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/228917/files/IPSJ-SLDM23204050.pdf","label":"IPSJ-SLDM23204050.pdf"},"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-SLDM23204050.pdf","filesize":[{"value":"1.2 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"10"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_login","version_id":"54ac01f3-3293-47b4-adc7-bf4ebf0aa6fe","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2023 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"長倉, 光輝"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"藤吉, 邦洋"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Koki, Nagakura","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kunihiro, Fujiyoshi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11451459","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8639","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"集合対間配線問題とは，同数のソース端子とシンク端子が与えられ，これらの端子間を任意の組合せで 1 対 1 接続する単層配線問題である．集合対間配線では端子間の配線長やその差を小さくすることが求められる．この配線はプリント基板上のバス配線やエスケープ配線の部分問題として現れる．この問題の最適解を求める手法として，整数線形計画問題（ILP）ソルバを用いた手法と充足可能性問題（SAT）ソルバを用いた手法が提案されている．しかし，従来の SAT ソルバを用いた手法では，配線長の制御のために用いる制約が膨大で，配線領域が大きい場合にはメモリ不足で解けなかった．そこで，本研究では配線領域が大きい問題でも解けるように，従来の SAT ソルバを用いた集合対間配線の改良手法を提案する．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"A set-pair routing problem is a single-layer routing problem in which combinations of these pins to be connected by routing is flexible. The problem requires routing in which minimum the longest routing length and the length difference. The set-pair routing appears partially in a printed circuit board (PCB). In addition, several methods have been proposed to find a suboptimal routing solution by using flow graph. Furthermore, two methods have been proposed for finding the optimal routing solution to this problem, one using the integer linear programming (ILP) solver and the other using the satisfiability problem (SAT) solver. However, the conventional method using the SAT solver has a huge number of constraints used to control the routing length, and when the routing area is large, it cannot be solved due to insufficient memory. Therefore, this paper presents an improved routing method for a set-pair routing problem using the SAT solver to solve problems with large routing areas.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"6","bibliographic_titles":[{"bibliographic_title":"研究報告システムとLSIの設計技術（SLDM）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2023-11-10","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"50","bibliographicVolumeNumber":"2023-SLDM-204"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"created":"2025-01-19T01:28:02.952864+00:00","updated":"2025-01-19T11:40:24.320776+00:00","id":228917}