Timing-driven physical design EDA algorithms for tackling process variations

Abstract

Moore’s law states that the total number of transistors of an integrated circuit approximatelydoubles every two years. Maintaining this trend, requires tools able to cope with the everincreasingcomplexity of chip design. Electronic Design Automation (EDA) has so far addressedthis problem by providing automated tools and flows which enabled designers to handle chipsconsisting of more than a few millions transistors.However, the ever shrinking of the size of transistors and interconnects, now poses new obstaclesfor designers and automated EDA flows. Smaller dimension devices, although providingmore speed and less area, pose new challenges. Contemporary Deep-Sub-Micron (DSM) fabricationprocesses suffer from the presence of manufacturing variations, due to unpredictability inthe exact dimensions and characteristics of transistors and wires. These variations now affecthigh-level characteristics of the chips such as their speed and power consumption. Technologyvendors have always provided a number of characterizations for each circuit element atdifferent operating scenaria (operating corners). Nowadays, more corners are needed to accountfor process variations, which adds to the complexion of achieving closure for all cornerssimultaneously.One way to mitigate this phenomenon is to integrate multiple operating scenaria into asingle, unified model, which can then be incorporated into existing flows. Statistical modelsoffer this capability. They can encapsulate each corner into a random distribution, which canreflect the variation of speed and power consumption characteristics of the circuit elements. Inthis case, the delay and power becomes statistical rather than deterministic. Although suchstatistical models exist, their use in EDA flows has not been demonstrated. An alternative approachfor combating variations is to design circuits which include clock-less or asynchronousspeed-independent designs. These, possess the property of adjusting to their operating conditionsinstead of failing for fixed constraints. This approach requires further development ofasynchronous circuits, the implementation of which has not been proven viable in EDA flows.Currently, there is significant lack of EDA tools capable of handling asynchronous circuits,making their use impossible in industrial designs.In this work, we have developed and evaluated placement and post-placement optimizationalgorithms, which aim to tackle the problem of process variations in contemporary EDA flows.We present a novel placement algorithm, SCPlace, which based on a statistical timing modelin its optimization engine, alleviates the need for multi-corner placement. SCPlace is the first large-scale statistical optimization tool appearing in literature targeting placement, which is thecornerstone of physical implementation. SCPlace exploits statistical wire delay bounds, generatedby our novel statistical slack assignment algorithms, which distribute slack according tostatistical distributions. We have also developed a post-placement statistical leakage reductionalgorithm, which is able to perform in-place statistical leakage reduction without negativelyaffecting statistical delay. Our third contribution is CPlace, a fully automated placer for asynchronous,cyclic circuits. CPlace is able to meet both performance and speed independentconstraints.Experimental results indicate that SCPlace compares favourably with state-of-the-art, industrialand academic placers, providing routable designs which achieve superior timing yieldcomputed from the resulting statistical delay distributions. Our statistical leakage reductionflow achieves 20% average leakage reduction, without affecting the statistical delay of the preplacedcircuit. Our results also show that CPlace provides routable placements for asynchronouscircuit and superior placements compared to state-of-the-art industrial and academic placerswhich cannot guarantee speed independent constraints. All three of our flows have been designedwith ease of integration into contemporary EDA flows in mind, through the use of onlyindustry-standard formats and by collaborating with commercial EDA tools.

Ο νόμος του Moore υποδεικνύει ότι ο αριθμός των τρανζίστορ σε ένα ολοκληρωμένοκύκλωμα διπλασιάζεται κάθε δύο χρόνια. Για να διατηρηθεί αυτή η τάση, απαιτείταιτόσο οι διαστάσεις των τρανζίστορ να συρρικνώνονται, όσο και να υπάρχουν εργαλείαικανά να χειριστούν την αυξανόμενη πολυπλοκότητα των κυκλωμάτων. Ο τομέας τουΗλεκτρονικού Σχεδιαστικού Αυτοματισμού (ΗΣΑ) μέχρι τώρα, αντιμετώπισε το πρό-βλημα αυτό, προσϕέροντας ροές και εργαλεία, τα οποία έκαναν δυνατό το χειρισμόκυκλωμάτων με πλήθος τρανζίστορ αρκετών εκατομμυρίων. Σήμερα όμως, τα εργα-λεία ΗΣΑ πρέπει να αντιμετωπίσουν και το ϕαινόμενο της κατασκευαστικής μεταβλη-τότητας, το οποίο εισάγει αβεβαιότητα σε σημαντικά χαρακτηριστικά των κυκλωμάτων,όπως ο χρονισμός και η κατανάλωση.Σε αυτήν τη διατριβή, αναπτύξαμε και αξιολογήσαμε αλγορίθμους βελτιστοποίησηςγια το στάδιο της τοποθέτησης και της βελτιστοποίησης μετά την τοποθέτηση, ώστενα αντιμετωπιστεί το ϕαινόμενο της μεταβλητότητας. Παρουσιάζουμε έναν καινοτόμοαλγόριθμο τοποθέτησης, SCPlace, ο οποίος βασιζόμενος στη στατιστική χρονική ανά-λυση του κυκλώματος, χειρίζεται την αβεβαιότητα στον χρονισμό. Επιπλέον, αναπτύ-ξαμε ένα εργαλείο βελτιστοποίησης της κατανάλωσης λόγω ρεύματος διαρροής, μετάτην τοποθέτηση, το οποίο βελτιστοποιεί για κατανάλωση χωρίς να επηρεάζει αρνητικάτο στατιστικό χρονικό ωϕέλιμο του κυκλώματος. Τέλος, η τρίτη συνεισϕορά της δια-τριβής αυτής είναι το εργαλείο CPlace, ένα εργαλείο τοποθέτησης, το οποίο μπορεί ναχειρίζεται ασύγχρονα κυκλώματα, τα οποία είναι λιγότερο επιρρεπή στα αποτελέσματατης μεταβλητότητας.Τα πειραματικά αποτελέσματα δείχνουν ότι το SCPlace πετυχαίνει καλύτερα απο-τελέσματα από τα καλύτερα βιομηχανικά και ακαδημαϊκά εργαλεία όσο αϕορά τη στα-τιστική συμπεριϕορά του χρονισμού του κυκλώματος μετά την τοποθέτηση. Η ροή μαςγια βελτιστοποίηση της κατανάλωσης πετυχαίνει 20% μείωση της κατανάλωσης χωρίςκαμία επίδραση στο στατιστικό χρονικό ωϕέλιμο του κυκλώματος. Τέλος, το CPlaceμπορεί με επιτυχία να χειριστεί ασύγχρονα κυκλώματα σεβόμενο τις χρονικές υποθέ-σεις οι οποίες είναι απαραίτητες για τη λειτουργία τους. Όλα τα εργαλεία που αναπτύ-ξαμε συμμορϕώνονται με βιομηχανικά στάνταρ και έχουν σχεδιαστεί ώστε να μπορούννα ενταχθούν άμεσα σε βιομηχανικές ροές υλοποίησης κυκλωμάτων.