Applying FPGA to Biological Problems

download report

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