A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid

Efficient task scheduling is critical to achieving high performance on grid computing environment. The task scheduling on grid is studied as optimization problem in this paper. A heuristic task scheduling algorithm satisfying resources load balancing on grid environment is presented. The algorithm schedules tasks by employing mean load based on task predictive execution time as heuristic information to obtain an initial scheduling strategy. Then an optimal scheduling strategy is achieved by selecting two machines satisfying condition to change their loads via reassigning their tasks under the heuristic of their mean load. Methods of selecting machines and tasks are given in this paper to increase the throughput of the system and reduce the total waiting time. The efficiency of the algorithm is analyzed and the performance of the proposed algorithm is evaluated via extensive simulation experiments. Experimental results show that the heuristic algorithm performs significantly to ensure high load balancing and achieve an optimal scheduling strategy almost all the time. Furthermore, results show that our algorithm is high efficient in terms of time complexity.     

Framework and Algorithm for Grid QoS Infrastructure in Optical Burst Switching Networks with GMPLS Support

Recently, in order to satisfy the requirements of all kinds of high-performance computing and transmission applications, researchers begin to focus on grid technology and have made lots of research work. Among the corresponding aspects, a complete and feasible grid framework is rather pivotal to provide nontrivial QoS guarantee in this grid architecture, which should include Grid application layer, Grid middleware layer, and network layer, even the concrete resources. In this paper, a novel architecture for Grid QoS infrastructure is proposed based on other architectures suggested by Globus project, Global Grid forum and IETF. The architecture is complete and consists of three QoS layers from top to bottom including Grid application, middleware and network layer. In addition, the algorithm based on advance resource reservation is also provided and described in optical burst switching （OBS） networks with GMPLS（Generalized Multi-Protocol Label Switching） support. The algorithm with pruned topology and shared risk links group constraints is designed for supporting the realization of routing function in the architecture. Extensive simulations with dynamic traffic are made to prove the validity and properness.     

Context-aware active task discovery for pervasive computing

Task computing is mainly involved with how to interact with equipment and services for users. In such new mode users can only concern with the task need to be completed, without having to consider how to complete it. In recent years, this new mode has been considered the preferred choice under the environment of pervasive computing. Active task discovery is the key to task computing, which depends on context and automatically relates the corresponding services to complete the given operation. In this paper, based on active task computing model we present a new context-aware active task discovery mode and raise a good algorithm for discovering and executing task.     

Performance evaluation of a parallel cascade semijoin algorithm for computing path expressions in object database systems

