Routing is a crucial step in the VLSI design flow. With advancements in manufacturing technology, more constraints have emerged in design rules, particularly regarding obstacles during routing, leading to increased routing complexity. Unfortunately, many global routers struggle to generate efficient obstacle-free solutions due to the lack of scalable obstacle-avoiding tree generation methods and the capability to handle modern designs with complex obstacles and nets. In this work, we propose an efficient obstacle-aware global routing flow for VLSI designs with obstacles. The flow includes a rule-based obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) algorithm during the tree generation phase. This algorithm is both scalable and fast, providing tree topologies avoiding obstacles in the early stage globally. With its guidance, in the later stages, the OARSMT-guided and obstacle-aware sparse maze routing are proposed to further minimize obstacle violations and reduce overflow costs. Compared to previously advanced methods on the benchmark with obstacles, our approach successfully eliminates obstacle violations and reduces wirelength and overflow cost, while sacrificing only a limited number of via counts and runtime overhead.

With the approaching post-Moore era, it is becoming increasingly impractical to decrease the transistor size in digital VLSI for better performance. To address this issue, one approach is to optimize the digital circuit at the transistor level to reduce the transistor count. Although previous works have explored ways to conduct transistor network optimization, most of these efforts have focused on single-output networks or applied heuristics only, limiting their scope or optimization quality. In this paper, we propose an exact transistor network optimization algorithm that supports multi-output logic and is formulated as a SAT problem. Our approach maintains a high optimization level by employing the exact algorithm, while also incorporating a hybrid process that uses a heuristic algorithm to predict the solution range as a guidance for better efficiency. Experimental results show that the proposed algorithm has a 5.32% better optimization level given 54% less runtime compared with the state-of-the-art work.

For VLSI physical design, the routing problem has attracted attention in recent years due to the emerging manufacturing technologies. Tree generation is one key routing step directly affecting the routing quality, which is to find the rectilinear steiner minimal tree (RSMT) of each net. Ordinary RSMT algorithms such as FLUTE fail to generate valid trees avoiding obstacles. In contrast, current obstacle-avoiding RSMT (OARSMT) algorithms can incur a large runtime overhead compared with FLUTE. To reduce the runtime cost while maintaining the quality, a novel OARSMT algorithm is proposed in this work. By proposing multiple rule-based routing schemes, which are fast while maintaining the awareness of global conditions from mature RSMT solutions, OARSMT solutions with reasonable qualities can be quickly obtained, even for large and complicated cases. Compared with the state-of-the-art works, traded with limited wirelength overhead, the proposed algorithm has ∼10x-2700x and ∼150x-5800x runtime speedup under randomized testcases and standard benchmarks, respectively.