11 ms·

I agree with everything except for "just as easily". It's trivial to extract memory parallelism from separate instruction streams and heroic to impossible for a

by _yosefk 14y ago

I agree with everything except for "just as easily". It's trivial to extract memory parallelism from separate instruction streams and heroic to impossible for a single stream. Think processing 1000 linked lists sequentially vs processing 4 groups of 250 lists each. Which OOO CPU will parallelize the processing of 4 lists given a program processing 1000 lists serially? Even "rather wimpy" cores - single-issue cores branded as in-order - can issue "outstanding loads" (issue a request, keep executing until the result is needed). It's way way better than nothing but it's also very far from succeeding as consistently as separate instruction streams.

rayiner 14y ago
> I agree with everything except for "just as easily". It's trivial to extract memory parallelism from separate instruction streams and heroic to impossible for a single stream. Think processing 1000 linked lists sequentially vs processing 4 groups of 250 lists each. You're not comparing like with like. Do you have one linked list with 1,000 nodes, or do you have four linked lists with 250 nodes each? Those are two different problems. The latter problem has 4x as much memory parallelism as the former one (and indeed, is probably the pedagogical example of explaining memory parallelism). A single out-of-order CPU with out-of-order memory pipeline can traverse four linked lists in parallel just as easily as four CPU's can do so sequentially. Just keep four cursors and advance each one in a round-robin fashion.
- _yosefk 14y ago
  I specifically said "1000 linked lists" with an unknown amount of nodes in each. "Just keep four cursors" - why four and not N? This involves rather ugly and not quite portable/"scalable" code (different processors can issue different amounts of outstanding memory requests). For a large N, you run out of register names for variables, and register renaming only gets you so far. There are cases when ILP is easier to express than TLP and there are the opposite cases; it's not "just as easy" - in many cases one is much easier than the other. Having to keep multiple cursors is the perfect example when TLP is easier; consider the fact that different lists have different lengths, which a load balancing scheduler can take care of nicely without any programming effort and your single-threaded version will have trouble with.
solarexplorer 14y ago
> It's trivial to extract memory parallelism from separate instruction streams and heroic to impossible for a single stream. That's why the brawny CPUs are multithreaded and come as chip muliprocessors. But if you add too many instruction streams, bandwidth quickly becomes a serious problem. That's why a chip full of wimpy processors is not such a good idea. (except for a few special cases of course) After all, there is a reason people still have brawny cpus in their computers, instead of using the gpu for everything. The cpus have to do all the dirty serial work while the gpus play with their pixels...

by _yosefk 14y ago

rayiner 14y ago

> I agree with everything except for "just as easily". It's trivial to extract memory parallelism from separate instruction streams and heroic to impossible for a single stream. Think processing 1000 linked lists sequentially vs processing 4 groups of 250 lists each. You're not comparing like with like. Do you have one linked list with 1,000 nodes, or do you have four linked lists with 250 nodes each? Those are two different problems. The latter problem has 4x as much memory parallelism as the former one (and indeed, is probably the pedagogical example of explaining memory parallelism). A single out-of-order CPU with out-of-order memory pipeline can traverse four linked lists in parallel just as easily as four CPU's can do so sequentially. Just keep four cursors and advance each one in a round-robin fashion.

_yosefk 14y ago
I specifically said "1000 linked lists" with an unknown amount of nodes in each. "Just keep four cursors" - why four and not N? This involves rather ugly and not quite portable/"scalable" code (different processors can issue different amounts of outstanding memory requests). For a large N, you run out of register names for variables, and register renaming only gets you so far. There are cases when ILP is easier to express than TLP and there are the opposite cases; it's not "just as easy" - in many cases one is much easier than the other. Having to keep multiple cursors is the perfect example when TLP is easier; consider the fact that different lists have different lengths, which a load balancing scheduler can take care of nicely without any programming effort and your single-threaded version will have trouble with.

solarexplorer 14y ago

> It's trivial to extract memory parallelism from separate instruction streams and heroic to impossible for a single stream. That's why the brawny CPUs are multithreaded and come as chip muliprocessors. But if you add too many instruction streams, bandwidth quickly becomes a serious problem. That's why a chip full of wimpy processors is not such a good idea. (except for a few special cases of course) After all, there is a reason people still have brawny cpus in their computers, instead of using the gpu for everything. The cpus have to do all the dirty serial work while the gpus play with their pixels...