4 ms·

I think you're referring to the following paragraph: One fundamental fact on modern hardware is that data cache locality is good, and not being in the cache su

by vog 16y ago

I think you're referring to the following paragraph: One fundamental fact on modern hardware is that data cache locality is good, and not being in the cache sucks. This is not likely to change. However, this did not happen to please the "two dominant C/C++ compilers". The reason is much more fundamental: One of the most expensive parts of the hardware is memory, and fast memory is a lot more expensive to produce than slower memory. So we have the choice between using the same (and thus slow) memory throughout the system, or combining different kinds of memory so that at software has at least the _chance_ to run faster. This is a fundamental issue, and the only thing you can do is trying to find the optimal share for each kind of memory. But no matter how well you choose: software will only be able to exploit this if it is designed for locality. If you can fix that (i. e. if you can find a cheap way to produce gigabytes of fast memory that makes chaches obsolete) the current compilers won't stop you from exploiting it: The code that is optimized for locality will still run as fast, and the code that can't be optimized for locality will run orders of magnitudes faster. So we aren't in a local optimum at all. You can still optimize further "just" by producing faster and cheaper hardware.

kragen 16y ago
One of the most expensive parts of the hardware is memory, and fast memory is a lot more expensive to produce than slower memory. So we have the choice between using the same (and thus slow) memory throughout the system, or combining different kinds of memory so that at software has at least the chance to run faster. This is a fundamental issue, and the only thing you can do is trying to find the optimal share for each kind of memory. Although all modern high-performance (edit: I mean non-embedded-microcontroller) computers work this way, it's not the only possible way. The Tera MTA takes a different, cacheless approach. First, the problem with modern RAM in desktop machines is not that it sucks at bandwidth. You can get your bandwidth arbitrarily high by multibanking. Multibanking requires more buses or point-to-point links, but that's a tolerable cost. The problem with modern RAM is that it sucks at latency, compared to what the CPU would like. Well, what do you do about latency? You make your requests earlier, and make sure you have other things to do in the meantime, when they get back. The Tera did this by having 128 sets of registers – 128 hardware threads — and switching to the next thread on every cycle. That means that, if all the thread slots were full, every thread only executed an instruction every 128 cycles, which is plenty of time to hide the latency of a slow memory fetch, as long as the memory bandwidth was adequate. So basically every thread gets to pretend that it's running on a machine with zero-latency RAM — memory that's as fast as the registers. And pointer-chasing becomes as fast as looping over an array. There are some other advantages to this design. Pipelining logic is very simple, because unless your pipeline gets insanely deep, you never have two instructions in the pipeline from the same thread, so you don't have register hazards. (Cache is still beneficial in such a design, since it reduces the bandwidth that the links to main memory need to support. But the Tera didn't use it.) I don't really understand why the Tera MTA failed in the market, and I suspect the problems were commercial rather than technical — customers had to take a big risk by porting their software to an unproven HPC platform, a platform whose performance characteristics were completely unlike anything else in the market (and unlike anything you can buy today). So customer uptake was insufficient to provide the cash flow needed to keep updating the design to keep up with Intel and AMD. The technical reason such a design might fail would be if the silicon resources needed to support an entirely independent core were comparable to the silicon resources needed to support a hardware thread. Consider the GreenArrays GA144 chip: 144 independent cores, each with a tiny amount of independent RAM, on the same chip. Such a chip will be at least as fast as a chip with 144 independent register sets, but a single execution pipeline — in the worst case, it's bottlenecked on getting data out of RAM, and only one of its cores is usable, making it just as fast, while in the best case, it runs 144 times as fast. So a chip with 144 register sets needs to be cheaper — i.e. smaller — than the GA144. (Well, or easier to program, but presumably you can use more mainstream multicore chips to prove the example instead.)
- ramchip 16y ago
  Isn't there a much simpler reason - that programs are generally single-threaded? I imagine it would take a lot of work to port basic tools like a web browser to such an architecture without it running much slower. A lot of applications do little parallelizable number-crunching, but a lot of branching and sequential operations. How could you make parsing XML or HTML fast on this? What about a text processor or a compiler?
  - kragen 16y ago
    It's true, if Intel could make a single processor core that went eight times as fast on single-threaded code, they would do that instead of making eight-core chips, unless the cost difference was horrific. But they can't, so if you want your code to go faster, you have to find a way to parallelize it. This started happening in earnest about 20 years ago in the supercomputer market, which is where the Tera was sold. About 10 years ago, it started happening in desktop CPUs (check out Herb Sutter's article about "the end of the free lunch") and now it's starting to happen in embedded microcontrollers, with the Parallax Propeller and the GreenArrays chips. As it happens, the Tera didn't lose to faster single-threaded supercomputer CPUs. By the time the MTA came out, even the most stalwart defenders of the fast-single-threaded-performance approach, like the Cray SV1 and the NEC SX-5, had succumbed to the necessity of CPU parallelism. But the approach that was taking over the supercomputer market at the time was actually far more parallel, and far more difficult to program efficiently --- NUMA machines and then Beowulfs. So that's why I don't think it was single-threaded programs that made the Tera fail in the supercomputer market. The question of how to meaningfully parallelize XML and HTML parsing, compilation, text processing in general, and web browsers are very interesting indeed. It's not obvious how to do it, but it might turn out to be tractable. A group at Berkeley was doing some research on it in 2007 and 2008: http://www.eecs.berkeley.edu/~lmeyerov/projects/pbrowser/ http://www.eecs.berkeley.edu/~lmeyerov/projects/pbrowser/
    - ramchip 16y ago
      My point was not aimed at the Tera specifically, but rather at this architecture as a solution to the memory problem in general. As you say, supercomputers have been using multi-threaded code for a long time now, so it's not a technical problem for this case, but it can be for the kind of applications 'regular users' may need. Thanks for the references. I'm in embedded systems but I hadn't heard of the Parallax Propeller before, it's an interesting architecture.
rayiner 16y ago
There is not a fundamental conflict between GC and cache generally. The conflict is with how caches are implemented in most CPUs. Consider a simple generational collector with a nursery of N cache lines. The allocator will bump allocate into LINE_0, LINE_1... until LINE_N, and then copy all survivors into the mature generation. When it starts allocating again, it will start at LINE_0. Ie: it will touch at least N cache lines before ever coming back to any given cache line. If N > the size of the cache, each allocation will involve a cache miss. Each time the allocator allocates into a cache line, it will have been evicted already, and will need to be brought into the cache before it is written to. The key observation here is that you're dealing with an artificial W-W dependency, not a real R-W dependency. When the allocator allocates into a cache line, it doesn't care what the data already in that cache line is! The cache line doesn't need to be brought in from memory because it is garbage and will be overwritten completely. There are lots of solutions to the problem. At every allocation the allocator could simply issue a prefetch for the next line, because it knows it will need it soon. Or, you could have an instruction that simply blows away a cache line, marking it cached+dirty in the coherence protocol without generating a main memory access. In fact, I'm not sure that modern CPUs don't detect this condition in their write buffers already. Something like Bulldozer's write coalescing cache could certainly do this. Aside from this issue, generational GC's are very cache friendly. Collection inherently compacts memory, and the order of collecting tends to bring objects onto the same pages and sometimes the same cache lines as the objects that refer to them. As an aside, the other big cache-thrashing process, marking, can also be made cache friendly on modern architectures. If your CPU has SMT, you can run the marker in a concurrent thread. It can sit there take advantage of the available memory parallelism that most programs leave on the table.

by vog 16y ago

kragen 16y ago

One of the most expensive parts of the hardware is memory, and fast memory is a lot more expensive to produce than slower memory. So we have the choice between using the same (and thus slow) memory throughout the system, or combining different kinds of memory so that at software has at least the chance to run faster. This is a fundamental issue, and the only thing you can do is trying to find the optimal share for each kind of memory. Although all modern high-performance (edit: I mean non-embedded-microcontroller) computers work this way, it's not the only possible way. The Tera MTA takes a different, cacheless approach. First, the problem with modern RAM in desktop machines is not that it sucks at bandwidth. You can get your bandwidth arbitrarily high by multibanking. Multibanking requires more buses or point-to-point links, but that's a tolerable cost. The problem with modern RAM is that it sucks at latency, compared to what the CPU would like. Well, what do you do about latency? You make your requests earlier, and make sure you have other things to do in the meantime, when they get back. The Tera did this by having 128 sets of registers – 128 hardware threads — and switching to the next thread on every cycle. That means that, if all the thread slots were full, every thread only executed an instruction every 128 cycles, which is plenty of time to hide the latency of a slow memory fetch, as long as the memory bandwidth was adequate. So basically every thread gets to pretend that it's running on a machine with zero-latency RAM — memory that's as fast as the registers. And pointer-chasing becomes as fast as looping over an array. There are some other advantages to this design. Pipelining logic is very simple, because unless your pipeline gets insanely deep, you never have two instructions in the pipeline from the same thread, so you don't have register hazards. (Cache is still beneficial in such a design, since it reduces the bandwidth that the links to main memory need to support. But the Tera didn't use it.) I don't really understand why the Tera MTA failed in the market, and I suspect the problems were commercial rather than technical — customers had to take a big risk by porting their software to an unproven HPC platform, a platform whose performance characteristics were completely unlike anything else in the market (and unlike anything you can buy today). So customer uptake was insufficient to provide the cash flow needed to keep updating the design to keep up with Intel and AMD. The technical reason such a design might fail would be if the silicon resources needed to support an entirely independent core were comparable to the silicon resources needed to support a hardware thread. Consider the GreenArrays GA144 chip: 144 independent cores, each with a tiny amount of independent RAM, on the same chip. Such a chip will be at least as fast as a chip with 144 independent register sets, but a single execution pipeline — in the worst case, it's bottlenecked on getting data out of RAM, and only one of its cores is usable, making it just as fast, while in the best case, it runs 144 times as fast. So a chip with 144 register sets needs to be cheaper — i.e. smaller — than the GA144. (Well, or easier to program, but presumably you can use more mainstream multicore chips to prove the example instead.)

