O trabalho usa a síntese do leiaute através do ASTRAN em circuitos que foram otimizados através da técnica de SCCG (Static CMOS Complex Gates) visando alcançar reduções em número de transistores. A metodologia apresentada permite a flexibilidade de utilizar células de quaisquer tamanho ou redes de transistores nos circuito otimizados. O trabalho compara estes circuitos otimizados pela método do ASTRAN e circuitos utilizando a metodologia standard cell. O fluxo de síntese é composto pelas etapas de otimização da netlist, verificação/extração e caracterização da células. O trabalho adaptou as tecnologias de fabricação CMOS de 600nm e 180nm para a ferramenta ASTRAN a partir das informações dos design kits das bibliotecas stantard cell XC06 e XC018 da XFAB. A síntese do leiaute das células complexas geradas é realizada pela ferramenta ASTRAN. Os experimentos foram realizados nas tecnologias de 180nm e 600nm para um conjunto de circuitos de bechmarks do ITC’99. As comparações foram realizadas entre a netlist otimizada e duas netlists geradas para cada biblioteca da XFAB. Uma netlist abrange todas as células da biblioteca e a outra tem uma restrição de células que são consideradas complexas (somadores, multiplexadores, XOR/XNOR, AOI e OAI). A netlist com restrições foi elaborada com a motivação de verificar se uma netlist com células complexas geradas exclusivamente para o circuito alvo se tornaria mais benéfico em termos de redução do número de transistores. Os resultados para 180nm apresentaram reduções nos melhores casos em número de transistores com até 15%, em potência dinâmica com até 24% e em potência de leakage com até 22%. Os resultados para 600nm apresentaram reduções nos melhores casos em número de transistores com até 17%, em área com até 14%, em potência dinâmica com até 22%, em potência de leakage com até 29%. Os experimentos mostraram que é possível alcançar reduções em número de transistores ao combinar o uso do ASTRAN com a técnica de otimização pelo uso de SCCG. / The work uses the synthesis of the layout through ASTRAN in circuits that have been optimized through the SCCG technique (Static CMOS Complex Gates) in order to achieve reductions in the number of transistors. The presented methodology allows the flexibility of using cells of any size or transistor networks in the optimized circuits. The work compares these circuits optimized by the ASTRAN method and circuits using the standard cell methodology. The synthesis flow is composed by the netlist optimization, verification / extraction and cell characterization steps. The work adapted 600nm and 180nm CMOS fabrication technologies for the ASTRAN tool from the design information of the XFAB standard cell XC06 and XC018 libraries. The synthesis of the complex cells generated is performed by the ASTRAN tool. The experiments were performed on the 180nm and 600nm technologies for a set of ITC'99 bechmarks circuits. Comparisons were made between the optimized netlist and two netlists generated for each XFAB library. A netlist covers all cells in the library and the other netlist has a restriction of cells that are considered complex (adders, multiplexers, XOR / XNOR, AOI, and OAI). The netlist with restrictions was designed with the motivation to check if a netlist with complex cells generated exclusively for the target circuit would become more beneficial in terms of reducing the number of transistors. The results for 180nm showed reductions in the best cases in the number of transistors with up to 15%, in dynamic power up to 24% and in leakage power with up to 22%. The results for 600nm showed reductions in the best cases in the number of transistors with up to 17%, in an area up to 14%, in dynamic power with up to 22%, in leakage power with up to 29%. The experiments showed that it is possible to achieve reductions in the number of transistors by combining the use of ASTRAN with the optimization technique using SCCG.

