Massively parallel genomic sequence search on the Blue Gene/P architecture

ABSTRACT

This paper presents our first experiences in mapping and optimizing genomic sequence search onto the massively parallel IBM Blue Gene/P (BG/P) platform. Specifically, we performed our work on mpiBLAST, a parallel sequence-search code that has been optimized on numerous supercomputing environments. In doing so, we identify several critical performance issues. Consequently, we propose and study different approaches for mapping sequence-search and parallel I/O tasks on such massively parallel architectures. We demonstrate that our optimizations can deliver nearly linear scaling (93% efficiency) on up to 32,768 cores of BG/P. In addition, we show that such scalability enables us to complete a large-scale bioinformatics problem --- sequence searching a microbial genome database against itself to support the discovery of missing genes in genomes --- in only a few hours on BG/P. Previously, this problem was viewed as computationally intractable in practice.

REFERENCES

• 1: P. Balaji, W. Feng, H. Lin, J. Archuleta, S. Matsuoka, A. Warren, J. Setubal, E. Lusk, R. Thakur, I. Foster, D. S. Katz, S. Jha, K. Shinpaugh, S. Coghlan, and D. Reed. Distributed Data I/O with ParaMEDIC: Experiences with a Worldwide Supercomputer. In Proceedings of the IEEE International Supercomputing Conference (ISC): Best paper award, Dresden, Germany, June 2008.
• 2: R. D. Bjornson , A. H. Sherman , S. B. Weston , N. Willard , J. Wing, TurboBLAST(r): A Parallel Implementation of BLAST Built on the TurboHub, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.325, April 15-19, 2002
• 3: R. C. Braun , K. T. Pedretti , T. L. Casavant , T. E. Scheetz , C. L. Birkett , C. A. Roberts, Parallelization of local BLAST service on workstation clusters, Future Generation Computer Systems, v.17 n.6, p.745-754, April 2001 [doi>10.1016/S0167-739X(00)00057-1]
• 4: N. Camp, H. Cofer, and R. Gomperts. High-throughput BLAST. http://www.sgi.com/industries/sciences/chembio/resources/papers/HTBlast/HT_Whitepaper.html.
• 5: E. Chi, E. Shoop, J. Carlis, E. Retzel, and J. Riedl. Efficiency of shared-memory multiprocessors for a genetic sequence similarity search algorithm. Technical Report TR97--005, University of Minnesota, Computer Science Department, 1997.
• 6: Phyllis E. Crandall , Ruth A. Aydt , Andrew A. Chien , Daniel A. Reed, Input/output characteristics of scalable parallel applications, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.59-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224396]
• 7: A. Darling, L. Carey, and W. Feng. The design, implementation, and evaluation of mpiBLAST. In Proceedings of the ClusterWorld Conference and Expo, in conjunction with the 4th International Conference on Linux Clusters: The HPC Revolution, 2003.
• 8: Mark K. Gardner , Wu-chun Feng , Jeremy Archuleta , Heshan Lin , Xiaosong Mal, Parallel genomic sequence-searching on an ad-hoc grid: experiences, lessons learned, and implications, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188564]
• 9: Heshan Lin , Xiaosong Ma , Praveen Chandramohan , Al Geist , Nagiza Samatova, Efficient Data Access for Parallel BLAST, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.72.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.190]
• 10: M. Marra, S. Jones, C. Astell, R. Holt, A. Brooks-Wilson, Y. Butterfield, J. Khattra, J. Asano, S. Barber, S. Chan, A. Cloutier, S. Coughlin, D. Freeman, N. Gim, O. Griffith, S. Leach, M. Mayo, H. McDonald, S. Montgomery, P. Pandoh, A. Petrescu, G. Robertson, J. Schein, A. Siddiqui, D. Smailus, J. Stott, G. Yang, F. Plummer, A. Andonov, H. Artsob, N. Bastien, K. Bernard, T. Booth, D. Bowness, M. Drebot, L. Fernando, R. Flick, M. Garbutt, M. Gray, A. Grolla, S. Jones, H. Feldmann, A. Meyers, A. Kabani, Y. Li, S. Normand, U. Stroher, G. Tipples, S. Tyler, R. Vogrig, D. Ward, B. Watson, R. Brunham, M. Krajden, M. Petric, D. Skowronski, C. Upton, and R. Roper. The genome sequence of the sars-associated coronavirus. Science, 2003.
• 11: D. Mathog. Parallel BLAST on split databases. Bioirformatics, 19(14), 2003.
• 12: John M. May, Parallel I/O for high performance computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 13: Message Passing Interface Forum. MPI-2: Extensions to the Message-Passing Standard, July 1997.
• 14: Jaroslaw Nieplocha , Robert J. Harrison , Richard J. Littlefield, Global arrays: a nonuniform memory access programming model for high-performance computers, The Journal of Supercomputing, v.10 n.2, p.169-189, June 1996
• 15: Nils Nieuwejaar , David Kotz , Apratim Purakayastha , Carla Schlatter Ellis , Michael L. Best, File-Access Characteristics of Parallel Scientific Workloads, IEEE Transactions on Parallel and Distributed Systems, v.7 n.10, p.1075-1089, October 1996 [doi>10.1109/71.539739]
• 16: Christopher Oehmen , Jarek Nieplocha, ScalaBLAST: A Scalable Implementation of BLAST for High-Performance Data-Intensive Bioinformatics Analysis, IEEE Transactions on Parallel and Distributed Systems, v.17 n.8, p.740-749, August 2006 [doi>10.1109/TPDS.2006.112]
• 17: D. Quintero and M. Hennecke. GPFS Multicluster with the IBM System Blue Gene Solution and eHPS Clusters. IBM Redpaper, REDP-4168-00, October 24, 2006, http://www.redbooks.ibm.coin/abstracts/redp4168.html?Open.
• 18: H. Rangwala, E. Lantz, R. Musselman, K. Pinnow, B. Smith, and B. Wallenfelt. Massively Parallel BLAST for the Blue Gene/L. In High Availability and Performance Workshop, 2005.
• 19: Frank B. Schmuck , Roger L. Haskin, GPFS: A Shared-Disk File System for Large Computing Clusters, Proceedings of the Conference on File and Storage Technologies, p.231-244, January 28-30, 2002
• 20: Evgenia Smirni , Ruth A. Aydt , Andrew A. Chien , Daniel A. Reed, I/O Requirements of Scientific Applications: An Evolutionary View, Proceedings of the 5th IEEE International Symposium on High Performance Distributed Computing, p.30, August 06-09, 1996
• 21: E. Smirni , D. A. Reed, Lessons from characterizating the input/output behavior of parallel scientific applications, Performance Evaluation, v.33 n.1, p.27-44, June 1998 [doi>10.1016/S0166-5316(98)00009-1]
• 22: C. Sosa and G. Lakner. IBM System Blue Gene Solution: Blue Gene/P Application Development. IBM Red-Book, SG24--7287, ISBN 0738488674, Rochester, Minnesoat, 2008. http://www.redbooks.ibm.com/abstracts/sg247287.html?Open.
• 23: Rajeev Thakur , Alok Choudhary, An extended two-phase method for accessing sections of out-of-core arrays, Scientific Programming, v.5 n.4, p.301-317, Winter 1996
• 24: Rajeev Thakur , Alok Choudhary , Rajesh Bordawekar , Sachin More , Sivaramakrishna Kuditipudi, Passion: Optimized I/O for Parallel Applications, Computer, v.29 n.6, p.70-78, June 1996
• 25: Rajeev Thakur , William Gropp , Ewing Lusk, Data Sieving and Collective I/O in ROMIO, Proceedings of the The 7th Symposium on the Frontiers of Massively Parallel Computation, p.182, February 21-25, 1999
• 26: Rajeev Thakur , William Gropp , Ewing Lusk, On implementing MPI-IO portably and with high performance, Proceedings of the sixth workshop on I/O in parallel and distributed systems, p.23-32, May 05-05, 1999, Atlanta, Georgia, United States [doi>10.1145/301816.301826]
• 27: Rajeev Thakur , William Gropp , Ewing L. Lusk, An Experimental Evaluation of the Parallel I/O Systems of the IBM SP and Intel Paragon Using a Production Application, Proceedings of the Third International ACPC Conference with Special Emphasis on Parallel Databases and Parallel I/O: Parallel Computation, p.24-35, September 23-25, 1996
• 28: Oystein Thorsen , Brian Smith , Carlos P. Sosa , Karl Jiang , Heshan Lin , Amanda Peters , Wu-chun Feng, Parallel genomic sequence-search on a massively parallel system, Proceedings of the 4th international conference on Computing frontiers, May 07-09, 2007, Ischia, Italy [doi>10.1145/1242531.1242542]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance