4.10 Summary............................................................................................ 115

References ..................................................................................................... 116

5. Application Mapping on Network-on-Chip ......................................... 119

5.1 Introduction ....................................................................................... 119

5.2 Mapping Problem ............................................................................. 120

5.3 ILP Formulation ................................................................................ 123

5.3.1 Other ILP Formulations ...................................................... 127

5.4 Constructive Heuristics for Application Mapping ...................... 128

5.4.1 Binomial Merging Iteration ................................................ 130

5.4.2 Topology Mapping and Traffic Surface Creation ............ 131

5.4.3 Hardware Cost Optimization ............................................ 132

5.5 Constructive Heuristics with Iterative Improvement.................. 134

5.5.1 Initialization Phase.............................................................. 134

5.5.2 Shortest Path Computation................................................. 135

5.5.3 Iterative Improvement Phase ............................................. 136

5.5.4 Other Constructive Strategies............................................ 137

5.6 Mapping Using Discrete PSO ......................................................... 141

5.6.1 Particle Structure ................................................................. 141

5.6.2 Evolution of Generations .................................................... 142

5.6.3 Convergence of DPSO ......................................................... 143

5.6.4 Overall PSO Algorithm....................................................... 144

5.6.5 Augmentations to the DPSO .............................................. 144

5.6.5.1 Multiple PSO ......................................................... 144

5.6.5.2 Initial Population Generation ............................. 145

5.6.6 Other Evolutionary Approaches........................................ 148

5.7 Summary............................................................................................ 150

References ..................................................................................................... 150

6. Low-Power Techniques for Network-on-Chip ..................................... 155

6.1 Introduction ....................................................................................... 155

6.2 Standard Low-Power Methods for NoC Routers ......................... 158

6.2.1 Clock Gating ......................................................................... 158

6.2.2 Gate Level Power Optimization ........................................ 159

6.2.3 Multivoltage Design ............................................................ 160

6.2.3.1 Challenges in Multivoltage Design ................... 161

6.2.4 Multi-V T Design.................................................................... 164

6.2.5 Power Gating ........................................................................ 165

6.3 Standard Low-Power Methods for NoC Links............................. 166

6.3.1 Bus Energy Model................................................................ 167

6.3.2 Low-Power Coding .............................................................. 168

6.3.3 On-Chip Serialization ......................................................... 170

6.3.4 Low-Swing Signaling .......................................................... 171

Contents
vii