CAD of Circuits and Integrated Systems

3Case Study: Application of Heuristics and Metaheuristics in the Design of Integrated Circuits and Systems

3.1. Introduction

Since integrated systems have grown in complexity, the methods used for their design increasingly rely on the use of computer science and operational research. However, even though the current processors are characterized by high performance in terms of executing the instructions of a given program, it is still true that a conventional resolution of certain problems does not yield the expected results within a reasonable CPU time. Determining the computational complexity of a given (tractable or intractable) problem is, in fact, the basis for deciding whether to implement an exact algorithm or opt for an approximate method. For this purpose, the notions of computational complexity and problem classification were examined in Chapter 1. Since the exact or approximate algorithm of a given problem cannot be determined without knowledge of the respective problem, Chapter 2 focused on clarifying this issue and defining its various aspects. We hope that these two chapters will enable the reader to better approach Chapter 3, which presents the exact or approximate methods in the context of a given problem. It will be seen that many of the approached problems that are related to the design of integrated circuits and systems are not tractable, and therefore they need to be solved by approximate methods. Since these methods have the double difficulty of being in ...