Bounds for Certain Multiprocessing Anomalies

In recent years there has been increased interest in t h e s t u d y of the potential a d v a n t a g e s afforded by t h e use of a c o m p u t e r with m a n y processors in parallel. While it is generally t i n e t h a t a set of t a s k s m a y be processed in less time by this t y p e of multiprocessing, it has been pointed out t h a t certain anomalies 1 , 2 m a y occur, even t h o u g h the processors are used in a very " n a t u r a l " w a y (e.g., it can h a p p e n t h a t increasing t h e n u m b e r of processors can increase the time required to complete a given set of tasks). It is t h e purpose of this p a p e r to derive precise b o u n d s on the extent to which these anomalies can affect t h e time required to process a set of tasks, given certain r a t h e r n a t u r a l rules for t h e operation of the multiprocessing system. 1.1 Description of the System L e t us suppose t h a t we are given n identical processing units P t , 1 ^ i ^ n, and a set of t a s k s T = { T, · · · , Tm} to be processed by t h e Pi. We are also given a partial-order* [0,°o). Once a processor P, begins a task T j , it works w i t h o u t i n t e r r u p t i o n on Tj until completion of t h a t t a s k , t a k i n g altogether n(Tj) u n i t s of time. It is also required t h a t if