الفهرس 
Design Challenges
Problem Formulation and Related WorkOnly 14 pages are availabe for public view
 |  | from | 150 |  |  |
| | | from | 150 | | |
Abstract
Circuit simulation has always been a crucial step in system design and verification. A chip design has to be simulated multiple times to verify that it is properly operating. To ensure the reliability of the design flow, RC parasitic effects are extracted at the interconnect structures and accounted for during simulation. The advanced technologies and continuous scaling are resulting in designs becoming more complex and dense. Real chip designs usually have huge parasitic networks which lead to very expensive, or even intractable, simulation. This increasing cost gave rise to the need for efficient techniques capable of improving the simulation run-time and providing a higher system capacity. One such technique is Model order Reduction (MOR).
MOR is applied on circuits so that, instead of simulating the circuit’s complex model, computation efforts are reduced by simulating a simpler version of it. This model simplification is achieved by reducing the parasitic networks while preserving the circuit’s essential properties as well as the terminals specified by the designer. Even though MOR reduces the system’s complexity, the full reduction of networks having many terminals often results in a smaller dense network instead of a large sparse one. The high density of the resulting network might, in fact, slow down the simulation.
This thesis contributes a novel dense sub-circuit reduction system where the system uses dense sub-graph mining techniques on top of MOR techniques. The proposed has the advantage of being integrated with any MOR technique for circuit reduction as well as any dense sub-graph mining technique. Our work also does a comparative analysis between four dense sub-graph mining algorithms in the context of circuit reduction. The comparison showed that the greedy approximation algorithm for edge density maximization is recommended to be applied on the circuit reduction problem since it has good results in terms of the density of the detected sub-graph, the size of the detected sub-graph, and the scalability of the system on large networks.
To assess the effectiveness of our proposed work, the developed approach was integrated with a commercial tool and tested on real-world designs. It was further evaluated against TICER, a commercial reduction tool, to provide a fair comparison. The results prove the success of our work in reducing the dense sub-circuits in timely manner. The results show improvement in the circuits’ sparsity. Additionally, the results show enhancements in some reduction and simulation aspects.