Narrow Results

In this paper, we consider the problem of scheduling independent jobs in partitionable mesh connected systems. The problem is NP-hard, since it includes the multiprocessor scheduling problem as a special case when all jobs request for one processor. We analyze a simple approximation algorithm called A_m. In particular, we show that if the sizes of submeshes requested by jobs are independent and identically distributed (i.i.d.) random variables uniformly distributed in the range [1..M₁]×[1..M₂], where M₁×M₂ is the size of a partitionable mesh connected system, and task execution times are i.i.d. random variables with finite mean and variance, then the average-case performance ratio E(A_m(L))/E(OPT(L)) is asymptotically bounded from above by 1.6637594…. The average-case performance ratio improves significantly when jobs request for square submeshes or small submeshes.

The main objective of the proposed methodology is multi-objective job scheduling using hybridization of whale and BAT optimization algorithm (WBAT) which is used to change existing solution and to adopt a new good solution based on the objective function. The scheduling function in the proposed job scheduling strategy first creates a set of jobs and cloud node to generate the population by assigning jobs to cloud node randomly and evaluate the fitness function which minimizes the makespan and maximizes the quality of jobs. Second, the function uses iterations to regenerate populations based on WBAT behavior to produce the best job schedule that gives minimum makespan and good quality of jobs. The experimental results show that the performance of the proposed methods is better than the other methods of job scheduling problems.

As one of the most popular frameworks for large-scale analytics processing, Hadoop is facing two challenges: both applications and storage devices become heterogeneous. However, existing data placement and job scheduling schemes pay little attention to such heterogeneity of either application I/O requirements or I/O device capability, thus can greatly degrade system efficiencies. In this paper, we propose ASPS, an Application and Storage-aware data Placement and job Scheduling approach for Hadoop clusters. The idea is to place application data and schedule application tasks considering both application I/O requirements and storage device characteristics. Specifically, ASPS first introduces novel metrics to quantify I/O requirements of applications. Then, based on the quantification, ASPS places data of different applications to the preferred storage devices. Finally, ASPS tries to launch jobs with high I/O requirements on the nodes with the same type of faster devices to improve system efficiency. We have implemented ASPS in Hadoop framework. Experimental results show that ASPS can reduce the completion time of a single application by up to 36% and the average completion time of six concurrent applications by 27%, compared to existing data placement policies and job scheduling approaches.

Computational Grid (CG) is an emerging paradigm in which geographically distributed resources are logically unified as a computational unit. A challenging problem in such systems is the allocation of jobs to resources that minimizes both makespan and flowtime parameters. In this paper, we present an experimental study on Genetic Algorithms (GAs) for scheduling independents jobs to Grid resources based on two replacement strategies: Steady-State GA (SSGA) and Struggle GA (SGA). SSGA distinguishes for its accentuated convergence of the population that rapidly reaches good solutions though it is soon stagnated. The SGA is based on struggle replacement and adaptively maintains diverse population, reducing thus convergence rapidity. The experimental results, based on a benchmark simulation model, showed that SGA outperforms SSGA for moderate size instances. On the other hand, the time needed by the SGA to reach makespan values obtained by the SSGA rapidly increases as more jobs and machines are added to the Grid. Thus, for larger size instances, SGA is not able to improve the results of the SSGA. Finally, we also report and analyze flowtime values for the considered benchmark.

A grid is a geographically distributed resource sharing environment across multiple organizations. The most typical grid resources are clusters with high performance/cost ratio. In general, these clusters are shared as non-dedicated grid resources since local users may run their jobs simultaneously. Local jobs are usually queued and processed in a batch mode with uncertain waiting time, while grid jobs always require advance reservations with guaranteed resource allocation.

In this paper, we provide quantitative analysis on the impact of advance reservations over queued jobs, in terms of job waiting time and resource utilization, respectively. It is observed that advance reservations will lead to longer job waiting time and lower resource utilization. That is to say, advance reservations should cost more than queued jobs. In this work, based on quantitative experimental results, an empirical formula for cost estimation of advance reservations over queued jobs is presented. It is suggested that compared with queued jobs, advance reservations should be doubly charged to compensate resource utilization loss. If the notice time of an advance reservation is short below a threshold, additional cost should be applied further since queue waiting time is increased.

Computational grids have the potential for solving large-scale scientific applications using heterogeneous and geographically distributed resources. In addition to the challenges of managing and scheduling these applications, reliability challenges arise because of the unreliable nature of grid infrastructure. Two major problems that are critical to the effective utilization of computational resources are efficient scheduling of jobs and providing fault tolerance in a reliable manner. This paper addresses these problems by combining the checkpoint replication based fault tolerance mechanism with minimum total time to release (MTTR) job scheduling algorithm. TTR includes the service time of the job, waiting time in the queue, transfer of input and output data to and from the resource. The MTTR algorithm minimizes the response time by selecting a computational resource based on job requirements, job characteristics, and hardware features of the resources. The fault tolerance mechanism used here sets the job checkpoints based on the resource failure rate. If resource failure occurs, the job is restarted from its last successful state using a checkpoint file from another grid resource. Globus ToolKit is used as the grid middleware to set up a grid environment and evaluate the performance of the proposed approach. The monitoring tools Ganglia and Network Weather Service are used to gather hardware and network details, respectively. The experimental results demonstrate that, the proposed approach effectively schedule the grid jobs with fault-tolerant way thereby reduces TTR of the jobs submitted in the grid. Also, it increases the percentage of jobs completed within specified deadline and making the grid trustworthy.

Cloud computing is attracting an increasing number of simulation applications running in the virtualized cloud data center. These applications are submitted to the cloud in the form of simulation jobs. Meanwhile, the management and scheduling of simulation jobs are playing an essential role to offer efficient and high productivity computational service. In this paper, we design a management and scheduling service framework for simulation jobs in two-tier virtualization-based private cloud data center, named simulation execution as a service (SimEaaS). It aims at releasing users from complex simulation running settings, while guaranteeing the QoS requirements adaptively. Furthermore, a novel job scheduling algorithm named adaptive deadline-aware job size adjustment (ADaSA) algorithm is designed to realize high job responsiveness under QoS requirement for SimEaaS. ADaSA tries to make full use of the idle fragmentation resources by tuning the number of requested processes of submitted jobs in the queue adaptively, while guaranteeing that jobs’ deadline requirements are not violated. Extensive experiments with trace-driven simulation are conducted to evaluate the performance of our ADaSA. The results show that ADaSA outperforms both cloud-based job scheduling algorithm KCEASY and traditional EASY in terms of response time (up to 90%) and bounded slow down (up to 95%), while obtains approximately equivalent deadline-missed rate. ADaSA also outperforms two representative moldable scheduling algorithms in terms of deadline-missed rate (up to 60%).

In order to provide a uniform virtual view of resources for different users and applications, a grid computing framework with spaces (GCFS) is proposed. Based on the asynchronous mechanisms of the spaces model, this framework uses spaces to share data for applications. Spaces offer a virtual workspace for both resource providers and consumers in job scheduling. Task assignment is implemented by the coordination between the task manager and task schedulers. The space manager can dynamically create or destroy space services in response to the change of resource supplies and demands. Finally, a simulation of third generation (3G) wireless systems is developed to demonstrate the above ideas, and it is found that a flexible grid computing environment can be realized via GCFS.