Floating metals are special conductors introduced into conductor structures by design for manufacturing (DFM). They bring difficulty to accurate capacitance simulation. In this work, we aim to accelerate the floating random walk (FRW) based capacitance simulation for structures with considerable amounts of general floating metals. We first discuss how the existing modified FRW is affected by the integral surfaces of floating metals and propose an improved placement of integral surface. Then, we propose a hybrid approach called incomplete network reduction to avoid random transitions trapped by floating metals. Experiments on structures from IC and FPD design, which involves multiple floating metals and single or multiple master conductors, have shown the effectiveness of the proposed techniques. The proposed techniques reduce the computational time of capacitance calculation, while preserving the accuracy.

Precharacterizing the transition cubes containing stratified dielectrics is inevitable for the floating random walk (FRW)-based capacitance extraction. Each multilayer-dielectric transition cube is characterized by a pair of Green’s function table (GFT) and weight value table (WVT), and all these GFTs and WVTs usually have large volume and constitute the major memory cost of the FRW algorithm. In this work, we explore the geometric symmetry of the multilayer-dielectric transition cube to enable volume reduction and fast generation of the GFT and WVT. For a general transition cube with stratified dielectrics and the one with four equal-thickness dielectrics, two schemes are proposed to reduce the volume of GFT and WVT by$8\times $and over$10\times $, respectively. Accordingly, an approach for fast generation of the reduced GFT/WVT is proposed, which is proved to produce the same result as the original GFT/WVT values. And, an improved FRW algorithm is proposed to utilize the reduced GFTs/WVTs without the sacrifice of runtime or accuracy. Both theoretical analysis and numerical experiments are conducted to demonstrate the remarkable volume reduction of precharacterization data (GFTs/WVTs). The fast GFT/WVT generation approach and the improved FRW algorithm are also validated with numerical experiments, showing over$10\times $speedup of the precharacterization process, and accurate and memory-efficient capacitance extraction as well.

As the feature size scales down, the process technology becomes more complicated and the design margin shrinks, accurate parasitic extraction during IC design is largely demanded. In this invited paper, we survey the recent advancements on parasitic extraction techniques, especially those enhancing the floating random walk based capacitance solver and incorporating machine learning methods. The work dealing with process variation are also addressed. After that, we briefly discuss the challenges for capacitance extraction under advanced process technologies, including manufacture-aware geometry variations and middle-end-of-line (MEOL) parasitic extraction, etc.

In this paper, two techniques are proposed to enhance the floating random walk (FRW) based capacitance solver for handling non-stratified dielectrics in very large-scale integrated (VLSI) circuits. They follow an existing approach which employs approximate eight-octant transition cubes while simulating the structure with conformal dielectrics. Firstly, the symmetry property of the transition probabilities of the eight-octant cube is revealed and utilized to derive an on-the-fly sampling scheme during the FRW procedure. This avoids the pre-characterization, saves substantial memory, and improves computational accuracy for extracting the structure with non-stratified dielectrics. Then, the space management technique is extended to improve the runtime efficiency for simulating structures with thousands of non-stratified dielectrics. Numerical experiments are carried out to validate the proposed techniques and show their effectiveness for handling structures with conformal dielectrics and air bubbles. Moreover, the extended space management brings up to 1441X speedup for handling structures with from several thousand to nearly one million non-stratified dielectrics.

Capacitance extraction or simulation has become a challenging problem in the computer-aided design of integrated circuits (ICs), flat panel display, etc. Due to its scalability and reliability, the parallel floating random walk (FRW) based capacitance solver is widely used. In practice, the parallel FRW algorithms involve an issue of reproducibility and may consume a lot of time in the scenario requesting high accuracy. To relieve these issues, techniques are developed in this paper to enhance the reproducibility and reusability of the parallel FRW based simulation. With them we ensure that same result is reproduced while rerunning the parallel FRW solver with same setting. A "jump start" feature is also implemented to reduce the total runtime of simulating same structure with multiple accuracy criteria. Experiments on shared-memory and distributed-memory platforms have validated the effectiveness of the presented techniques. Compared with a synchronization based approach ensuring the reproducibility, the proposed technique with static workload allocation can brings 4.8X more parallel speedup while sacrificing nothing.

Principal component analysis (PCA) is widely used for dimension reduction and embedding of real data in social network analysis, information retrieval, and natural language processing, etc. In this work we propose a fast randomized PCA algorithm for processing large sparse data. The algorithm has similar accuracy to the basic randomized SVD (rPCA) algorithm (Halko et al., 2011), but is largely optimized for sparse data. It also has good flexibility to trade off runtime against accuracy for practical usage. Experiments on real data show that the proposed algorithm is up to 9.1X faster than the basic rPCA algorithm without accuracy loss, and is up to 20X faster than the \texttt{svds} in Matlab with little error. The algorithm computes the first 100 principal components of a large information retrieval data with 12,869,521 persons and 323,899 keywords in less than 400 seconds on a 24-core machine, while all conventional methods fail due to the out-of-memory issue.

Due to the advantages on scalability and reliability, the floating random walk (FRW) algorithm has been widely adopted for calculating the capacitances among three-dimensional (3-D) conductors. This is evidenced by the industrial practice of interconnect capacitance extraction during the design of high-performance very large-scale integrated (VLSI) circuits. In this work, the FRW algorithm is enhanced through the distributed parallel computing. With an efficient and adaptive task allocation scheme, the communication among different computer nodes is largely reduced. A distributed algorithm for accelerating the space management is also proposed. They have been implemented with Message Passing Interface (MPI) and applied to the high-precision capacitance simulation for touchscreen design and the interconnect capacitance extraction of VLSI circuits. Experiments on a computer cluster show that the proposed techniques achieve up to 114X speedup while using 120 cores, and build up the space management structure for a VLSI case including two million conductor blocks in just 22 seconds (37X parallel speedup on 60 cores).