Ordered escape routing (OER), which seeks the routing paths from some signal pins to the boundary of a pin array in a given order, is an important research topic for PCB design. Although reinforcement learning based methods for OER have been proposed, the routing capacity between two adjacent pins is assumed to be just one. In this work, we propose MCMC-Escape, a Monte-Carlo tree search (MCTS) based multi-capacity ordered escape router, which includes, in turn, the initial solving approach, the improved Monte-Carlo tree search (improved MCTS) process, and the last routing attempt approach based on wires removing and re-routing. In the improved MCTS, the prior knowledge based pruning strategies and the fine-tuning strategy are proposed to enhance the efficiency of solving multi-capacity OER (MC-OER) problems, while the weight adjusting strategy is proposed to address the path occupancy issues arising from multiple capacity. Experimental results demonstrate that MCMC-Escape can effectively solve large-scale MC-OER problems and outperform existing methods in terms of routing success rate, runtime and wire length. For a set of problems with 50×50 pin array, MCMC-Escape achieves 4X higher success rate of routing with 50% less solving time than MCMCF-Router [ 1 ], while reducing the average total wire length.

Ordered escape routing (OER), which means that the pins need to be routed to the boundary of a pin array in a given order, is an important research topic in PCB design. Although OER has been widely investigated, most works assume that the routing capacity between two adjacent pins is just 1 and the structure of the pin array is a grid pin array. In this article, we focus on multi-capacity ordered escape routing (MC-OER) both in grid pin arrays and staggered pin arrays, which means that multiple wires are allowed to pass through between two adjacent pins. We first propose a multi-capacity multi-commodity flow (MC-MCF) model for the MC-OER problem. To accelerate the routing process, MCMCF-Router is proposed. In MCMCF-Router, a wiring resources driven partition strategy is proposed to reduce the problem size, followed by the approach based on routing conflicts. These approaches largely accelerate the MC-MCF model based method and increase the routability with minimal sacrifice on wire length. Experiments on various cases (with up to 525 pins) show that the proposed method achieves 100% routability within reasonable time (<810 seconds). Compared to the state-of-the-art works for single-capacity OER problems, MCMCF-Router performs similarly well or better.

Efficient and lossless digital waveform compression is essentially important for large-scale IC design. In this paper, a compression and storage scheme with detailed-encoding is proposed for compressing the digital waveform including signal transition and auxiliary information. The proposed scheme encodes different values according to their detailed characteristics and utilizes a modified look-up table to reduce the memory cost for storing signal aliases. It is also integrated into a block-by-block compressing procedure which facilitates the secondary lossless compression, pipeline computation and variable-length coding techniques for fast conversion from the output of simulator to the compressed file. Experiments are carried out with 8 digital waveform files from industrial cases. The results show that the proposed method enables 402X average (and up to 1561X) compression ratio with respect to the original VCD format. Compared to the existing compression method for digital waveform, it costs similar or less time while achieving up to 2.56X more compression with about 20% reduction of memory usage averagely.