Power-efficient DRAM Speculation (PEDS) is a power optimization targeted at broadcast-based shared-memory multiprocessor systems that speculatively access DRAM in parallel with the broadcast snoop. Although speculatively accessing DRAM has the potential performance advantage of overlapping DRAM latency with the snoop, it wastes power for memory requests that obtain data from other processorspsila caches. PEDS takes advantage of information provided by a Region Coherence Array to identify requests that have a high likelihood of obtaining data from another processorpsilas cache, and does not access DRAM speculatively for those requests. By doing so, PEDS eliminates DRAM reads, reduces DRAM power consumption, reduces contention for DRAM resources, and increases the opportunity for DRAM power management. PEDS requires almost no additional hardware in systems that incorporate Region Coherence Arrays. Detailed simulation results show PEDS reduces average DRAM read traffic 28-32%, reduces average DRAM power dissipation 17-22%, and reduces average DRAM energy consumption 16-21%.

Prefetching in shared-memory multiprocessor systems is an increasingly difficult problem. As system designs grow to incorporate larger numbers of faster processors, memory latency and interconnect traffic increase. While aggressive prefetching techniques can mitigate the increasing memory latency, they can harm performance by wasting precious interconnect bandwidth and prematurely accessing shared data, causing state downgrades at remote nodes that force later upgrades.This paper investigates Stealth Prefetching, a new technique that utilizes information from Coarse-Grain Coherence Tracking (CGCT) for prefetching data aggressively, stealthily, and efficiently in a broadcast-based shared-memory multiprocessor system. Stealth Prefetching utilizes CGCT to identify regions of memory that are not shared by other processors, aggressively fetches these lines from DRAM in open-page mode, and moves them close to the processor in anticipation of future references. Our analysis with commercial, scientific, and multiprogrammed workloads show that Stealth Prefetching provides an average speedup of 20% over an aggressive baseline system with conventional prefetching.

To maintain coherence in conventional shared-memory multiprocessor systems, processors first check other processors' caches before obtaining data from memory. This coherence checking adds latency to memory requests and leads to large amounts of interconnect traffic in broadcast-based systems. Our results for a set of commercial, scientific and multiprogrammed workloads show that on average 67% (and up to 94%) of broadcasts are unnecessary. Coarse-grain coherence tracking is a new technique that supplements a conventional coherence mechanism and optimizes the performance of coherence enforcement. The coarse-grain coherence mechanism monitors the coherence status of large regions of memory, and uses that information to avoid unnecessary broadcasts. Coarse-grain coherence tracking is shown to eliminate 55-97% of the unnecessary broadcasts, and improve performance by 8.8% on average (and up to 21.7%).

The problem of testing shared memories for memory coherence and consistency is studied. First, it is proved that detecting violations of coherence in an execution is NP-complete, and it remains NP-complete for a number of restricted instances. This result leads to a proof that all known consistency models are NP-hard to verify. The complexity of verifying consistency models is not a mere consequence of coherence, and verifying sequential consistency remains NP-complete even after coherence has been verified.

The general problem of verifying coherence for shared-memory multiprocessor executions is NP-Complete. Verifying memory consistency models is therefore NP-Hard, because memory consistency models require coherence for some or all operations. However, verifying memory consistency remains NP-Complete for executions known to be coherent.