Dynamic reconfiguration

Dynamic Reconfiguration

Architectures and Algorithms

SERIES IN COMPUTER SCIENCE

Series Editor: Rami G. Melhem

University of Pittsburgh

Pittsburgh, Pennsylvania

DYNAMIC RECONFIGURATION

Architectures and Algorithms

Ramachandran Vaidyanathan and Jerry L. Trahan

ENGINEERING ELECTRONIC NEGOTIATIONS

A Guide to Electronic Negotiation Technologies for the Design and

Implementation of Next-Generation Electronic Markets—Future

Silkroads of eCommerce

Michael Ströbel

HIERARCHICAL SCHEDULING IN PARALLEL AND CLUSTER

SYSTEMS

Sivarama Dandamudi

MOBILE IP

Present State and Future

Abdul Sakib Mondal

OBJECT-ORIENTED DISCRETE-EVENT SIMULATION WITH JAVA

A Practical Introduction

José M. Garrido

A PARALLEL ALGORITHM SYNTHESIS PROCEDURE FOR HIGH￾PERFORMANCE COMPUTER ARCHITECTURES

Ian N. Dunn and Gerard G. L. Meyer

PERFORMANCE MODELING OF OPERATING SYSTEMS USING

OBJECT-ORIENTED SIMULATION

A Practical Introduction

José M. Garrido

POWER AWARE COMPUTING

Edited by Robert Graybill and Rami Melhem

THE STRUCTURAL THEORY OF PROBABILITY

New Ideas from Computer Science on the Ancient Problem of

Probability Interpretation

Paolo Rocchi

Dynamic Reconfiguration

Architectures and Algorithms

Ramachandran Vaidyanathan

and

Jerry L. Trahan

Louisiana State University

Baton Rouge, Louisiana

KLUWER ACADEMIC PUBLISHERS

NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW

eBook ISBN: 0-306-48428-5

Print ISBN: 0-306-48189-8

©2004 Kluwer Academic Publishers

New York, Boston, Dordrecht, London, Moscow

Print ©2003 Kluwer Academic/Plenum Publishers

New York

All rights reserved

No part of this eBook may be reproduced or transmitted in any form or by any means, electronic,

mechanical, recording, or otherwise, without written consent from the Publisher

Created in the United States of America

Visit Kluwer Online at: http://kluweronline.com

and Kluwer's eBookstore at: http://ebooks.kluweronline.com

To

Sudha, Shruti, and Deepti

and

Suzanne, Dana, and Drew

This page intentionally left blank

Contents

List of Figures xiii

Preface xix

Part I Basics

1. PRINCIPLES AND ISSUES 3

1.1 Illustrative Examples 4

1.2 The R-Mesh at a Glance 9

1.3 Important Issues 11

Problems 13

Bibliographic Notes 14

2. THE RECONFIGURABLE MESH: A PRIMER 17

2.1 The Reconfigurable Mesh 17

2.1.1 The (Two-Dimensional) R-Mesh 18

2.2 Expressing R-Mesh Algorithms 22

2.3 Fundamental Algorithmic Techniques 23

2.3.1 Data Movement 24

2.3.2 Efficiency Acceleration—Adding Bits 27

2.3.3 Neighbor Localization—Chain Sorting 33

2.3.4 Sub-R-Mesh Generation—Maximum Finding 40

2.3.5 Distance Embedding—List Ranking 43

2.3.6 Connectivity Embedding—

Connectivity 46

2.3.7 Function Decomposition—Adding N Numbers 49

2.4 Why an R-Mesh? 58

Problems 58

Bibliographic Notes 68

viii DYNAMIC RECONFIGURATION

3. MODELS OF RECONFIGURATION 71

3.1 The Reconfigurable Mesh—A Second Coat 71

3.1.1 Restricted Bus Structure 72

3.1.2 Word Size 75

3.1.3 Accessing Buses 77

3.1.4 Higher Dimensions 79

3.1.5 One-Way Streets 86

3.2 More Ways to Reconfigure 90

3.2.1 Reconfigurable Network 91

3.2.2 Reconfigurable Multiple Bus Machine 91

3.2.3 Optical Models 92

3.2.4 Reconfiguration in FPGAs 96

3.3 How Powerful Is Reconfiguration? 98

Problems 100

Bibliographic Notes 110

Part II Algorithms

4. ARITHMETIC ON THE R-MESH 117

4.1 Starter Set 117

4.1.1 Conversion among Number Formats 118

4.1.2 Floating Point Numbers 119

4.1.3 Maximum/Minimum 120

4.2 The Foundation 122

4.2.1 Addition 123

4.2.2 Multiplication 134

4.2.3 Division 139

4.3 Multiplying Matrices 139

