This book presents a detailed summary of research on automatic layout of device-level analog circuits that was undertaken in the late 1980s and early 1990s at Carnegie Mellon University. We focus on the work behind the creation of the tools called KOAN and ANAGRAM II, which form part of the core of the CMU ACACIA analog CAD system. KOAN is a device placer for custom analog cells; ANANGRAM II a detailed area router for these analog cells. We strive to present the motivations behind the architecture of these tools, including detailed discussion of the subtle technology and circuit concerns that must be addressed in any successful analog or mixed-signal layout tool. Our approach in organizing the chapters of the book has been to present our algo rithms as a series of responses to these very real and very difficult analog layout problems. Finally, we present numerous examples of results generated by our algorithms. This research was supported in part by the Semiconductor Research Corpora tion, by the National Science Foundation, by Harris Semiconductor, and by the International Business Machines Corporation Resident Study Program. Finally, just for the record: John Cohn was the designer of the KOAN placer; David Garrod was the designer of the ANAGRAM II router (and its predeces sor, ANAGRAM I). This book was architected by all four authors, edited by John Cohn and Rob Rutenbar, and produced in finished form by John Cohn.

As MOS devices are scaled to meet increasingly demanding circuit specifications, process variations have a greater effect on the reliability of circuit performance. For this reason, statistical techniques are required to design integrated circuits with maximum yield. Statistical Modeling for Computer-Aided Design of MOS VLSI Circuits describes a statistical circuit simulation and optimization environment for VLSI circuit designers. The first step toward accomplishing statistical circuit design and optimization is the development of an accurate CAD tool capable of performing statistical simulation. This tool must be based on a statistical model which comprehends the effect of device and circuit characteristics, such as device size, bias, and circuit layout, which are under the control of the circuit designer on the variability of circuit performance. The distinctive feature of the CAD tool described in this book is its ability to accurately model and simulate the effect in both intra- and inter-die process variability on analog/digital circuits, accounting for the effects of the aforementioned device and circuit characteristics. Statistical Modeling for Computer-Aided Design of MOS VLSI Circuits serves as an excellent reference for those working in the field, and may be used as the text for an advanced course on the subject.

It is a great honor to provide a few words of introduction for Dr. Georges Gielen's and Prof. Willy Sansen's book "Symbolic analysis for automated design of analog integrated circuits." The symbolic analysis method presented in this book represents a significant step forward in the area of analog circuit design. As demonstrated in this book, symbolic analysis opens up new possibilities for the development of computer-aided design (CAD) tools that can analyze an analog circuit topology and automatically size the components for a given set of specifications. Symbolic analysis even has the potential to improve the training of young analog circuit designers and to guide more experienced designers through second-order phenomena such as distortion. This book can also serve as an excellent reference for researchers in the analog circuit design area and creators of CAD tools, as it provides a comprehensive overview and comparison of various approaches for analog circuit design automation and an extensive bibliography. The world is essentially analog in nature, hence most electronic systems involve both analog and digital circuitry. As the number of transistors that can be integrated on a single integrated circuit (IC) substrate steadily increases over time, an ever increasing number of systems will be implemented with one, or a few, very complex ICs because of their lower production costs.

This book is an extension of one author's doctoral thesis on the false path problem. The work was begun with the idea of systematizing the various solutions to the false path problem that had been proposed in the literature, with a view to determining the computational expense of each versus the gain in accuracy. However, it became clear that some of the proposed approaches in the literature were wrong in that they under estimated the critical delay of some circuits under reasonable conditions. Further, some other approaches were vague and so of questionable accu racy. The focus of the research therefore shifted to establishing a theory (the viability theory) and algorithms which could be guaranteed correct, and then using this theory to justify (or not) existing approaches. Our quest was successful enough to justify presenting the full details in a book. After it was discovered that some existing approaches were wrong, it became apparent that the root of the difficulties lay in the attempts to balance computational efficiency and accuracy by separating the tempo ral and logical (or functional) behaviour of combinational circuits. This separation is the fruit of several unstated assumptions; first, that one can ignore the logical relationships of wires in a network when considering timing behaviour, and, second, that one can ignore timing considerations when attempting to discover the values of wires in a circuit."

