Different Implementations of VLIW .
|
Prev: The Mark Thorson FAQ: Read all about this LIAR, BULLY, THUG, CYBERSTALKER and HARASSER
Next: The Mark Robert Thorson FAQ: Read all about this LIAR, BULLY, THUG, CYBERSTALKER and HARASSER
From: Nick Maclaren on 6 May 2008 18:08 In article <4820cf61$1(a)darkstar>, eugene(a)cse.ucsc.edu (Eugene Miya) writes: |> |> >Yes. However, that paragraph on its own is misleading - I wasn't |> >referring to TeX, but to the X Windowing System Toolkit and widget |> >sets - the context made that clear. |> |> It's Knuth's challenge. |> If either of you even thinks you can get significant parallelism from TeX, |> show me, and I will forward to DEK. I can assure you that he would be |> amused. I watched as about a 100 people at Stanford back from that |> challenge. |> |> Remember we are looking for a factor of at least 8. I suggest that you try to get a factor of 2 from the X Windowing System Toolkit - the exercise would stretch your mind. Regards, Nick Maclaren.
From: Bernd Paysan on 6 May 2008 07:21 Nick Maclaren wrote: > I spend some months on it, and have looked at TeX. I wouldn't. > I would put it in the garbage. Actually, I think there's a lot of inherent parallelism in the task TeX tries to achieve (typesetting). The way it's implemented however assures that everything is serialized. The same is true for GCC (with less impact for the user, because you can always make -j for more parallelism). -- Bernd Paysan "If you want it done right, you have to do it yourself" http://www.jwdt.com/~paysan/
From: Nick Maclaren on 6 May 2008 07:38 In article <mir5f5-l65.ln1(a)annette.mikron.de>, Bernd Paysan <bernd.paysan(a)gmx.de> writes: |> Nick Maclaren wrote: |> > I spend some months on it, and have looked at TeX. I wouldn't. |> > I would put it in the garbage. |> |> Actually, I think there's a lot of inherent parallelism in the task TeX |> tries to achieve (typesetting). The way it's implemented however assures |> that everything is serialized. The same is true for GCC (with less impact |> for the user, because you can always make -j for more parallelism). Yes. However, that paragraph on its own is misleading - I wasn't referring to TeX, but to the X Windowing System Toolkit and widget sets - the context made that clear. TeX is merely grim, as one would expect from a Pascal-derived source. Regards, Nick Maclaren.
From: Bernd Paysan on 7 May 2008 07:16 Eugene Miya wrote: > It's Knuth's challenge. > If either of you even thinks you can get significant parallelism from TeX, > show me, and I will forward to DEK. I can assure you that he would be > amused. I watched as about a 100 people at Stanford back from that > challenge. I would certainly have to completely rewrite TeX (rebuild from scratch). I'm talking about the task TeX has to do, no the implementation. The implementation is serialized beyond repair. However, there are different ways to achieve parallelism: For a mere factor of 8, a simple filter design would do (using multiple cores): First filter takes TeX source and expands macros. Next filter takes expanded TeX and builds paragraphs out of it. Paragraphs then can be wrapped in parallel (TeX gives each paragraph several tries and chooses the best one). In effect, you can wrap all paragraphs of a single document at once. Next is to combine paragraphs to pages, this needs to serialize again (but for a factor 8, one paragraph at a time is completely sufficient). Ok, then let's assume we want to use VLIW or other vector techniques to get more fine-grain parallelism out of TeX. This requires different data structures. For example kerning: Optimally, we build a matrix of kerning for character A followed by character B (wastes space, because most of the entries are 0). If our text also is placed in an array (instead of a linked list), we can see that adding kerning is a 100% parallel task - there's no interdependency, the limiting factor is just how many accesses we can make to that kerning matrix (random access, but the kerning matrix fits easily into L1 cache). For breaking paragraphs at high speed (and thus high parallelism), we first fold words (or syllables after hyphenating) into single object (reduce data) - high parallelism, O(log(N)) sequential limit. Then we compute fixed and glue width for the sequence of all words in the paragraph, this is a vector operation with a sequential sum part, i.e. we have a O(log(N)) sequential limit in this operation. Then we bisect the paragraphs to find possible line breaks - this is a sequential algorithm, but since we have an array, we don't need to walk through the list while we do the bisection steps. Finally, calculate "badness", and select the best. -- Bernd Paysan "If you want it done right, you have to do it yourself" http://www.jwdt.com/~paysan/
From: Robert Myers on 7 May 2008 14:33
On May 6, 6:36 pm, eug...(a)cse.ucsc.edu (Eugene Miya) wrote: > It's Knuth's challenge. > If either of you even thinks you can get significant parallelism from TeX, > show me, and I will forward to DEK. I can assure you that he would be > amused. I watched as about a 100 people at Stanford back from that > challenge. > Elephant graveyard of naysayers. The beginnings of "computer science" were fun and productive. Since then? Because the first machines weren't parallel, we don't know anything about parallel programming, and as long as we're citing the experts on those first machines, we never will. Time for some productive amnesia. Blank pieces of paper. No name- dropping. Robert. |