The area of computational science is growing, as more scientists are finding more problems (and larger problems) that require computational resources exceeding the capacity of a single machine. The next logical step in developing computational capability for handling these large problems is to distribute these problems over multiple machines loosely connected in a “grid”.
The rapid emergence of grid computing and the promise of grid utilities may enable scientific simulation on a size and time scale heretofore unimaginable. The computing resources of grids may have their greatest impact in the fields of life sciences and science medicine. Understanding the interaction of medicines with living systems from a molecular scale to the scale of organs and systems of organs would benefit greatly from harnessing the power of computing grids. High performance grid solutions in the life sciences may someday enable personalized medicine and personalized genomics.
The idea of a computing grid was first suggested almost 40 years ago, when MIT's Fernando Corbato and other designers of the Multics operating system envisioned a computer facility operating “like a power company or water company”. Reference is made to V. A. Vyssotsky, F. J. Corbató, R. M. Graham, in Fall Joint Computer Conference, AFIPS Conf. Proc. 27, 203 (1965), available at http://www.multicians.org/fjcc3.html.
In the 1960's, the primitive network infrastructure, early non-portable programming languages, and incompatible component interfaces made it difficult to build a multi-computer system of any significant size or power. Since then, advances in each of these areas (and more) have contributed to the current environment that is conducive to creating large grid computing systems out of distributed heterogeneous parts.
As the ability to process large problems grows, the appetite for large computation seems to grow faster. Whereas, just 10 years ago, scientists were content to compute the structure of a single small molecule, today they want to solve the protein-folding problem and to calculate the structures of complex assemblies of macromolecules. As grid computing moves from the purely scientific arena to become an integral part of the practice of medicine and the design of drugs, the complexity and volume of problems for the grid may grow.
Previous efforts in grid computing have addressed the issues involved with spreading a problem over a large number of computers, load sharing, and the use of idle cycles to employ more partially available computers. Each computer used to process the distributed problem within the grid is a compute agent. Independently parallel computing (IPC) processes the same data, the same code, and the same application, all in parallel. The same code is solved many times. The larger problem is broken into pieces, sent to many computers for processing, then returned to the client. IPC requires computers that are homogeneous, having the same operating system, and that have resources to process their piece of the problem to completion. When the computing problem is broken into equal loads and distributed for processing among this homogenous group of computers, the processing of the computing problem becomes exclusive for these computers; they become dedicated to the processing of that problem until processing is complete.
Systems such as the PointCast Client and SETI@Home use the screen saver process to perform useful work through IPC. SETI@Home created one of the first large-scale distributed computations by distributing small amounts of work (searching for extra-terrestrial intelligence from radio telescope data) to a large number of clients (almost 3 million) over the Internet. The SETI@Home system, for example, sends a self-contained computation to each compute node (in a user base of almost 3 million computers) that then returns the results back to a centralized site.
Another system, Condor, was one of the first systems to use idle workstations on a local area network. Condor performs an initial load check to make sure that the jobs it is distributing all go to compute nodes that can handle them, then dispatches problems to idle computers that have advertised that they can execute jobs.
A more recent system, the Globus package, helps grid programmers by offering middleware for distributed metacomputing. Globus provides a mechanism for communication, data exchange and job submission, all using a single sign-on. It also provides a mechanism for resource discovery (a concept similar to LDAP or UDDI Web Services discovery). It does not deal with non-compute resources, replicas, local user management, backend system management or compute agent management.
Similar to IPC, connected parallel computing also applies to applications and problems that are too large to fit on one computer. However, the problem addressed by these applications can't be broken into many identical pieces for processing. Rather, the problem requires dividing the application and the data into small pieces that are dissimilar. Once these dissimilar pieces are distributed to computers for processing, these pieces need to communicate with one another based on the manner in which the application or problem was divided.
There have already been many surveys of computing grid systems and computing grid problems but there is still at least one large class of complex scientific problems that have not yet been fully addressed. Reference is made to Mark Baker, Rajkumar Buyya and Domenico Laforenza, “The Grid: A Survey on Global Efforts in Grid Computing,” Paul Shread, “Even Small Companies Can Benefit From Grid Computing,” and Grid Survey, The foregoing systems and problems fall in the category of cellular automata or finite element models (FEM). There is currently very little work in creating a general parallel infrastructure for FEM or cellular automata problems using multiple general-purpose computers. The finite element method is the formulation of a global model to simulate static or dynamic response to applied forces. Cellular automata provide a framework for a large class of discrete models with homogeneous interactions. Cellular automata are basically a subset of the FEM family. Cellular automata are finite by definition, but they also have additional qualities that allow them to be exploited differently than the more general FEMs.
One approach to solving cellular automata and FEM problems has been to use large single address space machines that can be composed of one or more tightly-coupled computers that use hardware assist to create a single large address space. Another approach has been to use multiple homogeneous computers that use message passing. Both of these solutions require a large number of expensive dedicated machines. For certain organizations with very important problems and a significant budget, the large dedicated machine cluster is an excellent solution. However, there is a growing segment of the scientific community that needs access to a large compute facility but doesn't have the budget to afford the large dedicated computer complex.
Cellular automata and FEM are both best addressed by the connected parallel computing approach. FEM divides the problem space into elements. Each element has both data and code. However, the solution to the problem of one element depends not only on the data local to that one element but also to other elements to which that one element is connected. For example, the study of stress on a bone depends not just on the elements receiving the stress. The stress is propagated throughout the bone through the connections between elements. A FEM study of stress and response on a bone divides the bone into finite elements. Each element might have data such as elasticity and codes.
As medical and biological data goes digital and data volumes increase exponentially, large-scale simulation may become critical both to advancing scientific understanding and for the design of new system level treatments. Fortunately, many of the computational techniques required to attempt such system level studies are already under development. Furthermore, these problems are naturally adaptable to parallel processing (parallelizable). All known life is cellular. Every living cell contains all of the instructions for its replication and operation. All of the functions of a multicellular organism are performed by transporting molecular messages, establishing concentration gradients across membranes, and by local physical (e.g., protein folding) and chemical (e.g., metabolic) reactions. In principle, at the algorithmic level there are no new breakthroughs required to solve problems as complex as understanding the chemistry of life. However, all of these future applications require massive resources on the scale of a computing grid.
Unlike parallel applications that are easily distributed on a network, large-scale models of living cellular systems require ongoing communication between the computers participating in the computation. Even within a cell, membranes encapsulate function providing essential special gradients. They also, in some sense, encapsulate complexity. For example, one can imagine a model of a living cell containing an object called a “mitochondria”. The model of the mitochondria might be a spatial model that accurately solves the chemistry of energy generation within the cell at a molecular level, or the mitochondria might represent a functional object that, given appropriate inputs, produces adenosine triphosphate (ATP) based on a mathematical algorithm. In either case, the cell may be described by objects, each of which provides defined function at some time scale, at a point in space, in response to various input signatures.
Models of living systems can be solved numerically by partitioning space into “small” regions or finite elements, where “small” is defined by the smallest natural scale in a problem. However, in practice the overall scale of a problem to be studied along with the available compute resource may limit the resolution of the calculation. Problem scale and available resources thus impose a lower bound on the finite element size. For large problems, collections of finite elements should be processed on different computers.
A very simple example can be used to understand the complexity introduced by requiring communication between adjacent cells in any FEM class problem. One such example is a “Game of Life” based on a modified Eden Model for bacterial growth. Reference is made to Murray Eden and Philippe Thevenaz, “The Eden Model History of a Stochastic Growth Model,” available at http://bigwww.epfl.ch/publications/eden9701.html; M. Eden, Proceedings of the Fourth Berkeley Symposium on Mathematics, Statistics, and Probability, edited by J. Neumann (University of California, Berkeley, 1961), Vol. 4, p. 233. In this example, three model “bacteria” (A, B, C) are growing in a two dimensional space (e.g., the surface of a Petri dish). Using Cartesian coordinates, the smallest “elements” or “cells” in this space are squares with sides of unit length. Objects are used to represent the data contained in any cell, in this case the bacteria that may be present. Each cell also contains the methods or rules that describe local rules comprising how the bacteria interact with one another, and propagation methods that describe how they spread or reproduce. In this example, the interaction method causes bacteria A to eat bacteria B, bacteria B to eat bacteria C, and bacteria C to eat bacteria A. Reproduction or propagation to adjacent sites or cells requires that each cell also store pointers to neighboring cells. These pointers define a graph and together with the propagation method add the communication requirement to the problem. In the example, the propagate method causes, at every iteration, an entity at site (i,j) to spread to it's nearest neighbors at sites (i+1,j),(i−1,j),(i,j+1),(i,j−1) each with probability 0.5 (the classic Eden model for bacterial growth).
In this hypothetical example, the problem being studied is so large it cannot be solved on a single computer. Conceptually, it is simple to divide space (the Cartesian region) into partitions or collections of original problem cells (OPCs). Since each cell contains all the data, methods, and pointers to interacting neighbors that it needs to perform the onsite calculation, the problem is highly parallelizable. If a neighbor OPC is located on the same compute node, it is a “local neighbor”. If an OPC is located on a different compute node, it is a “remote neighbor”. If a problem is made up of OPCs with no neighbors at all, it is called “embarrassingly parallel” in the sense that no communication is needed to iterate the problem. If each of the four problem partitions for this example are dispatched to four different machines, then the cells in the outer shell have one or more nearest neighbors that are located on a remote machine. The problem, as defined, requires that every machine exchange data with machines handling adjacent regions of space at every cycle. They need not exchange all data, only the outer shell or interfacial cells. If the dimensionality of space is d, the data exchanged has dimensionality (d−1) provided the interfaces between partitions are kept “smooth”.
The grid infrastructure required to solve this class of problem should provide for efficient communication between neighboring problem pieces. Since the state of one part of the overall problem depends (transitively) on all adjacent parts, it is necessary to keep the parts relatively synchronized. If the compute agent responsible for one part of the problem were to fall behind, then the other compute agents could proceed no faster than the slowest one. The existing grid systems using currently available technology do not provide for inter-communicating problem pieces or manage the load of individual nodes to balance the progress of all the compute agents.
There exist a plethora of commercial tools to facilitate finite element analysis studies on a single workstation comprising products by algor, altair, ansys, comsol, cosmos/m, EDS, and others. Reference is made to Commercial FEM products, When the problem to be solved is very large and the solution to the problem is economically important, dedicated parallel machines are employed. There is no shortage of complex problems requiring parallel computation to solve. The primary cost factor limiting the application of these techniques is the availability of parallel machines and storage.
Cellular problems are ubiquitous in nature comprising the life sciences, physics, and chemistry. They describe anything involving cellular interaction (e.g., all of life) or anything involving flow (air, fluids, money, finance, system biology, drug interactions, circuit design, weather forecasting, population study, spread of disease in populations, cellular automata, crash testing, etc.). To better exploit the power of the grid, one should go beyond solving the most massively parallel (e.g., SETI@Home) class of problems and develop techniques to efficiently manage problems requiring frequent communication between adjacent problem partitions.
The promise of grid computing in general is that a method may be found to employ idle computers around the world to work on all sorts of problems, ranging from scientific problems to business problems to just plain interesting problems, like the search for extra terrestrial life. However, the state of “grid computing” today is a set of utilities and tools that exist to help one build a grid system. There are very few general-purpose complete grid systems, and there are no grid systems that are tailored to the general-purpose management of FEM problems where those problems can be dynamically managed to squeeze the most out of the computer resources.
In addition, once a problem has been created, with the mesh defined, the owner wishing to parallelize a problem usually has to define the pieces of the problem that may be sent to the various compute agents that may (collectively) solve the problem. The initial partitioning of a distributed computing task can be critical, and is often a source of tedium for the user. Thus, given a problem such as analyzing a bone (a femur), the user would be responsible for taking the bone and creating the various collections that would delineate the sub-problem regions for the compute agents that may then solve the problem. This process is tedious and time consuming.
Once a problem is distributed on a grid, balancing the progress of the problem among all its pieces becomes an issue. Given any problem that requires communication between compute nodes to proceed (any interconnected parallel problem), a single slow compute agent can slow down an entire computation. Similarly, a failed node can halt the computation altogether. On a grid, recovery from a failed node presents the same problem as recovery from a node that has become so busy that it is no longer useful. A slightly slower compute agent might be assigned a smaller or “easier” piece to solve. A failed or heavily loaded machine should be replaced. Current grid technology does not provide for such needed load balancing.
Current grid technology resizes problem pieces (referred to as Variable Problem Partitions or VPPs) by moving individual elements (referred to as OPCs) from one VPP to another. This technique is inherently inefficient, as it changes the design of the problem, it causes a recalculation of the problem edges and it can cause a significant increase in communication costs if the problem piece edges “roughen”.
Grid computing is still in its infancy. There are numerous tools available for building various types of grid applications, but as yet, no one size fits all. Although problems solved by grid computing are often very sophisticated, the problem management software today is still quite primitive. Existing grid software manages the movement of problem pieces from machine to machine (or server to machine). However, it does not provide for sophisticated management of the problem pieces, does not account for correlations between problem pieces, does not provide a representation of problem piece requirements, and does not adapt the problem itself to dynamic changes in available computing resources.
A system is needed that uses a simple interface and allows domain experts to use the grid to tackle many of the most challenging and interesting scientific and engineering questions. This system should be able to efficiently partition FEM problems across a large collection of computer resources and manage communication between nodes. This system should also be able to dynamically optimize the complexity of problem pieces to match the changing landscape of compute node capabilities on the grid. Furthermore, this system should be able to partition a spatial problem into any regular or describable irregular configuration. The need for such a system has heretofore remained unsatisfied.
USPTO Backgrounds
USPTO Backgrounds