A phylogeny is an evolutionary tree reconstructed from its leaves (each of which represents a different species) by using DNA sequence or gene data and a plausible model of evolution. Phylogenies are crucial tools in understanding biological evolution and biological mechanisms and their reconstruction has been one of the main algorithmic problems in computational biology. Reconstruction of the evolutionary history of a group of organisms has changed the face of biology and is being used increasingly in drug discovery, epidemiology, and genetic engineering. Unfortunately, such reconstructions typically involve solving difficult optimization problems, so that even moderately large datasets can require months to years of computation. In addition, almost all evolutionary reconstructions presently assume that the historical pattern is one of strict divergence that can be represented by a binary tree. This assumption is frequently violated, especially by plants which often hybridize readily and thus produce networks of relationships.
The future of high-performance computing relies on the efficient use of clusters with symmetric multiprocessor nodes and scalable interconnection networks. Hardware benchmark results reveal awesome performance rates for each component; however, few applications on SMP clusters ever reach a fraction of these peak speeds. Our focus is to develop a hybrid, hierarchical methodology that is a much closer abstraction of the underlying machine and is ideally suited to SMP clusters. The current deployment of teraflops and the future development of petaflops systems will certainly require the exploitation of similar advanced programming models.
We are addressing a number of basic combinatorial computations that are commonly needed in various large scale applications. One such computation is sorting, a problem that has been studied extensively in the literature because of its many important applications and because of its intrinsic theoretical significance. Our research has produced the fastest known high-level, practical algorithms for many combinatorial problems such as sorting, personalized communication, selection, list ranking, and data redistribution, on general purpose parallel machines.
Image processing applications are well-suited to high performance computing techniques for several reasons: uniform grid layouts, spatial locality, and highly regular kernels. Images used for analysis are produced from a variety of applications, for example, remote sensing, image understanding, face recognition, detection of surface defects in industrial manufacturing, military target recognition, etc. Some of the processing is low-level, such as image calibration or enhancement, while other analysis is intermediate- or high-level, such as segmenting an image into objects or regions and classifying each. We have developed a high performance suite of practical algorithms for image processing that seem to outperform all other known implementations on the same platforms.
