An Acceleration for Any-Angle Routing Using Quasi-Newton Method on GPGPU

In PCB routing and package routing, routes must satisfy various constraints and specifications. In recent years, an any-angle routing using a quasi-Newton method has been proposed to obtain a routing pattern satisfying the constraints and specifications. However, computational time of the quasi-Newt...

Full description

Saved in:
Bibliographic Details
Main Authors: Honda, Takahiro, Kohira, Yukihide
Format: Conference Proceeding
Language:English
Subjects:
Acceleration
any-angle routing
Function approximation
GPGPU
Graphics processing units
Linear programming
package routing
PCB routing
quasi-Newton method
Routing
Wires
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In PCB routing and package routing, routes must satisfy various constraints and specifications. In recent years, an any-angle routing using a quasi-Newton method has been proposed to obtain a routing pattern satisfying the constraints and specifications. However, computational time of the quasi-Newton method is long because many computations are iterated for the evaluation of the objective function and its gradient. In this paper, we propose an acceleration method for the any-angle routing using a quasi-Newton method by GPGPU. Moreover, we also propose an improved method by omitting the redundant calculation of the evaluation of the objective function. Experiments show that the proposed method is effective by the comparison on the quality of obtained routes and the computational time.
DOI:10.1109/MCSoC.2014.46