Load balancing across a highly heterogeneous processor cluster using file status probes

Ray tracing for Kirchhoff migration is an "embarrassingly parallel" operation, and so can be distributed across a cluster of workstations or personal computers. However, since the computation time associated with individual rays varies with the length of a ray and with the complexity of the velocity model and processors can have widely different computation speeds, load balancing (and hence computational efficiency) across a heterogeneous cluster of processors is a significant problem. Load balancing operations are traditionally implemented by the operating system outside of the program to be executed, and generally require a priori knowledge of the number and the types of processors to be used. We develop an alternative load balancing scheme that is implemented by UNIX Network File System functions for interrogating the existence of files in a working directory from within a running program and so requires no specialized algorithms for monitoring job flow, nor a priori knowledge of the number or types of processors that are participating in the job execution. Processors can be added or removed at any time during the job execution, and the system is crash-proof in the sense that a job will successfully complete as long as at least one processor remains running; there is no master node, so no individual node is indispensable. These ideas are successfully applied to ray tracing for 3-D prestack Kirchhoff depth migration of a field ground-penetrating radar data set from the Ferron Sandstone in east-central Utah. (C) 2002 Elsevier Science Ltd. All rights reserved.