独立任务调度的启发式算法

任务调度是一个NP-hard问题,而且是并行与分布式计算中一个必不可少的组成部分,特别是在网格计算环境下任务调度更加复杂。该文提出了满足负载均衡的一个启发式任务调度算法。给出了选择处理机和任务的方法,以提高算法的效率。实验表明该算法是一个高效率的调度算法,并且几乎总是找到了最优调度方案。     

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.     

Aligning block permutation methods for topology transformation on computational grids

Many traditional parallel matrix computing algorithms are performed on regular resource topologies, such as mesh. However, the grid resource topology is often irregular in practice. In this paper, we present a transformation algorithm of grid resource topology for achieving virtual meshes. And on the virtual mesh, these traditional parallel algorithms can be performed in a modern computational grid environment. The basic idea of our topology transformation is to align the basic blocks of grid computational resources through permutations in a virtual mesh. Designing a cost function of heuristic search scheme for the transformation, we use it to fully exploit the computational and communicational abilities of grid resources. The experiment results show that our aligning block permutation can significantly reduce the time complexity of search tree. They also show that the heuristic search scheme can effectively find the block permutation that makes better use of computational and communicational abilities of grid resources.     

具有模糊多目标的网格任务调度算法

在异构的网格计算平台上,网格中有用户、资源管理员、组织管理者等实体,这些实体对网格的管理、使用、维护、安全性、可靠性等目标都提出了要求,并且这些目标有时是不可量化的。针对具有模糊多目标网格计算的任务调度问题,提出模糊多目标网格任务调度模型,使用模糊化等式对多目标进行模糊处理,给出求解该模型的模糊化定理,并对该定理进行证明。利用差分优化算法无需目标函数连续可微的特点,提出使用模糊差分优化算法完成模糊多目标的网格任务调度。实验结果表明,模糊差分优化算法较现有算法在执行时间上处于劣势,但在可靠性、安全性和丢失任务数三个指标上要优于现有算法。     

树型网格计算环境下的独立任务调度

任务调度是实现高性能网格计算的一个基本问题,然而,设计和实现高效的调度算法是非常具有挑战性的.讨论了在网格资源计算能力和网络通信速度异构的树型计算网格环境下,独立任务的调度问题.与实现最小化任务总的执行时间不同(该问题已被证明是NP难题),为该任务调度问题建立了整数线性规划模型,并从该线性规划模型中得到最优任务分配方案??各计算节点最优任务分配数.然后,基于最优任务分配方案,构造了两种动态的需求驱动的任务分配启发式算法:OPCHATA(optimization-based priority-computation heuristic algorithm for task allocation)和OPBHATA(optimization-basedpriority-bandwidth heuristic algorithm for task allocation).实验结果表明:在异构的树型计算网格环境下实现大量独立任务调度时,该算法的性能明显优于其他算法.     

一种基于QoS的自适应网格失效检测器

失效检测器是构建可靠的网格计算环境所必需的基础组件之一.由于网格中存在大量对失效检测有着不同QoS需求的分布式应用,对于一个网格失效检测器来说,为保持其有效性和可扩展性,应该既能够准确提供应用程序所需的失效检测QoS,又能够避免为满足不同QoS而设计多套失效检测器所产生的多余负载.基于QoS基本评价指标,采用PULL模式主动检测策略实现了一种新的失效检测器--GA-FD(adaptive failure detector for grid),可以同时支持多个应用程序定量描述的QoS需求,不需要关于消息行为和时钟同步的任何假设.同时,证明了GA-FD在部分同步模型下可实现一个◇P类的失效检测器,并给出了相应的实验及数据.     

基于分布式计算的电网运行可靠性评估算法研究

针对电网运行可靠性评估计算量大,但又要求计算时间短的问题,提出了一种基于分布式计算的电网运行可靠性评估算法。该算法采用改进的状态选择和分析方案,解决了计算终端间随机数序列的关联性问题,有效地降低了通信量,提高了计算速度。基于该算法编制的评估软件已通过RTS-24系统和某省级电网的实际运行测试,测试结果表明,该算法不仅能够有效评估电网运行可靠性,而且计算速度随计算终端数增加呈一定倍数提高。     

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

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

兵棋地图快速数字化算法的研究与实现

