Efficient techniques for handling and sparsification of dense matrices in very large-scale circuit simulation

Abstract

The integration of more components into modern Systems-on-Chip (SoCs) due to the ever increasing technology scaling has led to very large parasitic networks consisting of million of nodes, which have to be simulated in many times or frequencies to verify the proper operation of chip. Moreover, because of the aggressive technology scaling, the reliability analysis of a SoC requires to take into account, except for the self-inductance which was sufficient in older technologies, but also the mutual inductance between the different subsystems in SoC. However, the inclusion of all mutual inductive couplings results in a fully dense inductance matrix that renders the circuit simulation computationally expensive. Model Order Reduction (MOR) techniques have been employed routinely to substitute the large scale parasitic model by a model of lower order with similar response at the input/output ports. However, all established MOR techniques result in dense system matrices that render their simulation impractical.To this end, in this dissertation we present efficient techniques for the solution of the linear systems arising in transient analysis of large mutually inductive circuits, as well as a methodology for the sparsification of the dense matrices resulting from MOR. The proposed techniques for solving the linear systems in transient analysis involve the compression of the dense inductance matrix, approximating suitably sub-blocks of it by low-rank products and the development of a general purpose preconditioner for the iterative solution of the transient linear system (which comprises sparse blocks alongside the dense inductance block). On the other hand, our proposed methodology for the sparsification of the dense MOR matrices employs a sequence of algorithms based on the computation of the nearest diagonally dominant matrix, which has a direct correspondence to graph and the subsequent sparsification of that graph. Experimental results for the sparsification of the dense MOR matrices indicate that high sparsity ratio of the reduced system matrices can be achieved with very small loss of accuracy, while the proposed techniques for solving the linear systems in transient analysis of large mutually inductive circuits indicate substantial compression rates of the dense inductance matrix without compromising accuracy, along with considerable reduction in iteration count and execution time of iterative solution methods.

Η τοποθέτηση περισσότερου υλικού σε ένα μοντέρνο SoC (System-on-Chip) εξαιτίας της ολοένα και μειούμενης τεχνολογίας ολοκλήρωσης έχει οδηγήσει σε πολύ μεγάλα παρασιτικά RLC δίκτυα αποτελούμενα από εκατομμύρια κόμβους, τα οποία πρέπει να προσομοιωθούν σε πολλές χρονικές στιγμές και συχνότητες έτσι ώστε να επαληθευτεί η σωστή λειτουργία του ολοκληρωμένου κυκλώματος. Επίσης, ο έλεγχος αξιοπιστίας ενός ολοκληρωμένου, εξαιτίας και πάλι της μειούμενης τεχνολογίας ολοκλήρωσης, απαιτεί να ληφθεί υπόψιν η επίδραση εκτός της παρασιτικής αυτεπαγωγής των υποσυστημάτων σε ένα SoC, που επαρκούσε σε παλαιότερες τεχνολογίες, αλλά και όλων των αμοιβαία επαγωγικών συζεύξεων μεταξύ αυτών. Ωστόσο η συμπερίληψη όλων των αμοιβαία επαγωγικών συζεύξεων καταλήγει σε ένα πλήρως πυκνό πίνακα επαγωγών που καθιστά την προσομοίωση κυκλώματος δύσκολα διαχειρίσιμη τόσο από αποθηκευτικής όσο και από υπολογιστικής πλευράς. Τεχνικές Μείωση Τάξης Μοντέλου (ΜΤΜ) έχουν χρησιμοποιηθεί συστηματικά για να αντικαταστήσουν το πολύ μεγάλης κλίμακας παρασιτικό RLC μοντέλο με ένα πολύ μικρότερης τάξης μοντέλο με παρόμοια απόκριση στις θύρες εισόδου/εξόδου. Ωστόσο, όλες οι τεχνικές ΜΤΜ καταλήγουν σε ένα μοντέλο με πυκνούς πίνακες που καθιστούν την προσομοίωση, και σε αυτήν την περίπτωση, μη πρακτική.Έτσι, σε αυτή την διδακτορική διατριβή παρουσιάζουμε αποδοτικές τεχνικές για την επίλυση των γραμμικών συστημάτων που προκύπτουν κατά την μεταβατική ανάλυση πολύ μεγάλων αμοιβαία επαγωγικών κυκλωμάτων, όπως επίσης και μια μεθοδολογία για την αραιοποίηση των πυκνών πινάκων που προκύπτουν μετά την ΜΤΜ. Οι προτεινόμενες τεχνικές για την επίλυση των γραμμικών συστημάτων στην μεταβατική ανάλυση περιλαμβάνουν την συμπίεση του πυκνού πίνακα επαγωγών προσεγγίζοντας κατάλληλα υπό-μπλοκ του αρχικού πίνακα με low-rank γινόμενα, όπως επίσης και την ανάπτυξη ενός προρυθμιστή γενικού σκοπού για την επαναληπτική επίλυση του γραμμικού συστήματος που πρέπει να λύσουμε κατά την μεταβατική ανάλυση (το οποίο συνίσταται από αραιά μπλοκ μαζί με το πυκνό μπλοκ των επαγωγών). Από την άλλη μεριά, η προτεινόμενη μεθοδολογία για την αραιοποίηση των πυκνών πινάκων μετά την ΜΤΜ χρησιμοποιεί μια ακολουθία αλγορίθμων βασισμένη στον υπολογισμό του κοντινότερου διαγώνια υπερισχύων πίνακα, που έχει μια ένα-προς-ένα αντιστοιχία με γράφο, και την εν- συνεχεία αραιοποίηση αυτού του γράφου. Τα πειραματικά μας αποτελέσματα υποδεικνύουν ότι μπορεί να επιτευχθεί ένα αρκετά αραιό σύστημα ελαττωμένων πινάκων, μετά την ΜΤΜ, με πολύ μικρή μείωση της ακρίβειας προσομοίωσης ενώ οι προτεινόμενες τεχνικές στην επίλυση των γραμμικών συστημάτων κατά την μεταβατική ανάλυση υποδεικνύουν ουσιώδη συμπίεση του πίνακα επαγωγών χωρίς να θυσιάζεται η ακρίβεια προσομοίωσης, σε συνδυασμό με μια αξιοπρόσεχτη μείωση στον αριθμό των επαναλήψεων και τον συνολικό χρόνο εκτέλεσης των επαναληπτικών μεθόδων επίλυσης.