Splash 2 FPGAs in a Custom Computing Machine

This book describes the Splash 2 computing system as designed and built at the Supercomputing Research Center. This is a novel attached processor using Xilinx 4010 FPGAs as its processing elements and whose application programming language is VHDL. This is the first publication that details the complete Splash 2 project -- the hardware and software systems, the architecture and their implementations, and the design process by which the architecture evolved from an earlier version machine. This text allows you to understand why the machine has been engineered in the way it has. In addition to the description of the machine, several applications are described in detail, permitting the reader to gain an understanding of the capabilities and the limitations of this kind of computing device. The Splash 2 program is significant for two reasons. First, Splash 2 is part of a complete computer system that achieves supercomputer like performance on a number of different applications. The second significant aspect is that this large system is capable of performing real computations on real problems. In order to understand what happens when the application programmer is permitted to design the processor architecture of the machine that execute his programs, it is necessary to see the system as a whole. This book looks in-depth at one of the handful of data points in the design space of this new kind of machine.

Duncan A. Buell NCR Professor of Computer Science and Engineering Dept. of Computer Science and E University of South Carolina.

PREFACE

xi

1 CUSTOM COMPUTING MACHINES: AN INTRODUCTION

1

(9)

1.1 Introduction

1

(3)

1.2 The Context for Splash 2

4

(6)

1.2.1 FPGAs

4

(1)

1.2.2 Architecture

5

(1)

1.2.3 Programming

6

(4)

2 THE ARCHITECTURE OF SPLASH 2

10

(9)

2.1 Introduction

10

(1)

2.2 The Building Blocks

11

(1)

2.3 The System Architecture

12

(1)

2.4 Data Paths

13

(3)

2.5 The Splash 2 Array Board

16

(1)

2.5.1 The Linear Array

16

(1)

2.5.2 The Splash 2 Crossbar

16

(1)

2.5.3 Xilinx Chip X0 and Broadcast Mode

17

(1)

2.6 The Interface Board and Control Features

17

(2)

3 HARDWARE IMPLEMENTATION

19

(12)

3.1 Introduction

19

(2)

3.2 Development Board Design

21

(1)

3.3 Interface Board Design

21

(4)

3.3.1 DMA Channel

23

(1)

3.3.2 XL and XR

23

(1)

3.3.3 Interrupts

24

(1)

3.3.4 Clock

24

(1)

3.3.5 Programming and Readback

24

(1)

3.3.6 Miscellaneous Registers

25

(1)

3.4 Array Board Design

25

(6)

3.4.1 Processing Element

26

(2)

3.4.2 Control Element

28

(1)

3.4.3 External Memory Access

28

(1)

3.4.4 Crossbar

28

(1)

3.4.5 Programming and Readback

29

(1)

3.4.6 Miscellaneous Registers

29

(2)

4 SPLASH 2: THE EVOLUTION OF A NEW ARCHITECTURE

31

(15)

4.1 Splash 1

31

(3)

4.2 Splash 2: Thoughts on a Redesign

34

(2)

4.3 Programming Language

36

(1)

4.4 Choice of FPGAs

37

(1)

4.5 Choice of Host and Bus

38

(1)

4.6 Chip-to-Chip Interconnections

39

(3)

4.7 Multitasking

42

(1)

4.8 Chip X0 and Broadcast

43

(1)

4.9 Other Design Decisions

43

(3)

5 SOFTWARE ARCHITECTURE

46

(14)

5.1 Introduction

46

(1)

5.2 Background

47

(2)

5.3 VHDL as a Programming Language

49

(2)

5.3.1 History and Purpose of VHDL

50

(1)

5.3.2 VHDL Language Features

50

(1)

5.3.3 Problems with VHDL

51

(1)

5.4 Software Environment

51

(4)

5.5 Programmer's View of Splash 2

55

(5)

5.5.1 Programming Process

55

(1)

5.5.2 Processing Element View

56

(1)

5.5.3 Interface Board View

57

(1)

5.5.4 Host View

57

(3)

6 SOFTWARE IMPLEMENTATION

60

(17)

6.1 Introduction

60

(1)

6.2 VHDL Environment

60

(6)

6.2.1 Splash 2 VHDL Library

61

(1)

6.2.2 Standard Entity Declarations

61

(3)

6.2.3 Programming Style

64

(2)

6.3 Splash 2 Simulator

66

(4)

6.3.1 Structure

66

(1)

6.3.2 Configuring the Simulator

67

(1)

6.3.3 Input and Output

68

(1)

6.3.4 Crossbar and Memory Models

68

(2)

6.3.5 Hardware Constraints

70

(1)

6.4 Compilation

70

(2)

6.4.1 Logic Synthesis

70

(1)

6.4.2 Physical Mapping

71

(1)

6.4.3 Debugging Support

71

(1)

6.5 Runtime System

72

(3)

6.5.1 T2: A Symbolic Debugger

72

(1)

6.5.2 Runtime Library

73

(1)

6.5.3 Device Driver

74

(1)

6.6 Diagnostics