Powerful new technology has been made available to researchers by an increasingly competitive workstation market. Papers from Canada, Japan, Italy, Germany, and the U.S., to name a few of the countries represented in this volume, discuss how workstations are used in experiments and what impact this new technology will have on experiments. As usual for IFIP workshops, the emphasis in this volume is on the formulation of strategies for future research, the determination of new market areas, and the identification of new areas for workstation research. This is the first volume of a book series reporting the work of IFIP WG 5.10. The mission of this IFIP work- ing group is to promote, develop and encourage advancement of the field of computer graphics as a basic tool, as an enabling technology and as an important part of various application areas.

The development of the 'factory of the future' by major international corporations such as General Motors, IBM, Westinghouse, etc now involves many practising engineers. This book is an attempt to identify and describe some of the building blocks required for computer aided engineering for manufacture. It begins with numerical control and the infrastructure required for the automation of individual 'islands' within existing factories. Computer aided design and computer aided manufacture are then discussed in detail together with their integration to improve manufacturing efficiency and flexibility. Robotics and flexible manufacturing systems are examined, as well as the management of these systems required for production optimization. Finally, there is an overview of the relatively new field of artificial intelligence, which is being increasingly used in most aspects of computer aided engineering for manufacture. There are many topics which could have been included or expanded upon with advantage, but the authors have attempted to strike a balance so that the reader can obtain the maximum usefulness from a reasonably concise volume.

Multi-objective optimization deals with the simultaneous optimization of two or more objectives which are normally in con?ict with each other. Since mul- objective optimization problems are relatively common in real-world appli- tions, this area has become a very popular research topic since the 1970s. However, the use of bio-inspired metaheuristics for solving multi-objective op- mization problems started in the mid-1980s and became popular until the mid- 1990s. Nevertheless, the e?ectiveness of multi-objective evolutionary algorithms has made them very popular in a variety of domains. Swarm intelligence refers to certain population-based metaheuristics that are inspired on the behavior of groups of entities (i.e., living beings) interacting locallywitheachotherandwiththeirenvironment.Suchinteractionsproducean emergentbehaviorthatismodelledinacomputerinordertosolveproblems.The two most popular metaheuristics within swarm intelligence are particle swarm optimization (which simulates a ?ock of birds seeking food) and ant colony optimization (which simulates the behavior of colonies of real ants that leave their nest looking for food). These two metaheuristics havebecome verypopular inthelastfewyears, andhavebeenwidelyusedinavarietyofoptimizationtasks, including some related to data mining and knowledge discovery in databases. However, such work has been mainly focused on single-objective optimization models. The use of multi-objective extensions of swarm intelligence techniques in data mining has been relatively scarce, in spite of their great potential, which constituted the main motivation to produce this book

System-on-a-Chip (SOC) integrated circuits composed of embedded cores are now commonplace. Nevertheless, there remain several roadblocks to rapid and efficient system integration. Test development is seen as a major bottleneck in SOC design and manufacturing capabilities. Testing SOCs is especially challenging in the absence of standardized test structures, test automation tools, and test protocols. In addition, long interconnects, high density, and high-speed designs lead to new types of faults involving crosstalk and signal integrity.

SOC (System-on-a-Chip) Testing for Plug and Play Test Automation is an edited work containing thirteen contributions that address various aspects of SOC testing.

SOC (System-on-a-Chip) Testing for Plug and Play Test Automation is a valuable reference for researchers and students interested in various aspects of SOC testing.

