A BISTABILITY THROUGHPUT PHENOMENON IN A SHARED-MEMORY MIMD MACHINE

This paper examines a previously unanalyzed bistability phenomenon wit h respect to the number of threads that are doing useful work. This ph enomenon is illustrated by a single work queue on a shared-memory mach ine. An analysis of designs that use two separate memory accesses to l ock and unlock critical sections (split transaction) and that employ a first come/first serve queuing mechanism for shared-memory locations is presented. A bistability in the number of threads working, brought about by these conditions, is analyzed and experimentally demonstrated . A simple analysis is presented which predicts the throughput at a cr itical section of code as a function of the number of applied threads. The study concludes that the mean size of the work items that can be executed in parallel without the possibility of stalling is proportion al to the square of the number of threads applied.