A family of heuristics for agent-based elastic Cloud bag-of-tasks concurrent scheduling
September 2013
J. Octavio Guitierrez -Garcia, Post doc in Korea (now in ITAM )
Kwang Mong Sim, United Kingdom.
Published in FGCS, link
In this paper they have presented the results of 14 scheduling heuristics which they have used to schedule BoTs in a dynamic environment using agents communicating and coordination using Contract Net Protocol.
BoTs : numerous unconnected (i.e. without precedence constraints) tasks which can be highly parallelized given their unconnected nature.
Classification of scheduling heuristics
immediate mode : map BoT tasks to cloud resources as soon as they arrive at the scheduler, eg. FCFS
batch mode : pre-schedule BoT tasks on a previously defined set of cloud resources before starting the execution, eg. Min-min, Max-min.
Aim : to maximize resource utilization
Why agents? They are endowed with distributed and cooperative problem solving techniques.
Contract Net Protocol : allow automated and dynamic selection and composition of cloud resources from a pool of cloud providers to execute BoTs.
Why agent based problem solving technique? it supports distributed, concurrent, and parallel scheduling and execution of BoTs in heterogeneous sets of dynamically provisionned cloud resources allocated in terms of 1 hour time slots (after the model in Amazon EC2)
Scheduling heuristics - derived from a combination of the following two phases
1) Task Ordering
- Unordered (U)
- Tasks ordered by size from large to small (LtoS)
- Tasks ordered by sized from small to large (StoL)
2)Task Mapping Policies
- Random Mapping(R)
- Maximum expected remaining allocation time mapping (MaxET)
- Maximum current remaining allocation time mapping (MaxCT)
- Minimum expected remaining allocation time mapping (MinET)
- Minimum current remaining allocation time mapping (MinCT)
{U, LtoS, StoL) X {R, MaxET, MaxCT, MinET, MinCT} /{U,R}
{U,R} represents a completely random immediate mode scheduling heuristic that follows FCFS allocation policy... therefore this is used for comparison.
Implementation
It is implemented using JADE (Jave Agent Development framework).... (finally! something familiar :) )
Important Observations and conclusions from Garcia et al (that I feel may be relevant for my work )
- BoTs containing many small tasks and few big tasks scheduled using the MaxET task mapping policy ( {U, LtoS, StoL} X {MaxET}) had the shortest makespans regardless of the task ordering type.
- Due to the NP-complete nature of the scheduling problem, there was not dominant scheduling heuristic for all the BoT types ( uniformly, normally, right-normally and left-half normally distributed BoT's ), neither the proposed cloud scheduling heuristics based on the remaining allocation time of cloud resources nor the benchmark scheduling heuristics.
- Agents in the testbed were capable of successfully executing and scheduling BoTs concurrently with a 100% success rate for randomly generated BoTs of a wide variety of sizes in randomly generated cloud environments even with high execution request rates and handling multiple BoTs at the same time.
- agents in the testbed efficiently scheduled and executed BoTs by sending only a linearly increasing number of messages among CAs, BAs, SPAs and RAs that depends only in the number of tasks contained in BoTs.
- Agents' distributed and cooperative problem solving techniques are efficient enough to support concurrent scheduling and execution of multiple BoTs with extremely high execution request rates and stringent constraints.
Performance Metrics
- Av BoT makespan
- BoT Success rate
- Av. BoT scheduling overhead time
- Av. no. of msg exchanged for executing BoT's
Found this in future research directions useful
Designing cloud scheduling heuristics for handling data
No comments:
Post a Comment