LRoute: A delay minimal router for hierarchical CPLDs

K. K. Lee, Martin D F Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper describes LRoute, a novel router for the popular and scalable hierarchical Complex Programmable Logic Devoices (CPLDs). CPLD routing has constraints om 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 languageEnglish (US)
Title of host publicationACM/SIGDA International Symposium on Field Programmable Gate Arrays - FPGA
Pages12-20
Number of pages9
StatePublished - 2001
Externally publishedYes
Event2001 ACM/SIGDA 9th International Sysmposium on Field Programmable Gate Arrays (FPGA 2001) - Monterrey, CA, United States
Duration: Feb 11 2001Feb 13 2001

Other

Other2001 ACM/SIGDA 9th International Sysmposium on Field Programmable Gate Arrays (FPGA 2001)
CountryUnited States
CityMonterrey, CA
Period2/11/012/13/01

Fingerprint

Routers
Field programmable gate arrays (FPGA)
Topology
Mathematical programming
Networks (circuits)
Industry

Keywords

  • Complex Programmable Logic Devices
  • Hierarchical Model
  • Lagrangian Relaxation
  • Routing

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

Lee, K. K., & Wong, M. D. F. (2001). LRoute: A delay minimal router for hierarchical CPLDs. In ACM/SIGDA International Symposium on Field Programmable Gate Arrays - FPGA (pp. 12-20)

LRoute : A delay minimal router for hierarchical CPLDs. / Lee, K. K.; Wong, Martin D F.

ACM/SIGDA International Symposium on Field Programmable Gate Arrays - FPGA. 2001. p. 12-20.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lee, KK & Wong, MDF 2001, LRoute: A delay minimal router for hierarchical CPLDs. in ACM/SIGDA International Symposium on Field Programmable Gate Arrays - FPGA. pp. 12-20, 2001 ACM/SIGDA 9th International Sysmposium on Field Programmable Gate Arrays (FPGA 2001), Monterrey, CA, United States, 2/11/01.
Lee KK, Wong MDF. LRoute: A delay minimal router for hierarchical CPLDs. In ACM/SIGDA International Symposium on Field Programmable Gate Arrays - FPGA. 2001. p. 12-20
Lee, K. K. ; Wong, Martin D F. / LRoute : A delay minimal router for hierarchical CPLDs. ACM/SIGDA International Symposium on Field Programmable Gate Arrays - FPGA. 2001. pp. 12-20
@inproceedings{ca12a63f8db34951b70b3fcdc1a4bc4f,
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 Devoices (CPLDs). CPLD routing has constraints om 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 = "Complex Programmable Logic Devices, Hierarchical Model, Lagrangian Relaxation, Routing",
author = "Lee, {K. K.} and Wong, {Martin D F}",
year = "2001",
language = "English (US)",
pages = "12--20",
booktitle = "ACM/SIGDA International Symposium on Field Programmable Gate Arrays - FPGA",

}

TY - GEN

T1 - LRoute

T2 - A delay minimal router for hierarchical CPLDs

AU - Lee, K. K.

AU - Wong, Martin D F

PY - 2001

Y1 - 2001

N2 - This paper describes LRoute, a novel router for the popular and scalable hierarchical Complex Programmable Logic Devoices (CPLDs). CPLD routing has constraints om 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 Devoices (CPLDs). CPLD routing has constraints om 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 - Complex Programmable Logic Devices

KW - Hierarchical Model

KW - Lagrangian Relaxation

KW - Routing

UR - http://www.scopus.com/inward/record.url?scp=0035006768&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035006768&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0035006768

SP - 12

EP - 20

BT - ACM/SIGDA International Symposium on Field Programmable Gate Arrays - FPGA

ER -