ACM Transactions on Computer Systems · 1993 · 236 citations · 26 references
ComputingComputer EngineeringComputer ScienceOperating SystemsParallel ComputingSchedulingCpu SchedulingDynamic SchedulingMultiprocessor SystemsShared-memory MultiprocessingShared-memory ParallelismTask SchedulingDynamic Job SchedulingMultiprocessor SchedulingParallel Job SchedulingParallel SchedulingScheduling In Multiprocessor SystemsShared MemoryShared Memory MultiprocessorsTask Parallelism In Shared-memory Systems
The study proposes and empirically evaluates a dynamic processor‑scheduling policy for multiprogrammed shared‑memory multiprocessors. The policy dynamically reallocates processors among parallel jobs based on their current parallelism, and is implemented and tested on a Sequent Symmetry multiprocessor using prototype code and diverse parallel applications to assess performance, space‑sharing advantages, and kernel‑application cooperation. Results show that the dynamic policy improves overall performance, fairness, and response time, supporting its adoption in production systems.
We propose and evaluate empirically the performance of a dynamic processor-scheduling policy for multiprogrammed shared-memory multiprocessors. The policy is dynamic in that it reallocates processors from one parallel job to another based on the currently realized parallelism of those jobs. The policy is suitable for implementation in production systems in that: We have evaluated our scheduler and compared it to alternatives using a set of prototype implementations running on a Sequent Symmetry multiprocessor. Using a number of parallel applications with distinct qualitative behaviors, we have both evaluated the policies according to the major criterion of overall performance and examined a number of more general policy issues, including the advantage of “space sharing” over “time sharing” the processors of a multiprocessor, and the importance of cooperation between the kernel and the application in reallocating processors between jobs. We have also compared the policies according to other criteia important in real implementations, in particular, fairness and respone time to short, sequential requests. We conclude that a combination of performance and implementation considerations makes a compelling case for our dynamic scheduling policy.
26
A hierarchical O(N log N) force-calculation algorithm
Josh Barnes, Piet Hut · Nature · 1986 · 3.7K citations
Mean-Value Analysis of Closed Multichain Queuing Networks
M. Reiser, S. S. Lavenberg · Journal of the ACM · 1980 · 1.2K citations · Full text
Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska et al. · ACM Transactions on Computer Systems · 1992 · 432 citations · Full text