PEs. Load-based algorithms take into account the load on the individual PE while tracking the overlap between sets of PEs assigned to different jobs. 1. Minimal maximum load. In this scheme, PEs are sorted based on the load on them that each job will have on the PEs. The availability of the free PEs in the slot determines the capacity of the slot. Suppose that PEs are allocated to a job which has threads, the PE in the load order (last one) will determine the maximum load that any PE can have which is available in the slot. The slot which has minimal maximum load on any PE is chosen and a number of least loaded free PEs are used in the slot. 2. Minimal average load. Unlike the previous scheme, in which slots were chosen based on the minimal maximum load on PE, here slots are chosen based on the average of the load on the least loaded PEs. Buddy based algorithm In this algorithm the PEs are assigned in clusters, not individually. The PEs are first partitioned into groups that are power of two. Each member of the group will be assigned a controller and when a job of size n arrives, it is assigned to a controller of size 2[lg 2] (the smallest power to 2 that is larger than or equal to n). The controller is assigned by first sorting all the used slots, and then identifying groups of 2[lg 2] contiguous free processors. If a controller has all the PEs free in some of the slots, then only a newly arrived job will be assigned to that controller. Otherwise a new slot is opened. Migration based algorithm In all the above-mentioned algorithms, the initial placement policy is fixed and jobs are allocated to the PEs based on that. However, this scheme migrates jobs from one set of PEs to another set of PEs, which in turn improves the run fraction of the system. See also Coscheduling Parallel computing References Gang Scheduling, Timesharing on Parallel Computers, SC98, November 1998 (a summary) Performance Characteristics of Gang Scheduling in Multiprogrammed Environments, SC97, November 1997 Processor scheduling algorithms