In the last few decades, two major phenomena have revolutionized the electronic industry – the ever-increasing dependence on electronic circuits and the Complementary Metal Oxide Semiconductor (CMOS) downscaling. These two phenomena have been complementing each other in a way that while electronics, in general, have demanded more computations per functional unit, CMOS downscaling has aptly supported such needs. However, while the computational demand is still rising exponentially, CMOS downscaling is reaching its physical limits. Hence, the need to explore viable emerging nanotechnologies is more imperative than ever. This thesis focuses on streamlining the existing design automation techniques for a class of emerging reconfigurable nanotechnologies. Transistors based on this technology exhibit duality in conduction, i.e. they can be configured dynamically either as a p-type or an n-type device on the application of an external bias. Owing to this dynamic reconfiguration, these transistors are also referred to as Reconfigurable Field-Effect Transistors (RFETs). Exploring and developing new technologies just like CMOS, require tackling two main challenges – first, design automation flow has to be modified to enable tailor- made circuit designs. Second, possible application opportunities should be explored where such technologies can outsmart the existing CMOS technologies. This thesis targets the above two objectives for emerging reconfigurable nanotechnologies by proposing approaches for enabling an Electronic Design Automation (EDA) flow for circuits based on RFETs and exploring hardware security as an application that exploits the transistor-level dynamic reconfiguration offered by this technology. This thesis explains the bottom-up approach adopted to propose a logic synthesis flow by identifying new logic gates and circuit design paradigms that can particularly exploit the dynamic reconfiguration offered by these novel nanotechnologies. This led to the subsequent need of finding natural Boolean logic abstraction for emerging reconfigurable nanotechnologies as it is shown that the existing abstraction of negative unate logic for CMOS technologies is sub-optimal for RFETs-based circuits. In this direction, it has been shown that duality in Boolean logic is a natural abstraction for this technology and can truly represent the duality in conduction offered by individual transistors. Finding this abstraction paved the way for defining suitable primitives and proposing various algorithms for logic synthesis and technology mapping. The following step is to explore compatible physical synthesis flow for emerging reconfigurable nanotechnologies. Using silicon nanowire-based RFETs, .lef and .lib files have been provided which can provide an end-to-end flow to generate .GDSII file for circuits exclusively based on RFETs. Additionally, new approaches have been explored to improve placement and routing for circuits based on reconfigurable nanotechnologies. It has been demonstrated how these approaches led to superior results as compared to the native flow meant for CMOS. Lastly, the unique property of transistor-level reconfiguration offered by RFETs is utilized to implement efficient Intellectual Property (IP) protection schemes against adversarial attacks. The ability to control the conduction of individual transistors can be argued as one of the impactful features of this technology and suitably fits into the paradigm of security measures. Prior security schemes based on CMOS technology often come with large overheads in terms of area, power, and delay. In contrast, RFETs-based hardware security measures such as logic locking, split manufacturing, etc. proposed in this thesis, demonstrate affordable security solutions with low overheads. Overall, this thesis lays a strong foundation for the two main objectives – design automation, and hardware security as an application, to push emerging reconfigurable nanotechnologies for commercial integration. Additionally, contributions done in this thesis are made available under open-source licenses so as to foster new research directions and collaborations.:Abstract List of Figures List of Tables 1 Introduction 1.1 What are emerging reconfigurable nanotechnologies? 1.2 Why does this technology look so promising? 1.3 Electronics Design Automation 1.4 The game of see-saw: key challenges vs benefits for emerging reconfigurable nanotechnologies 1.4.1 Abstracting ambipolarity in logic gate designs 1.4.2 Enabling electronic design automation for RFETs 1.4.3 Enhanced functionality: a suitable fit for hardware security applications 1.5 Research questions 1.6 Entire RFET-centric EDA Flow 1.7 Key Contributions and Thesis Organization 2 Preliminaries 2.1 Reconfigurable Nanotechnology 2.1.1 1D devices 2.1.2 2D devices 2.1.3 Factors favoring circuit-flexibility 2.2 Feasibility aspects of RFET technology 2.3 Logic Synthesis Preliminaries 2.3.1 Circuit Model 2.3.2 Boolean Algebra 2.3.3 Monotone Function and the property of Unateness 2.3.4 Logic Representations 3 Exploring Circuit Design Topologies for RFETs 3.1 Contributions 3.2 Organization 3.3 Related Works 3.4 Exploring design topologies for combinational circuits: functionality-enhanced logic gates 3.4.1 List of Combinational Functionality-Enhanced Logic Gates based on RFETs 3.4.2 Estimation of gate delay using the logical effort theory 3.5 Invariable design of Inverters 3.6 Sequential Circuits 3.6.1 Dual edge-triggered TSPC-based D-flip flop 3.6.2 Exploiting RFET’s ambipolarity for metastability 3.7 Evaluations 3.7.1 Evaluation of combinational logic gates 3.7.2 Novel design of 1-bit ALU 3.7.3 Comparison of the sequential circuit with an equivalent CMOS-based design 3.8 Concluding remarks 4 Standard Cells and Technology Mapping 4.1 Contributions 4.2 Organization 4.3 Related Work 4.4 Standard cells based on RFETs 4.4.1 Interchangeable Pull-Up and Pull-Down Networks 4.4.2 Reconfigurable Truth-Table 4.5 Distilling standard cells 4.6 HOF-based Technology Mapping Flow for RFETs-based circuits 4.6.1 Area adjustments through inverter sharings 4.6.2 Technology Mapping Flow 4.6.3 Realizing Parameters For The Generic Library 4.6.4 Defining RFETs-based Genlib for HOF-based mapping 4.7 Experiments 4.7.1 Experiment 1: Distilling standard-cells from a benchmark suite 4.7.2 Experiment 2A: HOF-based mapping . 4.7.3 Experiment 2B: Using the distilled standard-cells during mapping 4.8 Concluding Remarks 5 Logic Synthesis with XOR-Majority Graphs 5.1 Contributions 5.2 Organization 5.3 Motivation 5.4 Background and Preliminaries 5.4.1 Terminologies 5.4.2 Self-duality in NPN classes 5.4.3 Majority logic synthesis 5.4.4 Earlier work on XMG 5.4.5 Classification of Boolean functions 5.5 Preserving Self-Duality 5.5.1 During logic synthesis 5.5.2 During versatile technology mapping 5.6 Advanced Logic synthesis techniques 5.6.1 XMG resubstitution 5.6.2 Exact XMG rewriting 5.7 Logic representation-agnostic Mapping 5.7.1 Versatile Mapper 5.7.2 Support of supergates 5.8 Creating Self-dual Benchmarks 5.9 Experiments 5.9.1 XMG-based Flow 5.9.2 Experimental Setup 5.9.3 Synthetic self-dual benchmarks 5.9.4 Cryptographic benchmark suite 5.10 Concluding remarks and future research directions 6 Physical synthesis flow and liberty generation 6.1 Contributions 6.2 Organization 6.3 Background and Related Work 6.3.1 Related Works 6.3.2 Motivation 6.4 Silicon Nanowire Reconfigurable Transistors 6.5 Layouts for Logic Gates 6.5.1 Layouts for Static Functional Logic Gates 6.5.2 Layout for Reconfigurable Logic Gate 6.6 Table Model for Silicon Nanowire RFETs 6.7 Exploring Approaches for Physical Synthesis 6.7.1 Using the Standard Place & Route Flow 6.7.2 Open-source Flow 6.7.3 Concept of Driver Cells 6.7.4 Native Approach 6.7.5 Island-based Approach 6.7.6 Utilization Factor 6.7.7 Placement of the Island on the Chip 6.8 Experiments 6.8.1 Preliminary comparison with CMOS technology 6.8.2 Evaluating different physical synthesis approaches 6.9 Results and discussions 6.9.1 Parameters Which Affect The Area 6.9.2 Use of Germanium Nanowires Channels 6.10 Concluding Remarks 7 Polymporphic Primitives for Hardware Security 7.1 Contributions 7.2 Organization 7.3 The Shift To Explore Emerging Technologies For Security 7.4 Background 7.4.1 IP protection schemes 7.4.2 Preliminaries 7.5 Security Promises 7.5.1 RFETs for logic locking (transistor-level locking) 7.5.2 RFETs for split manufacturing 7.6 Security Vulnerabilities 7.6.1 Realization of short-circuit and open-circuit scenarios in an RFET-based inverter 7.6.2 Circuit evaluation on sub-circuits 7.6.3 Reliability concerns: A consequence of short-circuit scenario 7.6.4 Implication of the proposed security vulnerability 7.7 Analytical Evaluation 7.7.1 Investigating the security promises 7.7.2 Investigating the security vulnerabilities 7.8 Concluding remarks and future research directions 8 Conclusion 8.1 Concluding Remarks 8.2 Directions for Future Work Appendices A Distilling standard-cells B RFETs-based Genlib C Layout Extraction File (.lef) for Silicon Nanowire-based RFET D Liberty (.lib) file for Silicon Nanowire-based RFETs