手工兵棋电子化过程中一个重要的方面就是兵棋地图的数字化,而兵棋地图数字化的基础工作就是地图网格化以及网格定位。在兵棋系统中,为了减小误差,一般采用六角网格覆盖原始地图的方法来实现地图的网格化。在实际推演过程中,作战地图覆盖范围一般很大,那么怎样提高网格化以及网格定位效率就成了地图数字化过程中必须考虑的问题。文章描述了一种效率很高的六边形网格绘制算法,并提出了基于元启发式方法的快速地图网格定位算法,它的时间以及空间复杂都仅有O（1）,能够很好的满足兵棋系统中超大地图数字化的要求。     

未来大数据环境下的配用电通信网虚拟网络架构及应用

根据智能配电网的通信需求,本文提出了基于无线 Mesh 网和电力线通信网的智能配电网通信框架。在此框架的基础上,设计了一个遗传算法和启发式算法,为不同类型的业务分别建立虚拟网络并将其映射到异构的物理网络中,通过增加传输分集来保证实时业务的可靠性。通过仿真,验证两种映射算法在保证实时业务可靠性的基础上,使尽力而为型业务的吞吐率达到最大化。     

Business-driven short-term management of a hybrid IT infrastructure

We consider the problem of managing a hybrid computing infrastructure whose processing elements are comprised of in-house dedicated machines, virtual machines acquired on-demand from a cloud computing provider through short-term reservation contracts, and virtual machines made available by the remote peers of a best-effort peer-to-peer (P2P) grid. Each of these resources has different cost basis and associated quality of service guarantees. The applications that run in this hybrid infrastructure are characterized by a utility function: the utility gained with the completion of an application depends on the time taken to execute it. We take a business-driven approach to manage this infrastructure, aiming at maximizing the profit yielded, that is, the utility produced as a result of the applications that are run minus the cost of the computing resources that are used to run them. We propose a heuristic to be used by a contract planner agent that establishes the contracts with the cloud computing provider to balance the cost of running an application and the utility that is obtained with its execution, with the goal of producing a high overall profit. Our analytical results show that the simple heuristic proposed achieves very high relative efficiency in the use of the hybrid infrastructure. We also demonstrate that the ability to estimate the grid behaviour is an important condition for making contracts that allow such relative efficiency values to be achieved. On the other hand, our simulation results with realistic error predictions show only a modest improvement in the profit achieved by the simple heuristic proposed, when compared to a heuristic that does not consider the grid when planning contracts, but uses it, and another that is completely oblivious to the existence of the grid. This calls for the development of more accurate predictors for the availability of P2P grids, and more elaborated heuristics that can better deal with the several sources of non-determinism present in this hybrid infrastructure.     

基于A*改进算法的四向移动机器人路径搜索研究

在由栅格法构建的环境地图中,利用A*算法进行路径搜索时存在搜索范围广、搜索速度慢、路径曲折等问题.针对栅格地图及具有四向移动机器人的特点,从搜索方向、启发函数构建、机器人加减速以及转向成本等几个方面对A*算法进行研究和改进,提出一种基于启发信息的扩展节点算法,降低偏离最佳路径节点的扩展数量.改进后的A*算法平均可降低67.1%的搜索面积、49.2%的计算时长、24.9%的路径成本及减少51.1%的转向次数,提高了路径的搜索速度和平滑度.     

计算一类网络K--终点可靠性的线性时间算法

可靠性保护缩减的方法是计算网络可靠性的常用手段之一，而且关心哪类网络的可靠性存在线性时间算法．给出了一类新的可靠性保护缩减-桥缩减和一类无向网络，称之为WST网络，该类网络是对串并联网络的扩展并且对该类网络提出了一个计算K-终点可靠性的线性时间算法，其算法复杂性为O(|E|^2)．     

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

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

A cell-based point-in-polygon algorithm suitable for large sets of points

The paper describes a new algorithm for solving the point-in-polygon problem. It is especially suitable when it is necessary to check whether many points are placed inside or outside a polygon. The algorithm works in two steps. First, a grid of cells equal in size is generated, and the polygon is laid on that grid. A heuristic approach is proposed for cell dimensioning. The cells of the grid are marked as being inside, outside, or on the polygon border. A modified flood-fill algorithm is applied for cell classification. In the second step, points are tested individually. If the tested point falls into an inner or an outer cell, the result is returned without any additional calculations. If the cell contains the polygon border, it is possible to determine the local point position. The analysis of time complexity shows that the initialization is finished in time, while the expected time complexity for checking an individual point is , where n represents the number of polygon edges. The algorithm works with O(n) space complexity. The paper also gives practical results using artificial and real polygons from a GIS environment.     

