Splash 2 FPGAs in a Custom Computing Machine

by Buell, Duncan A.; Arnold, Jeffrey M.; Kleinfelder, Walter J.

• ISBN13: 9780818674136
• ISBN10: 081867413X
• Edition: 1st
• Format: Hardcover
• Copyright: 1996-06-13
• Publisher: Wiley-IEEE Computer Society Pr

Summary

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.

Author Biography

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

Table of Contents

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