To derive rational and convincible solutions to practical decision making problems in complex and hierarchical human organizations, the decision making problems are formulated as relevant mathematical programming problems which are solved by developing optimization techniques so as to exploit characteristics or structural features of the formulated problems. In particular, for resolving con?ict in decision making in hierarchical managerial or public organizations, the multi level formula tion of the mathematical programming problems has been often employed together with the solution concept of Stackelberg equilibrium. However, weconceivethatapairoftheconventionalformulationandthesolution concept is not always suf?cient to cope with a large variety of decision making situations in actual hierarchical organizations. The following issues should be taken into consideration in expression and formulation of decision making problems. Informulationofmathematicalprogrammingproblems, itistacitlysupposedthat decisions are made by a single person while game theory deals with economic be havior of multiple decision makers with fully rational judgment. Because two level mathematical programming problems are interpreted as static Stackelberg games, multi level mathematical programming is relevant to noncooperative game theory; in conventional multi level mathematical programming models employing the so lution concept of Stackelberg equilibrium, it is assumed that there is no communi cation among decision makers, or they do not make any binding agreement even if there exists such communication. However, for decision making problems in such as decentralized large ?rms with divisional independence, it is quite natural to sup pose that there exists communication and some cooperative relationship among the decision maker

Artificial intelligence provides an environmentally rich paradigm within which design research based on computational constructions can be carried out. This has been one of the foundations for the developing field called "design computing."

Recently, there has been a growing interest in what designers do when they design and how they use computational tools. This forms the basis of a newly emergent field called "design cognition" that draws partly on cognitive science.

