The multiprocessing of a program has two stages: multithreading of a program and the simultaneous execution of the threads on multiple processors. Multithreading is the partitioning of a program into logically independent parts such that the parts can execute in parallel. A program can be multithreaded and still not achieve multiprocessing if all the threads of the program are executed on a single processor, for example, where only one processor is available. Multiprocessing of a program requires that threads of a multithreaded program execute simultaneously on different processors. Processes are entities that are scheduled by the operating system to run on processors. In a multithreaded program different processes would execute different threads in the program.
Consider an analogy. Suppose a farmer has a field that needs to be plowed. He writes orders for plowing of the field. Plowing the field is 10 days worth of work. If the farmer's orders instruct one worker to plow the field, the orders correspond to a single-threaded program (that is, a program that cannot be multiprocessed). If the farmer makes up ten sets of orders that each instruct one worker to plow 1/10th of the field, then the orders correspond to a multithreaded program.
In the analogy, workers correspond to the processes, tractors with plows correspond to the processors, and the foreman directing the workers corresponds to the operating system. The farmer has already divided the work into ten parts. If the foreman has only a single tractor available and gives a set of orders to a worker each day, plowing of the field will still require ten days. This is like running a multithreaded program on a single processor system. If the foreman has more than one tractor, he has the equivalent of a multiprocessor system. If he assigns several workers to plow simultaneously, he is multiprocessing the work.
The goal of multiprocessing is to reduce the execution time of a program. Execution time is the time between when a program is first submitted for execution and when the program finishes execution. Execution time is contrasted with central processing unit (CPU)-time or processor-time, which is the time that a program executes on a processor. For illustrative purposes, assume that there is only one program running on a multiprocessor system. Assume that program A requires ten hours to execute on a single processor. The CPU time for the program would be ten hours. If the program can be multithreaded into ten equal parts and executed simultaneously on ten different processors, then the execution time of the program will be about one hour.
The CPU time would remain approximately the same (ten hours) since each of the ten threads of the program would execute for one hour on each of ten processors for a total of ten hours. The CPU time would be approximately the same ten hours instead of exactly the same ten hours because there is always a cost or overhead for multiprocessing a program. A multithreaded program will require more instructions than the equivalent single threaded program. The additional instructions are required to start the execution of a thread, to synchronize the execution of a thread with other threads, and to terminate the execution of a thread.
The execution time for program A executing on ten processors will actually always be longer than one hour because of the overhead of multiprocessing as discussed above and because of the time required to schedule additional processors to help in the processing of program A. The time to schedule additional processors to help in the processing of a multithreaded program will be referred to as the gather time. If the gather time for a processor in this example is one second and each processor is gathered serially only once, then the execution time of program A will be one hour and ten seconds. A gather time for a processor of one second when the processors execute a thread that takes a one hour to execute is negligible. If the thread takes only one second to execute, the CPU time in this example would be ten seconds and the execution time would be ten seconds so that multiprocessing in this case would gain nothing and would in fact utilize nine additional processors for no gain. The gather time for processors thus has a direct bearing on the effectiveness of multiprocessing.
In terms of the analogy, assume the foreman has ten tractors and ten workers on the farm. The execution time starts when the foreman gets the orders from the farmer. The foreman must hand out the work assignments to each worker. The time required to make the work assignments is part of the overhead of multiprocessing. If, instead of one worker receiving instructions from the foreman, there are ten workers that must each be given instructions, the overhead is increased by a factor of ten. If handing out the assignments takes one minute for each man and each man will do a full day's worth of plowing, then the field will be plowed in one day and multiprocessing will be a success. If, instead of plowing, the job consists of moving 10 sacks of grain and it takes one minute to hand out the assignments but only one minute to move each sack, then multiprocessing the job would use ten men to no advantage.
If the foreman has no tractors on the farm and has to get them from other sites, then the time required to get each tractor to the farm (the gather time) has to be considered as part of the overhead. If each worker must spend 10 minutes fetching a tractor before he can begin the day's plowing, then multiprocessing is still reasonable. But if each worker has to spend a day to fetch a tractor in order to plow for a day, then multiprocessing is less reasonable.
As the discussion above indicates, a short gather time can make multiprocessing useful. "Short" is a relative term. If gather time is short relative to the amount of time that the gathered processors will spend processing, then multiprocessing is useful. A shorter gather time makes it profitable to multiprocess threads with smaller CPU times.
One method currently used to avoid the problem of a long gather time is to dedicate all the processors (or a fixed number of processors) of a multiprocessor system to the execution of each multithreaded program. Dedicating the processors to one multithreaded program means that the processors are always executing code in the program and do not have to be gathered from the operating system. The code that is executed in the program may be a thread of work or may be a loop in the program that looks for threads of work to execute. The loop that looks for threads of work in the program is referred to as a wait loop. If the processors spend much time in the wait loop, this is not an efficient use of processors. If the processors are an inexpensive resource, this may be acceptable. For a multiprocessor system where each processor is a high performance processor, it may not make economic sense to dedicate processors to a multithreaded program that may only use the processors a fraction of the total time they are available to it.
In terms of the analogy, the foreman can keep ten tractors standing by at the farm during the entire plowing season. If some fields are not ready for plowing, then some tractors wait idly. If the farmer is not paying much for the tractors, this may be acceptable but is hardly optimal.
In a typical Unix.sup.1 system running on tightly-coupled multiprocessors, an additional processor can be gathered by creating a new process with a fork system call. The new process is created so that it can execute an available thread and is commonly referred to as a shared image process. It does not necessarily execute immediately but is scheduled through the normal Unix scheduling mechanism. It is a full context process. Building its context-information takes a significant amount of time. FNT .sup.1 Unix is a registered trademark of AT&T Bell Laboratories.
An article entitled "The Convex C240 Architecture" by Chastain et al. (CH2617-9/88/0000/0321, 1988 IEEE at page 324 et seq.) describes the Convex Automatic Self-Scheduling Processors (ASAP) scheduling mechanism which provides one method for gathering processors. In the ASAP mechanism, an idle CPU (processor) is defined as a CPU which has no process context. The idle CPUs continually poll, searching for a process in need of compute power. A process indicates that it can use additional compute resource by executing a spawn instruction. Normal process scheduling utilizes the ASAP mechanism by having the Unix scheduler request an additional processor. The ASAP mechanism is a hardware implementation that uses the spawn instruction to request all idle CPUs.
An important problem with the ASAP mechanism is a potential for CPUs to respond to a request for additional compute power and find that there is no work to be done because other CPUs have taken all the work. This can waste CPU resources if CPUs spend a significant amount of time being gathered into processes where there is no work. A second problem is that, potentially, all idle CPUs will respond to a single spawn request as opposed to multiple spawn requests. If the same multithreaded program having different threads executes spawn instructions, the first thread to execute the spawn instruction may get all the idle CPUs (which may or may not be needed) and the CPUs would have to return to the idle state before they could respond to the second spawn instruction.
In terms of the analogy, the ASAP mechanism corresponds to having the foreman send up a signal when tractors are needed as opposed to sending workers out to fetch the tractors. An idle worker waits on each tractor, watching for the signal. When they see the signal, they all drive their tractors to the farm. When they get to the farm, they may find that there is not enough work to go around. The workers are idle. This is in contrast to workers who are plowing with the tractors. This distinction is made with the ASAP idle CPUs and with the microprocesses discussed later. If the tractor is being used for plowing on another farm, it could be used to respond to the signal by having the worker on the tractor (worker 1) get off the tractor, and another worker (worker 2) get on the tractor and respond to the signal. The switch of workers is done because worker 1 has orders to plow the current field and has to remember where to start plowing again when the tractor is returned. This part of the analogy is very close to the way an operating system schedules processes (the workers) to processors (the tractors). In other words, a tractor in use requires additional time to disengage from the current job before starting a new one. A feature of the idle CPU and the microprocess is that no time is spent on disengaging from the current job since there is no current job.
U.S. Pat. No. 4,631,674 to Blandy describes the IBM Active Wait mechanism which gathers processors from the operating system and then holds them for some period of time for later use. After a processor is finished executing the thread for which it was requested, it enters a wait loop. While it is in the wait loop, it scans queues for additional work that is ready for execution. The Active Wait mechanism is an effective way of assigning processes already in use by a program.
In the farm analogy, the Active Wait mechanism is concerned with workers that are already at the farm. If the workers are at the farm, they wait there for some period of time before going to other work sites. The advantage being that workers already at the farm can be gathered very quickly.
A method is needed for gathering processors for executing threads from different parts of a multithreaded program. The method needs to be efficient in the sense that a processor can be gathered quickly and that a sufficient number of processors is gathered. The method should also be flexible to allow for different strategies to be used during periods of different system loads.