LRoute: a delay minimal router for hierarchical CPLDs

K. K. Lee; Martin D. F. Wong

doi:10.1145/360276.360290

LRoute: a delay minimal router for hierarchical CPLDs

K. K. Lee, Martin D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

Abstract

This paper describes LRoute, a novel router for the popular and scalable hierarchical Complex Programmable Logic Devices (CPLDs). CPLD routing has constraints on routing topologies due to architectural limitations and performance considerations. These constraints make the problem quite different from FPGA routing and render the routing problem more complicated. Extensions of popular FPGA routers like the maze router performs poorly on such CPLDs. There is also little published work on CPLD routing. LRoute uses a different paradigm based on the Lagrangian Relaxation framework in the theory of mathematical programming. It respects the topology constraints imposed and routes a circuit with minimum delay. We tested this router on a set of industry problems that commercial software failed to route. Our router was able to route all of them very quickly.

Original language	English
Title of host publication	FPGA '01
Subtitle of host publication	Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays
Editors	Martine Schlag, Russell Tessier
Place of Publication	United States
Publisher	Association for Computing Machinery (ACM)
Pages	12-20
Number of pages	9
ISBN (Print)	9781581133417
DOIs	https://doi.org/10.1145/360276.360290
Publication status	Published - Feb 2001
Event	9th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2001 - Doubletree Hotel, Monterey, United States Duration: 11 Feb 2001 → 13 Feb 2001 https://www.isfpga.org/past/fpga2001/ (Conference website) https://www.isfpga.org/past/fpga2001/FinalProg.pdf (Conference program) https://dl.acm.org/doi/proceedings/10.1145/360276 (Conference proceedings)

Publication series

Name	Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA

Symposium

Symposium	9th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2001
Country/Territory	United States
City	Monterey
Period	11/02/01 → 13/02/01
Internet address	https://www.isfpga.org/past/fpga2001/ (Conference website) https://www.isfpga.org/past/fpga2001/FinalProg.pdf (Conference program) https://dl.acm.org/doi/proceedings/10.1145/360276 (Conference proceedings)

User-Defined Keywords

Lagrangian relaxation
complex programmable logic devices
hierarchical model
routing

Access to Document

10.1145/360276.360290

Cite this

Lee, K. K., & Wong, M. D. F. (2001). LRoute: a delay minimal router for hierarchical CPLDs. In M. Schlag, & R. Tessier (Eds.), FPGA '01: Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays (pp. 12-20). (Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA). Association for Computing Machinery (ACM). https://doi.org/10.1145/360276.360290

Lee, K. K. ; Wong, Martin D. F. / LRoute : a delay minimal router for hierarchical CPLDs. FPGA '01: Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays. editor / Martine Schlag ; Russell Tessier. United States : Association for Computing Machinery (ACM), 2001. pp. 12-20 (Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA).

@inproceedings{1b168a04e5594bbe8b27e4ad55963fd0,

title = "LRoute: a delay minimal router for hierarchical CPLDs",

abstract = "This paper describes LRoute, a novel router for the popular and scalable hierarchical Complex Programmable Logic Devices (CPLDs). CPLD routing has constraints on routing topologies due to architectural limitations and performance considerations. These constraints make the problem quite different from FPGA routing and render the routing problem more complicated. Extensions of popular FPGA routers like the maze router performs poorly on such CPLDs. There is also little published work on CPLD routing. LRoute uses a different paradigm based on the Lagrangian Relaxation framework in the theory of mathematical programming. It respects the topology constraints imposed and routes a circuit with minimum delay. We tested this router on a set of industry problems that commercial software failed to route. Our router was able to route all of them very quickly.",

keywords = "Lagrangian relaxation, complex programmable logic devices, hierarchical model, routing",

author = "Lee, {K. K.} and Wong, {Martin D. F.}",

note = "Funding information: This work was partially supported by the National Science Foundation under grant CCR-9912390, by the Texas Advanced Research Program under Grant No. 003658288, and by a grant from the Vantis Corporation. Publisher copyright: {\textcopyright} 2001 ACM; 9th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2001 ; Conference date: 11-02-2001 Through 13-02-2001",

year = "2001",

month = feb,

doi = "10.1145/360276.360290",

language = "English",

isbn = "9781581133417",

series = "Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA",

publisher = "Association for Computing Machinery (ACM)",

pages = "12--20",

editor = "Martine Schlag and Russell Tessier",

booktitle = "FPGA '01",

address = "United States",

url = "https://www.isfpga.org/past/fpga2001/, https://www.isfpga.org/past/fpga2001/FinalProg.pdf, https://dl.acm.org/doi/proceedings/10.1145/360276",

}

