high performance computing on graphics processing units: hgpu.org

The on-chip power delivery network constitutes a vital subsystem of modern nanometer-scale integrated circuits, since it affects in a critical way the performance and correct operation of the devices. As technology scaling enters in the nanometer regime, there is an increasing need for accurate and efficient analysis of the power delivery network. The impact of first-order phenomena like IR drop or electromigration or second-order phenomena like Joule heating, that were neglected until recently, on the power delivery network, necessitates the existence of fast and accurate methodologies for electrical and thermal analysis of the power grid. A typical power delivery network is modeled as an RLC network and its electrical or thermal analysis amounts at solving a linear system of equations. Due to the sheer size of contemporary power delivery networks (which comprise millions or billions of nodes), its analysis is a very challenging process, both in terms of computational and memory requirements. Parallel architectures that have recently appeared and provide a large amount of computational resources appear as the platform of choice for executing computationally demanding algorithms. However, most state-of-theart algorithms for power grid analysis do not entail a large degree of parallelism and have excessive memory requirements, which makes their mapping onto parallel architectures difficult or even infeasible. To this end, this dissertation proposes three new methodologies for analysis of large-scale power delivery networks found in contemporary integrated circuits. We present two algorithms for electrical analysis and one algorithm for combined electro-thermal analysis of the power delivery network. The novel characteristic of the proposed algorithms is the large degree of multi-level parallelism that they entail. As a results, they appear as ideal candidates for mapping onto parallel architectures. Our algorithms are able to greatly accelerate the simulation process, achieving up to two or three orders of magnitude speedup for power grid electrical analysis and one order of magnitude speedup for electro-thermal analysis, while at the same time scaling linearly with the number of power grid nodes.