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-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.