This article considers the application of a primal nested-decomposition method to solve staircase linear programs (SLPs) on distributed-memory, multiple-instruction-multiple-data computers. Due to the coupling that exists among the stages of an SLP, a standard parallel-decompositon algorithm for these problems would allow only a subset of the subproblem processes to overlap with one another at any give time. We propose algorithms that seek to increase the amount of overlap among the processes as well as utilize idle time beneficially. Computational results testing the effectiveness of our algoritms are reported, using a standard set of test problems.