This book addresses the difficulty of obtaining a quality solution, that is, pre optimal or even optimal, in a reasonable time from a central processing unit (CPU). As polynomial problems can be treated by exact methods, the problem posed concerns non-polynomial problems, for which it is necessary to develop efficient algorithms based on heuristics or meta-heuristics. Chapter 3 of this book demonstrates how to develop such algorithms, which are characterized by: an initialization of argued solutions (sometimes, the global optimum can be obtained from such an initialization); a non-random generation of solutions (to avoid generating the same solution several times, or even generating solutions that cannot be achieved); avoidance of being trapped by a local optimum; good use of CPU time by reducing the size of the space of solutions to be explored (which is often very large for such problems) without compromising the quality of the solution; plus a reasoned displacement from one solution to another, to improve the quality of the solution as the processing is carried out. These aspects are applied to concrete applications in the design of integrated circuits and systems at various levels. To do this and to help the reader better understand this problem, Chapters 1 and 2 present basic notions on computational complexity, and the design of integrated circuits and systems.

Table of Contents:
Preface ix Chapter 1. Basic Notions on Computational Complexity and Approximate Techniques 1 1.1. Computational complexity 1 1.1.1. Introduction 1 1.1.2. Big O notation 2 1.1.3. Ω Notation 3 1.1.4. Calculation of T(n) 4 1.2. Language computability 10 1.2.1. Turing machine and class P 10 1.2.2. Non-deterministic algorithm and class NP 12 1.2.3. NP-complete problems 16 1.2.4. NP-hard problems 27 1.2.5. NP-intermediate problems 31 1.2.6. Co-NP problems 33 1.2.7. Class hierarchy 34 1.3. Heuristics and metaheuristics 35 1.3.1. Definitions 35 1.3.2. Graph theory 36 1.3.3. Branch and bound technique 37 1.3.4. Tabu search technique 41 1.3.5. Simulated annealing technique 43 1.3.6. Genetic and evolutionary algorithms 45 1.4. Conclusion 48 Chapter 2. Basic Notions on the Design of Digital Circuits and Systems 49 2.1. Introduction 49 2.2. History of VLSI circuit design 49 2.2.1. Prediffused circuit 49 2.2.2. Sea of gates 49 2.2.3. Field-programmable gate array – FPGA 51 2.2.4. Elementary pre-characterized circuit (standard cells) 52 2.2.5. Full-custom circuit 53 2.2.6. Silicon compilation 54 2.3. System design level 57 2.3.1. Synthesis 57 2.3.2. Floorplanning 64 2.3.3. Analysis 65 2.3.4. Verification 66 2.4. Register transfer design level 69 2.4.1. Synthesis 69 2.4.2. Analysis 90 2.4.3. Verification 91 2.5. Module design level 92 2.5.1. Synthesis 92 2.5.2. Analysis 93 2.5.3. Verification 98 2.6. Gate design level 99 2.6.1. Synthesis 99 2.6.2. Analysis 111 2.6.3. Verification 112 2.7. Transistor level 112 2.7.1. NMOS and CMOS technologies 112 2.7.2. Theory of MOS transistor (current IDS) 114 2.7.3. Transfer characteristics of the inverter 117 2.7.4. Static analysis of the inverter 118 2.7.5. Threshold voltage of the inverter 119 2.7.6. Estimation of the rise and fall times of a capacitor 120 2.8. Interconnections 124 2.8.1. Synthesis of interconnections 126 2.8.2. Synthesis of networks-on-chip 140 2.9. Conclusion 151 Chapter 3. Case Study: Application of Heuristics and Metaheuristics in the Design of Integrated Circuits and Systems 153 3.1. Introduction 153 3.2. System level 154 3.2.1. Synthesis of systems-on-chip (SoCs) with low energy consumption 154 3.2.2. Heuristic application to dynamic voltage and frequency scaling (DVFS) for the design of a real-time system subject to energy constraint 160 3.3. Register transfer level 174 3.3.1. Integer linear programming applied to the scheduling of operations of a data flow graph (DFG) 174 3.3.2. The scheduling of operations in a controlled data flow graph (considering the speed–power consumption tradeoff) 176 3.3.3. Efficient code assignment to the states of a finite state machine (aimed at reaching an effective control part in terms of surface, speed and power consumption) 176 3.3.4. Synthesis of submicron transistors and interconnections for the design of high-performance (low-power) circuits subject to power (respectively time) and surface constraints 196 3.4. Module level 207 3.4.1. Design of low-power digital circuits 207 3.4.2. Reduction of memory access time for the design of embedded systems 219 3.5. Gate level 227 3.5.1. Estimation of the average and maximal power consumption of a digital circuit 227 3.5.2. Automated layout generation of some regular structures (shifters, address decoders, PLAs) 234 3.5.3. Automated layout generation of digital circuits according to the River PLA technique 238 3.6. Interconnections 239 3.6.1. Low-power buffer insertion technique for the design of submicron interconnections with delay and surface constraints 239 3.6.2. Data encoding and decoding for low-power aided design of submicron interconnections 250 3.6.3. High-level synthesis of networks-on-chip subject to bandwidth, surface and power consumption constraints 253 3.7. Conclusion 263 References 267 Index 273