This new conference series aims to provide a bridge between the two fields of "design computing" and "design cognition." The papers in this volume are from the "First International Conference on Design Computing and Cognition" (DCC'04) held at the Massachusetts Institute of Technology, USA. They represent state-of-the art research and development in design computing and cognition. They are of particular interest to researchers, developers and users of advanced computation in design and those who need to gain a better understanding of designing.

This book is the outcome of the NATO Advanced Research Workshop on Machine Intelligence and Knowledge Engineering for Robotic Applications held at Maratea, Italy in May 1986. Attendance of the workshop was by invitation only. Most of the participants and speakers are recognized leaders in the field, representing industry, government and academic c0mrnunity worldwide. The focus of the workshop was to review the recent advances of machine intelligence and knowledge engineering for robotic appli cations. It covers five main areas of interest. They are grouped into five sections: 1. Robot Vision 2. Knowledge Representation and Image Understanding 3. Robot Control and Inference Systems 4. Task Planning and Expert Systems 5. Software/Hardware Systems Also included in this book are a paper from the Poster Session and a brief report of the panel discussion on the Future Direction in Knowledge-Based Robotics. Section I of this book consists of four papers. It begins with a review of the basic concepts of computer vision, with emphasis on techniques specific for robot vision systems. The next paper pre sents a comprehensive 3-D vision system for robotic application."

Routing of VLSI chips is an important, time consuming, and difficult problem. The difficulty of the problem is attributed to the large number of often conflicting factors that affect the routing quality. Traditional techniques have approached routing by ignoring some of these factors and imposing unnecessary constraints in order to make routing tractable. In addition to the imposition of these restrictions, which simplify the problems to a degree but at the same time reduce the routing quality, traditional approaches use brute force. They often transform the problem into mathematical or graph problems and completely ignore the specific knowledge about the routing task that can greatly help the solution. This thesis overcomes some of the above problems and presents a system that performs routing close to what human designers do. In other words it heavily capitalizes on the knowledge of human expertise in this area, it does not impose unnecessary constraints, it considers all the different factors that affect the routing quality, and most importantly it allows constant user interaction throughout the routing process. To achieve the above, this thesis presents background about some representative techniques for routing and summarizes their characteristics. It then studies in detail the different factors (such as minimum area, number of vias, wire length, etc.) that affect the routing quality, and the different criteria (such as vertical/horizontal constraint graph, merging, minimal rectilinear Steiner tree, etc.) that can be used to optimize these factors.

The NATO Advanced Research Workshop on Signal Processing and Pattern Recognition in Nondestructive Evaluation (NOE) of Materials was held August 19-22, 1987 at the Manoir St-Castin, Lac Beauport, Quebec, Canada. Modern signal processing, pattern recognition and artificial intelligence have been playing an increasingly important role in improving nondestructive evaluation and testing techniques. The cross fertilization of the two major areas can lead to major advances in NOE as well as presenting a new research area in signal processing. With this in mind, the Workshop provided a good review of progress and comparison of potential techniques, as well as constructive discussions and suggestions for effective use of modern signal processing to improve flaw detection, classification and prediction, as well as material characterization. This Proceedings volume includes most presentations given at the Workshop. This publication, like the meeting itself, is unique in the sense that it provides extensive interactions among the interrelated areas of NOE. The book starts with research advances on inverse problems and then covers different aspects of digital waveform processing in NOE and eddy current signal analysis. These are followed by four papers of pattern recognition and AI in NOE, and five papers of image processing and reconstruction in NOE. The last two papers deal with parameter estimation problems. Though the list of papers is not extensive, as the field of NOE signal processing is very new, the book has an excellent collection of both tutorial and research papers in this exciting new field.

Purpose of this book is to combine different approaches in the study of arm movement in space in order to create new synergy between domains of researchwhich tend to be developed independently. It is from these synergies that a new understanding of the control of arm and hand movement can ermerge.Previous books have been devoted to artificial neural networks for sensorimotor control (for example Advanced Neural Computers, R. Eckmiller ed. Elsevier). The present book is the first one to propose a precise and direct comparison between current computational development and new experimental results of neurophysiology and new experimental results of neurophysiology and neurophysics. The book covers different levels of neuralcontrol: spinal cord, red nucleus, premotor cortex, motor cortex, parietal cortex, thalamus and cerebellum. An important place is devoted to the problems of muscle coordination, internal representations of movement variables, in different nervous regions and to the problem of coordinate transformations underlying reaching and manipulation. For the physiologist, the book proposes not only a comprehensive picture of new experimental results but also a theoretical basis for a better understandingof central coding of movement by neuroinal populations. For neural networks and robotics students, this book provides a very rich knowledge on the way the brain controls arm movements by using visual information, it can offer them new concepts and ideas to generate more efficient artificial systems having in mind the powerful capacity of the human brain.

Wireless networking enables two or more computers to communicate using standard network protocols without network cables. Since their emergence in the 1970s, wireless networks have become increasingly pop ular in the computing industry. In the past decade, wireless networks have enabled true mobility. There are currently two versions of mobile wireless networks. An infrastructure network contains a wired backbone with the last hop being wireless. The cellular phone system is an exam ple of an infrastructure network. A multihop ad hoc wireless network has no infrastructure and is thus entirely wireless. A wireless sensor network is an example of a multihop ad hoc wireless network. Ad hoc wireless networking is a technique to support robust and ef ficient operation in mobile wireless networks by incorporating routing functionality into mobile hosts. This technique will be used to realize the dream of "anywhere and anytime computing," which is termed mo bile computing. Mobile computing is a new paradigm of computing in which users carrying portable devices have access to shared infrastruc ture in any location at any time. Mobile computing is a very challenging topic for scientists in computer science and electrical engineering. The representative system for ad hoc wireless networking is called MANET, an acronym for "Mobile Ad hoc NETworks." MANET is an autonomous system consisting of mobile hosts connected by wireless links which can be quickly deployed."

This book contains 26 papers presented at the NATO Advanced Research Workshop on "CAD Based Programming for Sensory Robots," held in IL CIOCCa, Italy, July 4-6, 1988. CAD based robot programming is considered to be the process where CAD (Computer Based) models are used to develop robot programs. If the program is generated, at least partially, by a programmer interacting, for example, with a computer graph i c d sp i 1 ay of the robot and its workce 11 env ironment, the process is referred to as graphical off-line programming. On the other hand, if the robot program is generated automatically, for example, by a computer, then the process is referred to as automatic robot programmi ng. The key element here is the use of CAD models both for interact i ve and automat i c generat i on of robot programs. CAD based programmi ng, therefore, bri ngs together computer based model i ng and robot programmi ng and as such cuts across several discipl ines including geometric model ing, robot programming, kinematic and dynamic modeling, artificial intelligence, sensory monitoring and so-on.

The aim of computer-aided surgery (CAS) is to advance the utilization of computers in the development of new technologies for medical services. The Asian Conference on Computer Aided Surgery (ACCAS) series provides a forum for academic researchers, clinical scientists, surgeons, and industrial partners to exchange new ideas, techniques, and the latest developments in the field. The ACCAS brings together researchers from all fields related to medical activity visualization, simulation and modeling, virtual reality for CAS, image-guided diagnosis and therapies, CAS for minimally invasive intervention, medical robotics and instrumentation, surgical navigation, clinical application of CAS, telemedicine and telesurgery, and CAS education. The ACCAS is also interested in promoting collaboration among people from different disciplines and different countries in Asia and the world. This volume helps to achieve that goal and is a valuable resource for researchers and clinicians in the field.

Knighting in sequence biology Edward N. Trifonov Genome classification, construction of phylogenetic trees, became today a major approach in studying evolutionary relatedness of various species in their vast - versity. Although the modern genome clustering delivers the trees which are very similar to those generated by classical means, and basic terminology is the same, the phenotypic traits and habitats are not anymore the playground for the classi- cation. The sequence space is the playground now. The phenotypic traits are - placed by sequence characteristics, "words", in particular. Matter-of-factually, the phenotype and genotype merged, to confusion of both classical and modern p- logeneticists. Accordingly, a completely new vocabulary of stringology, information theory and applied mathematics took over. And a new brand of scientists emerged - those who do know the math and, simultaneously, (do?) know biology. The book is written by the authors of this new brand. There is no way to test their literacy in biology, as no biologist by training would even try to enter into the elite circle of those who masters their almost occult language. But the army of - formaticians, formal linguists, mathematicians humbly (or aggressively) longing to join modern biology, got an excellent introduction to the field of genome cl- tering, written by the team of their kin.

The goal of the research out of which this monograph grew, was to make annealing as much as possible a general purpose optimization routine. At first glance this may seem a straight-forward task, for the formulation of its concept suggests applicability to any combinatorial optimization problem. All that is needed to run annealing on such a problem is a unique representation for each configuration, a procedure for measuring its quality, and a neighbor relation. Much more is needed however for obtaining acceptable results consistently in a reasonably short time. It is even doubtful whether the problem can be formulated such that annealing becomes an adequate approach for all instances of an optimization problem. Questions such as what is the best formulation for a given instance, and how should the process be controlled, have to be answered. Although much progress has been made in the years after the introduction of the concept into the field of combinatorial optimization in 1981, some important questions still do not have a definitive answer. In this book the reader will find the foundations of annealing in a self-contained and consistent presentation. Although the physical analogue from which the con cept emanated is mentioned in the first chapter, all theory is developed within the framework of markov chains. To achieve a high degree of instance independence adaptive strategies are introduced."

Iterative Learning Control for Deterministic Systems is part of the new Advances in Industrial Control series, edited by Professor M.J. Grimble and Dr. M.A. Johnson of the Industrial Control Unit, University of Strathclyde. The material presented in this book addresses the analysis and design of learning control systems. It begins with an introduction to the concept of learning control, including a comprehensive literature review. The text follows with a complete and unifying analysis of the learning control problem for linear LTI systems using a system-theoretic approach which offers insight into the nature of the solution of the learning control problem. Additionally, several design methods are given for LTI learning control, incorporating a technique based on parameter estimation and a one-step learning control algorithm for finite-horizon problems. Further chapters focus upon learning control for deterministic nonlinear systems, and a time-varying learning controller is presented which can be applied to a class of nonlinear systems, including the models of typical robotic manipulators.The book concludes with the application of artificial neural networks to the learning control problem. Three specific ways to neural nets for this purpose are discussed, including two methods which use backpropagation training and reinforcement learning. The appendices in the book are particularly useful because they serve as a tutorial on artificial neural networks.

This book presents the results of an international workshop on Modelling and Analysis of Arms Control Problems held in Spitzingsee near Munich in October 1985 under the joint sponsorship of NATO's Scientific Affairs Division and the Volkswagen Foundation. The idea for this workshop evolved in 1983, as a consequence of discussions in the annual Systems Science Seminar at the Computer Science Department of the Federal Armed Forces University ~1unich on the topic of Quantitative Assessment in Arms Control 1) * There was wide agreement among the contribu tors to that seminar and its participants that those efforts to assess the potential contributions of systems and decision sciences, as well as systems analysis and"mathematical modelling, to arms control issues should be ex panded and a forum should be provided for this activity. It was further agreed that such a forum should include political scientists and policy analysts working in the area of arms control.

This volume introduces innovative power estimation and optimization methodologies to support the design of low power embedded systems based on high-performance VLIW microprocessors. A VLIW processor is a (generally) pipelined processor that can execute, in each clock cycle, a set of explicitly parallel operations.

A number of fundamental topics in the field of high performance clock distribution networks is covered in this book. High Performance Clock Distribution Networks is composed of ten contributions from authors at academic and industrial institutions. Topically, these contributions can be grouped within three primary areas. The first topic area deals with exploiting the localized nature of clock skew. The second topic area deals with the implementation of these clock distribution networks, while the third topic area considers more long-range aspects of next-generation clock distribution networks. High Performance Clock Distribution Networks presents a number of interesting strategies for designing and building high performance clock distribution networks. Many aspects of the ideas presented in these contributions are being developed and applied today in next-generation high-performance microprocessors.

Mixed-Mode Simulation and Analog Multilevel Simulation addresses the problems of simulating entire mixed analog/digital systems in the time-domain. A complete hierarchy of modeling and simulation methods for analog and digital circuits is described. Mixed-Mode Simulation and Analog Multilevel Simulation also provides a chronology of the research in the field of mixed-mode simulation and analog multilevel simulation over the last ten to fifteen years. In addition, it provides enough information to the reader so that a prototype mixed-mode simulator could be developed using the algorithms in this book. Mixed-Mode Simulation and Analog Multilevel Simulation can also be used as documentation for the SPLICE family of mixed-mode programs as they are based on the algorithms and techniques described in this book.

In the summer of 1981 I was asked to consider the possibility of manufacturing a 600,000 transistor microprocessor in 1985. It was clear that the technology would only be capable of manufacturing 100,000-200,000 transistor chips with acceptable yields. The control store ROM occupied approximately half of the chip area, so I considered adding spare rows and columns to increase ROM yield. Laser-programmed polysilicon fuses would be used to switch between good and bad circuits. Since only half the chip area would have redundancy, I was concerned that the increase in yield would not outweigh the increased costs of testing and redundancy programming. The fabrication technology did not yet exist, so I was unable to experimentally verify the benefits of redundancy. When the technology did become available, it would be too late in the development schedule to spend time running test chips. The yield analysis had to be done analytically or by simulation. Analytic yield analysis techniques did not offer sufficient accuracy for dealing with complex structures. The simulation techniques then available were very labor-intensive and seemed more suitable for redundant memories and other very regular structures [Stapper 80J. I wanted a simulator that would allow me to evaluate the yield of arbitrary redundant layouts, hence I termed such a simulator a layout or yield simulator. Since I was unable to convince anyone to build such a simulator for me, I embarked on the research myself.