Hyper-sweep
Summary
This is a Fortran90 or C callable software library for exhaustively searching a multidimensional (hyper) cube or hyper sphere in arbitrary numbers of dimensions in parallel. It can be used to perform enumerative search of a parameter space with either simple bounds on each parameter (leading to a hyper-cube) or bounds on the norm of the spatial position (leading to a hyper-sphere). It includes an option to perform numerical integration of user-supplied functions through parallelized Monte Carlo integration. In all cases the search and integration operations can be nested over multiple grids, which are re-positioned and refined according to prescribed criteria. Parallelization is invisible to the user and can be performed over an arbitrary number of cores in a cluster with approximately linear scaling in performance. Overall computation cost scales with the time required to evaluate the user supplied optimisation (or integration) function; the number of dimensions, and the grid density of the hyper-cube, or number of samples in the hyper-sphere.
|
An illustration of a nested grid in three dimensions. The program pgs mpi visits each point in the lattice and finds either the maximum or minimum of a user supplied function. The workload is distributed approximately evenly among an arbitrary number of cores in a cluster. |
An example problem would be the minimization of an objective function for a global minimum or maximum evaluated over a fixed lattice. Examples using the source library are included. The key feature of the code is the automatic distribution of work across an arbitrary number of computational cores, which is achieved by using the Hilbert curve.
| Distribution of the b = 5 Hilbert curve across 16 processors. The position of each grid node on the Hilbert curve is used to determine which processor it gets mapped to. |
The level of parameter space discretization is determined by the user but must be a power of 2. In practice exhaustive search becomes prohibitive in dimensions beyond 10. For testing purposes the code can be compiled and run on platforms without MPI installed.
A pdf manual is available here and provides information on installation and usage. A copy of the manual is included in the download package.
Download
The code can be downloaded here. The package includes the above pdf manual and some examples. You will need to register with iEarth prior to download.
The contents of this package is provided under the terms of the GPL licence
Enquires should be directed to the author Malcolm Sambridge.