ACM SIGPLAN Notices · 2000 · 544 citations · 26 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureOperating SystemsSchedulingCpu SchedulingJob SchedulingParallel ArchitecturesParallel Computer ArchitectureTask SchedulingHardware SchedulingMultithreadingResponse TimeRuntime SchedulingScheduler DesignScheduling AlgorithmsScheduling In Multiprocessor SystemsThread Scheduling
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.
26
A Proof for the Queuing Formula: <i>L</i> = λ<i>W</i>
John D. C. Little · Operations Research · 1961 · 2.7K citations
Dean M. Tullsen, Susan J. Eggers, Henry M. Levy · 1995 · 1.4K citations · Full text
Dennis M. Ritchie, Ken Thompson · Communications of the ACM · 1983 · 970 citations
Dennis M. Ritchie, Ken Thompson · Communications of the ACM · 1974 · 819 citations · Full text
Dean M. Tullsen, Susan J. Eggers, Joel Emer et al. · 1996 · 782 citations