The schedule parallel programming package with recycling job queues and iterated dependency graphs
Floyd B. Hanson, D. C. Sorensen · Concurrency Practice and Experience · 1990
Abstract The SCHEDULE parallel programming package has been modified so that many more total processes may be spawned as long as the number of currently active processes satisfy the former limits of the package rather than the cumulative total number. This has been accomplished principally by changing the queueing system for both the job parameter queue and the ready jobs queue. The original linear queues are converted to circular queues, in that finished places in the queues are reused for new jobs and that the physical end of the queue is logically connected to the physical beginning of the queue. Two additional features facilitate the change in queues. The first is the implementation of a third queue, a free list, which keeps a list of the currently free slots on the job parameter queue. The second new feature is the use of SCHEDULE generated job tags rather than user‐generated job tags within the package. The user program now gets a job tag number from SCHEDULE with a subroutine call. Another improvement permits the iteration of dependency graphs, with minimal restoration of dependency data. This improvement facilitates the application of the SCHEDULE package to iterations and time‐stepping problems, by saving and reusing the iterated part of the dependency graph. This feature can result in a significant reduction in the number of newly spawned processes that would otherwise be needed for iterations.