Quantum gravity and string theories of fundamental forces can be simulated using models based on dynamically triangulated random surfaces. [27] For example, the two dimensional worldsheet of a one dimensional string can be discretized as an irregular triangular mesh. Calculations involve integrating over all possible worldsheets, which can be approximated by a Monte Carlo sum over a large number of different meshes. These are obtained by making random changes to the positions and connections of nodes in the mesh throughout the calculation using the standard Metropolis algorithm, [22] resulting in a dynamically triangulated random surface. A number of simulations of string theories have been performed using this method. [29]
Random surface models can also be used to simulate systems which have real fluctuating surfaces, such as biological and chemical membranes, lipid bilayers, microemulsions, and phase boundaries. [27, 28] This application has much in common with solving PDEs using irregular, adaptive grids.
Since these problems require a Monte Carlo simulation, it is possible to use independent parallelism, with a different mesh and different random numbers on each processor, and then average the results over processors. This is supported by HPF, and works well as long as the problem size is small enough so that it fits into the memory of a single processor, and the equilibration of the Monte Carlo algorithm is relatively fast. However for large mesh sizes one or both of these constraints will generally be violated, so a data parallel algorithm where the mesh is distributed over processors is necessary.
The triangulated random surface can be represented as a graph. Two major components of the parallel algorithm are graph partitioning to find a good domain decomposition which balances load and minimizes communication, and graph coloring so that neighboring vertices and edges are not updated in parallel, which would invalidate the Monte Carlo procedure.
Due to the dynamic and irregular nature of the problem, efficient parallelization is difficult, and probably not possible on SIMD machines. A dynamic mesh means that even if the domain decomposition is initially optimal, neighboring vertices will move to other processors during the simulation, thus requiring substantial non-local communication. So dynamic redistribution of data is required to minimize communication overhead. This is available in HPF using the REDISTRIBUTE directive.
It is interesting to note that optimization of performance by improving data locality is not limited to distributed memory parallel machines, but is also crucial in sequential computers. Modern RISC microprocessors are so fast that access to external memory has a large overhead, so good performance is only obtained by optimal use of cache memory. This is analogous to the difference in access times between local memory and off-processor memory in a distributed memory parallel computer.
Maintaining data locality can be difficult for irregular problems such as the dynamically triangulated random surface, and requires the equivalent of dynamic domain decomposition for a parallel machine. For the sequential code, this means constantly updating a secondary data structure which holds the data for neighboring points, rather than just accessing that data from irregular sections of the primary array. For the sequential random surface code, optimizing the data locality in this way gave substantial performance enhancements, up to a factor of 2 for the Intel i860 processor, which has a small cache. [30] The program performs much better on more modern processors with large cache memory.