BCA Channel Routing to Minimize Wirelength for Generalized Channel Problem

Routing has a crucial impact on chip design [1]. In this paper, a BCA (Below-Cross-Above) routing, especially for critical routing layers, is proposed. It is assumed that horizontal routing capacity is tight and that all pins of a net need to be connected by a Single Trunk Steiner Tree. Our proposed...

Full description

Saved in:
Bibliographic Details
Main Authors: Wang, Zezhong, Shimoda, Masayuki, Takahashi, Atsushi
Format: Conference Proceeding
Language:English
Subjects:
Channel routing problem
Chip scale packaging
Circuits and systems
Global routing
Greedy algorithms
Minimization
Pins
Routing
Steiner trees
Wirelength minimization
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 5
container_issue
container_start_page 1
container_title
container_volume
creator Wang, Zezhong
Shimoda, Masayuki
Takahashi, Atsushi
description Routing has a crucial impact on chip design [1]. In this paper, a BCA (Below-Cross-Above) routing, especially for critical routing layers, is proposed. It is assumed that horizontal routing capacity is tight and that all pins of a net need to be connected by a Single Trunk Steiner Tree. Our proposed algorithm is a greedy algorithm based on a well-known Left-Edge algorithm. The track assignment of nets is determined iteratively by taking net priority into account to reduce the vertical length while keeping the required number of tracks as small as possible. In experiments, it is confirmed that the vertical wirelength is reduced by around 40% compared with the track assignment by Left Edge algorithm.
doi_str_mv 10.1109/ISCAS58744.2024.10558428
format conference_proceeding
fullrecord <record><control><sourceid>ieee_CHZPO</sourceid><recordid>TN_cdi_ieee_primary_10558428</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>10558428</ieee_id><sourcerecordid>10558428</sourcerecordid><originalsourceid>FETCH-LOGICAL-i248t-80818ff0b2ea8d451aa8689ee3c7706caa7973f03755f3d9ffd609975a5b0623</originalsourceid><addsrcrecordid>eNo9j8tOwzAURA0SEqX0D1j4BxKuX7G9DBGUoiIQrcSycprr1ihxkBMW8PVE4rGaxWiO5hBCGeSMgb1ebapyo4yWMufAZc5AKSO5OSELq60RCoQAa9kpmXGmTMYUV-fkYhjeADhAwWfk4aYqaXV0MWJLX_qPMcQDHXv6GGLowhfS15CwxXgYj9T3iS4xYnLt1DT_s-fU1y12l-TMu3bAxW_OyfbudlvdZ-un5aoq11ng0oyZAcOM91BzdKaRijlnCmMRxV5rKPbOaauFB6GV8qKx3jfFJKGVU_V0WczJ1Q82IOLuPYXOpc_dn7r4BnGeTb0</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>BCA Channel Routing to Minimize Wirelength for Generalized Channel Problem</title><source>IEEE Xplore All Conference Series</source><creator>Wang, Zezhong ; Shimoda, Masayuki ; Takahashi, Atsushi</creator><creatorcontrib>Wang, Zezhong ; Shimoda, Masayuki ; Takahashi, Atsushi</creatorcontrib><description>Routing has a crucial impact on chip design [1]. In this paper, a BCA (Below-Cross-Above) routing, especially for critical routing layers, is proposed. It is assumed that horizontal routing capacity is tight and that all pins of a net need to be connected by a Single Trunk Steiner Tree. Our proposed algorithm is a greedy algorithm based on a well-known Left-Edge algorithm. The track assignment of nets is determined iteratively by taking net priority into account to reduce the vertical length while keeping the required number of tracks as small as possible. In experiments, it is confirmed that the vertical wirelength is reduced by around 40% compared with the track assignment by Left Edge algorithm.</description><identifier>EISSN: 2158-1525</identifier><identifier>EISBN: 9798350330991</identifier><identifier>DOI: 10.1109/ISCAS58744.2024.10558428</identifier><language>eng</language><publisher>IEEE</publisher><subject>Channel routing problem ; Chip scale packaging ; Circuits and systems ; Global routing ; Greedy algorithms ; Minimization ; Pins ; Routing ; Steiner trees ; Wirelength minimization</subject><ispartof>2024 IEEE International Symposium on Circuits and Systems (ISCAS), 2024, p.1-5</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/10558428$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,776,780,785,786,27902,54530,54907</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/10558428$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Wang, Zezhong</creatorcontrib><creatorcontrib>Shimoda, Masayuki</creatorcontrib><creatorcontrib>Takahashi, Atsushi</creatorcontrib><title>BCA Channel Routing to Minimize Wirelength for Generalized Channel Problem</title><title>2024 IEEE International Symposium on Circuits and Systems (ISCAS)</title><addtitle>ISCAS</addtitle><description>Routing has a crucial impact on chip design [1]. In this paper, a BCA (Below-Cross-Above) routing, especially for critical routing layers, is proposed. It is assumed that horizontal routing capacity is tight and that all pins of a net need to be connected by a Single Trunk Steiner Tree. Our proposed algorithm is a greedy algorithm based on a well-known Left-Edge algorithm. The track assignment of nets is determined iteratively by taking net priority into account to reduce the vertical length while keeping the required number of tracks as small as possible. In experiments, it is confirmed that the vertical wirelength is reduced by around 40% compared with the track assignment by Left Edge algorithm.</description><subject>Channel routing problem</subject><subject>Chip scale packaging</subject><subject>Circuits and systems</subject><subject>Global routing</subject><subject>Greedy algorithms</subject><subject>Minimization</subject><subject>Pins</subject><subject>Routing</subject><subject>Steiner trees</subject><subject>Wirelength minimization</subject><issn>2158-1525</issn><isbn>9798350330991</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2024</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNo9j8tOwzAURA0SEqX0D1j4BxKuX7G9DBGUoiIQrcSycprr1ihxkBMW8PVE4rGaxWiO5hBCGeSMgb1ebapyo4yWMufAZc5AKSO5OSELq60RCoQAa9kpmXGmTMYUV-fkYhjeADhAwWfk4aYqaXV0MWJLX_qPMcQDHXv6GGLowhfS15CwxXgYj9T3iS4xYnLt1DT_s-fU1y12l-TMu3bAxW_OyfbudlvdZ-un5aoq11ng0oyZAcOM91BzdKaRijlnCmMRxV5rKPbOaauFB6GV8qKx3jfFJKGVU_V0WczJ1Q82IOLuPYXOpc_dn7r4BnGeTb0</recordid><startdate>20240519</startdate><enddate>20240519</enddate><creator>Wang, Zezhong</creator><creator>Shimoda, Masayuki</creator><creator>Takahashi, Atsushi</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope></search><sort><creationdate>20240519</creationdate><title>BCA Channel Routing to Minimize Wirelength for Generalized Channel Problem</title><author>Wang, Zezhong ; Shimoda, Masayuki ; Takahashi, Atsushi</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i248t-80818ff0b2ea8d451aa8689ee3c7706caa7973f03755f3d9ffd609975a5b0623</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2024</creationdate><topic>Channel routing problem</topic><topic>Chip scale packaging</topic><topic>Circuits and systems</topic><topic>Global routing</topic><topic>Greedy algorithms</topic><topic>Minimization</topic><topic>Pins</topic><topic>Routing</topic><topic>Steiner trees</topic><topic>Wirelength minimization</topic><toplevel>online_resources</toplevel><creatorcontrib>Wang, Zezhong</creatorcontrib><creatorcontrib>Shimoda, Masayuki</creatorcontrib><creatorcontrib>Takahashi, Atsushi</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE Electronic Library (IEL)</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Wang, Zezhong</au><au>Shimoda, Masayuki</au><au>Takahashi, Atsushi</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>BCA Channel Routing to Minimize Wirelength for Generalized Channel Problem</atitle><btitle>2024 IEEE International Symposium on Circuits and Systems (ISCAS)</btitle><stitle>ISCAS</stitle><date>2024-05-19</date><risdate>2024</risdate><spage>1</spage><epage>5</epage><pages>1-5</pages><eissn>2158-1525</eissn><eisbn>9798350330991</eisbn><abstract>Routing has a crucial impact on chip design [1]. In this paper, a BCA (Below-Cross-Above) routing, especially for critical routing layers, is proposed. It is assumed that horizontal routing capacity is tight and that all pins of a net need to be connected by a Single Trunk Steiner Tree. Our proposed algorithm is a greedy algorithm based on a well-known Left-Edge algorithm. The track assignment of nets is determined iteratively by taking net priority into account to reduce the vertical length while keeping the required number of tracks as small as possible. In experiments, it is confirmed that the vertical wirelength is reduced by around 40% compared with the track assignment by Left Edge algorithm.</abstract><pub>IEEE</pub><doi>10.1109/ISCAS58744.2024.10558428</doi><tpages>5</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier EISSN: 2158-1525
ispartof 2024 IEEE International Symposium on Circuits and Systems (ISCAS), 2024, p.1-5
issn 2158-1525
language eng
recordid cdi_ieee_primary_10558428
source IEEE Xplore All Conference Series
subjects Channel routing problem
Chip scale packaging
Circuits and systems
Global routing
Greedy algorithms
Minimization
Pins
Routing
Steiner trees
Wirelength minimization
title BCA Channel Routing to Minimize Wirelength for Generalized Channel Problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-13T20%3A45%3A47IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=BCA%20Channel%20Routing%20to%20Minimize%20Wirelength%20for%20Generalized%20Channel%20Problem&rft.btitle=2024%20IEEE%20International%20Symposium%20on%20Circuits%20and%20Systems%20(ISCAS)&rft.au=Wang,%20Zezhong&rft.date=2024-05-19&rft.spage=1&rft.epage=5&rft.pages=1-5&rft.eissn=2158-1525&rft_id=info:doi/10.1109/ISCAS58744.2024.10558428&rft.eisbn=9798350330991&rft_dat=%3Cieee_CHZPO%3E10558428%3C/ieee_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i248t-80818ff0b2ea8d451aa8689ee3c7706caa7973f03755f3d9ffd609975a5b0623%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=10558428&rfr_iscdi=true