Computers typically operate by having a processor execute a program. The program is represented using a sequence of instructions that may be executed by the processor. In order to improve processing speed, multi-processor computing systems are in operation. Such multi-processor systems may have as few as two processors, but could also have numerous processors.
By adding a second processor to a computing system, the system is theoretically twice as powerful and can perform double the computations. In a perfect world, the actual performance of a computing system would scale linearly with the number of processors. Unfortunately, this is typically not the case as there are other bottlenecks within the system that limit the performance increase with each additional processor.
One such bottleneck is in the program itself. In order for a program to take advantage of multiple processors, it should be able to execute multiple processes in parallel. If a program is not written in such a way to take advantage of multiple processors, it will generally only execute on a single processor resulting in any additional processors simply idling rather than performing actual work.
If a programmer knows the number of processors available to execute the program, the programmer can write the program in such a way to take advantage of the known processors. One example of such a system would be to assign each window to a processor. In this way, each window would remain responsive with a dedicated processor.
While such a system would be workable with a small number of processors, it quickly becomes unwieldy as the number of processors increases. Furthermore, if the program is written anticipating a certain number of processors, it may be unable to take advantage of a computing system having more processors than originally contemplated leaving the additional processors idle. Worse yet, the program may not run at all on a computing system with an unanticipated number of processors.
Some solutions do not require a programmer to explicitly program parallel execution and manage the coordination of execution. One such solution uses the concept of chores. A chore is generally defined as an opportunity for parallelism. Using the concept of chores, a programmer can, at the time of programming, identify portions of code that can be executed in parallel if possible, without worrying about the actual details of load balancing, paging, and communication between processors. Instead, a runtime system determines which chores to run in parallel depending on available processors and resources.
Often, there are many more opportunities for parallelism than actual processors to execute the chores. Is some cases, there may be several orders of magnitude more opportunities for parallelism at any given time that there are processor available to take advantage of those opportunities. In conventional solutions, there are significant resources used to create each chore in which a block of code is assigned to a particular processor. Furthermore, there are resources required during a “steal” operation in which an available processor takes a chore from another processor. In the environment in which there are many more chores than there are processors, the chore creation operation may be frequent, whereas the chore steal operation may be infrequent. As a result, the overhead associated with creating and executing chores limits the performance of and scalability of a chore-based system.