A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. MDSV DESIGNS FOR GLOBAL ROUTING <s> Modern global routers use various routing methods to improve routing speed and the quality. Maze routing is the most time-consuming process for existing global routing algorithms. This paper presents two bounded-length maze routing (BLMR) algorithms (optimal-BLMR and heuristic-BLMR) to perform much faster routing than traditional maze routing algorithms. The proposed sequential global router, which adopts a heuristic-BLMR, identifies less-wirelength routing results with less runtime than state-of-the-art global routers. This study also proposes a parallel multi-threaded collision-aware global router based on a previous sequential global router. Unlike the conventional partition-based concurrency strategy, the proposed algorithm uses a task-based concurrency strategy. Experimental results reveal that the proposed sequential global router uses less wirelength and runs about 1.9X to 18.67X faster than other state-of-the-art global routers. Compared to the proposed sequential global router, the proposed parallel global router yields almost the same routing quality with average 2.71 and 3.12-fold speedup on overflow-free and hard-to-route benchmarks, respectively, when running on an Intel quad-core system. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. MDSV DESIGNS FOR GLOBAL ROUTING <s> Multiple dynamic supply voltage (MDSV) provides an effective way to reduce dynamic power and is widely used in high-end or low-power designs. The challenge of routing MDSV designs is that the net in MDSV designs needs to be planned carefully to avoid electrical problems or functional failure as a long interconnect path pass through the shutdown power domains. As the first work to address the MDSV global routing problem, power domain-aware routing (PDR) problem is defined and the point-to-point PDR algorithm is also presented herein with look-ahead path selection method and look-up table acceleration approach. For multi-pin net routings, a novel constant-time table-lookup mechanism by invoking four enhanced monotonic routings to fast compute the least-cost monotonic path from every node to the target sub-tree is presented to speed up the query about routing cost (including driven-length slack) to target during multi-source multi-target PDR. Experimental results confirm that the proposed MDSV-based global router can efficiently identify legally optimized routing results for MDSV designs, and can effectively reduce overflow, wire length, inserted level shifters and runtime. <s> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. MDSV DESIGNS FOR GLOBAL ROUTING <s> We study the minimum rectilinear Steiner tree problem in the presence of obstacles. Traversing obstacles is not strictly forbidden, but the total length of each connected component in the intersection of the tree with the interior of the blocked area is bounded by a constant. This problem is motivated by the layout of repeater tree topologies, a central task in chip design. Large blockages might be crossed by wires on higher layers, but repeaters may not be placed within the blocked area. A too long unbuffered piece of interconnect would lead to timing violations. We present a 2-approximation algorithm with a worst case running time of O(k log k)^2, where k is the number of terminals plus the number of obstacle corner points. Under mild assumptions on the obstacle structure, as they are prevalent in chip design, the running time is O(k log k)^2. Compared to strictly obstacle-avoiding trees, the algorithm provides significantly shorter solutions. It solves real world instances with 783\,352 terminals within 126 seconds, proving its practical applicability. <s> BIB003
With the development of process technologies, nanoscale Complementary Metal-Oxide-Semiconductor (CMOS) circuits have experienced a dramatic increase in transistor density over the past three decades, resulting in increased density of power consumption in the circuit. According to related research, the power density on the microprocessor increases at twice the rate every three years. Such high-density power consumption will cause the temperature of the wafer to overheat, which will reduce the reliability of the circuit. Therefore, the problem of power consumption has to be taken seriously. However, most current routing algorithms are proposed to reduce the number of overflows, wirelength and computation time, and all functions operate in the same voltage mode. This traditional voltage supply mode can easily cause excessive unnecessary power consumption. This is because all of the functions of the chip operate in the same high-voltage mode, while other devices that can operate in the lower-voltage mode also operate at high voltages, increasing the power consumption of the chip, thereby reducing battery life. In order to change this voltage supply model, industry chip companies and researchers have proposed Multiple Supply Voltage (MSV) design modes that can control the voltage of different functional components to effectively reduce power consumption through complex control strategies. So multi-voltage design is widely used in advanced applications or low power applications. Compared to MSV designs, MDSV technology can further reduce power consumption. In the MDSV design, the voltage of each power domain can be dynamically changed according to the corresponding power modes. In some power modes, such as standby mode and sleep mode, some power domain can even be set to completely off to save power. The introduction of MDSV brings new opportunities and challenges to the physical design of VLSI circuits, and causes the update of the entire layout domain algorithms. It puts forward new requirements for the physical design process with MDSV as the voltage supply model including layout planning and placement, routing, parameters extraction, etc. It also poses a great challenge to the study of EDA (Electronics Design Automation) tools, which is closely related to the global routing. Reference BIB002 is the first time to build a corresponding global router for a MDSV design mode. However, this work has oversimplified its mathematical problems, and failed to conduct corresponding experimental research from the goal of reducing power. In the MDSV design mode, a net may pass through more than one power domain, some of which may be off and the other power domains are still in active modes. For an active net that has long-distance routing in a closed power domain, a functional conflict may occur if its repeater is placed in a closed power domain. Therefore, limiting the routing length of the active net in the closed power domain is an extremely important global routing problem in the MDSV design. In BIB001 , a lengthlimited maze routing algorithm is proposed to control the wirelength of the routing path. At the same time, BIB003 also proposes a fast SMT construction algorithm that considers the limit of the routable wirelength within obstacles. But none of them considers that the length constraints under different power domains are different. Therefore, the two global routers BIB001 , BIB003 may still produce some illegal routing results under the MDSV design mode. The existing research work on the MDSV design mode mainly focuses on some local stages such as layout and clock tree construction, and lack an effective and complete solution of global routing under the MDSV design. If the novel MDSV is introduced into global routing phase, new global routing issues will arise, including new constraints and mathematical models. It is necessary to propose more effective algorithms. In the research of our team and the industry companies including Cadence Design Systems in the US, we found that the global routing algorithms under MDSV design can effectively reduce the large amount of power consumption, but the current academic community lacks research on the global routing under MDSV design mode. In fact, in order to solve the dynamic power problem, scholars have also developed some new tools based on MSV and other related technologies. However, in these tools, the relevant routing algorithms need to be changed to solve the routing problems in the new design mode. Therefore, it is of great theoretical value and practical significance to find an effective global routing algorithm under the MDSV design and construct an efficient low-power global router.