Cooperating CoScheduling: A Coscheduling Proposal Aimed at Non-Dedicated Heterogeneous NOWs

Implicit coscheduling techniques applied to non-dedicated homogeneousNetworks Of Workstations (NOWs) have shown they can perform well whenmany local users compete with a single parallel job. Implicitcoscheduling deals with minimizing the communication waiting time ofparallel processes by identifying the processes in need of coschedulingthrough gathering and analyzing implicit runtime information, basicallycommunication events. Unfortunately, implicit coscheduling techniques donot guarantee the performance of local and parallel jobs, when thenumber of parallel jobs competing against each other is increased. Thus,a low efficiency use of the idle computational resources is achieved.In order to solve these problems, a new technique, named CooperatingCoScheduling (CCS), is presented in this work. Unlike traditionalimplicit coscheduling techniques, under CCS, each node takes itsscheduling decisions from the occurrence of local events, basicallycommunication, memory, Input/Output and CPU, together with foreignevents received from cooperating nodes. This allows CCS to provide asocial contract based on reserving a percentage of CPU and memoryresources to ensure the progress of parallel jobs without disturbing thelocal users, while coscheduling of communicating tasks is ensured.Besides, the CCS algorithm uses status information from the cooperatingnodes to balance the resources across the cluster when necessary.Experimental results in a non-dedicated heterogeneous NOW reveal thatCCS allows the idle resources to be exploited efficiently, thusobtaining a satisfactory speedup and provoking an overhead that isimperceptible to the local user.