Multiprocessor simulation: Achieving accuracy, efficiency, and flexibility

Many studies of novel parallel algorithms and multiprocessor systems rely on software simulation. Unfortunately, it is difficult to design simulators that achieve both accuracy and efficiency while maintaining the flexibility to support a wide range of studies. We propose techniques to improve the accuracy, efficiency, and flexibility of multiprocessor simulation systems.; We begin by presenting Tango, a general simulation framework. Tango compiles the application into a "pay-for-what-you-need" system that is customized to efficiently meet the accuracy requirements of individual experiments. Users may configure Tango to use execution-driven simulation to accurately simulate nondeterministic programs. Flexibility is extended to the memory system by allowing users to easily incorporate new memory system simulators.; Memory system simulation is often key to accuracy and efficiency. Therefore, we further improve simulation by first understanding how memory systems impact program performance, and then making effective simplifications to our memory models. We identify dimensions of parallel program execution, and measure the variability in reference characteristics across these dimensions in several programs. Because programs synchronize and have nonuniform reference characteristics, their performance is sensitive to not only average memory latency, but also variability in memory latencies. We use simulation to demonstrate this sensitivity, and show that obtaining accurate results when simulating parallel programs requires memory models to incorporate any significant memory latency variabilities across program computational dimensions.; We propose designing simulators that avoid emulating the caching status of data and instead model the impact of the memory system on program performance. We demonstrate this approach through the design of three example simulators that all gain efficiency by replacing full simulation of caches with the use of an estimated miss rate. Measurements using benchmarks are made to compare speedup and synchronization wait time predictions of our simulators with those from a traditional memory system simulator. While all three example simulators provide excellent program speedup predictions, the simulators differ in the accuracy of synchronization wait time predictions. For our benchmarks, the simulators are up to 16 to 60 times faster than traditional cache memory simulators, and they use up to 15 to 600 times less memory.