ABSTRACT
This chapter touches the surface of an important problem: How should jobs be allocated on parallel processors? It considers a computer consisting of a number of processors, memory modules, and a communication network between processors and memory. On such machines, one is often confronted with solving a task composed of many independent subtasks (or jobs) where it is necessary to synchronize the processors after all of the subtasks have been processed. The chapter introduces the useful notions of characteristic maximum and increasing failure rate, and we bring out a correspondence between Chernoff's Theorem and the central limit theorem. The analysis is also based on the notion of the characteristic maximum. This is a good estimate of the expected value of the maximum of a large number of independent random variables. The chapter also introduce this notion, to show how it relates to the distribution of the maximum, and then devotes to methods of obtaining estimates of the characteristic maximum.
