Presentation | 2022-11-28 A Routing Method by SAT for Set-Pair Routing Problem Koki Nagakura, Rintaro Yokoya, Kunihiro Fujiyoshi, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Set-pair routing problem is a single-layer routing problem in which a one-to-one connection is made between equal numbers of source and sink terminals in arbitrary combinations with, requiring reduction wire length between connections and their length differences. In methods for solving set-pair routing problem, a method that represents routing graph as a flow graph and controls the wire length using ILP has been proposed. Incidentally, it has been reported that the SAT-based method is faster than the ILP-based method for the Numberlink, which is considered to have a high affinity with routing problems. Therefore, we propose a method for solving set-pair routing problem by SAT. We propose a modified formulation for Numberlink, and a formulation uses fewer variables that takes advantage of its special characteristics of set-pair routing problem. Additionally, by adding constraints to control the wire length, we solve set-pair routing problem by SAT solver. Then, experimental results show the effectiveness of the proposed method. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Set-Pair Routing Problem / SAT |
Paper # | VLD2022-21,ICD2022-38,DC2022-37,RECONF2022-44 |
Date of Issue | 2022-11-21 (VLD, ICD, DC, RECONF) |
Conference Information | |
Committee | VLD / DC / RECONF / ICD / IPSJ-SLDM |
---|---|
Conference Date | 2022/11/28(3days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Kanazawa Bunka Hall |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | Design Gaia 2022 -New Field of VLSI Design- |
Chair | Minako Ikeda(NTT) / Tatsuhiro Tsuchiya(Osaka Univ.) / Kentaro Sano(RIKEN) / Masafumi Takahashi(Kioxia) / Hiroyuki Ochi(Ritsumeikan Univ.) |
Vice Chair | Shigetoshi Nakatake(Univ. of Kitakyushu) / Toshinori Hosokawa(Nihon Univ.) / Yoshiki Yamaguchi(Tsukuba Univ.) / Tomonori Izumi(Ritsumeikan Univ.) / Makoto Ikeda(Univ. of Tokyo) |
Secretary | Shigetoshi Nakatake(NBS) / Toshinori Hosokawa(Hirosaki Univ.) / Yoshiki Yamaguchi(Nihon Univ.) / Tomonori Izumi(Chiba Univ.) / Makoto Ikeda(NEC) / (Toyohashi Univ. of Tech.) |
Assistant | Takuma Nishimoto(Hitachi) / / Yukitaka Takemura(INTEL) / Yasunori Osana(Ryukyu Univ.) / Yoshiaki Yoshihara(KIOXIA) / Jun Shiomi(Osaka Univ.) / Takeshi Kuboki(Sony Semiconductor Solutions) |
Paper Information | |
Registration To | Technical Committee on VLSI Design Technologies / Technical Committee on Dependable Computing / Technical Committee on Reconfigurable Systems / Technical Committee on Integrated Circuits and Devices / Special Interest Group on System and LSI Design Methodology |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | A Routing Method by SAT for Set-Pair Routing Problem |
Sub Title (in English) | |
Keyword(1) | Set-Pair Routing Problem |
Keyword(2) | SAT |
1st Author's Name | Koki Nagakura |
1st Author's Affiliation | Tokyo University of Agriculture and Technology(Tokyo Univ of A and T) |
2nd Author's Name | Rintaro Yokoya |
2nd Author's Affiliation | Tokyo University of Agriculture and Technology(Tokyo Univ of A and T) |
3rd Author's Name | Kunihiro Fujiyoshi |
3rd Author's Affiliation | Tokyo University of Agriculture and Technology(Tokyo Univ of A and T) |
Date | 2022-11-28 |
Paper # | VLD2022-21,ICD2022-38,DC2022-37,RECONF2022-44 |
Volume (vol) | vol.122 |
Number (no) | VLD-283,ICD-284,DC-285,RECONF-286 |
Page | pp.pp.13-18(VLD), pp.13-18(ICD), pp.13-18(DC), pp.13-18(RECONF), |
#Pages | 6 |
Date of Issue | 2022-11-21 (VLD, ICD, DC, RECONF) |