An optimal asynchronous scheduling algorithm for software cache consistency
Authors:
- BreternitzBRBreternitz
- Michael LaiMLMichael Lai
- 1 January 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, 502-511
Abstract
We present a linear time algorithm for scheduling iterations of a loop that has no loop-carried dependences. The algorithm is optimal in the sense that any p consecutive iterations in the schedule can be executed simultaneously without any possibility of false sharing, where p is the number of processors, and the algorithm uses at most two wait synchronizations per iteration. Our algorithm is asynchronous in the sense that it allows the loop iterations to be scheduled greedily so that no processor will ever be kept idle if it could be safely executing an iteration. This property makes our algorithm superior to a "barrier" type algorithm, in which barrier synchronizations are used instead of pairwise signal-wait synchronizations.Keywords
This publication has 7 references indexed in Scilit:
- Scheduling time-critical instructions on RISC machinesACM Transactions on Programming Languages and Systems, 1993
- Characterizing the caching and synchronization performance of a multiprocessor operating system1992
- Automatic software cache coherence through vectorization1992
- Implementation and performance of Munin1991
- A data locality optimizing algorithm1991
- Scheduling expressions on a pipelined processor with a maximal delay of one cycleACM Transactions on Programming Languages and Systems, 1989
- A New Solution to Coherence Problems in Multicache SystemsIEEE Transactions on Computers, 1978