Reliability-aware scheduling strategy for heterogeneous distributed computing systems

Heterogeneous computing systems are promising computing platforms, since single parallel architecture based systems may not be sufficient to exploit the available parallelism with the running applications. In some cases, heterogeneous distributed computing (HDC) systems can achieve higher performance with lower cost than single-machine supersystems. However, in HDC systems, processors and networks are not failure free and any kind of failure may be critical to the running applications. One way of dealing with such failures is to employ a reliable scheduling algorithm. Unfortunately, most existing scheduling algorithms for precedence constrained tasks in HDC systems do not adequately consider reliability requirements of inter-dependent tasks. In this paper, we design a reliability-driven scheduling architecture that can effectively measure system reliability, based on an optimal reliability communication path search algorithm, and then we introduce reliability priority rank (RRank) to estimate the task’s priority by considering reliability overheads. Furthermore, based on directed acyclic graph (DAG) we propose a reliability-aware scheduling algorithm for precedence constrained tasks, which can achieve high quality of reliability for applications. The comparison studies, based on both randomly generated graphs and the graphs of some real applications, show that our scheduling algorithm outperforms the existing scheduling algorithms in terms of makespan, scheduling length ratio, and reliability. At the same time, the improvement gained by our algorithm increases as the data communication among tasks increases.     

Two-machine flowshop scheduling with bicriteria problem

This paper attempts to solve a two-machine flowshop bicriteria scheduling problem with release dates for the jobs, in which the objective function is to minimize a weighed sum of total flow time and makespan. To tackle this scheduling problem, an integer programming model with N²+3N variables and 5N constraints where N is the number of jobs, is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, a heuristic scheduling algorithm is presented. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. The average solution quality of the heuristic algorithm is above 99% and is much better than that of the SPT rule as a benchmark. A 15-job case requires only 0.018 s, on average, to obtain an ultimate or even optimal solution. The heuristic scheduling algorithm is a more practical approach to real world applications than the integer programming model.     

一种基于新的条件信息熵的高效知识约简算法

分析了在知识约简过程中现有条件信息熵的不足,给出一种新的条件信息熵,由此定义新的属性重要性.将其与基于正区域和基于现有条件信息熵的属性重要性进行比较,结果表明新的属性重要性是一种更准确、更全面的启发信息.以新的属性重要性为启发信息设计约简算法,并给出计算新的条件信息熵的高效算法.理论分析和实验结果表明,与基于现有条件信息熵的约简算法相比,该约简算法时间复杂度较低,且在搜索最小或次优约简方面更优.     

An efficient implementation of the Min-Min heuristic

Min—Min is a popular heuristic for scheduling tasks to heterogeneous computational resources, which has been applied either directly or as part of more sophisticated heuristics. However, for large scenarios such as grid computing platforms, the time complexity of a straightforward implementation of Min—Min, which is quadratic in the number of tasks, may be prohibitive. This has motivated the development of high performance computing (HPC) implementations, and the use of simpler heuristics for the sake of acceptable execution times. We propose a simple algorithm that implements Min—Min requiring only O(mn) operations for scheduling n tasks on m machines. Our experiments show, in practice, that a straightforward sequential implementation of this algorithm significantly outperforms other state of the art implementations of Min—Min, even compared to HPC implementations. In addition, the proposed algorithm is at least as suitable for parallelization as a direct implementation of Min—Min.     

Reliability of grid service systems

Grid computing system is different from conventional distributed computing systems by its focus on large-scale resource sharing, where remote accessing and information communication have great influence on grid computing. As an important metric for services, the grid service reliability is studied in this paper. There are some earlier studies on the reliability analysis of conventional small-scale distributed systems, which ignored the communication time and processing time when studying the reliability, but it is not practical in the reliability analysis of grid services due to the wide-area property of the network. Thus, this paper presents a model for the grid services and develops an approach to analyze the grid service reliability. Detailed algorithms to compute the grid service reliability are presented and a self-sensing technology is proposed for parameterization and monitoring. A numerical example is used for the purpose of illustration. Finally, the new model is compared with different types of conventional models, through which this model is verified more suitable for grid service reliability.