4.3.1 Matrix-Vector Multiplication 140

4.3.2 Matrix Multiplication 142

4.3.3 Sparse Matrix Multiplication 143

Problems 146

Bibliographic Notes 149

5. SORTING AND SELECTION 153

5.1 Sorting on an R-Mesh 154

5.2 A Sub-Optimal Sorting Algorithm 155

5.3 An Optimal Sorting Algorithm 156

Contents ix

5.3.1 Constant Time Sorting 156

5.3.2 Area-Time Tradeoffs 158

5.3.3 Sorting on Three-Dimensional R-Meshes 159

5.4 Selection on an R-Mesh 162

5.4.1 Indexing Schemes 162

5.4.2 An Outline of the Selection Algorithm 163

5.4.3 The Selection Algorithm 165

5.4.4 The Sorted Sample Algorithm 167

5.4.5 Complexity Analysis 171

Problems 173

Bibliographic Notes 176

6. GRAPH ALGORITHMS 179

6.1 Graph Representations 180

6.2 Algorithms for Trees 180

6.2.1 Euler Tour 181

6.2.2 Euler Tour Applications 182

6.2.3 Tree Reconstruction 186

6.3 Algorithms for Graphs 192

6.3.1 Minimum Spanning Tree 192

6.3.2 Connectivity Related Problems 193

6.4 Algorithms for Directed Graphs 198

6.4.1 The Algebraic Path Problem Approach 198

6.4.2 Directed Acyclic Graphs 202

6.5 Efficient List Ranking 206

6.5.1 The Deterministic Method 207

6.5.2 The Randomized Approach 212

Problems 218

Bibliographic Notes 229

7. COMPUTATIONAL GEOMETRY & IMAGE PROCESSING 231

7.1 Computational Geometry 232

7.1.1 Convex Hull 232

7.1.2 Convex Polygon Problems 244

7.1.3 Nearest Neighbors 249

7.1.4 Voronoi Diagrams 250

7.1.5 Euclidean Minimum Spanning Tree 253

7.1.6 Triangulation 254

x DYNAMIC RECONFIGURATION

7.2 Image Processing 254

7.2.1 Basics 255

7.2.2 Histogram 257

7.2.3 Quadtree 261

7.2.4 Moments 267

7.2.5 Image Transforms 269

Problems 269

Bibliographic Notes 272

Part III Simulations and Complexity

8. MODEL AND ALGORITHMIC SCALABILITY 277

8.1 Scaling Simulation on a Smaller Model Instance 278

8.1.1 Scaling the HVR-Mesh 281

8.1.2 Scaling the LR-Mesh 283

8.1.3 Scaling the FR-Mesh 289

8.1.4 Scaling the R-Mesh 294

8.2 Self-Simulation on a Larger Model Instance 298

8.3 Scaling Algorithms 299

8.3.1 Degree of Scalability 300

8.3.2 Matrix Multiplication 301

8.3.3 Matrix-Vector Multiplication 302

Problems 307

Bibliographic Notes 310

9. COMPUTATIONAL COMPLEXITY OF

RECONFIGURATION 313

9.1 Mapping Higher Dimensions to Two Dimensions 314

9.1.1 Lower Bound on Mapping 315

9.1.2 Mapping Dimensions to Two Dimensions 315

9.1.3 Separation of the One-Dimensional R-Mesh from

Higher Dimensional R-Meshes 320

9.2 Simulations between Bit and Word Models 320

9.3 Relations to the PRAM 322

9.4 Loosen Up—Polynomially Bounded Models 326

9.5 Segmenting and Fusing Buses 326

9.5.1 The Reconfigurable Multiple Bus Machine 327

9.5.2 Relative Power of Polynomially Bounded Models 329

Contents xi

9.5.3 Relating the B-RMBM and the PRAM 332

9.5.4 Relating the S-RMBM, HVR-Mesh, and PRAM 333

9.5.5 Relating the F-RMBM, E-RMBM, and R-Mesh 336

9.6 Relations to Turing Machines and Circuits: Hierarchy 340

9.6.1 Turing Machine Definitions 340

9.6.2 Circuit Definitions 340

9.6.3 Complexity Classes 341

9.6.4 Relations to Turing Machines 342

9.6.5 Relations to Circuits 346

Problems 348

Bibliographic Notes 351

Part IV Other Reconfigurable Architectures

10. OPTICAL RECONFIGURABLE MODELS 357

10.1 Models, Models Everywhere 358

10.1.1 The LARPBS Model 360

10.1.2 Other Models 364

10.2 Basic Algorithmic Techniques 368

10.2.1 Permutation Routing 369

10.2.2 Binary Prefix Sums 369

10.3 Algorithms for Optical Models 374

