10
5. Summary of Current Implementations
Table 1 provides a list of current implementations for each of the three SSCA benchmarks. The benchmarks have been implemented in several languages, with contributions from industry, academia, supercomputing centers and national labs.
Kepner and Meuse from MIT Lincoln Labs maintain the reference executable implementations inMatlab for the three SSCAs. Bader and Madduri have developed a parallel implementation of SSCA #2 in C using the POSIX thread library for commodity symmetric multiprocessors (SMPs). They evaluate the data layout choices and algorithmic design issues for each kernel, and also present execution time and benchmark validation results.17 Gilbert, Reinhardt and Shah describe a StarP implementation of SSCA #2 in [18]. The various SSCA implementations have also been compared for productivity studies.
| Benchmark Language | Bioinformatics (SSCA#1) | Graph Theory (SSCA#2) | Sensor and IO (SSCA#3) |
| Written spec | 0.5 (GT/LL) | 2.0 (GT/LL) | 0.8 (LL) |
| C | 0.5k1† (PSC) | 2.0 (GT) | 0.5 (ISI) |
| C & MPI | 0.5k1† (PSC) | ||
| C & MPI & OpenMP | |||
| UPC | 0.5k1† (UNM/GT/PSC) | 1.0* (UNM/GT) | |
| C & Pthreads | 0.5k1* (UNM/GT) | 2.0* (UNM/GT) | |
| C++ | 1.0 (LL/MITRE/CS) | ||
| Fortran | 2.0† (Sun) | 0.5io (LM) | Fortran & OpenMP | 2.0† (Sun) |
| Matlab | 0.5 (LL) | 2.0 (LL) | 0.8 (LL) |
| MatlabMPI | 1.0 (LL) | 0.8 (LL) | |
| Matlab & mexGA | 0.5* (OSC) | 1.0* (OSC) | 0.8* (LL) |
| StarP | 2.0* (UCSB) | 0.5 (UCSB) | |
| pMatlab | 1.0 (LL) | 1.0 (LL) | |
| Octave | 0.8* (OSC) | 1.0* (UW) | 0.8 (OSC) |
| Octave & mexGA | 0.8* (OSC) | 1.0* (OSC) | 0.5* (OSC) |
| Python | Python & MPI | ||
| Java | 0.5k1† (PSC) | 1.0int† (GT) | |
| Chapel | 0.5 (Cray) | 1.0int† (Cray) | |
| X10 | 0.5k1† (UNM/GT/PSC) | 1.0* (UNM/GT/IBM) | |
| Fortress | |||
|
CS: CodeSourcery, LLC GT: Georgia Institute of Technology ISI: Univ. of Southern California, Information Sciences Institute LL: MIT Lincoln Labs LM: Lockheed Matrin MITRE: MITRE Corporation OSC: Ohio Supercomputer Center PSC: Pittsburgh Supercomputer Center UCSB: Univ. of California, Santa Barbara UNM: Univ. of New Mexico UTK: Univ. of Tennessee UW: University of Wisconsin |
|||
Table 1. Current SSCA benchmark implementation status (* indicates a completed implementation that has not been released yet, and † indicates work in progress).
References
1DARPA Information Processing Technology Office. High productivity computing systems project, 2004.
www.darpa.mil/ipto/programs/hpcs/
2Kepner, J., Koester, D. P., et al. "HPCS Scalable Synthetic Compact Application (SSCA) Benchmarks," 2004. www.highproductivity.org/SSCABmks.htm
3Altschul, S. F., Gish, W., Miller, W., Myers, E. W., Lipman, D. J. "Basic local alignment search tool," J. Molecular Biology, 215:403–410, 1990.
4Durbin, R., Eddy, S., Krogh, A., Mitchison, G. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge, UK, 1998.
5Eddy, S. R. "Profile hidden Markov models," Bioinformatics, 25:755–763, 1998.
6Gribskov, M., McLachlan, A. D., Eisenberg, D. "Profile analysis," Methods of Enzymology, 183:146–159, 1990.
7Gupta, S. K., Kececioglu, J. D., Schaffer, A. A. "Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment," Journal of Computational Biology, 2:459–472, 1995.
8Gusfield, D. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.
9Hillis, D. M., Moritz, C., Mable, B. K. (Eds.) Molecular Systematics. Sinauer Associates, Sunderland, MA, second edition, 1996.
10Lesk, A. M. Introduction to Bioinformatics. Oxford University Press, 2002.
11Myers, E. W., Miller, W. "Optimal alignments in linear space," Comp. Appl. Biosciences, 4:11–17, 1988.
12Setubal, J., Meidanis, J. (Eds.) Introduction to Computational Molecular Biology. PWS Publishers, 1996.
13Thompson, J. D., Higgins, D. G., Gibson, T. J. "CLUSTALW: improving the senstivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice," Nucleic Acids Res., 22:4673–4680, 1994.
14Waterman, M. S. Introduction to Computational Biology: Maps, Sequences and Genomes. Chapman & Hall / CRC, Boca Raton, FL, 1995.
15Dongarra, J. J., Bunch, J. R., Moler, C. B., Stewart, G. W. LINPACK Users’ Guide SIAM, Philadelphia, PA, 1979.
16Kepner, J., Koester, D. P., et al. HPCS SSCA #2 Graph Analysis Benchmark Specifications v1.0, April 2005.
17Bader, D. A., Madduri, K. "Design and implementation of the HPCS graph analysis benchmark on symmetric multiprocessors," In Proceedings of the 12th Int’l Conf. on High Performance Computing (HiPC 2005), Goa, India, December 2005. Springer-Verlag.
18Gilbert, J. R., Reinhardt, S., Shah, V. "High performance graph algorithms from parallel sparse matrices," Submitted to PARA06 proceedings, 2006.
19Chakrabarti, D., Zhan, Y., Faloutsos, C. "R-MAT: A recursive model for graph mining," In Proceedings of the 4th SIAM Intl. Conf. on Data Mining (SDM), Orlando, FL, April 2004.
20Freeman, L. C. "A set of measures of centrality based on betweenness," Sociometry, 40(1):35–41, 1977.
21Brandes, U. "A faster algorithm for betweenness centrality," J. Mathematical Sociology, 25(2):163–177, 2001.
22Bader, D. A., Madduri, K. "Parallel algorithms for evaluating centrality indices in real-world networks," In Proceedings of the 35th Int’l Conf. on Parallel Processing (ICPP), Columbus, OH, August 2006.
2Kepner, J., Koester, D. P., et al. "HPCS Scalable Synthetic Compact Application (SSCA) Benchmarks," 2004. www.highproductivity.org/SSCABmks.htm
3Altschul, S. F., Gish, W., Miller, W., Myers, E. W., Lipman, D. J. "Basic local alignment search tool," J. Molecular Biology, 215:403–410, 1990.
4Durbin, R., Eddy, S., Krogh, A., Mitchison, G. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge, UK, 1998.
5Eddy, S. R. "Profile hidden Markov models," Bioinformatics, 25:755–763, 1998.
6Gribskov, M., McLachlan, A. D., Eisenberg, D. "Profile analysis," Methods of Enzymology, 183:146–159, 1990.
7Gupta, S. K., Kececioglu, J. D., Schaffer, A. A. "Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment," Journal of Computational Biology, 2:459–472, 1995.
8Gusfield, D. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.
9Hillis, D. M., Moritz, C., Mable, B. K. (Eds.) Molecular Systematics. Sinauer Associates, Sunderland, MA, second edition, 1996.
10Lesk, A. M. Introduction to Bioinformatics. Oxford University Press, 2002.
11Myers, E. W., Miller, W. "Optimal alignments in linear space," Comp. Appl. Biosciences, 4:11–17, 1988.
12Setubal, J., Meidanis, J. (Eds.) Introduction to Computational Molecular Biology. PWS Publishers, 1996.
13Thompson, J. D., Higgins, D. G., Gibson, T. J. "CLUSTALW: improving the senstivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice," Nucleic Acids Res., 22:4673–4680, 1994.
14Waterman, M. S. Introduction to Computational Biology: Maps, Sequences and Genomes. Chapman & Hall / CRC, Boca Raton, FL, 1995.
15Dongarra, J. J., Bunch, J. R., Moler, C. B., Stewart, G. W. LINPACK Users’ Guide SIAM, Philadelphia, PA, 1979.
16Kepner, J., Koester, D. P., et al. HPCS SSCA #2 Graph Analysis Benchmark Specifications v1.0, April 2005.
17Bader, D. A., Madduri, K. "Design and implementation of the HPCS graph analysis benchmark on symmetric multiprocessors," In Proceedings of the 12th Int’l Conf. on High Performance Computing (HiPC 2005), Goa, India, December 2005. Springer-Verlag.
18Gilbert, J. R., Reinhardt, S., Shah, V. "High performance graph algorithms from parallel sparse matrices," Submitted to PARA06 proceedings, 2006.
19Chakrabarti, D., Zhan, Y., Faloutsos, C. "R-MAT: A recursive model for graph mining," In Proceedings of the 4th SIAM Intl. Conf. on Data Mining (SDM), Orlando, FL, April 2004.
20Freeman, L. C. "A set of measures of centrality based on betweenness," Sociometry, 40(1):35–41, 1977.
21Brandes, U. "A faster algorithm for betweenness centrality," J. Mathematical Sociology, 25(2):163–177, 2001.
22Bader, D. A., Madduri, K. "Parallel algorithms for evaluating centrality indices in real-world networks," In Proceedings of the 35th Int’l Conf. on Parallel Processing (ICPP), Columbus, OH, August 2006.