Este trabalho objetiva o estudo da avaliação de desempenho de partes de controle de circuitos integrados, em relação ao consumo de área em silício e atraso de propagação de sinais. Para a implementação são adotados dois diferentes estilos de leiaute (PLA e gate matrix). Para ambos os casos foi utilizado um conjunto único de regras de projeto. A análise dos circuitos visando implementação com PLA 6 é feita com base em estimativas de área e atraso deste, sendo definidas as suas células básicas. Para gate matrix, é feita a síntese de leiaute com um gerador automático de leiaute para circuitos em lógica aleatória e o atraso é estimado por modelo simplificado. A avaliação elétrica para calcular o atraso dos sinais é baseada em modelos simplificados de timing, previamente estudados, que levam em conta elementos parasitas das redes de transistores. São analisadas partes de controle de sistemas reais e máquinas de estados finitos hipotéticas. O trabalho visa propor a melhor estratégia de implementação, através da previsão do desempenho dos circuitos, em função do tamanho e complexidade (em número de portas e sinais de interface) do circuito. / The subject of this work is the performance analysis of control parts of integrated circuits, as a function of silicon area and signals propagation delay. Two different layout styles are used for implementation (PLA and gate matrix). Both of them use the same design rules. The analysis of the circuits implemented with PLA is based on area and delay estimation, with the basic cells already defined. For gate matrix, the layout synthesis is made with an automatic layout generator for random logic circuits and the delay is estimated by simplified models. The electrical evaluation to compute the delay signal is based on simplified timing models, previously studied, taking into account parasitic elements of the transistor networks. Control parts of real systems and finite state machines are analysed. This work aims to select the best implementation strategy, based on performance estimation, as a function of the size and complexity (gates and interface signals) of the circuit.

Este trabalho objetiva o estudo da avaliação de desempenho de partes de controle de circuitos integrados, em relação ao consumo de área em silício e atraso de propagação de sinais. Para a implementação são adotados dois diferentes estilos de leiaute (PLA e gate matrix). Para ambos os casos foi utilizado um conjunto único de regras de projeto. A análise dos circuitos visando implementação com PLA 6 é feita com base em estimativas de área e atraso deste, sendo definidas as suas células básicas. Para gate matrix, é feita a síntese de leiaute com um gerador automático de leiaute para circuitos em lógica aleatória e o atraso é estimado por modelo simplificado. A avaliação elétrica para calcular o atraso dos sinais é baseada em modelos simplificados de timing, previamente estudados, que levam em conta elementos parasitas das redes de transistores. São analisadas partes de controle de sistemas reais e máquinas de estados finitos hipotéticas. O trabalho visa propor a melhor estratégia de implementação, através da previsão do desempenho dos circuitos, em função do tamanho e complexidade (em número de portas e sinais de interface) do circuito. / The subject of this work is the performance analysis of control parts of integrated circuits, as a function of silicon area and signals propagation delay. Two different layout styles are used for implementation (PLA and gate matrix). Both of them use the same design rules. The analysis of the circuits implemented with PLA is based on area and delay estimation, with the basic cells already defined. For gate matrix, the layout synthesis is made with an automatic layout generator for random logic circuits and the delay is estimated by simplified models. The electrical evaluation to compute the delay signal is based on simplified timing models, previously studied, taking into account parasitic elements of the transistor networks. Control parts of real systems and finite state machines are analysed. This work aims to select the best implementation strategy, based on performance estimation, as a function of the size and complexity (gates and interface signals) of the circuit.

Este trabalho objetiva o estudo da avaliação de desempenho de partes de controle de circuitos integrados, em relação ao consumo de área em silício e atraso de propagação de sinais. Para a implementação são adotados dois diferentes estilos de leiaute (PLA e gate matrix). Para ambos os casos foi utilizado um conjunto único de regras de projeto. A análise dos circuitos visando implementação com PLA 6 é feita com base em estimativas de área e atraso deste, sendo definidas as suas células básicas. Para gate matrix, é feita a síntese de leiaute com um gerador automático de leiaute para circuitos em lógica aleatória e o atraso é estimado por modelo simplificado. A avaliação elétrica para calcular o atraso dos sinais é baseada em modelos simplificados de timing, previamente estudados, que levam em conta elementos parasitas das redes de transistores. São analisadas partes de controle de sistemas reais e máquinas de estados finitos hipotéticas. O trabalho visa propor a melhor estratégia de implementação, através da previsão do desempenho dos circuitos, em função do tamanho e complexidade (em número de portas e sinais de interface) do circuito. / The subject of this work is the performance analysis of control parts of integrated circuits, as a function of silicon area and signals propagation delay. Two different layout styles are used for implementation (PLA and gate matrix). Both of them use the same design rules. The analysis of the circuits implemented with PLA is based on area and delay estimation, with the basic cells already defined. For gate matrix, the layout synthesis is made with an automatic layout generator for random logic circuits and the delay is estimated by simplified models. The electrical evaluation to compute the delay signal is based on simplified timing models, previously studied, taking into account parasitic elements of the transistor networks. Control parts of real systems and finite state machines are analysed. This work aims to select the best implementation strategy, based on performance estimation, as a function of the size and complexity (gates and interface signals) of the circuit.

Les travaux de recherche présentés dans cette thèse se situent dans une problématique d’aide à la conception d’enveloppes isolantes pour la rénovation thermique de bâtiments résidentiels collectifs. Ces enveloppes isolantes sont composées de panneaux multifonctionnels rectangulaires, configurables et préfabriqués en usine. Leur conception repose sur les cinq caractéristiques suivantes. Premièrement, le nombre de panneaux nécessaires pour concevoir une enveloppe ainsi que leur taille respective ne sont pas
 connus au début de la rénovation (mais leur taille est cependant bornée). Deuxièmement, en raison des contraintes de fabrication, chaque fenêtre et chaque porte présentes sur la façade à rénover doivent être insérées dans un et un seul panneau. Troisièmement, les panneaux sont fixés à des endroits spécifiques de la façade, assez résistants pour supporter leur poids, nommés zones d’accroche. Quatrièmement, ni trous (zone non couverte), ni chevauchements entre panneaux ne sont autorisés. Cinquièmement, afin de garantir une isolation thermique performante tout en minimisant son coût, les enveloppes doivent être
 composées d’un nombre minimal de panneaux. Aux vues de la complexité de ce problème, nous restreignons nos travaux de recherche aux façades rectangulaires portant des menuiseries et des zones d’accroche rectangulaires. Compte tenu des cinq caractéristiques énoncées et de l’hypothèse de forme rectangulaire des éléments traités (panneaux, façades, menuiseries, zones d’accroche), la conception des enveloppes est à la fois un problème de découpe et de conditionnement à deux dimensions et un problème de configuration. Ce problème est formalisé et traité comme un problème de satisfaction de contraintes et a pour but d’aider la conception dédites enveloppes isolantes. En tant que tel, les travaux de cette thèse présentent deux contributions majeures. En raison des caractéristiques originales du problème de calepinage de façades, sa description et sa formalisation comme un problème de satisfaction de contraintes constituent la première contribution de ces travaux de thèse. Deuxièmement, les solutions algorithmiques basées sur les contraintes constituent notre seconde contribution. En particulier, ces travaux de thèse présentent deux solutions manuelles et trois automatiques pour le problème de conception d’enveloppes isolantes. / The research presented in this thesis falls within the problem of supporting the design of thermal insulating envelopes for the renovation of collective residential buildings. These insulating envelopes are composed of rectangular multi-functional panels, configurable and prefabricated in the factory. Their design is based on the following five characteristics. First, the number of panels needed to design an envelope and their size are not known at the beginning of the renovation (but their size is however bounded). Second, because of manufacturing constraints, every window and every door present on the facade to be renovated must be inserted into one and only one panel. Third, panels are attached to specific areas of the facade strong enough to support their weight, called supporting areas. Fourth, neither holes (uncovered area) or overlapping between panels are allowed. Fifth, to ensure efficient thermal insulation while minimizing cost, envelopes should be composed of a minimum number of panels. In view of the complexity of this problem, we restrict our research to rectangular facades with rectangular joinery and supporting areas. Given the five stated characteristics and the assumption of rectangular elements (panels, facades, 
joinery, supporting areas), the envelopes design is both a two-dimensional Cutting & Packing problem as well as a configuration one. This problem is formalized and treated as a constraint satisfaction problem and aims to support the design of such insulating structures. As such, the thesis presents two major contributions. Given the original features of the building renovation problem, its description and its formalization as a constraint satisfaction problem are the first contribution of the work. Second, constraint-based algorithmic solution’s are our second contribution. In particular, the thesis presents two manual and three automatic solutions for the design problem of insulating envelopes.

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.

