Parallel hierarchical molecular structure estimation

Cheng Che Chen, Jaswinder Pal Singh, Russ B. Altman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Determining the three-dimensional structure of biological molecules such as proteins and nucleic acids is an important element of molecular biology because of the intimate relation between form and function of these molecules. Individual sources of data about molecular structure are subject to varying degrees of uncertainty. We have previously examined the parallelization of a probabilistic algorithm for combining multiple sources of uncertain data to estimate the structure of molecules and predict a measure of the uncertainty in the estimated structure. In this paper we extend our work on two fronts. First we present a hierarchical decomposition of the original algorithm which reduces the sequential computational complexity tremendously. The hierarchical decomposition in turn reveals a new axis of parallelism not present in the “flat” organization of the problems, as well as new parallelization issues. We demonstrate good speedups on two cache-coherent shared-memory multiprocessors, the Stanford DASH and the SGI Challenge, with distributed and centralized memory organization, respectively. Our results point to several areas of further study to make both the hierarchical and the parallel aspects more flexible for general problems: automatic structure decomposition, processor load balancing across the hierarchy, and data locality management in conjunction with load balancing. We outline the directions we are investigating to incorporate these extensions.

Original languageEnglish (US)
Title of host publicationProceedings of the 1996 ACM/IEEE Conference on Supercomputing, SC 1996
PublisherAssociation for Computing Machinery
ISBN (Electronic)0897918541
DOIs
StatePublished - 1996
Event1996 ACM/IEEE Conference on Supercomputing, SC 1996 - Pittsburgh, United States
Duration: Nov 17 1996Nov 22 1996

Publication series

NameProceedings of the International Conference on Supercomputing
Volume1996-November

Conference

Conference1996 ACM/IEEE Conference on Supercomputing, SC 1996
Country/TerritoryUnited States
CityPittsburgh
Period11/17/9611/22/96

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • Computing with uncertainty
  • Hierarchical computation
  • Molecular structures
  • Shared-memory parallel processing

Fingerprint

Dive into the research topics of 'Parallel hierarchical molecular structure estimation'. Together they form a unique fingerprint.

Cite this