Results

Research Interests and Results

Dr. Miller's research interests include Parallel Algorithms and Architectures, Computational Crystallography, Cyberinfrastructure, High-Performance Computing, Grid Computing, Computational Geometry, and Image Analysis.

As of 5/2010, Dr. Miller had an h-index of 29.

Parallel Algorithms. Dr. Miller and colleagues (most notably, Prof. Quentin F. Stout, U. Mich), developed a cadre of efficient and optimal computational paradigms, solution strategies, and data movement operations for a wide variety of parallel architectures, including the mesh, pyramid, hypercube, and PRAM, as well as innovative architectures, such as their reconfigurable mesh. Miller has also applied this toolbox of techniques to create efficient and optimal algorithms to solve fundamental problems in areas including, but not limited to, computational geometry, image analysis, graph theory, and NP-hard problems. A number of seminal peer-reviewed papers have been published that introduce this material. Impact of this material follows.

• Several of our papers covering the reconfigurable mesh have been cited 200+ times each according to Google Scholar.
• Google Scholar lists more than 14,000 papers that present results for the reconfigurable mesh.
• Major papers of ours covering pyramid computer algorithms have been cited 100+ times and several major papers covering mesh algorithms and parallel algorithms to solve problems in computational geometry have been cited nearly 100 times each.

• We introduced a paradigm that could be used within the context of divide-and-conquer or an iterative process whereby one reduces the number of processors being used in the algorithm by an architecture-dependent amount in order to arrive at an optimal solution to a problem. That is, by continuously using fewer processors, one could arrive at a faster algorithm. This notion was in dramatic contrast to the prevailing wisdom of keeping as many processors as possible busy in order to arrive at an efficient algorithm.
• We showed that for a large class of problems, the top of pyramid computer is unnecessary. In fact, we proved that for many problems, a lower bound on the running time is proportional to the square root of the number of processors on the edge of mesh at the base of the pyramid. This result served as a wake up call to many in the image processing community who believed that virtually all image-based problems could be solved in polylogarithmic time on a pyramid computer.
• We introduced a generic divide-and-conquer paradigm that showed by matching certain characteristics of an architecture to the algorithm, efficient and often optimal, divide-and-conquer solutions could be obtained for a wide set of problems on a large set of parallel architectures.
• We introduced fundamental data movement operations that could be ported to a wide variety of parallel architectures and could then be used in conjunction with some of our algorithmic strategies as part of an extensive toolkit to efficiently solve higher-level problems.
• We (including V.K. Prasanna Kumar, USC), and simultaneously several other groups, introduced a reconfigurable mesh that would allow the mesh connections to be enabled or disabled on the fly and assumed that every connected set of processors was connected via a bus rather than a series of mesh links. We were able to show that this model was actually more powerful than the shared-memory PRAM model, previously assumed to be the most powerful model available.

Highlights of algorithms for the various models include the following.

• For the mesh, we introduced asymptotically optimal data movement operations and paradigms. We used these procedures to introduce asymptotically optimal solutions to fundamental problems in areas that included computational geometry, image analysis, and graph theory.
• For the pyramid, we introduced asymptotically efficient/optimal data movement operations. We used these operations to introduce asymptotically optimal solutions to fundamental problems in areas that included graph theory and image analysis.
• For the hypercube, we introduced asymptotically efficient (and often optimal) solutions to fundamental problems in areas that included computational geometry, image analysis and graph theory.
• For the PRAM, we provided asymptotically optimal solutions to problems in computational geometry.
• For the reconfigurable mesh, we introduced asymptotically optimal data movement operations. We used these data movement operations to provide asymptotically optimal algorithms for fundamental problems involving graphs and images.
• We introduced the first asymptotically optimal algorithm to solve the convex hull problem for planar point input on a fixed degree network (a modified AKS network).

• We introduced efficient solutions to fundamental problems in computational geometry for the mesh, hypercube, and PRAM.
• We introduced efficient solutions to fundamental problems in image processing for the mesh, hypercube, pyramid, and reconfigurable mesh.
• We introduced efficient solutions to fundamental problems in graph theory for the mesh, pyramid, hypercube and reconfigurable mesh.

Molecular Structure Determination. Dr. Miller works on a large project in direct methods of crystal structure determination with a world-class group of scientists at the Hauptman-Woodward Medical Research Institute, most notably Nobel Laureate Dr. Herbert A. Hauptman, Dr. George DeTitta, and Dr. Charles M. Weeks.

This project represents a classic model of computational science and engineering. That is, the project involves a computer scientist (Miller), working closely with theoretical and experimental scientists in a disciplinary area (structural biology). The result of this project is the Shake-and-Bake method and associated worldwide community code.

This computer program has significantly increased the size of molecular structures routinely amenable to direct methods by orders of magnitude. Further, it has been shown to be applicable to much larger proteins if they contain the amino-acid methionine labeled with a selenium atom. This project has had significant impact world-wide.

• Our algorithm was listed on the IEEE Poster "Top Algorithms of the 20th Century".
• Approximately 10,000 users from around the world have downloaded the Shake-and-Bake algorithm.
• A direct methods of crystallography paper covering the major breakthrough of Shake-and-Bake has been cited over 14,500 times according to Google Scholar.
• Numerous original papers of ours introducing Shake-and-Bake have been cited 100+ times each, with some being cited as many as 300+ times.

