A statistical approach to contention modeling for high-level heterogeneous multiprocessor simulation

Single chip systems featuring multiple heterogeneous processors and a variety of communication and memory architectures have emerged to satisfy the demand for networking, handheld computing, and other custom devices. The complex interactions between applications, schedulers, and processor resources, along with the resulting contention delays for shared busses and memories, are the chief limitation against raising the modeling abstraction level above the clock cycle. Without raising the simulation abstraction level, multiprocessor simulations are slow to build and execute, severely limiting the number of design iterations that can be considered, thus restricting the design space that can be explored.; This work introduces a new level of design which we call the Stochastic Contention Level (SCL). Instead of considering shared resource accesses at the clock cycle granularity, SCL simulations operate on blocks that are thousands to millions of clock cycles long, summarizing the stochastic behavior of large groups of shared resource accesses throughout the time period. The SCL idea is enabled by three key contributions: merging of an analytical stochastic model with discrete event simulation, the parameterization of shared resource access patterns used for contention modeling, and the method for predicting when to retrain the contention model during the design exploration process.; The first contribution of the SCL design is its integration of a purely analytical stochastic model within a discrete event simulation framework. By merging these two historically independent modeling techniques, we develop a novel simulation technique that does not rely on the clock cycle abstraction to capture performance impacts of contention. Unlike the previous analytical and statistical simulation methods that capture average performance over time, the SCL simulation strategy identifies time-related contention bottlenecks within the system and can capture system response time to arriving jobs and events.; Central to the realization of the SCL design is the parameterization of shared resource access patterns in the form of access attributes , defining a statistical regression relationship between shared resource access patterns and the resulting contention. By sampling contention information from a short cycle accurate simulation, access attributes train the statistical contention model specifically for the control flow behavior of the currently executing applications. Applying the trained model to a high-level event-based simulation results in significant performance advantages; heterogeneous multiprocessor systems can be simulated on average 40X faster than with cycle accurate simulators with accuracy penalties of less than 1%.; Another contribution of the SCL approach is the Error Prediction Model (EPM), which is a regression model quantifying the contention model sensitivity to various system changes, providing the ability to predict statistical model error to within an average of 5%. Using the EPM, the designer can determine the impact of the design change on model error, significantly decreasing the need for statistical model retraining during the design exploration process. The EPM can operate with the data collected directly from the high-level simulation and does not need detailed cycle accurate simulation in order to make good retraining recommendations.; The SCL approach is applied for a design exploration process of a personal digital assistant system. The PDA example features multiple concurrent applications vying for shared memory, where the designer is tasked with reducing the overall system response time by adding/subtracting processors, adjusting shared bus speed, or adding local memories. By raising the abstraction level of contention modeling, the SCL design approach reduced design exploration time of the PDA example from over a week to only several hours. This significant increase in simulation performance enables more design ite...