Timing optimization techniques for scalable physical synthesis of digital integrated circuits

Abstract

Physical synthesis is a fundamental part of the design flow of the modern VLSI since it transforms automatically the designer's RTL models to an integrated circuit ready for fabrication. As the technology continues to scale and the number of transistors per chip grows, the complexity of designing an integrated circuit increases steadily. The burden of delivering efficient designs passes through the physical synthesis tools that should satisfy two contradictory goals. First comes Quality-of-Results (QoR), i.e., to place and route a design that satisfies the required timing, area and power constraints. Then, comes efficiency that allows executing physical synthesis algorithms in the least amount of time even for very large designs. This thesis tackles exactly those two contradicting goals focusing on timing closure of complex digital designs. Timing closure is a complex process that involves many iterative optimization steps applied in various phases of the physical design flow. The scaling of the size of the designs, the examination of multiple modes of operations and multiple design corners including also On-Chip Variations (OCV), are major critical challenges that timing optimization should face effectively. To this end, we propose four timing optimization techniques that tackle efficiently such challenges. The proposed approaches can be used both for global timing optimization at the first steps of the physical synthesis flow or close to the end where repairing timing violations requires incremental operations that are nondisruptive and execute as fast as possible. In every case, the proposed methods are tuned for runtime scalability that allows their application to very large designs without sacrificing QoR. The first approach focuses on incremental timing-driven placement, with the goal to fix the placement of timing-critical cells and improve overall timing. As opposed to previous methods that independently move combinational gates, flip-flops, and/or LCBs using loosely-connected algorithms, we propose, an Lagrangian Relaxation-based (LR) timing-driven placement algorithm that handles the relocation of all types of cells in a unified manner. Cells are allowed to move within an appropriately positioned search window, the location of which is decided by force-like timing vectors covering both late and early timing violations. The magnitude of these timing vectors is determined by the value of the corresponding Lagrange Multipliers. The introduced placement optimization is applied in conjunction with a newly proposed flip-flop clustering algorithm that (re)assigns flip-flops to local clock buffers, to separate flip-flops with incompatible timing profiles and to facilitate the subsequent timing-optimization steps. The other two approaches focus on LR-based gate sizing and voltage threshold assignment techniques. Firstly, we present a way to transform a robust gate sizer, used as global optimizer, into an incremental optimizer that can successfully improve the timing, power and area of the design really fast even when considering multiple corners. The proposed methodology relies on different initialization of the LMs and therefore the solution is orthogonal to the core of the optimizer. This means that it is easy to be generalized and adopted by other similar timing optimizations to be transformed in an incremental context. Physical synthesis engines need to embrace all available parallelism to cope with the increasing complexity of modern designs and still offer high quality of results. To achieve this goal, the involved algorithms need to be expressed in a way that facilitates fast execution time across a range of computing platforms. Motivated by this target, in this thesis, we introduce a task-based parallel programming template that can be used for speeding up timing and power optimization. This approach utilizes all available parallelism and enables significant speedup relative to custom multithreaded approaches. Task-based parallelism is applied to all parts of the optimization engine covering also parts that are traditionally executed serially for preserving maximum timing accuracy. Additionally, this result was supported by two dynamic heuristics that restrict the number of examined gate sizes and simplify local timing updates. Both heuristics trade off additional runtime reduction with marginal leakage power increases. Timing optimization methods are completed by a novel methodology to reduce the timing impact of the clock-induced OCV. To reduce the magnitude of the clock-induced OCV, we incrementally relocate the flip-flops and the clock gaters in a bottom-up manner to implicitly guide the clock tree synthesis engine to produce clock trees with increased common clock tree paths. The relocation of the clock elements is performed using a soft clustering approach that is orthogonal to the clock tree synthesis method used. The clock elements are repeatedly relocated and incrementally re-clustered, thus gradually forming better clusters and settling to more appropriate positions to increase the common paths of the clock tree. This behavior is verified by applying the proposed method in industrial designs, resulting in clock trees which are more resilient to process variations, while exhibiting improved overall timing.

