Exploring high throughput computing paradigm for global routing

With aggressive technology scaling, the complexity of the global routing problem is poised to rapidly grow. Solving such a large computational problem demands a high throughput hardware platform such as modern Graphics Processing Units (GPU). In this work, we explore a hybrid GPU-CPU high-throughput...

Full description

Saved in:
Bibliographic Details
Main Authors: Yiding Han, Ancajas, D. M., Chakraborty, K., Roy, S.
Format: Conference Proceeding
Language:English
Subjects:
Concurrent computing
Graphics processing unit
Heuristic algorithms
Instruction sets
Routing
Throughput
Tiles
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:With aggressive technology scaling, the complexity of the global routing problem is poised to rapidly grow. Solving such a large computational problem demands a high throughput hardware platform such as modern Graphics Processing Units (GPU). In this work, we explore a hybrid GPU-CPU high-throughput computing environment as a scalable alternative to the traditional CPU-based router. We introduce Net Level Concurrency (NLC): a novel parallel model for router algorithms that aims to exploit concurrency at the level of individual nets. To efficiently uncover NLC, we design a Scheduler to create groups of nets that can be routed in parallel. At its core, our Scheduler employs a novel algorithm to dynamically analyze data dependencies between multiple nets. We believe such an algorithm can lay the foundation for uncovering data-level parallelism in routing: a necessary requirement for employing high throughput hardware. Detailed simulation results show an average of 4X speedup over NTHU-Route 2.0 with negligible loss in solution quality. To the best of our knowledge, this is the first work on utilizing GPUs for global routing.
ISSN:1092-3152
1558-2434
DOI:10.1109/ICCAD.2011.6105345