Les problèmes majeurs de la génération automatique du dessin des masques des circuits intégrés sont la dépendance vis-à-vis des règles de dessin et le dimensionnement correct des transistors. Les méthodes traditionnelles, telles que l'utilisation de cellules pré-caractérisées, manquent de flexibilité, car les portes des bibliothèques (en nombre limité) sont dessinées et dimensionnées (independarnment de l'application) pour une technologie donnée. Les méthodes de synthèse automatique du dessin des masques ont pour but de surmonter ces problèmes. Les techniques les plus couramment utilisées sont le "gate-matrix" et le "linear-matrix". L'indépendance vis-à-vis des règles de dessin est obtenue en utilisant la technique de description symbolique (dessin sous une grille unitaire), et les dimensions des transistors sont définies par le concepteur ou par un outil de dimensionnement. Nous proposons une méthode et un prototype logiciel pour la synthèse automatique des masques, en utilisant le style "linear-matrix multi-bander". La description d'entree du générateur est un fichier format SPICE (au niveau transistor), ce qui permet d'avoir un nombre très élevé de cellules, en particulier les portes complexes (A01), et ainsi avoir une meilleure optimisation lors de la phase d'assignation technologique. Les macro-cellules générées doivent être assemblées afin de réaliser un circuit complet. Deux contraintes supplémentaires sont ainsi imposées au générateur: malléabilité de la forme et position des broches d'entrées/sorties sur la périphérie de la macro-cellule. Les macro-cellules sont assemblées en utilisant un environnement de conception industriel. Les contributions de ce mémoire de doctorat sont d'une part le développement d'un générateur de macro-cellules flexible ayant les caracteristiques d'indépendance aux règles de dessin et d'intégration dans un environnement de macro-cellules, et d'autre part l'étude detailée des paramètres qui déterminent la surface occupée, les performances électriques et la puissance dissipée des macro-cellules générées automatiquement. / The main problems of the automatic layout synthesis are the design rules dependence and the transistor sizing. The traditional layout synthesis methods, like standard-cells, are not flexible, since the cells in the libraries are designed and sized for a specific technology. In this way, the designer must change his library at each technology improvement. The automatic layout synthesis methods overcomes these problems (design rules dependence and transistor sizing). Examples of layout styles are gate-matrix and linear-matrix. The technology independence is achieved by symbolic description (layout under an unitary grid), and the transistor sizes are defined by the designer or by a sizing tool. From these two constraints, we develop an automatic layout synthesis tool, using a linear-matrix multi-row layout style. The input description for our tool is a Spice file. This descriptions allows to define a greater number of cells (mainly AOIs gates), resulting a technology mapping with less constraints. The generated macro-cells must be assembled in order to construct a complete circuit. Two additional constraints are then imposed to the generator : variable aspect ratio and placement of the inputs/outputs pins in the macro-cell border. The macro-cells are assembled by an industrial CAD environment. The main contributions of this thesis are the development of a macro-cell generator (with the characteristics of technology independence and easy integration in a macro-cell environment) and the analysis of the parameters playing a role in the area, delay and power consumption.

Les problèmes majeurs de la génération automatique du dessin des masques des circuits intégrés sont la dépendance vis-à-vis des règles de dessin et le dimensionnement correct des transistors. Les méthodes traditionnelles, telles que l'utilisation de cellules pré-caractérisées, manquent de flexibilité, car les portes des bibliothèques (en nombre limité) sont dessinées et dimensionnées (independarnment de l'application) pour une technologie donnée. Les méthodes de synthèse automatique du dessin des masques ont pour but de surmonter ces problèmes. Les techniques les plus couramment utilisées sont le "gate-matrix" et le "linear-matrix". L'indépendance vis-à-vis des règles de dessin est obtenue en utilisant la technique de description symbolique (dessin sous une grille unitaire), et les dimensions des transistors sont définies par le concepteur ou par un outil de dimensionnement. Nous proposons une méthode et un prototype logiciel pour la synthèse automatique des masques, en utilisant le style "linear-matrix multi-bander". La description d'entree du générateur est un fichier format SPICE (au niveau transistor), ce qui permet d'avoir un nombre très élevé de cellules, en particulier les portes complexes (A01), et ainsi avoir une meilleure optimisation lors de la phase d'assignation technologique. Les macro-cellules générées doivent être assemblées afin de réaliser un circuit complet. Deux contraintes supplémentaires sont ainsi imposées au générateur: malléabilité de la forme et position des broches d'entrées/sorties sur la périphérie de la macro-cellule. Les macro-cellules sont assemblées en utilisant un environnement de conception industriel. Les contributions de ce mémoire de doctorat sont d'une part le développement d'un générateur de macro-cellules flexible ayant les caracteristiques d'indépendance aux règles de dessin et d'intégration dans un environnement de macro-cellules, et d'autre part l'étude detailée des paramètres qui déterminent la surface occupée, les performances électriques et la puissance dissipée des macro-cellules générées automatiquement. / The main problems of the automatic layout synthesis are the design rules dependence and the transistor sizing. The traditional layout synthesis methods, like standard-cells, are not flexible, since the cells in the libraries are designed and sized for a specific technology. In this way, the designer must change his library at each technology improvement. The automatic layout synthesis methods overcomes these problems (design rules dependence and transistor sizing). Examples of layout styles are gate-matrix and linear-matrix. The technology independence is achieved by symbolic description (layout under an unitary grid), and the transistor sizes are defined by the designer or by a sizing tool. From these two constraints, we develop an automatic layout synthesis tool, using a linear-matrix multi-row layout style. The input description for our tool is a Spice file. This descriptions allows to define a greater number of cells (mainly AOIs gates), resulting a technology mapping with less constraints. The generated macro-cells must be assembled in order to construct a complete circuit. Two additional constraints are then imposed to the generator : variable aspect ratio and placement of the inputs/outputs pins in the macro-cell border. The macro-cells are assembled by an industrial CAD environment. The main contributions of this thesis are the development of a macro-cell generator (with the characteristics of technology independence and easy integration in a macro-cell environment) and the analysis of the parameters playing a role in the area, delay and power consumption.