With the emerging of new applications,especially in Web,Such as E-Commerce,Digital Library and DNA Bank,object database systems show their stronger funcitons than other kinds of database systems due to their powerful representation ability on complex semantics and relationshiop.One distinguished feature of object database systems is path expression,and most queries on an object database ar based on path expression because it is the most natural and convenient way to access the object databse,for example,to navigate the hyper-links in a web-based database,The execution of path expression is usually extremely expensive on a very large database.Therefore,the improvement of path expression eecution efficiency is critical for the performance ofobject databases.As an importan approach realizing high-performance query processing ,the parallel processing of path expression on distributed object databases is explored in this paper.Up to now,some algorithms about how to compute path expressions and how to optimize path expression processing have been proposed for centralizedenvironments.But,few approaches have been presented for computing path expressions in parallel.In this paper,a new paralle algorithm for computing path expression named Parallel Cascade Semijoin(PCSJ)is proposed.Moreover,a new scheduling strategy called right-deep zigzag tree is designed to further improve the performance of the PCSJ algorithm.The exper-iments have been implemented in an NOW distributed and parallel environment.The results show that the PCSJ algorithm outperforms the other two parallel algorithms(the parallel version of forward pointer chasing algorithm(PFPC)and the index splitting parallel algorithm(IndexSplit) when computing path expressions with restrictive predicates and that the right-deep zigzage tree scheduling strategy has better performance than the right-deep tree scheduling strategy.     

Network and data location aware approach for simultaneous job scheduling and data replication in large-scale data grid environments

Data Grid integrates graphically distributed resources for solving data intensive scientific applications. Effective scheduling in Grid can reduce the amount of data transferred among nodes by submitting a job to a node, where most of the requested data files are available. Scheduling is a traditional problem in parallel and distributed system. However, due to special issues and goals of Grid, traditional approach is not effective in this environment any more. Therefore, it is necessary to propose methods specialized for this kind of parallel and distributed system. Another solution is to use a data replication strategy to create multiple copies of files and store them in convenient locations to shorten file access times. To utilize the above two concepts, in this paper we develop a job scheduling policy, called hierarchical job scheduling strategy （HJSS）, and a dynamic data replication strategy, called advanced dynamic hierarchical replication strategy （ADHRS）, to improve the data access efficiencies in a hierarchical Data Grid. HJSS uses hierarchical scheduling to reduce the search time for an appropriate computing node. It considers network characteristics, number of jobs waiting in queue, file locations, and disk read speed of storage drive at data sources. Moreover, due to the limited storage capacity, a good replica replacement algorithm is needed. We present a novel replacement strategy which deletes files in two steps when free space is not enough for the new replica： first, it deletes those files with minimum time for transferring. Second, if space is still insufficient then it considers the last time the replica was requested, number of access, size of replica and file transfer time. The simulation results show that our proposed algorithm has better performance in comparison with other algorithms in terms of job execution time, number of intercommunications, number of replications, hit ratio, computing resource usage and storage usage.     

Task mapper and application-aware virtual machine scheduler oriented for parallel computing

We design a task mapper TPCM for assigning tasks to virtual machines, and an application-aware virtual machine scheduler TPCS oriented for parallel computing to achieve a high performance in virtual computing systems. To solve the problem of mapping tasks to virtual machines, a virtual machine mapping algorithm (VMMA) in TPCM is presented to achieve load balance in a cluster. Based on such mapping results, TPCS is constructed including three components: a middleware supporting an application-driven scheduling, a device driver in the guest OS kernel, and a virtual machine scheduling algorithm. These components are implemented in the user space, guest OS, and the CPU virtualization subsystem of the Xen hypervisor, respectively. In TPCS, the progress statuses of tasks are transmitted to the underlying kernel from the user space, thus enabling virtual machine scheduling policy to schedule based on the progress of tasks. This policy aims to exchange completion time of tasks for resource utilization. Experimental results show that TPCM can mine the parallelism among tasks to implement the mapping from tasks to virtual machines based on the relations among subtasks. The TPCS scheduler can complete the tasks in a shorter time than can Credit and other schedulers, because it uses task progress to ensure that the tasks in virtual machines complete simultaneously, thereby reducing the time spent in pending, synchronization, communication, and switching. Therefore, parallel tasks can collaborate with each other to achieve higher resource utilization and lower overheads. We conclude that the TPCS scheduler can overcome the shortcomings of present algorithms in perceiving the progress of tasks, making it better than schedulers currently used in parallel computing.     

Dynamic call and connection admission control in automatically switched optical network for grid computing applications

In recent years,Grid computing applications are becoming more and more important to the scientific and business communities and are likely to open to the consumer market and widely develop in the near future,which is a great challenge brought by the potentially large number of Grid users(perhaps millions)and high frequency of their job requests.Automatically switched optical network(ASON),which is a promising high capacity intelligent transport network infrastructure,has been already deployed in the world and regarded as a promising solution to foster the expansion of Grid computing from local area networks to wide area networks.However,by theoretical analysis and simulative evaluation of Grid job blocking in the distributed call and connection setup process of ASON,this paper verifies that ASON and the conventional admission control mechanism confront a problem in supporting future large-scale Grid computing.In order to address this issue,a novel dynamic call and connection admission control(DCCAC)scheme is proposed to improve the network performance and guarantee quality of service(QoS)of Grid applications.This scheme is applicable with complete network information,no network information and partial network information.Numerical results show that the DCCAC scheme can improve the efficiency of the network to a great extent.Moreover,all the analysis and algorithms in this paper are based on ITU-T ASON recommendations,which make the DCCAC scheme more applicable in network engineering for future Grid computing.     

Robust RBPF for mobile robot using panoramic vision

We present a novel vision-based approach to self-localization that uses an improved scheme to integrate feature-based matching of panoramic images with a Rao-Blackwellized Particle Filter （RBPF） for mobile robot Simultaneous Localization and Mapping （SLAM）. The matching for SIFT multi-dimension features is implemented with a KD-tree which introduce the Mahalanobis distance instead of the Euclidean distance for matching features. The particle filter is combined with Gaussian Mixture Unscented Particle Filters （GMUPF） to for initializing landmarks and a Single-Cluster Graph-Partitioning algorithm for outlier rejection. The landmark position estimation and update is also implemented through GMUPF by which a single update step from moving and sensing can be done and the change to the map certainty can be done in constant time. Experiment results on real robot in our indoor environment show the advantages of our methods over previous approaches.     

An Effective Cloud Workflow Scheduling Approach Combining PSO and Idle Time Slot-Aware Rules

Workflow scheduling is a key issue and remains a challenging problem in cloud computing.Faced with the large number of virtual machine(VM)types offered by cloud providers,cloud users need to choose the most appropriate VM type for each task.Multiple task scheduling sequences exist in a workflow application.Different task scheduling sequences have a significant impact on the scheduling performance.It is not easy to determine the most appropriate set of VM types for tasks and the best task scheduling sequence.Besides,the idle time slots on VM instances should be used fully to increase resources'utilization and save the execution cost of a workflow.This paper considers these three aspects simultaneously and proposes a cloud workflow scheduling approach which combines particle swarm optimization(PSO)and idle time slot-aware rules,to minimize the execution cost of a workflow application under a deadline constraint.A new particle encoding is devised to represent the VM type required by each task and the scheduling sequence of tasks.An idle time slot-aware decoding procedure is proposed to decode a particle into a scheduling solution.To handle tasks'invalid priorities caused by the randomness of PSO,a repair method is used to repair those priorities to produce valid task scheduling sequences.The proposed approach is compared with state-of-the-art cloud workflow scheduling algorithms.Experiments show that the proposed approach outperforms the comparative algorithms in terms of both of the execution cost and the success rate in meeting the deadline.     

Graph-Theoretic Approach to Network Analysis

Networks are a class of general systems represented by becomes a weighted graph visualizing the constraints imposed their UC-structure. Suppressing the nature of elements the network by interconnections rather than the elements themselves. These constraints follow generalized Kirchhoff＇s laws derived from physical constraints. Once we have a graph; then the working environment becomes the graph-theory. An algorithm derived from graph theory is developed within the paper in order to analyze general networks. The algorithm is based on computing all the spanning trees in the graph G with an associated weight. This weight is the product ofadmittance＇s of the edges forming the spanning tree. In the first phase this algorithm computes a depth first spanning tree together with its cotree. Both are used as parents for controlled generation of off-springs. The control is represented in selecting the off-springs that were not generated previously. While the generation of off-springs, is based on replacement of one or more tree edges by cycle edges corresponding to cotree edges. The algorithm can generate a frequency domain analysis of the network.     

Bi-level fuzzy based advanced reservation of Cloud workflow applications on distributed Grid resources

The increasing demand on execution of large-scale Cloud workflow applications which need a robust and elastic computing infrastructure usually lead to the use of high-performance Grid computing clusters. As the owners of Cloud applications expect to fulfill the requested Quality of Services (QoS) by the Grid environment, an adaptive scheduling mechanism is needed which enables to distribute a large number of related tasks with different computational and communication demands on multi-cluster Grid computing environments. Addressing the problem of scheduling large-scale Cloud workflow applications onto multi-cluster Grid environment regarding the QoS constraints declared by application’s owner is the main contribution of this paper. Heterogeneity of resource types (service type) is one of the most important issues which significantly affect workflow scheduling in Grid environment. On the other hand, a Cloud application workflow is usually consisting of different tasks with the need for different resource types to complete which we call it heterogeneity in workflow. The main idea which forms the soul of all the algorithms and techniques introduced in this paper is to match the heterogeneity in Cloud application’s workflow to the heterogeneity in Grid clusters. To obtain this objective a new bi-level advanced reservation strategy is introduced, which is based upon the idea of first performing global scheduling and then conducting local scheduling. Global-scheduling is responsible to dynamically partition the received DAG into multiple sub-workflows that is realized by two collaborating algorithms: (1) The Critical Path Extraction algorithm (CPE) which proposes a new dynamic task overall critically value strategy based on DAG’s specification and requested resource type QoS status to determine the criticality of each task; and (2) The DAG Partitioning algorithm (DAGP) which introduces a novel dynamic score-based approach to extract sub-workflows based on critical paths by using a new Fuzzy Qualitative Value Calculation System to evaluate the environment. Local-scheduling is responsible for scheduling tasks on suitable resources by utilizing a new Multi-Criteria Advance Reservation algorithm (MCAR) which simultaneously meets high reliability and QoS expectations for scheduling distributed Cloud-base applications. We used the simulation to evaluate the performance of the proposed mechanism in comparison with four well-known approaches. The results show that the proposed algorithm outperforms other approaches in different QoS related terms.     

计算网格中经济模型调度算法

任务调度是网格计算系统的一个重要组成部分。随着网格计算的出现,由于缺少对网格资源的直接管理,给网格任务调度带来了新的挑战。目前的任务调度机制大多数只考虑了任务调度的服务质量(QoS),而没有考虑任务调度的费用。为此,在研究了目前已有的适应启发式任务调度算法之后,提出了在同等费用前提下,将任务调度到能够提供较高QoS的资源中去的任务调度算法。     

An optimization approach for decentralized QoS‐based scheduling based on utility and pricing in Grid computing

This paper presents an optimization approach for decentralized Quality of Service (QoS)‐based scheduling based on utility and pricing in Grid computing. The paper assumes that the quality dimensions can be easily formulated as utility functions to express quality preferences for each task agent. The utility values are calculated by the user‐supplied utility function that can be formulated with the task parameters. The QoS constraint Grid resource scheduling problem is formulated into a utility optimization problem. The QoS‐based Grid resource scheduling optimization is decomposed into two subproblems by applying the Lagrangian method. In the Grid, a Grid task agent acts as a consumer paying for the Grid resource and the resource providers receive profits from task agents. A pricing‐based QoS scheduling algorithm is used to perform optimally decentralized QoS‐based resource scheduling. The experiments investigate the effect of the QoS metrics on the global utility and compare the performance of the proposed algorithm with other economical Grid resource scheduling algorithms. Copyright © 2006 John Wiley & Sons, Ltd.     

基于QoS参数综合模型的网格资源选择优化

QoS是网格任务执行的基本保证,针对网格资源选择中复杂的QoS参数处理过程,将QoS参数按照用户的关心程度进行分类,提出了一种简化的参数处理模型,设计了支撑该模型的QoS体系结构,给出了优化资源调度过程的算法。实验表明,该模型提高了系统吞吐量和资源匹配成功率,缩短了任务的平均完成时间,最终实现了整个系统资源利用率的提高。     

一种基于预测的资源匹配算法

网格任务调度过程中的资源匹配是根据任务要求从网格资源信息服务（GRIS）中查找出合适资源的过程。GRIS中记录的往往是资源的静态信息，由于本地负载的动态变化使得基于资源静态信息来确定的候选资源集中一些资源并不能满足任务的QoS需求。基于相关资源动态信息预测资源未来状态，给出了网格任务平均完成时间及完成时间的分布函数，并根据任务QoS需求，兼顾考虑资源当前及未来状态，提出了一种资源匹配模型与匹配算法。通过实验表明，该算法能有效减少候选资源数目，从而降低调度时间复杂度。     

基于网格的任务调度与资源分配有效机制的研究

为实现QoS路由技术,提高网格的服务质量,本文定义了网格服务中任务调度的通信开销,给出了QoS路由树的生成原则,提出网格堆排序算法和QoS路由选择算法,利用算法实现了网格的任务调度与分配机制的设计.实验证明本设计能提高网格资源管理的效率.     

一个扩展的以QoS为指向的网格任务调度算法

在对网格计算的研究中,有人考虑了计算资源中服务质量(QoS)因素,在对传统的Min-Min算法加以改进的基础上,提出了QoS Guided Min-Min算法。在此基础上,本文提出一种新的扩展型算法,以进一步提高网格资源的利用率。最后,本文对以上三种算法的实验结果进行了比较分析。     

一种应用于网格计算环境的任务调度模式*

提出了一种新的网格任务调度模式,针对网格计算资源有组织、松耦合、自治等特性,建立基于多层次虚拟组织形式的计算资源模型;根据网格环境中应用任务粗粒度、特定资源依赖等特点,建立了网格任务的描述模型;提出并实现了相应的子任务生成算法、任务初始调度算法及自动调整算法。设计实现了能够支持仿真及实际网格计算环境可扩展网格任务调度器,通过理论分析和仿真实验对算法的正确性、效果和效率进行了评价。     

基于聚类和改进共生演算法的云任务调度策略

针对云计算环境中一些基于服务质量（QoS）调度算法存在寻优速度慢、调度成本与用户满意度不均衡的问题,提出了一种基于聚类和改进共生演算法的云任务调度策略。首先将任务和资源进行模糊聚类并对资源进行重排序放置,依据属性相似度对任务进行指导分配,减小对资源的选择范围;然后依据交叉和旋转学习机制改进共生演算法,提升算法的搜索能力;最后通过加权求和方式构造驱动模型,均衡调度代价与系统性能间关系。通过不同任务量的云任务调度仿真实验,表明该算法相比改进遗传算法、混合粒子群遗传算法和离散共生演算法,有效减少了进化代数,降低了调度成本并提升了用户满意度,是一种可行有效的任务调度算法。     

边缘环境下计算密集型任务调度研究综述

随着移动设备数量的急剧增长及计算密集型应用如人脸识别、车联网以及虚拟现实等的广泛使用,为了实现满足用户QoS请求的任务和协同资源的最优匹配,使用合理的计算密集型应用的任务调度方案,从而解决边缘云中心时延长、成本高、负载不均衡和资源利用率低等问题。阐述了边缘计算环境下计算密集型应用的任务调度框架、执行过程、应用场景及性能指标。从时间和成本、能耗和资源利用率以及负载均衡和吞吐量为优化目标的边缘计算环境下计算密集型应用的任务调度策略进行了对比和分析,并归纳出目前这些策略的优缺点及适用场景。通过分析5G环境下基于SDN的边缘计算架构,提出了基于SDN环境下的边缘计算密集型数据包任务调度策略、基于深度强化学习的计算密集型应用的任务调度策略和5G IoV网络中多目标跨层任务调度策略。从容错调度、动态微服务调度、人群感知调度以及安全和隐私等几个方面总结和归纳了目前边缘计算环境中任务调度所面临的挑战。