75

(2)

7 A DATA PARALLEL PROGRAMMING MODEL

77

(20)

7.1 Introduction

78

(2)

7.2 Data-parallel Bit C

80

(2)

7.2.1 dbC Overview

80

(1)

7.2.2 dbC Example

81

(1)

7.3 Compiling from dbC to Splash 2

82

(6)

7.3.1 Creating a Specialized SIMD Engine

83

(1)

7.3.2 Generic SIMD Code

84

(1)

7.3.3 Generating VHDL

84

(4)

7.4 Global Operations

88

(4)

7.4.1 Nearest-Neighbor Communication

88

(1)

7.4.2 Reduction Operations

89

(2)

7.4.3 Host/Processor Communication

91

(1)

7.5 Optimization: Macro Instructions

92

(2)

7.5.1 Creating a Macro Instruction

93

(1)

7.5.2 Discussion

94

(1)

7.6 Evaluation: Genetic Database Search

94

(1)

7.7 Conclusions and Future Work

95

(2)

8 SEARCHING GENETIC DATABASES ON SPLASH 2

97

(13)

8.1 Introduction

97

(3)

8.1.1 Edit Distance

98

(1)

8.1.2 Dynamic Programming Algorithm

98

(2)

8.2 Systolic Sequence Comparison

100

(4)

8.2.1 Bidirectional Array

100

(3)

8.2.2 Unidirectional Array

103

(1)

8.3 Implementation

104

(3)

8.3.1 Modular Encoding

105

(1)

8.3.2 Configurable Parameters

106

(1)

8.3.3 Bidirectional Array

107

(1)

8.3.4 Unidirectional Array

107

(1)

8.4 Benchmarks

107

(1)

8.5 Discussion

108

(1)

8.6 Conclusions

108

(2)

9 TEXT SEARCHING ON SPLASH 2

110

(7)

9.1 Introduction

110

(1)

9.2 The Text Searching Algorithm

111

(2)

9.3 Description of the Single-Byte Splash Program

113

(1)

9.4 Timings, Discussion

114

(1)

9.5 Outline of the 16-bit Approach

115

(1)

9.6 Conclusions

116

(1)

10 FINGERPRINT MATCHING ON SPLASH 2

117

(24)

10.1 Introduction

117

(3)

10.2 Background

120

(5)

10.2.1 Pattern Recognition Systems

121

(1)

10.2.2 Terminology

122

(1)

10.2.3 Stages in AFIS

123

(2)

10.3 Splash 2 Architecture and Programming Models

125

(1)

10.4 Fingerprint Matching Algorithm

125

(3)

10.4.1 Minutia Matching

126

(1)

10.4.2 Matching Algorithm

127

(1)

10.5 Parallel Matching Algorithm

128

(6)

10.5.1 Preprocessing on the Host

131

(1)

10.5.2 Computations on Splash

132

(1)

10.5.3 VHDL Specification for X0

133

(1)

10.6 Simulation and Synthesis Results

134

(3)

10.7 Execution on Splash 2

137

(2)

10.7.1 User Interface

137

(1)

10.7.2 Performance Analysis

137

(2)

10.8 Conclusions

139

(4)

11 HIGH-SPEED IMAGE PROCESSING WITH SPLASH 2

141

(25)

11.1 Introduction

141

(1)

11.2 The VTSplash System

142

(1)

11.3 Image Processing Terminology and Architectural Issues

143

(7)

11.4 Case Study: Median Filtering

150

(3)

11.5 Case Study: Image Pyramid Generation

153

(6)

11.5.1 Gaussian Pyramid

154

(1)

11.5.2 Two Implementations for Gaussian Pyramid on Splash 2

155

(2)

11.5.3 The Hybrid Pipeline Gaussian Pyramid Structure

157

(1)

11.5.4 The Laplacian Pyramid

157

(2)

11.5.5 Implementation of the Laplacian Pyramid on Splash 2

159

(1)

11.6 Performance

159

(4)

11.7 Summary

163

(3)

12 THE PROMISE AND THE PROBLEMS

166

(13)

12.1 Some Bottom-Line Conclusions

166

(3)

12.1.1 High Bandwidth I/O Is a Must

166

(1)

12.1.2 Memory Is a Must

167

(1)

12.1.3 Programming Is Possible, and Becoming More So

168

(1)

12.1.4 The Programming Environment Is Crucial

168

(1)

12.2 To Where from Here?

169

(2)

12.3 If Not Splash 3, Then What?

171

(6)

12.3.1 Architectures

172

(1)

12.3.2 Custom Processors

173

(1)

12.3.3 Languages

174

(3)

12.4 The "Killer" Applications

177

(1)

12.5 Final Words

178

(1)

A SPLASH 2 DEVELOPMENT--THE PROJECT MANAGER'S SUMMARY

179

(7)

B AN EXAMPLE APPLICATION

186

(4)

REFERENCES

190

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Splash 2 FPGAs in a Custom Computing Machine

Summary

Author Biography

Table of Contents

Supplemental Materials