4 ms·

> Surely, for example, multiple processors are no help to TeX. But but but, The STEPS project at http://vpri.org http://vpri.org did find a way ! Basically, e

> Surely, for example, multiple processors are no help to TeX. But but but, The STEPS project at http://vpri.org http://vpri.org did find a way ! Basically, each character is an object, and is placed relatively to the one just before it. Sure, you'd want to wait for the previous character before you place the next one, but you could easily deal with each paragraph separately… I'd like to blame hardware vendors as well, but I think they did their best to provide Moore's law Free Ride to single threaded programming. The first one who don't would be driven out of market. And now we know that parallelism can be applied quite pervasively, it'd be our fault not to do it.

taeric 15y ago
Pretty sure you can't do what you are saying for some layout considerations. For example, how do you layout a paragraph if you don't know whether or not it will be split across a page boundary?
- wmf 15y ago
  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 http://parlab.eecs.berkeley.edu/research/80
- gnosis 15y ago
  I don't really see a problem here. The entire document could be laid out as if the page length was infinite, and then -- depending on desired page length -- the page breaks could be inserted between the appropriate lines. In any case, in a typical document the overwhelming majority of paragraphs won't be affected by page breaks. So their layout could be parallelized regardless of where the page breaks wind up occurring.
  - taeric 15y ago
    When laying out a paragraph near a page boundary, you don't simply insert the page break wherever you want. In fact, depending on whether or not orphaned lines are desired, you may wind up adjusting the inter word spacing of several lines worth of characters. That said, the other poster is likely correct that you can probably just do an optimistic run in parallel across all paragraphs, and then rerun any that are "dirty" from other considerations. In this regard, it is a lot like multiplying two large numbers. There are some parts that are pretty much only done sequentially, but some could likely be guessed or pinned down in parallel. The question remains, how much benefit do you really get from this, over just speeding up the sequential operation? Especially in any layout that has figures or heaven help you columns. A single "dirty" find could likely render all of the parallel work worthless. Best example I could give would be a parallel "adder" adding 9999 to 1111. Since every single digit has a carry, the whole operation winds up being sequential anyway.

taeric 15y ago

Pretty sure you can't do what you are saying for some layout considerations. For example, how do you layout a paragraph if you don't know whether or not it will be split across a page boundary?

wmf 15y ago
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 http://parlab.eecs.berkeley.edu/research/80
gnosis 15y ago
I don't really see a problem here. The entire document could be laid out as if the page length was infinite, and then -- depending on desired page length -- the page breaks could be inserted between the appropriate lines. In any case, in a typical document the overwhelming majority of paragraphs won't be affected by page breaks. So their layout could be parallelized regardless of where the page breaks wind up occurring.
- taeric 15y ago
  When laying out a paragraph near a page boundary, you don't simply insert the page break wherever you want. In fact, depending on whether or not orphaned lines are desired, you may wind up adjusting the inter word spacing of several lines worth of characters. That said, the other poster is likely correct that you can probably just do an optimistic run in parallel across all paragraphs, and then rerun any that are "dirty" from other considerations. In this regard, it is a lot like multiplying two large numbers. There are some parts that are pretty much only done sequentially, but some could likely be guessed or pinned down in parallel. The question remains, how much benefit do you really get from this, over just speeding up the sequential operation? Especially in any layout that has figures or heaven help you columns. A single "dirty" find could likely render all of the parallel work worthless. Best example I could give would be a parallel "adder" adding 9999 to 1111. Since every single digit has a carry, the whole operation winds up being sequential anyway.