Η φυσική σχεδίαση αποτελεί ένα θεμελιώδες μέρος της ροής σχεδιασμού των σύγχρονων VLSI καθώς μετατρέπει αυτοματοποιημένα την περιγραφή της λειτουργίας του κυκλώματος από γλώσσες περιγραφής υλικού, όπως η Verilog και η VHDL, σε ολοκληρωμένα κυκλώματα έτοιμα για κατασκευή. Με τη συνεχόμενη όμως σμίκρυνση κατασκευής των ολοκληρωμένων κυκλωμάτων ακολουθώντας το νόμο του Moore, η τεχνολογία των ημιαγωγών παρέχει κατ' επανάληψη περισσότερα τρανζίστορ αυξάνοντας παράλληλα την πολυπλοκότητα σχεδίασης ενός ολοκληρωμένου κυκλώματος. Έτσι τα εργαλεία φυσικής σύνθεσης πρέπει να παρέχουν αποτελεσματικά κυκλώματα ικανοποιώντας δύο αντιφατικούς στόχους. Πρώτος στόχος είναι η ποιότητα των τελικών αποτελεσμάτων. Δηλαδή το τελικό κύκλωμα να μην παραβιάζει τους περιορισμούς χρονισμού, εμβαδού και ισχύος. Ενώ ο δεύτερος στόχος είναι η αποδοτικότητα. Έτσι, οι πολύπλοκοι αλγόριθμοι φυσικής σύνθεσης θα πρέπει να εκτελούνται γρήγορα ώστε να είναι εφικτή η υλοποίηση ακόμη και του πιο σύνθετου κυκλώματος σε ένα εύλογο χρόνο. Η παρούσα Διατριβή ασχολείται ακριβώς με αυτούς τους δύο στόχους εστιάζοντας στην ικανοποίηση των χρονικών περιορισμών των σύγχρονων πολύπλοκων ψηφιακών κυκλωμάτων. Η ικανοποίηση των χρονικών περιορισμών αποτελεί μία σύνθετη διαδικασία που αποτελείται από πολλαπλές επαναληπτικές μεθόδους που εφαρμόζονται σε διάφορα στάδια της φυσικής σύνθεσης. Με την περαιτέρω όμως σμίκρυνση της τεχνολογίας κατασκευής των ολοκληρωμένων κυκλωμάτων, οι τεχνικές βελτιστοποίησης του χρονισμού καλούνται να αντιμετωπίσουν αποτελεσματικά νέες προκλήσεις. Έτσι, στην παρούσα Διατριβή προτείνονται τέσσερεις διαφορετικές τεχνικές βελτιστοποίησης της χρονικής συμπεριφοράς των κυκλωμάτων που μπορούν να εφαρμοστούν εξίσου αποτελεσματικά στα αρχικά αλλά και στα τελικά στάδια της ροής φυσικής σύνθεσης. Επίσης, όλες οι προτεινόμενες μέθοδοι έχουν σχεδιαστεί ώστε να εγγυώνται τη γρήγορη ολοκλήρωσή τους ακόμη και σε κυκλώματα μεγάλων διαστάσεων χωρίς να υποβιβάζουν την ποιότητα των τελικών αποτελεσμάτων. Η πρώτη μέθοδος επανατοποθετεί τα κελιά του κυκλώματος με στόχο τη βελτίωση της χρονικής τους συμπεριφοράς λαμβάνοντας υπόψιν τα ιδιαίτερα χαρακτηριστικά της κάθε περίπτωσης (λογικές πύλες και φλιπ φλοπς), διατηρώντας όμως την ποιότητα του κυκλώματος όσον αφορά το συνολικό μήκος καλωδίου και την πυκνότητα χωροθέτησης. Η επαναληπτική μέθοδο βελτιστοποίησης βασίζεται στις αρχές της μη γραμμικής βελτιστοποίησης με περιορισμούς και της αφαίρεσης τους μέσω των πολλαπλασιαστών Langrange. Οι επόμενες δύο μέθοδοι καθορίζουν το μέγεθος των κελιών με σκοπό τη βελτίωση της χρονικής συμπεριφοράς του κυκλώματος χωρίς να αυξηθεί το συνολικό εμβαδόν και η κατανάλωση ισχύος. Αρχικά, προτείνεται μία νέα αρχικοποίηση των πολλαπλασιαστών Lagrange ώστε οι μέθοδοι για τον καθορισμό των μεγεθών των κελιών που χρησιμοποιούνται στα αρχικά στάδια της φυσικής σχεδίασης να μπορούν να εφαρμοστούν εξίσου αποτελεσματικά και στα τελευταία στάδια όπου οι βαθμοί ελευθερίας είναι περιορισμένοι επιτυγχάνοντας ταχύτερη σύγκλιση. Στη συνέχεια, προτείνονται τρόποι επιτάχυνσης των μεθόδων βελτιστοποίησης του χρονισμού των κυκλωμάτων μέσω παράλληλου προγραμματισμού (task-based parallel programming) για την αξιοσημείωτη βελτίωση του χρόνου εκτέλεσης των αλγορίθμων χωρίς την υποβάθμιση των χαρακτηριστικών των κυκλωμάτων. Τέλος, προτείνεται μία νέα τεχνική συσταδοποίησης (clustering) των ακολουθιακών κελιών του κυκλώματος (φλιπ-φλοπς και κελιά απενεργοποίησης του ρολογιού) με στόχο τη δημιουργία ενός βελτιστοποιημένου δικτύου διαμοίρασης ρολογιού περισσότερο ανθεκτικό στις μεταβολές χρονισμού που προκύπτουν από τις διακυμάνσεις στα χαρακτηριστικά του κυκλώματος. Σε κάθε περίπτωση, τα πειραματικά αποτελέσματα όλων των προτεινόμενων μεθόδων αποδεικνύουν την αποτελεσματικότητά και την αποδοτικότητά τους τόσο στη βελτίωση του χρονισμού των κυκλωμάτων των μεθόδων όσο και στο συνολικό χρόνο εκτέλεσης.