• The development of the minimal principle, which serves as a target function for optimization.
• The development, implementation, and deployment of the Shake-and-Bake method of structure determination.
  • For all intents and purposes, this algorithm "solved" the century-old phase problem of crystallography.
  • The optimization algorithm exploited a variety of techniques during the phase optimization stage, including the traditional tangent formula, the minimal function that we developed, and other traditional optimization strategies, including genetic algorithms and simulated annealing.
  • This program has been used to determine numerous critical structures, including vancomycin, the "antibiotic of last resort".
• The development of a cyclical approach that automatically alternates phase refinement in reciprocal space with the imposition of phase constrains in real space until the structure is determined. (That is, repeat a process until the problem is solved.)
• Using parallel computers (e.g., Intel iPSC/2, Intel iPSC/860, TMC CM-2, and TMC CM-5) to provide the compute cycles necessary to experiment with solution strategies that would eventually be employed on a standard PC.
• Providing an implementation of the solution strategy for a wide variety of parallel and sequential machines.
• The program has been able to solve all structures in the appropriate domains provided that reasonable quality data was provided as input.
• Due to the comprehensive nature of this project, funding was provided by 3 consecutive NIH program-project grants, a variety of NSF grants, as well as foundation and appropriations to support the acquisition of computing resources.

Cyberinfrastructure. The focus of Dr. Miller's Cyberinfrastructure Laboratory is on providing infrastructure necessary to perform high-end simulation and modeling.

• An effective and efficient grid monitoring system was developed and installed on production grids that allows one to asses the health and status of a grid.
• An efficient predictive scheduler was produced and installed on experimental grids that exploits a database of historical jobs to profile user/group/package usage.
• A data migration tool was developed and deployed on experimental grids that allows for the transparent migration of data between various resources on a grid.
• Dynamic resource allocation was designed, developed, and installed on a variety of grids.
• A grid-enabling template framework was developed and deployed that dramatically reduces the time to migrate software to a grid.
• Management tools were developed and deployed for the difficult and atypical heterogeneous grids.
• Numerous software packages were migrated to the grid, including applications in areas of structural biology, bioinformatics, ground water modeling, earthquake engineering, and computational chemistry, to name a few.

Center for Computational Research. Following his vision that in the 21st century, leading academic institutions would embrace the digital data-driven society that we live in and work to empower their students to compete in our knowledge-based economy, Dr. Miller founded the Center for Computational Research (CCR) at SUNY-Buffalo, where he served as Director from 1998-2006. During his tenure, CCR was continuously ranked as one of the leading supercomputing centers worldwide, earning Miller recognition as one of HPC Wire's Top People and Organizations to Watch (2003). Typically, CCR supported hundreds of projects simultaneously from a variety of local and national colleges, universities, non-profit organizations, government agencies, and the private sector. Miller's vision to 1) enable Research and Scholarship, 2) provide Education, Outreach, and Training, and 3) effect Technology Transfer to local industry was successfully served by CCR during his tenure.

One key to building such a successful center was Miller's ability to work with elected officials, local, regional, and national leaders, as well as a wide variety of vendors including Dell, SGI, IBM, EMC, and HP, to name a few. In fact, Miller's efforts with Dell culminated with the installation of the first Dell cluster to make the top500 list (22). Miller also worked with companies in order to generate animated videos for MTV, create traffic accident reconstructions, create traffic flow simulations, and generate medical and scientific visualizations. This work was performed with a variety of local, regional, and national companies and government agencies.

More details on Miller's contributions to CCR can be found on his Biography page.

Center of Excellence in Bioinformatics. The success of CCR and Miller's ability to work with elected officials were key to establishing the $290M New York State Center of Excellence in Bioinformatics, a major economic driver for Western New York. In fact, in establishing the Center of Excellence in January of 2001, New York State Gov. George E. Pataki stated that "This Center [of Excellence in Bioinformatics] will, through the University of Buffalo's Center for Computational Research, create academic and industrial partnerships...."

Education, Outreach, and Training (EOT). Prof. Miller has been teaching undergraduate and graduate courses since 1981. He has given numerous presentations to elected officials, defense contractors, scout troops, high-school students, prospective students and student-athletes, and citizens concerned with plans for construction in the community. In addition, he has produced reports on parallel processing education, organized panel discussions on EOT, serves on the editorial board of a journal devoted to teaching and case studies, and has introduced approximately 10 courses in areas involving cyberinfrastructure, high-end computing, and computational science. Further, under his direction workshops in computational science and high-end computing have been offered for high-school teachers, a year-long bioinformatics course has been developed and offered to high-school students, and training sessions in multiprocessor computing has been offered to faculty, students, and staff from area colleges and organizations. Finally, Dr. Miller was instrumental in the formation of the EOT-PACI program and set up similar programs locally. Finally, Miller was accessible to the media, being quoted in some 1500 news articles and appearing with regularity on television and radio.

Funding. Including personal peer reviewed funding, appropriations, contracts, and additional funds that CCR enabled during his tenure as Director, Dr. Miller has helped bring in approximately $0.5 billion dollars to Western New York.

Additional Information. Additional information is available on the Biography page of this web site.