It ends up being iterative. First you layout every paragraph in parallel, then layout the paragraphs on the page, then re-layout any paragraph that needs to be split, etc.

Some people are working on parallelizing HTML layout, so the same techniques should be applicable to TeX. http://parlab.eecs.berkeley.edu/research/80