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)