Segmented channel routability via satisfiability

Segmented channel routing is fundamental to the routing of row-based FPGAs. In this paper, we study segmented channel routability via satisfiability. Our method encodes the horizontal and vertical constraints of the routing problem as Boolean conditions. The routability constraint is satisfiable if...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on design automation of electronic systems 2004-10, Vol.9 (4), p.517-528
Main Authors: Hung, William N N, Song, Xiaoyu, Aboulhamid, El Mostapha, Kennings, Andrew, Coppola, Alan
Format: Article
Language:English
Subjects:
Routers
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c371t-8b0f30ef3cd2c28941d87dcad187c457568f24207a04613b58f8b9766b582cbd3
cites cdi_FETCH-LOGICAL-c371t-8b0f30ef3cd2c28941d87dcad187c457568f24207a04613b58f8b9766b582cbd3
container_end_page 528
container_issue 4
container_start_page 517
container_title ACM transactions on design automation of electronic systems
container_volume 9
creator Hung, William N N
Song, Xiaoyu
Aboulhamid, El Mostapha
Kennings, Andrew
Coppola, Alan
description Segmented channel routing is fundamental to the routing of row-based FPGAs. In this paper, we study segmented channel routability via satisfiability. Our method encodes the horizontal and vertical constraints of the routing problem as Boolean conditions. The routability constraint is satisfiable if and only if the net connections in the segmented channel are routable. Empirical results show that the method is time-efficient and applicable to large problem instances.
doi_str_mv 10.1145/1027084.1027090
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_29030244</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>28579603</sourcerecordid><originalsourceid>FETCH-LOGICAL-c371t-8b0f30ef3cd2c28941d87dcad187c457568f24207a04613b58f8b9766b582cbd3</originalsourceid><addsrcrecordid>eNqFkD1PwzAQhi0EEqUws0YMbGnP386IKihIlRiA2XIcG1ylSbETpP57DM3EwvQ-unt00r0IXWNYYMz4EgORoNjiNys4QTPMuSwlheo0c16VLPM5ukhpCwBcCj5D8OLed64bXFPYD9N1ri1iPw6mDm0YDsVXMEUyQ0g-TKNLdOZNm9zVlHP09nD_unosN8_rp9XdprRU4qFUNXgKzlPbEEtUxXCjZGNNg5W0jEsulCeMgDTABKY1V17VlRQiE7F1Q-fo9nh3H_vP0aVB70Kyrm1N5_oxaVIBBcLY_6LishJAs3jzR9z2Y-zyE5oQKjAjWGZpeZRs7FOKzut9DDsTDxqD_ulZTz3rqWf6DQV4bco</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>223614217</pqid></control><display><type>article</type><title>Segmented channel routability via satisfiability</title><source>Association for Computing Machinery:Jisc Collections:ACM OPEN Journals 2023-2025 (reading list)</source><creator>Hung, William N N ; Song, Xiaoyu ; Aboulhamid, El Mostapha ; Kennings, Andrew ; Coppola, Alan</creator><creatorcontrib>Hung, William N N ; Song, Xiaoyu ; Aboulhamid, El Mostapha ; Kennings, Andrew ; Coppola, Alan</creatorcontrib><description>Segmented channel routing is fundamental to the routing of row-based FPGAs. In this paper, we study segmented channel routability via satisfiability. Our method encodes the horizontal and vertical constraints of the routing problem as Boolean conditions. The routability constraint is satisfiable if and only if the net connections in the segmented channel are routable. Empirical results show that the method is time-efficient and applicable to large problem instances.</description><identifier>ISSN: 1084-4309</identifier><identifier>EISSN: 1557-7309</identifier><identifier>DOI: 10.1145/1027084.1027090</identifier><language>eng</language><publisher>New York: Association for Computing Machinery</publisher><subject>Routers ; Studies</subject><ispartof>ACM transactions on design automation of electronic systems, 2004-10, Vol.9 (4), p.517-528</ispartof><rights>Copyright Association for Computing Machinery Oct 2004</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c371t-8b0f30ef3cd2c28941d87dcad187c457568f24207a04613b58f8b9766b582cbd3</citedby><cites>FETCH-LOGICAL-c371t-8b0f30ef3cd2c28941d87dcad187c457568f24207a04613b58f8b9766b582cbd3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Hung, William N N</creatorcontrib><creatorcontrib>Song, Xiaoyu</creatorcontrib><creatorcontrib>Aboulhamid, El Mostapha</creatorcontrib><creatorcontrib>Kennings, Andrew</creatorcontrib><creatorcontrib>Coppola, Alan</creatorcontrib><title>Segmented channel routability via satisfiability</title><title>ACM transactions on design automation of electronic systems</title><description>Segmented channel routing is fundamental to the routing of row-based FPGAs. In this paper, we study segmented channel routability via satisfiability. Our method encodes the horizontal and vertical constraints of the routing problem as Boolean conditions. The routability constraint is satisfiable if and only if the net connections in the segmented channel are routable. Empirical results show that the method is time-efficient and applicable to large problem instances.</description><subject>Routers</subject><subject>Studies</subject><issn>1084-4309</issn><issn>1557-7309</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2004</creationdate><recordtype>article</recordtype><recordid>eNqFkD1PwzAQhi0EEqUws0YMbGnP386IKihIlRiA2XIcG1ylSbETpP57DM3EwvQ-unt00r0IXWNYYMz4EgORoNjiNys4QTPMuSwlheo0c16VLPM5ukhpCwBcCj5D8OLed64bXFPYD9N1ri1iPw6mDm0YDsVXMEUyQ0g-TKNLdOZNm9zVlHP09nD_unosN8_rp9XdprRU4qFUNXgKzlPbEEtUxXCjZGNNg5W0jEsulCeMgDTABKY1V17VlRQiE7F1Q-fo9nh3H_vP0aVB70Kyrm1N5_oxaVIBBcLY_6LishJAs3jzR9z2Y-zyE5oQKjAjWGZpeZRs7FOKzut9DDsTDxqD_ulZTz3rqWf6DQV4bco</recordid><startdate>20041001</startdate><enddate>20041001</enddate><creator>Hung, William N N</creator><creator>Song, Xiaoyu</creator><creator>Aboulhamid, El Mostapha</creator><creator>Kennings, Andrew</creator><creator>Coppola, Alan</creator><general>Association for Computing Machinery</general><scope>AAYXX</scope><scope>CITATION</scope><scope>JQ2</scope><scope>7SC</scope><scope>7SP</scope><scope>8FD</scope><scope>F28</scope><scope>FR3</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20041001</creationdate><title>Segmented channel routability via satisfiability</title><author>Hung, William N N ; Song, Xiaoyu ; Aboulhamid, El Mostapha ; Kennings, Andrew ; Coppola, Alan</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c371t-8b0f30ef3cd2c28941d87dcad187c457568f24207a04613b58f8b9766b582cbd3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2004</creationdate><topic>Routers</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hung, William N N</creatorcontrib><creatorcontrib>Song, Xiaoyu</creatorcontrib><creatorcontrib>Aboulhamid, El Mostapha</creatorcontrib><creatorcontrib>Kennings, Andrew</creatorcontrib><creatorcontrib>Coppola, Alan</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer and Information Systems Abstracts</collection><collection>Electronics &amp; Communications Abstracts</collection><collection>Technology Research Database</collection><collection>ANTE: Abstracts in New Technology &amp; Engineering</collection><collection>Engineering Research Database</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>ACM transactions on design automation of electronic systems</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hung, William N N</au><au>Song, Xiaoyu</au><au>Aboulhamid, El Mostapha</au><au>Kennings, Andrew</au><au>Coppola, Alan</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Segmented channel routability via satisfiability</atitle><jtitle>ACM transactions on design automation of electronic systems</jtitle><date>2004-10-01</date><risdate>2004</risdate><volume>9</volume><issue>4</issue><spage>517</spage><epage>528</epage><pages>517-528</pages><issn>1084-4309</issn><eissn>1557-7309</eissn><abstract>Segmented channel routing is fundamental to the routing of row-based FPGAs. In this paper, we study segmented channel routability via satisfiability. Our method encodes the horizontal and vertical constraints of the routing problem as Boolean conditions. The routability constraint is satisfiable if and only if the net connections in the segmented channel are routable. Empirical results show that the method is time-efficient and applicable to large problem instances.</abstract><cop>New York</cop><pub>Association for Computing Machinery</pub><doi>10.1145/1027084.1027090</doi><tpages>12</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1084-4309
ispartof ACM transactions on design automation of electronic systems, 2004-10, Vol.9 (4), p.517-528
issn 1084-4309
1557-7309
language eng
recordid cdi_proquest_miscellaneous_29030244
source Association for Computing Machinery:Jisc Collections:ACM OPEN Journals 2023-2025 (reading list)
subjects Routers
Studies
title Segmented channel routability via satisfiability
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T03%3A39%3A14IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Segmented%20channel%20routability%20via%20satisfiability&rft.jtitle=ACM%20transactions%20on%20design%20automation%20of%20electronic%20systems&rft.au=Hung,%20William%20N%20N&rft.date=2004-10-01&rft.volume=9&rft.issue=4&rft.spage=517&rft.epage=528&rft.pages=517-528&rft.issn=1084-4309&rft.eissn=1557-7309&rft_id=info:doi/10.1145/1027084.1027090&rft_dat=%3Cproquest_cross%3E28579603%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c371t-8b0f30ef3cd2c28941d87dcad187c457568f24207a04613b58f8b9766b582cbd3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=223614217&rft_id=info:pmid/&rfr_iscdi=true