Next: Results with Multithreading Up: Alternative Latency-Hiding Techniques Previous: Relaxed Memory Consistency


Although relaxed consistency models are effective at eliminating write latency, they do not address the problem of read latency. While prefetching is one technique for hiding read latency, another technique is for the processor to support multiple hardware contexts [85][73][39][36][3] (also known as multithreading). As we mentioned earlier in Section , multithreading has two advantages over prefetching. First, it can handle arbitrarily complex access patterns-even cases where it is impossible to predict the accesses ahead of time (and therefore prefetching cannot succeed). This is because multithreading simply reacts to misses once they occur, rather than attempting to predict them. Multithreading tolerates latency by attempting to overlap the latency of one context with the computation of other concurrent contexts. The second advantage of multithreading is that it requires no software support (assuming the code is already parallelized), which as we mentioned in the previous section is only an advantage if the user is unwilling or unable to recompile old code. Multithreading has three limitations: (i) it relies on additional concurrency within an application, which may not exist; (ii) some amount of time is lost when switching between contexts; and (iii) to minimize context-switching overheads, a significant amount of hardware support is necessary. In this section, we will evaluate multithreading and explore its interactions with software-controlled prefetching.

The performance improvement offered by multithreading depends on several factors. First, there is the number of contexts. With more contexts available, the processor is less likely to be out of ready-to-run contexts. However, the number of contexts is constrained by hardware costs and available parallelism in the application. Previous studies have shown that given processor caches, the interval between long-latency operations (i.e. cache misses) becomes fairly large, allowing just a handful of contexts to hide most of the latency [85]. The second factor is the context switch overhead. If the overhead is a sizable fraction of the typical run lengths (time between misses), a significant fraction of time may be wasted switching contexts. Shorter context switch times, however, require a more complex processor. Thirdly, the performance depends on the application behavior. Applications with clustered misses and irregular miss latencies will make it difficult to completely overlap computation of one context with memory accesses of other contexts. Multithreading processors will thus achieve a lower processor utilization on these programs than on applications with more regular miss behavior. Lastly, multiple contexts themselves affect the performance of the memory subsystem. The different contexts share a single processor cache and can interfere with each other, both constructively (by effectively prefetching another context's working set) and destructively (by displacing another context's working set). Also, as is the case with release consistency and prefetching, the memory system is more heavily loaded by multithreading, and thus latencies may increase.

In this study, we use processors with two and four contexts. We do not consider more contexts per processor because 16 4-context processors require 64 parallel threads and some of our applications do not achieve very good speedup with that many threads. We use two different context switch overheads: 4 and 16 cycles. A four-cycle context switch overhead corresponds to flushing/loading a short RISC pipeline when switching to the new instruction stream. An overhead of sixteen cycles corresponds to a less aggressive implementation. In our study, we include additional buffers to avoid thrashing and deadlock when two contexts try to read distinct memory lines that map to the same cache line. All of these experiments assume an RC model.

Next: Results with Multithreading Up: Alternative Latency-Hiding Techniques Previous: Relaxed Memory Consistency

Sat Jun 25 15:13:04 PDT 1994