Scheduling algorithms with bus bandwidth considerations for SMPs
Authors:
- C.D. AntonopoulosCAC.D. Antonopoulos
- D.S. NikolopoulosDND.S. Nikolopoulos
- T.S. PapatheodorouTPT.S. Papatheodorou
- 1 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01903918,p. 547-554
Abstract
The bus that connects processors to memory is known to be a major architectural bottleneck in SMPs. However, both software and scheduling policies for these systems generally focus on memory hierarchy optimizations and do not address the bus bandwidth limitations directly. We first present experimental results which indicate that bus saturation can cause an up to almost three-fold slowdown to applications. Motivated by these results, we introduce two scheduling policies that take into account the bus bandwidth consumption of applications. The necessary information is provided by performance monitoring counters which are present in all modern processors. Our algorithms organize jobs so that processes with high-bandwidth and low-bandwidth demands are co-scheduled to improve bus bandwidth utilization without saturating the bus. We found that our scheduler is effective with applications of varying bandwidth requirements, from very low to close to the limit of saturation. We also tuned our scheduler for robustness in the presence of bursts of high bus bandwidth consumption from individual jobs. The new scheduling policies improve system throughput by up to 68% (26% in average) in comparison with the standard Linux schedulerKeywords
This publication has 12 references indexed in Scilit:
- Scheduling algorithms with bus bandwidth considerations for SMPs2003
- The SPLASH-2 programs: characterization and methodological considerations2002
- Predicting performance on SMPs. A case study: the SGI Power Challenge2002
- Analytical cache models with applications to cache partitioning2001
- Performance analysis using the MIPS R10000 performance counters1996
- Evaluating the Performance of Cache-Affinity Scheduling in Shared-Memory MultiprocessorsJournal of Parallel and Distributed Computing, 1995
- A dynamic processor allocation policy for multiprogrammed shared-memory multiprocessorsACM Transactions on Computer Systems, 1993
- Using processor-cache affinity information in shared-memory multiprocessor schedulingIEEE Transactions on Parallel and Distributed Systems, 1993
- The implications of cache affinity on processor scheduling for multiprogrammed, shared memory multiprocessors1991
- Process control and scheduling issues for multiprogrammed shared-memory multiprocessors1989