Abstract
Spinning, or busy waiting, is commonly employed in parallel processors when
threads of execution must wait for some event, such as synchonization with
another thread. Because spinning is purely overhead, it is detrimental to both
user response time and system throughput.
In the paper we study how spinning is affected by two environmental factors,
multiprogramming and data-dependent execution times, and how the choice of
scheduling discipline can be used to reduce the amount of spinning in each
case. Both evironmental factors increase the variation in delay until the
awaited event occurs. In the case of multiprogramming, the thread that will
eventually generate the event must compete with uncertain number of other
threads for processors. In the case of data-dependent behavior, the delay
until the event occurs may depend strongly on the data presented at runtime.
We are interested in both the extent to which spin times increase over a simple
baseline environment when multiprogramming or data-dependency is intorduced and
how this can be reduced through scheduling. The scheduling disciplines we
examine are independent of the semantics of the parallel applications. They are
thus applicable to the parallel solution of a wide variety of problems and to
alternative approaches to solving any single problem independently of algorithm
employed.
Our analysis is conducted using simple, abstract models of parallel hardware and
software. We investigate how software models, one representing the archetypical
construct of fork/join rendezvous and the other mutual exclusion using a lock.
Our hardware model is most naturally applied to shared memory multiprocessors,
since we assume that each thread is capable of running on many different processors
during its execution with negligible penalty. both simulation and exact analytic
techniques are used to obtain performance results.
