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
