Global routing plays a crucial role in printed circuit board (PCB) design and affects the cost of the design significantly. Conventional methods based on rectangular grids have some limitations, whereas this paper introduces a new algorithm that employs a triangular grid model, which offers a more efficient solution to the problem. Firstly, we present a technique to sort all unconnected two-pin nets. Next, a triangular grid graph is constructed to represent the routing resources on the printed circuit board. Finally, we use the concept of maximum flow to identify the paths for global routing and apply detailed routing for the completion of wires. Results from experiments demonstrate that our algorithm is faster than two state-of-the-art routers and does not have any design rule violations for all industrial PCB instances.

Legalized routing is an essential part of PCB automatic routing. It solves the problem of wiring conflicts and obtains routing results that comply with the constraints of design rules. Traditional legalized routing problems mostly use trial backtracking methods, but with increasing design complexity and design rules, avoiding wiring conflicts between networks has become increasingly challenging. This paper proposes a legalized routing algorithm based on linear programming to obtain the optimal wiring trajectory under specified topological constraints. First, the corresponding routing model was established based on numerous routing rules, and a routing grid diagram was found using obstacles as grid points. Secondly, a global routing algorithm was used to obtain the estimated wiring path, and integer linear programming was used to realize the mathematical modeling of the legalized routing problem. Finally, a multi-line simultaneous routing strategy was used to design and implement a detailed routing algorithm, optimizing the routing results. We use C++ to complete the coding work and thoroughly test the PCB use cases of different sizes. The experimental results show that our algorithm still maintains a 100% routing success rate, good time performance, and excellent routing quality with large-scale use cases compared with the trial backtracking method.

Logic synthesis is a critical stage in the VLSI design flow. Logic synthesis methods without considering physical information would result in inferior solutions with timing violations and fail to meet high-performance design requirements. In this paper, we present an analytical placement algorithm that generates timing-friendly physical information to promote high-performance logic synthesis solutions. To address the crucial congestion issue, we first propose a fence-region-aware density model. Then, a boundary-based quadratic penalty model is constructed to ensure the cells do not violate the legal boundaries. Finally, we develop a Polak–Ribière-based placement algorithm to guide the cell movement while optimizing circuit timing. Compared to the advanced placement work, the experimental results on industrial benchmarks show that our proposed algorithm achieves 7% WNS improvement and 12% TNS optimization with 3% better logic depth.