Sie entwickeln Entwurfssysteme für elektronische Baugruppen? Dann gehören für Sie die mit der Pinzuordnung verbundenen Optimierungskriterien - die Verdrahtbarkeit im Elektronikentwurf - zum Berufsalltag. Um die Verdrahtbarkeit unter verschiedenen Gesichtspunkten zu verbessern, werden in diesem Buch neu entwickelte Algorithmen vorgestellt. Sie ermöglichen erstmals die automatisierte Pinzuordnung für eine große Anzahl von Bauelementen in hochkomplexen Schaltungen. Alle Aspekte müssen in kürzester Zeit exakt erfasst, eingeschätzt und im Entwurfsprozess zu einem optimalen Ergebnis geführt werden. Die beschriebenen Methoden reduzieren den Entwicklungsaufwand für elektronische Systeme auf ein Minimum und ermöglichen intelligente Lösungen auf der Höhe der Zeit. Die vorliegende Arbeit behandelt die Optimierung der Pinzuordnung und die dafür notwendige Verdrahtbarkeitsvorhersage im hierarchischen Layoutentwurf. Dabei werden bekannte Methoden der Verdrahtbarkeitsvorhersage aus allen Schritten des Layoutentwurfs zusammengetragen, gegenübergestellt und auf ihre Eignung für die Pinzuordnung untersucht. Dies führt schließlich zur Entwicklung einer Vorhersagemethode, die speziell an die Anforderungen der Pinzuordnung angepasst ist. Die Pinzuordnung komplexer elektronischer Geräte ist bisher ein vorwiegend manueller Prozess. Es existieren also bereits Erfahrungen, welche jedoch weder formalisiert noch allgemein verfügbar sind. In den vorliegenden Untersuchungen werden Methoden der Pinzuordnung algorithmisch formuliert und damit einer Automatisierung zugeführt. Besondere Merkmale der Algorithmen sind ihre Einsetzbarkeit bereits während der Planung des Layouts, ihre Eignung für den hierarchisch gegliederten Layoutentwurf sowie ihre Fähigkeit, die Randbedingungen differenzieller Paare zu berücksichtigen. Die beiden untersuchten Aspekte der Pinzuordnung, Verdrahtbarkeitsvorhersage und Zuordnungsalgorithmen, werden schließlich zusammengeführt, indem die neue entwickelte Verdrahtbarkeitsbewertung zum Vergleichen und Auswählen der formulierten Zuordnungsalgorithmen zum Einsatz kommt. / This work deals with the optimization of pin assignments for which an accurate routability prediction is a prerequisite. Therefore, this contribution introduces methods for routability prediction. The optimization of pin assignments, for which these methods are needed, is done after initial placement and before routing. Known methods of routability prediction are compiled, compared, and analyzed for their usability as part of the pin assignment step. These investigations lead to the development of a routability prediction method, which is adapted to the specific requirements of pin assignment. So far pin assignment of complex electronic devices has been a predominantly manual process. Hence, practical experience exists, yet, it had not been transferred to an algorithmic formulation. This contribution develops pin assignment methods in order to automate and improve pin assignment. Distinctive characteristics of the thereby developed algorithms are their usability during layout planning, their capability to integrate into a hierarchical design flow, and the consideration of differential pairs. Both aspects, routability prediction and assignment algorithms, are finally brought together by using the newly developed routability prediction to evaluate and select the assignment algorithms.

