Symbiotic jobscheduling for a simultaneous mutlithreading processor

By A. Snavely, Dean M. Tullsen. SIGP, 2000

689 citations recorded by the source corpus.

Simultaneous Multithreading machines fetch and execute instructions from multiple instruction streams to increase system utilization and speedup the execution of jobs. When there are more jobs in the system than there is hardware to support simultaneous execution, the operating system scheduler must choose the set of jobs to coscheduleThis paper demonstrates that performance on a hardware multithreaded processor is sensitive to the set of jobs that are coscheduled by the operating system jobscheduler. Thus, the full benefits of SMT hardware can only be achieved if the scheduler is aware of thread interactions. Here, a mechanism is presented that allows the scheduler to significantly raise the performance of SMT architectures. This is done without any advance knowledge of a workload's characteristics, using sampling to identify jobs which run well together.We demonstrate an SMT jobscheduler called SOS. SOS combines an overhead-free sample phase which collects information about various possible schedules, and a symbiosis phase which uses that information to predict which schedule will provide the best performance. We show that a small sample of the possible schedules is sufficient to identify a good schedule quickly. On a system with random job arrivals and departures, response time is improved as much as 17% over a schedule which does not incorporate symbiosis.

Subfields: Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/b05f897f47c785c13fc4763e63d65bebd5e5ffd7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

A case for bufferless routing in on-chip networks (2009, methodology): “We measure system throughput using Weighted-Speedup [49, 13]: where IPC alonei and IPC sharedi are the IPC of application i when running alone (without any interconnection network contention from any other application) and when running with the other applications, respectively.”
ATLAS: A scalable and high-performance scheduling algorithm for multiple memory controllers (2010, methodology): “We measure system throughput using the commonly-employed weighted speedup metric [51], which sums the Instructions Per Cycle (IPC) slowdown experienced by each benchmark compared to when it is run alone for the same number of instructions as it executed in the multi-programmed workload:”
Cooperative Caching for Chip Multiprocessors (2006, methodology): “For the same reason, two other SMT performance metrics using a single-thread execution baseline—weighted speedup (or WS, which is the sum of speedups) [134] and harmonic mean of speedups [98]—are not used.”
Adaptive insertion policies for managing shared caches (2008, background): “The weighted speedup metric indicates reduction in execution time [ 16 ].”
RAIDR: Retention-aware intelligent DRAM refresh (2012, methodology): “We report system performance using the commonly-used weighted speedup metric [44], where each application’s instructions per cycle (IPC) is normalized to its IPC when run-8 ning alone on the same system on the baseline auto-refresh con-ﬁguration at the same temperature, and the weighted speedup of…”
Base-delta-immediate compression: Practical data compression for on-chip caches (2012, methodology): “For multi-programmed workloads we use the weighted speedup [25] as the performance metric: For bandwidth consumption we use BPKI (bytes transferred over bus per thousand instructions [27]).”
Parallelism-Aware Batch Scheduling: Enhancing both Performance and Fairness of Shared DRAM Systems (2008, methodology): “Evaluation Metrics We measure fairness using the unfairness index proposed in [25, together with other threads divided by the memory stall time per instruction it experiences when running alone on the same system: MCPIshared i maxi MemSlowdowni MemSlowdowni = ,Unfairness = MCPIalone minj MemSlowd”
Stall-Time Fair Memory Access Scheduling for Chip Multiprocessors (2007, neutral): “This metric should not be used to evaluate system throughput [28, 15] since even throughput-oriented realistic systems need to consider fairness and ensure forward progress of individual threads.”
Fair cache sharing and partitioning in a chip multiprocessor architecture (2004, background): “Some studies have proposed metrics that, if optimized, balances between throughputand fairness [12, 15 ].”
The evicted-address filter: A unified mechanism to address both cache pollution and thrashing (2012, methodology): “We evaluate system performance using the weighted speedup metric [50], which is shown to correlate with the system throughput [11].”
Thread Cluster Memory Scheduling: Exploiting Differences in Memory Access Behavior (2010, methodology): “We measure system throughput using weighted speedup [21] and fairness using maximum slowdown.”
Tiered-latency DRAM: A low latency and low cost DRAM architecture (2013, methodology): “To measure performance, we use instruction throughput (IPC) for single-core systems and weighted speedup [49] for multi-core systems.”
Addressing shared resource contention in multicore processors via scheduling (2010, methodology): “Symbiotic Jobscheduling [21] is a method for co-scheduling threads on simultaneous multithreading processors (SMT) in a way that minimizes resource contention.”
A case for exploiting subarray-level parallelism (SALP) in DRAM (2012, methodology): “To measure performance, we use instruction throughput for single-core systems and weighted speedup [53] for multicore systems.”
A new memory monitoring scheme for memory-aware scheduling and partitioning (2002, background): “Snavely and Tullsen [14] proposed a scheduling algorithm considering various resource contention for simultaneous multithreading systems.”