The split-level relaxation technique is analyzed in a parallel processing framework. It is shown that there is much parallelism inherent in the algorithm that can be exploited. This has been confirmed by implementation of the algorithm on an actual multiprocessor. Although the results are good, the implementation can be made more efficient. The use of multiple queues instead of a centralized queue can reduce memory contention, particularly in large multiprocessors. An asynchronous implementation can also improve the performance.