Transcript Applying FPGA to Biological Problems

Applying
Field Programmable
Gate Arrays
to Biological Problems
Presented by
Debbi Ryle
Daryl Popig
Accelerated Data Concepts
June – 2006
Accelerated Data Concepts
Introductions

Accelerated Data Concepts
Specializing in Reconfigurable Computing Development



Debbi Ryle, Co-founder
Daryl Popig, Co-founder
Collaborations


Dr. Eric Stahlberg, OpenFPGA.org
David Pellerin, Impulse Accelerated Technologies
June – 2006
Accelerated Data Concepts
FPGA Technology

FPGA (field programmable gate array) are
digital logic chips containing:





Programmable logic blocks
Programmable interconnects & switch matrices
Programmable I/O
Block RAM
PowerPC processors

June – 2006
used in embedded systems
Accelerated Data Concepts
FPGA Technology





Inherently parallel device
Performs spatial processing of work
Reconfigurable - “Reconfigurable Computing”
 Loadable sets of logic blocks
 Specialized tasks
Eliminates bottlenecks associated with generalpurpose processors
Alternative direction to exploit Moore’s Law
June – 2006
Accelerated Data Concepts
Why is Digital Logic Faster Than Software?
Spatial vs. Temporal Computation
Processors divide computation across time, dedicated logic divides across space
y = Ax2 + Bx + C
Temporal Computation
t1
t1 = x
t2 = t1 * A
t2 = t2 + B
t2 = t2 * t1
y = t2 + C
Spatial Computation
x
*
*
t2
A
B
C
A
*
+
C
+
Y
June – 2006
B
Accelerated Data Concepts
Using FPGAs for Acceleration



Identify algorithms that can exploit FPGA finegrained parallelism
Look for candidate code using low-level data
parallelism
Exploit digital logic blocks ready to execute:


Computationally intensive calculations
Excessive multiple inner looping or backtracking
June – 2006
Accelerated Data Concepts
Candidate Applications




Drug Docking - prescreening small module compounds
for drug interaction
Medical Imagining - Cat Scanning
Molecular Simulation
Matlab
June – 2006
Accelerated Data Concepts
Computational Challenges



Smith-Waterman algorithm used to identify similarities
among bioinformatics sequences
Floyd-Warshall algorithm performing graph network
analysis
Searches through unstructured data (video, audio,
instrument signals, etc.)
June – 2006
Accelerated Data Concepts
FPGA - Design Approach






Code application in C language
Find the computational “hot spots”
Partition the algorithm into software and hardware
processing
Use interactive optimization tools to analyze and
improve the performance of hardware-accelerated
functions
Use a C-to-hardware compiler to generate
synthesizable hardware
Load the resulting bitmap file to the FPGA device
June – 2006
Accelerated Data Concepts
FPGA - Design Approach

Find the program’s “hot
spots”



Parallel threads
Computational routines
Nested N loops
June – 2006
Accelerated Data Concepts
FPGA - Design Approach

Partition the algorithm
into software and
hardware processing

Use data streaming,
message passing and/or
shared memory to
partition the algorithm
into multiple
communicating software
and hardware processes
June – 2006
Accelerated Data Concepts
FPGA - Design Approach

Use interactive optimization tools to analyze and
improve the performance of hardware-accelerated
functions

Emerging FPGA tools:
 Impulse-C
 Nallatech DimeTalk
 Mitronics
 SRC
June – 2006
Accelerated Data Concepts
FPGA - Design Approach

Use a C-tohardware
compiler to
generate
synthesizable
hardware

Load the
resulting bitmap
file to the FPGA
device
June – 2006
Accelerated Data Concepts
Programming Tools

New tools simplifying FPGA programming at a
higher level of abstraction

Allows software developers to code without intense
hardware knowledge

Allows easier Hardware/Software co-simulation

Converts C code to a Hardware Descriptive
Language which is then converted to a net list and
then the place and route tools make a FPGA
loadable bitmap
June – 2006
Accelerated Data Concepts
FPGA Hardware




Latest chip capacity denser with million gate devices
Requires less energy consumption
Reduce costs
Major Chip manufactures:



Xlinix
Altera
Available on wide variety of hardware platform:




SRC
CRAY Linux
Linux based
Windows based
June – 2006
Accelerated Data Concepts
Performance Gains



Searching speed-up by 45x
Smith-Waterman implementation speed ups by
64x
Network Graph analysis problems speed ups by
30x
June – 2006
Accelerated Data Concepts
Summary

General Processor limitations - Moores law
driving for alternatives

Hardware - chip capacity denser allowing more
complex algorithms

Software tools simplifying FPGA programming

World wide researcher’s interest OpenFPGA.org
June – 2006
Accelerated Data Concepts
Acknowledgements
Special Thanks to OCCBIO
Conference
For more information on FPGA
Technology, visit:



http://acceleratedata.com
http://www.openfpga.org
http://implusec.com
June – 2006
Accelerated Data Concepts
References

Givaris, T., Reconfigurable Computing,
http://www.ics.uci.edu/~dutt/ics212-wq05/reconfig.pdf

Lysaght, P. 2006, FPGAs in the decade after Von Neuman Century,
DATE06 conference proceedings, Munich, Germany

Pellerin, D., 2006, Hardware/Software co-design, FPGA II, DATE06
conference proceedings, Munich, Germany
June – 2006
Accelerated Data Concepts