Lee, KK & Wong, MDF 2001, LRoute: a delay minimal router for hierarchical CPLDs. in M Schlag & R Tessier (eds), FPGA '01: Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays. Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA, Association for Computing Machinery (ACM), United States, pp. 12-20, 9th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2001, Monterey, California, United States, 11/02/01. https://doi.org/10.1145/360276.360290

LRoute: a delay minimal router for hierarchical CPLDs. / Lee, K. K.; Wong, Martin D. F.
FPGA '01: Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays. ed. / Martine Schlag; Russell Tessier. United States: Association for Computing Machinery (ACM), 2001. p. 12-20 (Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - LRoute

T2 - 9th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2001

AU - Lee, K. K.

AU - Wong, Martin D. F.

N1 - Funding information: This work was partially supported by the National Science Foundation under grant CCR-9912390, by the Texas Advanced Research Program under Grant No. 003658288, and by a grant from the Vantis Corporation. Publisher copyright: © 2001 ACM

PY - 2001/2

Y1 - 2001/2

N2 - This paper describes LRoute, a novel router for the popular and scalable hierarchical Complex Programmable Logic Devices (CPLDs). CPLD routing has constraints on routing topologies due to architectural limitations and performance considerations. These constraints make the problem quite different from FPGA routing and render the routing problem more complicated. Extensions of popular FPGA routers like the maze router performs poorly on such CPLDs. There is also little published work on CPLD routing. LRoute uses a different paradigm based on the Lagrangian Relaxation framework in the theory of mathematical programming. It respects the topology constraints imposed and routes a circuit with minimum delay. We tested this router on a set of industry problems that commercial software failed to route. Our router was able to route all of them very quickly.

AB - This paper describes LRoute, a novel router for the popular and scalable hierarchical Complex Programmable Logic Devices (CPLDs). CPLD routing has constraints on routing topologies due to architectural limitations and performance considerations. These constraints make the problem quite different from FPGA routing and render the routing problem more complicated. Extensions of popular FPGA routers like the maze router performs poorly on such CPLDs. There is also little published work on CPLD routing. LRoute uses a different paradigm based on the Lagrangian Relaxation framework in the theory of mathematical programming. It respects the topology constraints imposed and routes a circuit with minimum delay. We tested this router on a set of industry problems that commercial software failed to route. Our router was able to route all of them very quickly.

KW - Lagrangian relaxation

KW - complex programmable logic devices

KW - hierarchical model

KW - routing

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-0035006768&origin=resultslist&sort=plf-f&src=s&sid=34e6dfce5dc0c661f80c45db8ef87536&sot=b&sdt=b&s=TITLE-ABS-KEY%28LRoute%3A+a+delay+minimal+router+for+hierarchical+CPLDs%29&sl=68&sessionSearchId=34e6dfce5dc0c661f80c45db8ef87536

U2 - 10.1145/360276.360290

DO - 10.1145/360276.360290

M3 - Conference proceeding

SN - 9781581133417

T3 - Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA

SP - 12

EP - 20

BT - FPGA '01

A2 - Schlag, Martine

A2 - Tessier, Russell

PB - Association for Computing Machinery (ACM)

CY - United States

Y2 - 11 February 2001 through 13 February 2001

ER -

Lee KK, Wong MDF. LRoute: a delay minimal router for hierarchical CPLDs. In Schlag M, Tessier R, editors, FPGA '01: Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays. United States: Association for Computing Machinery (ACM). 2001. p. 12-20. (Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA). doi: 10.1145/360276.360290

LRoute: a delay minimal router for hierarchical CPLDs

Abstract

Publication series

Symposium

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this