10.3.1 Basic Results 374

10.3.2 Sorting and Selection 377

10.3.3 Multiple Addition 383

10.3.4 Matrix Multiplication 383

10.3.5 387

10.4 Complexity of Optical Models 394

10.4.1 Simulating PRAMs 395

10.4.2 Equivalence of One-Dimensional Models 396

10.4.3 Relating the PR-Mesh and the LR-Mesh 399

10.4.4 Relating Two-Dimensional Optical Models 403

Problems 408

Bibliographic Notes 412

11. RUN-TIME RECONFIGURATION 417

11.1 FPGA Background 419

11.1.1 FPGA Structure 419

xii DYNAMIC RECONFIGURATION

11.1.2 FPGA System Model 422

11.2 Run-Time Reconfiguration Concepts and Examples 424

11.2.1 Basic Concepts 424

11.2.2 Examples: Specific Problems 428

11.2.3 Examples: Generic Problems 434

11.3 Hardware Operating System 438

11.3.1 Dynamic Instruction Set Computer 439

11.3.2 RAGE 440

11.3.3 Configuration Controllers 441

11.3.4 Task Compaction 442

11.4 Alternative Implementations 445

11.4.1 Early Configurable Computing Machines 446

11.4.2 Other Directions in RTR 447

11.5 Designing Implementable R-Mesh Algorithms 450

11.5.1 Bus Delay 451

11.5.2 An LR-Mesh Implementation 455

11.5.3 Retooling Algorithms for the Bends-Cost Measure 458

Problems 461

References 471

Index 499

List of Figures

1.1 An N-processor segmentable bus. 5

1.2 Bus structure for a binary tree algorithm. 6

1.3 Bus structure for finding the OR. 6

1.4 Example of a one-dimensional R-Mesh. 9

1.5 Example of a two-dimensional R-Mesh. 10

1.6 Example of computing on the R-Mesh. 10

2.1 A reconfigurable linear array. 17

2.2 An example of an R-Mesh. 19

2.3 Port partitions of an R-Mesh. 20

2.4 An R-Mesh bus configuration and graph. 20

2.5 Broadcasting on an R-Mesh. 25

2.6 Permutation routing. 27

2.7 Adding bits. 28

2.8 addition on an R-Mesh. 29

2.9 Examples of and 31

2.10 Neighbor localization example. 34

2.11 Chain sorting. 36

2.12 Concatenating lists in chain sorting. 39

2.13 Maximum finding example. 42

2.14 List ranking strategy. 45

2.15 Illustration of the

connectivity algorithm. 48

2.16 Adding a distributed unary integer to 1-bit numbers. 51

2.17 Dividing a distributed unary integer by 2. 52

2.18 Illustration of terms for adding integers. 53

2.19 Module

for carry generation. 55

xiv DYNAMIC RECONFIGURATION

2.20 Cascading modules 56

2.21 Labeled binary trees. 59

2.22 Finite automaton for Algorithm 2.3. 62

2.23 Finite automaton for Problem 2.21(a). 62

3.1 R-Meshes with restricted bus structures. 73

3.2 A three-dimensional R-Mesh. 80

3.3 Indexing ports for priority resolution. 81

3.4 A priority resolution example. 85

3.5 Directedness in buses. 87

3.6 The directed R-Mesh. 88

3.7 Reachability on a directed R-Mesh. 89

3.8 The Reconfigurable Multiple Bus Machine (RMBM). 92

3.9 Structure of an optical model. 93

3.10 Optical pipelining. 94

3.11 Coincident pulse addressing. 95

3.12 Structure of a typical FPGA. 96

3.13 Powers of conventional and reconfigurable models. 98

3.14 A 3 × 5 RMESH. 101

3.15 A 3-port shift switch. 105

3.16 Exclusive OR with shift switches. 106

3.17 A P × B Distributed Memory Bus Computer. 107

4.1 Example representations of for 119

4.2 Partitioning an R × C R-Mesh 121

4.3 Input arrangement in an R × C R-Mesh 123

4.4 Example of R-Mesh adding two 8-bit numbers. 124

4.5 Sample h-slice and v-slice. 126

4.6 Multiplication on the bit-model R-Mesh. 135

4.7 Slices of a three-dimensional R-Mesh. 141

4.8 Example sparse matrix and data movement. 144

5.1 Transposing and untransposing for columnsort. 156

5.2 Shifting and unshifting for columnsort. 157

5.3 A columnsorting network. 158

5.4 Components of columnsort on a three-dimensional

R-Mesh. 161

5.5 Indexing examples for R-Mesh processors. 163

5.6 Merge tree for a sorted sample. 168

5.7 Merge tree for a sub-R-Mesh of Algorithm 5.2. 170