Vertical stacking—based on modern manufacturing and integration technologies—of multiple 2D chips enables three-dimensional integrated circuits (3D ICs). This exploitation of the third dimension is generally accepted for aiming at higher packing densities, heterogeneous integration, shorter interconnects, reduced power consumption, increased data bandwidth, and realizing highly-parallel systems in one device. However, the commercial acceptance of 3D ICs is currently behind its expectations, mainly due to challenges regarding manufacturing and integration technologies as well as design automation. This work addresses three selected, practically relevant design challenges: (i) increasing the constrained reusability of proven, reliable 2D intellectual property blocks, (ii) planning different types of (comparatively large) through-silicon vias with focus on their impact on design quality, as well as (iii) structural planning of massively-parallel, 3D-IC-specific interconnect structures during 3D floorplanning. A key concept of this work is to account for interconnect structures and their properties during early design phases in order to support effective and high-quality 3D-IC-design flows. To tackle the above listed challenges, modular design-flow extensions and methodologies have been developed. Experimental investigations reveal the effectiveness and efficiency of the proposed techniques, and provide findings on 3D integration with particular focus on interconnect structures. We suggest consideration of these findings when formulating guidelines for successful 3D-IC design automation. / Dreidimensional integrierte Schaltkreise (3D-ICs) beruhen auf neuartigen Herstellungs- und Integrationstechnologien, wobei vor allem “klassische” 2D-ICs vertikal zu einem neuartigen 3D-System gestapelt werden. Dieser Ansatz zur Erschließung der dritten Dimension im Schaltkreisentwurf ist nach Expertenmeinung dazu geeignet, höhere Integrationsdichten zu erreichen, heterogene Integration zu realisieren, kürzere Verdrahtungswege zu ermöglichen, Leistungsaufnahmen zu reduzieren, Datenübertragungsraten zu erhöhen, sowie hoch-parallele Systeme in einer Baugruppe umzusetzen. Aufgrund von technologischen und entwurfsmethodischen Schwierigkeiten bleibt jedoch bisher die kommerzielle Anwendung von 3D-ICs deutlich hinter den Erwartungen zurück. In dieser Arbeit werden drei ausgewählte, praktisch relevante Problemstellungen der Entwurfsautomatisierung von 3D-ICs bearbeitet: (i) die Verbesserung der (eingeschränkten) Wiederverwendbarkeit von zuverlässigen 2D-Intellectual-Property-Blöcken, (ii) die komplexe Planung von verschiedenartigen, verhältnismäßig großen Through-Silicion Vias unter Beachtung ihres Einflusses auf die Entwurfsqualität, und (iii) die strukturelle Einbindung von massiv-parallelen, 3D-IC-spezifischen Verbindungsstrukturen während der Floorplanning-Phase. Das Ziel dieser Arbeit besteht darin, Verbindungsstrukturen mit deren wesentlichen Eigenschaften bereits in den frühen Phasen des Entwurfsprozesses zu berücksichtigen. Dies begünstigt einen qualitativ hochwertigen Entwurf von 3D-ICs. Die in dieser Arbeit vorgestellten modularen Entwurfsprozess-Erweiterungen bzw. -Methodiken dienen zur effizienten Lösung der oben genannten Problemstellungen. Experimentelle Untersuchungen bestätigen die Wirksamkeit sowie die Effektivität der erarbeiten Methoden. Darüber hinaus liefern sie praktische Erkenntnisse bezüglich der Anwendung von 3D-ICs und der Planung deren Verbindungsstrukturen. Diese Erkenntnisse sind zur Ableitung von Richtlinien für den erfolgreichen Entwurf von 3D-ICs dienlich.

