ERSA’11 PROGRAMME

ERSA INVITED TALK

Prof. Jeremy Buhler
Design-Space Exploration of Systolic Arrays for Biosequence Algorithms,
Prof. Jeremy Buhler, Prof. Roger Chamberlain, and Dr. Arpith Jacob,
Washington University in St. Louis., USA
Time: 03:50 - 04:10pm
Location: Gold Room

Abstract:

The last decade has seen a revolution in technologies to sequence large amounts of DNA. Multiple order-of-magnitude improvements in speed and cost have made direct sequencing the biologist’s choice not only for determining the DNA sequence of a genome but also for studying the expression and control of its genes. However, this boon for biology is potentially a bane for bioinformatics, as growth in the volume of sequence data outstrips improvements in the compute power of CPU-based computing platforms.

Reconfigurable computing is an attractive alternative to conventional systems for implementing sequence-based bioinformatics tools. Many important algorithms for tasks such as biosequence comparison, sequence-model alignment, and RNA structure prediction can be described by dynamic programming (DP) recurrences, which can be realized as highly parallel systolic arrays [4]. These arrays should map straightforwardly to implementations on reconfigurable hardware that greatly outperform conventional CPU-based implementations. In practice, however, a programmer must search among numerous possible array designs to find one that balances conflicting needs for high performance, bounded resource utilization, and ability to handle problems of realistic size. The demands of this difficult balancing act can make high-performance array implementation practically inaccessible to all but a few expert designers.

In this work, we describe our recent progress in simplifying and automating the exploration of array design space, with application to realizing DP recurrences from bioinformatics. Using the tools of polyhedral theory [1], we describe the space of all systolic arrays for a particular recurrence and formulate optimization criteria that allow us to search efficiently for good point designs in this space. We have demonstrated the utility of our methods by building high-performance FPGA implementations of the Nussinov [5] and Zuker [6] algorithms for secondary structure prediction in RNAs.

An important feature of many bioinformatics problems is that performance is measured not by latency of one operation (e.g. comparing two sequences or folding one RNA) but by throughput, the rate at which a large number of operations can be completed. Explicitly optimizing for throughput leads to a surprisingly easy-to-automate procedure for array design-space search; we have used this procedure to discover novel, highly efficient FPGA realizations of the Nussinov algorithm [2]. Using these ideas and others related to partitioned array design, we have constructed an FPGA implementation of the more complex Zuker algorithm [3] that outperforms conventional CPU implementations by over 100-fold.

Finally, we present a vision, based on our work, for automated compilation of common DP recurrences in bioinformatics to efficient fine-grained parallel implementations. Such a compiler would put the power of reconfigurable computing in the hands of the typical bioinformatics programmer and provide a boost to bioinformaticians in their ongoing race to keep up with advances in sequencing technology.

References

  1. A. Darte, R. Schreiber, B. R. Rau, and F. Vivien. Constructing and exploiting linear schedules with prescribed parallelism. ACM Trans. Design Automation of Electronic Systems, 7(1):159-172, 2002.
  2. A. Jacob, J. Buhler, and R. Chamberlain. Design of throughput-optimized arrays from recurrence abstractions. In Proc. 21st IEEE Intl. Conf. Application-Specific Architectures and Processors, pages 133-140, 2010.
  3. A. Jacob, J. Buhler, and R. Chamberlain. Rapid RNA folding: analysis and acceleration of hte zuker recurrence. In Proc. 18th IEEE Ann. Intl. Symp. Programmable Custom Computing Machines, pages 87-94, 2010.
  4. D. Lavenier, P. Quinton, and S. Rajopadhye. Advanced Systolic Design, chapter 23. CRC Press, 1999.
  5. R. Nussinov, G. Pieczenik, J. R. Griggs, and D. J. Kleitman. Algorithms for loop matchings. SIAM Journal on Applied Mathematics, 35(1):68-82, 1978.
  6. M. Zuker. Computer prediction of RNA structure. Methods in Enzymology, 180:262-288, 1989.

Bio:

Jeremy Buhler is an associate professor in the Dept. of Computer Science and Engineering at Washington University in St. Louis. He leads the department’s High Performance Computational Biology Group. His research interests include acceleration of algorithms for biological sequence comparison, mapping of bioinformatics algorithms onto fine-grained parallel architectures, and developing new bioinformatics tools in a variety of areas. He received his BA in Computer Science from Rice University and his MS and PhD in Computer Science from the University of Washington.