SUPERLINEAR SPEED‐UP AND THE HALTING PROBLEM
Paul B. Schneck · Software Practice and Experience · 1986
This paper describes a technique for refuting the claim that ‘new’ algorithms on parallel processing systems with n processors will yield a speed‐up of more than n. The technique uses a round‐robin service approach which is borrowed from that used in automata theory. It is shown that a sequential processor with this service technique can yield a speed‐up of 1/n times that claimed for a parallel processor.