The program use the bisection algorithm for computing the eigenvalues of a symmetric tridiagonal matrix. The application is essentially a search problem.
A symmetric tridiagonal N by N real matrix is known to have N real eigenvalues and it is easy to find an initial range on the real line containing all eigenvalues. Then, given a real number x, it is possible to calculate how many of the N eigenvalues are less than x. This primitive can be used to successively subdivide the real line and locate all eigenvalues to arbitrary precision.
A parallel implementation of bisection can use a static subdivision of the initial range, but this has poor parallel efficiency if the eigenvalues are clustered, because the work load is not balanced [DDR94]. A solution is to use a task queue with load balancing for the scheduling structure. Because our machine target is now a distributed memory multiprocessor, locality is a more obvious concern, but for bisection, the tridiagonal matrix is relatively small and can be statically replicated, so the only data associated with each task is the endpoints of their interval. A simple randomized scheduler sends each task to a random processor upon insertion. This scheduling structure is called RandQue in Multipol; it has poor locality properties if there is an advantage to executing tasks on the processor that created them, but is adequate for the bisection algorithm [CRY94].
The intervals stored in the RandQue act as the approximate solution as well as the scheduling structure. As the intervals shrink, the approximation improves until a solution of the desired accuracy is obtained. We will observe this phenomenon of a single data structure playing both roles in one other application, the Tripuzzle.