ramchip 16y ago
Isn't there a much simpler reason - that programs are generally single-threaded? I imagine it would take a lot of work to port basic tools like a web browser to such an architecture without it running much slower. A lot of applications do little parallelizable number-crunching, but a lot of branching and sequential operations. How could you make parsing XML or HTML fast on this? What about a text processor or a compiler?
- kragen 16y ago
  It's true, if Intel could make a single processor core that went eight times as fast on single-threaded code, they would do that instead of making eight-core chips, unless the cost difference was horrific. But they can't, so if you want your code to go faster, you have to find a way to parallelize it. This started happening in earnest about 20 years ago in the supercomputer market, which is where the Tera was sold. About 10 years ago, it started happening in desktop CPUs (check out Herb Sutter's article about "the end of the free lunch") and now it's starting to happen in embedded microcontrollers, with the Parallax Propeller and the GreenArrays chips. As it happens, the Tera didn't lose to faster single-threaded supercomputer CPUs. By the time the MTA came out, even the most stalwart defenders of the fast-single-threaded-performance approach, like the Cray SV1 and the NEC SX-5, had succumbed to the necessity of CPU parallelism. But the approach that was taking over the supercomputer market at the time was actually far more parallel, and far more difficult to program efficiently --- NUMA machines and then Beowulfs. So that's why I don't think it was single-threaded programs that made the Tera fail in the supercomputer market. The question of how to meaningfully parallelize XML and HTML parsing, compilation, text processing in general, and web browsers are very interesting indeed. It's not obvious how to do it, but it might turn out to be tractable. A group at Berkeley was doing some research on it in 2007 and 2008: http://www.eecs.berkeley.edu/~lmeyerov/projects/pbrowser/ http://www.eecs.berkeley.edu/~lmeyerov/projects/pbrowser/
  - ramchip 16y ago
    My point was not aimed at the Tera specifically, but rather at this architecture as a solution to the memory problem in general. As you say, supercomputers have been using multi-threaded code for a long time now, so it's not a technical problem for this case, but it can be for the kind of applications 'regular users' may need. Thanks for the references. I'm in embedded systems but I hadn't heard of the Parallax Propeller before, it's an interesting architecture.

rayiner 16y ago

There is not a fundamental conflict between GC and cache generally. The conflict is with how caches are implemented in most CPUs. Consider a simple generational collector with a nursery of N cache lines. The allocator will bump allocate into LINE_0, LINE_1... until LINE_N, and then copy all survivors into the mature generation. When it starts allocating again, it will start at LINE_0. Ie: it will touch at least N cache lines before ever coming back to any given cache line. If N > the size of the cache, each allocation will involve a cache miss. Each time the allocator allocates into a cache line, it will have been evicted already, and will need to be brought into the cache before it is written to. The key observation here is that you're dealing with an artificial W-W dependency, not a real R-W dependency. When the allocator allocates into a cache line, it doesn't care what the data already in that cache line is! The cache line doesn't need to be brought in from memory because it is garbage and will be overwritten completely. There are lots of solutions to the problem. At every allocation the allocator could simply issue a prefetch for the next line, because it knows it will need it soon. Or, you could have an instruction that simply blows away a cache line, marking it cached+dirty in the coherence protocol without generating a main memory access. In fact, I'm not sure that modern CPUs don't detect this condition in their write buffers already. Something like Bulldozer's write coalescing cache could certainly do this. Aside from this issue, generational GC's are very cache friendly. Collection inherently compacts memory, and the order of collecting tends to bring objects onto the same pages and sometimes the same cache lines as the objects that refer to them. As an aside, the other big cache-thrashing process, marking, can also be made cache friendly on modern architectures. If your CPU has SMT, you can run the marker in a concurrent thread. It can sit there take advantage of the available memory parallelism that most programs leave on the table.