Fundamental research on electronic design automation in VLSI design : routability

xiv, 119 leaves : ill. ; 30 cm.PolyU Library Call No.: [THS] LG51 .H577M EIE 2010 LuAs the feature size of integrated circuits is revolutionized into nanometer scale, delay of interconnection has become the dominant factor instead of the transistor internal delay. As a result, new demands on interconnection have been proposed to the developers, and they usually enhance the routability of the chip so as to improve the performance of interconnection. Under the general research topic of routability, our work is focused on congestion prediction, clock network synthesis, clock gating design and global routing. They are all critical steps regarding routability concerns in the VLSI physical design. In the early stages of the physical design, congestion prediction is necessary for the routability evaluation. An accurate estimation of a placement result is an effective metric to evaluate the behavior of the corresponding placer. In our work we propose three models, shortest Manhattan distance (SMD) model, Detour model and 3-step approach, for congestion prediction. The two major techniques applied in modern global routers, the detoured routing as well as the rip-up and rerouting, are considered in our work for further enhancement on estimation accuracy. The experimental results of our work present a progress on the performance compared to the previous congestion models. The behavior (timing delay) of clock network synthesis (CNS) is mainly determined by the clock skew and the PVT (Process, Voltage and Temperature) variation factors. In our work, we develop two new clock network synthesizers (DMST and DMSTSS) with several novel techniques to tackle these issues. A dual-MST based perfect matching and a hierarchical buffer sizing are proposed to handle the clock latency range (CLR), which is the major metric for performance evaluation. An iterative buffer insertion approach and a dual-MZ blockage handling technique are developed for a proper distribution of buffers and wires. Internal nodes of the clock tree are relocated based on the delay estimation by SPICE simulation. The clock skew can be further reduced in this procedure. Slew table construction is designed to conform to the constraint on slew rate. In the experimental results it is shown that our synthesizers can effectively reduce the CLR in a much shorter runtime.In the modern synchronous digital circuits, the clock network consumes a great share of the total power cost. Therefore, it is necessary to engage masking gates to reduce its power usage. This technique turns off the according clock tree sections during their idle periods. In the previous clock gating works, switched capacitance is a major metric to denote the power usage of the clock network and the according controller network. Two clock gating works, HKPUcg and HKPUst, are proposed in this thesis. HKPUcg aims at minimizing the switched capacitance,and the objective of HKPUst is reducing the clock skew. Two novel methods of power aware topology generation are proposed, respectively. Moreover, a new decision technique on gate insertion is developed to further reduce the switched capacitance and balance the delay difference. From the experimental results, we can see that our clock gating works can effectively reduce the total power usage. By SPICE simulation, the clock skew is small. Among the modern global routers, the technique of iterative rip-up and rerouting is widely applied. Based on this technique, we develop two methods of dynamic steiner point relocation and edge-based maze routing to further reduce the overflow and shorten the wirelength. The first approach is implemented in constant time with a new data structure constructed for pins, steiner points and subnet connection. The second approach is built up based on the propagation among the global edges instead of global bins. From the experimental results, we can see that our router is efficient and robust compared to the previous state-of-the-art global routers.Department of Electronic and Information EngineeringM.Phil., Dept. of Electronic and Information Engineering, The Hong Kong Polytechnic University, 201