Vertical stacking—based on modern manufacturing and integration technologies—of multiple 2D chips enables three-dimensional integrated circuits (3D ICs). This exploitation of the third dimension is generally accepted for aiming at higher packing densities, heterogeneous integration, shorter interconnects, reduced power consumption, increased data bandwidth, and realizing highly-parallel systems in one device. However, the commercial acceptance of 3D ICs is currently behind its expectations, mainly due to challenges regarding manufacturing and integration technologies as well as design automation. This work addresses three selected, practically relevant design challenges: (i) increasing the constrained reusability of proven, reliable 2D intellectual property blocks, (ii) planning different types of (comparatively large) through-silicon vias with focus on their impact on design quality, as well as (iii) structural planning of massively-parallel, 3D-IC-specific interconnect structures during 3D floorplanning. A key concept of this work is to account for interconnect structures and their properties during early design phases in order to support effective and high-quality 3D-IC-design flows. To tackle the above listed challenges, modular design-flow extensions and methodologies have been developed. Experimental investigations reveal the effectiveness and efficiency of the proposed techniques, and provide findings on 3D integration with particular focus on interconnect structures. We suggest consideration of these findings when formulating guidelines for successful 3D-IC design automation.:1 Introduction 1.1 The 3D Integration Approach for Electronic Circuits 1.2 Technologies for 3D Integrated Circuits 1.3 Design Approaches for 3D Integrated Circuits 2 State of the Art in Design Automation for 3D Integrated Circuits 2.1 Thermal Management 2.2 Partitioning and Floorplanning 2.3 Placement and Routing 2.4 Power and Clock Delivery 2.5 Design Challenges 3 Research Objectives 4 Planning Through-Silicon Via Islands for Block-Level Design Reuse 4.1 Problems for Design Reuse in 3D Integrated Circuits 4.2 Connecting Blocks Using Through-Silicon Via Islands 4.2.1 Problem Formulation and Methodology Overview 4.2.2 Net Clustering 4.2.3 Insertion of Through-Silicon Via Islands 4.2.4 Deadspace Insertion and Redistribution 4.3 Experimental Investigation 4.3.1 Wirelength Estimation 4.3.2 Configuration 4.3.3 Results and Discussion 4.4 Summary and Conclusions 5 Planning Through-Silicon Vias for Design Optimization 5.1 Deadspace Requirements for Optimized Planning of Through-Silicon Vias 5.2 Multiobjective Design Optimization of 3D Integrated Circuits 5.2.1 Methodology Overview and Configuration 5.2.2 Techniques for Deadspace Optimization 5.2.3 Design-Quality Analysis 5.2.4 Planning Different Types of Through-Silicon Vias 5.3 Experimental Investigation 5.3.1 Configuration 5.3.2 Results and Discussion 5.4 Summary and Conclusions 6 3D Floorplanning for Structural Planning of Massive Interconnects 6.1 Block Alignment for Interconnects Planning in 3D Integrated Circuits 6.2 Corner Block List Extended for Block Alignment 6.2.1 Alignment Encoding 6.2.2 Layout Generation: Block Placement and Alignment 6.3 3D Floorplanning Methodology 6.3.1 Optimization Criteria and Phases and Related Cost Models 6.3.2 Fast Thermal Analysis 6.3.3 Layout Operations 6.3.4 Adaptive Optimization Schedule 6.4 Experimental Investigation 6.4.1 Configuration 6.4.2 Results and Discussion 6.5 Summary and Conclusions 7 Research Summary, Conclusions, and Outlook Dissertation Theses Notation Glossary Bibliography / Dreidimensional integrierte Schaltkreise (3D-ICs) beruhen auf neuartigen Herstellungs- und Integrationstechnologien, wobei vor allem “klassische” 2D-ICs vertikal zu einem neuartigen 3D-System gestapelt werden. Dieser Ansatz zur Erschließung der dritten Dimension im Schaltkreisentwurf ist nach Expertenmeinung dazu geeignet, höhere Integrationsdichten zu erreichen, heterogene Integration zu realisieren, kürzere Verdrahtungswege zu ermöglichen, Leistungsaufnahmen zu reduzieren, Datenübertragungsraten zu erhöhen, sowie hoch-parallele Systeme in einer Baugruppe umzusetzen. Aufgrund von technologischen und entwurfsmethodischen Schwierigkeiten bleibt jedoch bisher die kommerzielle Anwendung von 3D-ICs deutlich hinter den Erwartungen zurück. In dieser Arbeit werden drei ausgewählte, praktisch relevante Problemstellungen der Entwurfsautomatisierung von 3D-ICs bearbeitet: (i) die Verbesserung der (eingeschränkten) Wiederverwendbarkeit von zuverlässigen 2D-Intellectual-Property-Blöcken, (ii) die komplexe Planung von verschiedenartigen, verhältnismäßig großen Through-Silicion Vias unter Beachtung ihres Einflusses auf die Entwurfsqualität, und (iii) die strukturelle Einbindung von massiv-parallelen, 3D-IC-spezifischen Verbindungsstrukturen während der Floorplanning-Phase. Das Ziel dieser Arbeit besteht darin, Verbindungsstrukturen mit deren wesentlichen Eigenschaften bereits in den frühen Phasen des Entwurfsprozesses zu berücksichtigen. Dies begünstigt einen qualitativ hochwertigen Entwurf von 3D-ICs. Die in dieser Arbeit vorgestellten modularen Entwurfsprozess-Erweiterungen bzw. -Methodiken dienen zur effizienten Lösung der oben genannten Problemstellungen. Experimentelle Untersuchungen bestätigen die Wirksamkeit sowie die Effektivität der erarbeiten Methoden. Darüber hinaus liefern sie praktische Erkenntnisse bezüglich der Anwendung von 3D-ICs und der Planung deren Verbindungsstrukturen. Diese Erkenntnisse sind zur Ableitung von Richtlinien für den erfolgreichen Entwurf von 3D-ICs dienlich.:1 Introduction 1.1 The 3D Integration Approach for Electronic Circuits 1.2 Technologies for 3D Integrated Circuits 1.3 Design Approaches for 3D Integrated Circuits 2 State of the Art in Design Automation for 3D Integrated Circuits 2.1 Thermal Management 2.2 Partitioning and Floorplanning 2.3 Placement and Routing 2.4 Power and Clock Delivery 2.5 Design Challenges 3 Research Objectives 4 Planning Through-Silicon Via Islands for Block-Level Design Reuse 4.1 Problems for Design Reuse in 3D Integrated Circuits 4.2 Connecting Blocks Using Through-Silicon Via Islands 4.2.1 Problem Formulation and Methodology Overview 4.2.2 Net Clustering 4.2.3 Insertion of Through-Silicon Via Islands 4.2.4 Deadspace Insertion and Redistribution 4.3 Experimental Investigation 4.3.1 Wirelength Estimation 4.3.2 Configuration 4.3.3 Results and Discussion 4.4 Summary and Conclusions 5 Planning Through-Silicon Vias for Design Optimization 5.1 Deadspace Requirements for Optimized Planning of Through-Silicon Vias 5.2 Multiobjective Design Optimization of 3D Integrated Circuits 5.2.1 Methodology Overview and Configuration 5.2.2 Techniques for Deadspace Optimization 5.2.3 Design-Quality Analysis 5.2.4 Planning Different Types of Through-Silicon Vias 5.3 Experimental Investigation 5.3.1 Configuration 5.3.2 Results and Discussion 5.4 Summary and Conclusions 6 3D Floorplanning for Structural Planning of Massive Interconnects 6.1 Block Alignment for Interconnects Planning in 3D Integrated Circuits 6.2 Corner Block List Extended for Block Alignment 6.2.1 Alignment Encoding 6.2.2 Layout Generation: Block Placement and Alignment 6.3 3D Floorplanning Methodology 6.3.1 Optimization Criteria and Phases and Related Cost Models 6.3.2 Fast Thermal Analysis 6.3.3 Layout Operations 6.3.4 Adaptive Optimization Schedule 6.4 Experimental Investigation 6.4.1 Configuration 6.4.2 Results and Discussion 6.5 Summary and Conclusions 7 Research Summary, Conclusions, and Outlook Dissertation Theses Notation Glossary Bibliography

