Algorithms for large - scale power delivery network analysis on massively parallel architectures

Abstract

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 electromi- gration 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-the- art 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.

Το δίκτυο τροφοδοσίας αποτελεί ένα ζωτικής σημασίας υποσύστημα στα μοντέρνα ολοκληρωμένα κυκλώματα, καθώς καθορίζει τη σωστή λειτουργία και την απόδοση του κυκλώματος. Λόγω της συνεχούς μείωσης της κλίμακας σχεδιασμού, υπάρχει μια αυξανόμενη ανάγκη για ακριβή και αποδοτική ανάλυση του δικτύου τροφοδοσίας. Ο αντίκτυπος των πρωτευόντων φαινομένων, όπως η πτώση τάσης ή η ηλεκτρομετανάστευση, αλλά και των δευτερευόντων φαινομένων, όπως η επίδραση του φαινομένου Joule heating στους αγωγούς, που δε λαμβάνονταν υπόψη μέχρι πρότινος, καθιστούν απαραίτητη την ύπαρξη κατάλληλων και αποδοτικών μεθοδολογιών για την ηλεκτρική και θερμική ανάλυση του δικτύου τροφοδοσίας.Ένα τυπικό δίκτυο τροφοδοσίας μοντελοποιείται ως ένα δίκτυο RLC και η ηλεκτρική και θερμική ανάλυσή του ανάγεται στην επίλυση ενός συστήματος γραμμικών εξισώσεων. Λόγω του μεγάλου μεγέθους των σύγχρονων δικτύων τροφοδοσίας (τα οποία περιλαμβάνουν εκατομμύρια ή δισεκατομμύρια κόμβους), η ανάλυσή τους είναι μια πολύ απαιτητική διαδικασία, τόσο από άποψη υπολογιστικής ισχύος όσο και από άποψη απαιτήσεων σε μνήμη. Οι παράλληλες αρχιτεκτονικές που έχουν εμφανιστεί πρόσφατα, προσφέρουν πολύ μεγάλη υπολογιστική ισχύ με αποτέλεσμα να εμφανίζονται ως η κατάλληλη πλατφόρμα για την εκτέλεση υπολογιστικά απαιτητικών αλγορίθμων. Ωστόσο, οι περισσότεροι αλγόριθμοι που χρησιμοποιούνται σήμερα στα περισσότερα εμπορικά εργαλεία για την ανάλυση του δικτύου τροφοδοσίας δεν εμπεριέχουν μεγάλο βαθμό παραλληλισμού και έχουν υπερβολικές απαιτήσεις μνήμης, γεγονός που καθιστά την υλοποίησή τους σε παράλληλες αρχιτεκτονικές ιδιαίτερα δύσκολη και σε αρκετές περιπτώσεις ανέφικτη.Βάσει των παραπάνω, η παρούσα διατριβή προτείνει τρεις νέες μεθοδολογίες για την ανάλυση των δικτύων τροφοδοσίας μεγάλης κλίμακας που εμπεριέχονται στα σύγχρονα ολοκληρωμένα κυκλώματα. Παρουσιάζονται δύο αλγόριθμοι για την ηλεκτρική ανάλυση και ένας αλγόριθμος για τη συνδυασμένη ηλεκτρο-θερμική ανάλυση του δικτύου τροφοδοσίας. Το νέο χαρακτηριστικό των προτεινόμενων αλγορίθμων είναι ο μεγάλος βαθός παραλληλισμού σε πολλαπλά επίπεδα, ο οποίος τους καθιστά κατάλληλους για την υλοποίηση σε παράλληλες αρχιτεκτονικές. Οι προτεινόμενοι αλγόριθμοι επιταχύνουν σημαντικά τη διαδικασία προσομοίωσης, επιτυγχάνοντας έως και τρεις τάξεις μεγέθους επιτάχυνση για την ηλεκτρική ανάλυση και μία τάξη μεγέθους επιτάχυνση για την ηλεκτρο-θερμική ανάλυση, ενώ την ίδια στιγμή κλιμακώνουν γραμμικά με τον αριθμό των κόμβων στο δίκτυο τροφοδοσίας τόσο σε υπολογιστική πολυπλοκότητα όσο και σε απαιτήσεις σε μνήμη.