Les problèmes majeurs de la génération automatique du dessin des masques des circuits intégrés sont la dépendance vis-à-vis des règles de dessin et le dimensionnement correct des transistors. Les méthodes traditionnelles, telles que l'utilisation de cellules pré-caractérisées, manquent de flexibilité, car les portes des bibliothèques (en nombre limité) sont dessinées et dimensionnées (independarnment de l'application) pour une technologie donnée. Les méthodes de synthèse automatique du dessin des masques ont pour but de surmonter ces problèmes. Les techniques les plus couramment utilisées sont le "gate-matrix" et le "linear-matrix". L'indépendance vis-à-vis des règles de dessin est obtenue en utilisant la technique de description symbolique (dessin sous une grille unitaire), et les dimensions des transistors sont définies par le concepteur ou par un outil de dimensionnement. Nous proposons une méthode et un prototype logiciel pour la synthèse automatique des masques, en utilisant le style "linear-matrix multi-bander". La description d'entree du générateur est un fichier format SPICE (au niveau transistor), ce qui permet d'avoir un nombre très élevé de cellules, en particulier les portes complexes (A01), et ainsi avoir une meilleure optimisation lors de la phase d'assignation technologique. Les macro-cellules générées doivent être assemblées afin de réaliser un circuit complet. Deux contraintes supplémentaires sont ainsi imposées au générateur: malléabilité de la forme et position des broches d'entrées/sorties sur la périphérie de la macro-cellule. Les macro-cellules sont assemblées en utilisant un environnement de conception industriel. Les contributions de ce mémoire de doctorat sont d'une part le développement d'un générateur de macro-cellules flexible ayant les caracteristiques d'indépendance aux règles de dessin et d'intégration dans un environnement de macro-cellules, et d'autre part l'étude detailée des paramètres qui déterminent la surface occupée, les performances électriques et la puissance dissipée des macro-cellules générées automatiquement. / The main problems of the automatic layout synthesis are the design rules dependence and the transistor sizing. The traditional layout synthesis methods, like standard-cells, are not flexible, since the cells in the libraries are designed and sized for a specific technology. In this way, the designer must change his library at each technology improvement. The automatic layout synthesis methods overcomes these problems (design rules dependence and transistor sizing). Examples of layout styles are gate-matrix and linear-matrix. The technology independence is achieved by symbolic description (layout under an unitary grid), and the transistor sizes are defined by the designer or by a sizing tool. From these two constraints, we develop an automatic layout synthesis tool, using a linear-matrix multi-row layout style. The input description for our tool is a Spice file. This descriptions allows to define a greater number of cells (mainly AOIs gates), resulting a technology mapping with less constraints. The generated macro-cells must be assembled in order to construct a complete circuit. Two additional constraints are then imposed to the generator : variable aspect ratio and placement of the inputs/outputs pins in the macro-cell border. The macro-cells are assembled by an industrial CAD environment. The main contributions of this thesis are the development of a macro-cell generator (with the characteristics of technology independence and easy integration in a macro-cell environment) and the analysis of the parameters playing a role in the area, delay and power consumption.

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