Sie entwickeln Entwurfssysteme für elektronische Baugruppen? Dann gehören für Sie die mit der Pinzuordnung verbundenen Optimierungskriterien - die Verdrahtbarkeit im Elektronikentwurf - zum Berufsalltag. Um die Verdrahtbarkeit unter verschiedenen Gesichtspunkten zu verbessern, werden in diesem Buch neu entwickelte Algorithmen vorgestellt. Sie ermöglichen erstmals die automatisierte Pinzuordnung für eine große Anzahl von Bauelementen in hochkomplexen Schaltungen. Alle Aspekte müssen in kürzester Zeit exakt erfasst, eingeschätzt und im Entwurfsprozess zu einem optimalen Ergebnis geführt werden. Die beschriebenen Methoden reduzieren den Entwicklungsaufwand für elektronische Systeme auf ein Minimum und ermöglichen intelligente Lösungen auf der Höhe der Zeit. Die vorliegende Arbeit behandelt die Optimierung der Pinzuordnung und die dafür notwendige Verdrahtbarkeitsvorhersage im hierarchischen Layoutentwurf. Dabei werden bekannte Methoden der Verdrahtbarkeitsvorhersage aus allen Schritten des Layoutentwurfs zusammengetragen, gegenübergestellt und auf ihre Eignung für die Pinzuordnung untersucht. Dies führt schließlich zur Entwicklung einer Vorhersagemethode, die speziell an die Anforderungen der Pinzuordnung angepasst ist. Die Pinzuordnung komplexer elektronischer Geräte ist bisher ein vorwiegend manueller Prozess. Es existieren also bereits Erfahrungen, welche jedoch weder formalisiert noch allgemein verfügbar sind. In den vorliegenden Untersuchungen werden Methoden der Pinzuordnung algorithmisch formuliert und damit einer Automatisierung zugeführt. Besondere Merkmale der Algorithmen sind ihre Einsetzbarkeit bereits während der Planung des Layouts, ihre Eignung für den hierarchisch gegliederten Layoutentwurf sowie ihre Fähigkeit, die Randbedingungen differenzieller Paare zu berücksichtigen. Die beiden untersuchten Aspekte der Pinzuordnung, Verdrahtbarkeitsvorhersage und Zuordnungsalgorithmen, werden schließlich zusammengeführt, indem die neue entwickelte Verdrahtbarkeitsbewertung zum Vergleichen und Auswählen der formulierten Zuordnungsalgorithmen zum Einsatz kommt.:1 Einleitung 1.1 Layoutentwurfsprozess elektronischer Baugruppen 1.2 Ziel der Arbeit 2 Grundlagen 2.1 Pinzuordnung 2.1.1 Definitionen 2.1.2 Freiheitsgrad 2.1.3 Komplexität und Problemgröße 2.1.4 Optimierungsziel 2.1.5 Randbedingungen 2.2 Reale Entwurfsbeispiele der Pinzuordnung 2.2.1 Hierarchieebenen eines Personal Computers 2.2.2 Multi-Chip-Module auf Hauptplatine 2.3 Einteilung von Algorithmen der Pinzuordnung 2.3.1 Klassifikation nach der Einordnung in den Layoutentwurf 2.3.2 Klassifikation nach Optimierungsverfahren 2.3.3 Zusammenfassung 2.4 Verdrahtbarkeitsvorhersage 2.4.1 Definitionen 2.4.2 Vorhersagegenauigkeit und zeitlicher Rechenaufwand 2.4.3 Methoden der Verdrahtbarkeitsvorhersage 3 Stand der Technik 3.1 Pinzuordnung 3.1.1 Einordnung in den Layoutentwurf 3.1.2 Optimierungsverfahren 3.2 Verdrahtbarkeitsvorhersage 3.2.1 Partitionierbarkeit 3.2.2 Verdrahtungslänge 3.2.3 Verdrahtungsweg 3.2.4 Verdrahtungsdichte 3.2.5 Verdrahtungsauslastung und Overflow 3.2.6 Manuelle optische Bewertung 3.2.7 Interpretation und Wichtung der Kriterien 4 Präzisierung der Aufgabenstellung 5 Pinzuordnungs-Algorithmen 5.1 Voraussetzungen 5.2 Topologische Heuristiken 5.2.1 Wiederholtes Unterteilen 5.2.2 Kreuzungen minimieren 5.2.3 Projizieren auf Gerade 5.3 Lineare Optimierung 5.4 Differenzielle Paare 5.5 Pinzuordnung in Hierarchieebenen 5.6 Nutzen der Globalverdrahtung 5.6.1 Methode 5.6.2 Layout der Ankerkomponenten 5.7 Zusammenfassung 6 Verdrahtbarkeitsbewertung während der Pinzuordnung 6.1 Anforderungen 6.2 Eignung bekannter Bewertungskriterien 6.2.1 Partitionierbarkeit / Komplexitätsanalyse 6.2.2 Verdrahtungslängen 6.2.3 Verdrahtungswege 6.2.4 Verdrahtungsdichte 6.2.5 Verdrahtungsauslastung 6.2.6 Overflow 6.2.7 Schlussfolgerung 6.3 Probabilistische Verdrahtungsdichtevorhersage 6.3.1 Grenzen probabilistischer Vorhersagen 6.3.2 Verdrahtungsumwege 6.3.3 Verdrahtungsdichteverteilung 6.3.4 Gesamtverdrahtungsdichte und Hierarchieebenen 6.4 Bewertung der Verdrahtungsdichteverteilung 6.4.1 Maßzahlen für die Verdrahtbarkeit eines Netzes 6.4.2 Maßzahlen für die Gesamtverdrahtbarkeit 6.5 Zusammenfassung 7 Pinzuordnungs-Bewertung 7.1 Anforderungen 7.2 Kostenterme 7.3 Normierung 7.3.1 Referenzwerte für Eigenschaften der Verdrahtungsdichte 7.3.2 Referenzwerte für Verdrahtungslängen 7.3.3 Referenzwerte für Signalkreuzungen 7.4 Gesamtbewertung der Verdrahtbarkeit 7.5 Priorisierung der Kostenterme 7.6 Zusammenfassung 8 Ergebnisse 8.1 Verdrahtbarkeitsbewertung 8.1.1 Charakteristik der ISPD-Globalverdrahtungswettbewerbe 8.1.2 Untersuchte probabilistische Schätzer 8.1.3 Kriterien zum Bewerten der Vorhersagegenauigkeit 8.1.4 Vorhersagegenauigkeit der probabilistischen Schätzer 8.2 Pinzuordnungs-Bewertung 8.2.1 Vollständige Analyse kleiner Pinzuordnungs-Aufgaben 8.2.2 Pinzuordnungs-Aufgaben realer Problemgröße 8.2.3 Differenzielle Paare 8.2.4 Nutzen der Globalverdrahtung 8.2.5 Hierarchieebenen 8.3 Zusammenfassung 9 Gesamtzusammenfassung und Ausblick Verzeichnisse Zeichen, Benennungen und Einheiten Abkürzungsverzeichnis Glossar Anhang A Struktogramme der Pinzuordnungs-Algorithmen A.1 Wiederholtes Unterteilen A.2 Kreuzungen minimieren A.3 Projizieren auf Gerade A.4 Lineare Optimierung A.5 Zufällige Pinzuordnung A.6 Differenzielle Paare A.7 Pinzuordnung in Hierarchieebenen A.8 Nutzen der Globalverdrahtung B Besonderheit der Manhattan-Länge während der Pinzuordnung C Weitere Ergebnisse C.1 Multipinnetz-Zerlegung C.1.1 Grundlagen C.1.2 In dieser Arbeit angewendete Multipinnetz-Zerlegung C.2 Genauigkeit der Verdrahtungsvorhersage C.3 Hierarchische Pinzuordnung Literaturverzeichnis / This work deals with the optimization of pin assignments for which an accurate routability prediction is a prerequisite. Therefore, this contribution introduces methods for routability prediction. The optimization of pin assignments, for which these methods are needed, is done after initial placement and before routing. Known methods of routability prediction are compiled, compared, and analyzed for their usability as part of the pin assignment step. These investigations lead to the development of a routability prediction method, which is adapted to the specific requirements of pin assignment. So far pin assignment of complex electronic devices has been a predominantly manual process. Hence, practical experience exists, yet, it had not been transferred to an algorithmic formulation. This contribution develops pin assignment methods in order to automate and improve pin assignment. Distinctive characteristics of the thereby developed algorithms are their usability during layout planning, their capability to integrate into a hierarchical design flow, and the consideration of differential pairs. Both aspects, routability prediction and assignment algorithms, are finally brought together by using the newly developed routability prediction to evaluate and select the assignment algorithms.:1 Einleitung 1.1 Layoutentwurfsprozess elektronischer Baugruppen 1.2 Ziel der Arbeit 2 Grundlagen 2.1 Pinzuordnung 2.1.1 Definitionen 2.1.2 Freiheitsgrad 2.1.3 Komplexität und Problemgröße 2.1.4 Optimierungsziel 2.1.5 Randbedingungen 2.2 Reale Entwurfsbeispiele der Pinzuordnung 2.2.1 Hierarchieebenen eines Personal Computers 2.2.2 Multi-Chip-Module auf Hauptplatine 2.3 Einteilung von Algorithmen der Pinzuordnung 2.3.1 Klassifikation nach der Einordnung in den Layoutentwurf 2.3.2 Klassifikation nach Optimierungsverfahren 2.3.3 Zusammenfassung 2.4 Verdrahtbarkeitsvorhersage 2.4.1 Definitionen 2.4.2 Vorhersagegenauigkeit und zeitlicher Rechenaufwand 2.4.3 Methoden der Verdrahtbarkeitsvorhersage 3 Stand der Technik 3.1 Pinzuordnung 3.1.1 Einordnung in den Layoutentwurf 3.1.2 Optimierungsverfahren 3.2 Verdrahtbarkeitsvorhersage 3.2.1 Partitionierbarkeit 3.2.2 Verdrahtungslänge 3.2.3 Verdrahtungsweg 3.2.4 Verdrahtungsdichte 3.2.5 Verdrahtungsauslastung und Overflow 3.2.6 Manuelle optische Bewertung 3.2.7 Interpretation und Wichtung der Kriterien 4 Präzisierung der Aufgabenstellung 5 Pinzuordnungs-Algorithmen 5.1 Voraussetzungen 5.2 Topologische Heuristiken 5.2.1 Wiederholtes Unterteilen 5.2.2 Kreuzungen minimieren 5.2.3 Projizieren auf Gerade 5.3 Lineare Optimierung 5.4 Differenzielle Paare 5.5 Pinzuordnung in Hierarchieebenen 5.6 Nutzen der Globalverdrahtung 5.6.1 Methode 5.6.2 Layout der Ankerkomponenten 5.7 Zusammenfassung 6 Verdrahtbarkeitsbewertung während der Pinzuordnung 6.1 Anforderungen 6.2 Eignung bekannter Bewertungskriterien 6.2.1 Partitionierbarkeit / Komplexitätsanalyse 6.2.2 Verdrahtungslängen 6.2.3 Verdrahtungswege 6.2.4 Verdrahtungsdichte 6.2.5 Verdrahtungsauslastung 6.2.6 Overflow 6.2.7 Schlussfolgerung 6.3 Probabilistische Verdrahtungsdichtevorhersage 6.3.1 Grenzen probabilistischer Vorhersagen 6.3.2 Verdrahtungsumwege 6.3.3 Verdrahtungsdichteverteilung 6.3.4 Gesamtverdrahtungsdichte und Hierarchieebenen 6.4 Bewertung der Verdrahtungsdichteverteilung 6.4.1 Maßzahlen für die Verdrahtbarkeit eines Netzes 6.4.2 Maßzahlen für die Gesamtverdrahtbarkeit 6.5 Zusammenfassung 7 Pinzuordnungs-Bewertung 7.1 Anforderungen 7.2 Kostenterme 7.3 Normierung 7.3.1 Referenzwerte für Eigenschaften der Verdrahtungsdichte 7.3.2 Referenzwerte für Verdrahtungslängen 7.3.3 Referenzwerte für Signalkreuzungen 7.4 Gesamtbewertung der Verdrahtbarkeit 7.5 Priorisierung der Kostenterme 7.6 Zusammenfassung 8 Ergebnisse 8.1 Verdrahtbarkeitsbewertung 8.1.1 Charakteristik der ISPD-Globalverdrahtungswettbewerbe 8.1.2 Untersuchte probabilistische Schätzer 8.1.3 Kriterien zum Bewerten der Vorhersagegenauigkeit 8.1.4 Vorhersagegenauigkeit der probabilistischen Schätzer 8.2 Pinzuordnungs-Bewertung 8.2.1 Vollständige Analyse kleiner Pinzuordnungs-Aufgaben 8.2.2 Pinzuordnungs-Aufgaben realer Problemgröße 8.2.3 Differenzielle Paare 8.2.4 Nutzen der Globalverdrahtung 8.2.5 Hierarchieebenen 8.3 Zusammenfassung 9 Gesamtzusammenfassung und Ausblick Verzeichnisse Zeichen, Benennungen und Einheiten Abkürzungsverzeichnis Glossar Anhang A Struktogramme der Pinzuordnungs-Algorithmen A.1 Wiederholtes Unterteilen A.2 Kreuzungen minimieren A.3 Projizieren auf Gerade A.4 Lineare Optimierung A.5 Zufällige Pinzuordnung A.6 Differenzielle Paare A.7 Pinzuordnung in Hierarchieebenen A.8 Nutzen der Globalverdrahtung B Besonderheit der Manhattan-Länge während der Pinzuordnung C Weitere Ergebnisse C.1 Multipinnetz-Zerlegung C.1.1 Grundlagen C.1.2 In dieser Arbeit angewendete Multipinnetz-Zerlegung C.2 Genauigkeit der Verdrahtungsvorhersage C.3 Hierarchische Pinzuordnung Literaturverzeichnis