分布式并行计算环境下混合遗传算法的研究

为提高混合遗传算法的计算效率和求解质量,提出一个并行混合遗传算法框架。该框架主要由遗传算法、小生境操作和单纯形3部分组成,遗传算法和小生境操作采用串行执行方式,单纯形采用分布式并行执行方式。分布式并行计算环境由4台计算机通过交换机连接构成,并设计了一个动态任务调度方案。一个典型工程算例验证了新算法的有效性,并且在分布式并行环境下取得了较好的加速比和并行效率。     

Grids and Grid technologies for wide‐area distributed computing

The last decade has seen a substantial increase in commodity computer and network performance, mainly as a result of faster hardware and more sophisticated software. Nevertheless, there are still problems, in the fields of science, engineering, and business, which cannot be effectively dealt with using the current generation of supercomputers. In fact, due to their size and complexity, these problems are often very numerically and/or data intensive and consequently require a variety ofheterogeneous resources that are not available on a single machine. A number of teams have conducted experimental studies on the cooperative use of geographically distributed resources unified to act as a single powerful computer. This new approach is known by several names, such as metacomputing, scalable computing, global computing, Internet computing, and more recently peer‐to‐peer or Grid computing. The early efforts in Grid computing started as a project to link supercomputing sites, but have now grown far beyond their original intent. In fact, many applications can benefit from the Grid infrastructure, including collaborative engineering, data exploration, high‐throughput computing, and of course distributed supercomputing. Moreover, due to the rapid growth of the Internet and Web, there has been a rising interest in Web‐based distributed computing, and many projects have been started and aim to exploit the Web as an infrastructure for running coarse‐grained distributed and parallel applications. In this context, the Web has the capability to be a platform for parallel and collaborative work as well as a key technology to create a pervasive and ubiquitous Grid‐based infrastructure. This paper aims to present the state‐of‐the‐art of Grid computing and attempts to survey the major international efforts in developing this emerging technology. Copyright © 2002 John Wiley & Sons, Ltd.     

分支定界算法的分布并行化研究

介绍了一种专用于计算分支定界算法的机群计算平台,其中所使用的分布并行策略减少了分支定界算法计算时间复杂度,减小了问题的规模;可以把计算平台机群中的任何一台计算机上计算出的当前全局最佳本分值,实时地广播给所有其他并行的计算机,并作为它们新的最佳本分值,实现分支节点的快速并行淘汰;应用启发式算法修改了分支定界算法,提高了分支节点的淘汰效率。选用旅行商问题实例作为测试基准。计算表明,在保证求得最优解的前提下,该平台能很好地提高分支定界算法的效率。     

分布式机器学习作业性能干扰分析与预测

通过分析分布式机器学习中作业性能干扰的问题,发现性能干扰是由于内存过载、带宽竞争等GPU资源分配不均导致的,为此设计并实现了快速预测作业间性能干扰的机制,该预测机制能够根据给定的GPU参数和作业类型自适应地预测作业干扰程度。首先,通过实验获取分布式机器学习作业运行时的GPU参数和干扰率,并分析出各类参数对性能干扰的影响;其次,依托多种预测技术建立GPU参数-干扰率模型进行作业干扰率误差分析;最后,建立自适应的作业干扰率预测算法,面向给定的设备环境和作业集合自动选择误差最小的预测模型,快速、准确地预测作业干扰率。选取5种常用的神经网络作业,在两种GPU设备上设计实验并进行结果分析。结果显示,所提出的自适应干扰预测（AIP）机制能够在不提供任何预先假设信息的前提下快速完成预测模型的选择和性能干扰预测,耗时在300 s以内,预测干扰率误差在2%~13%,可应用于作业调度和负载均衡等场景。     

An efficient list-based task scheduling algorithm for heterogeneous distributed computing environment

The task scheduling in heterogeneous distributed computing systems plays a crucial role in reducing the makespan and maximizing resource utilization. The diverse nature of the devices in heterogeneous distributed computing systems intensifies the complexity of scheduling the tasks. To overcome this problem, a new list-based static task scheduling algorithm namely Deadline-Aware-Longest-Path-of-all-Predecessors (DA-LPP) is being proposed in this article. In the prioritization phase of the DA-LPP algorithm, the path length of the current task from all its predecessors at each level is computed and among them, the longest path length value is assigned as the rank of the task. This strategy emphasizes the tasks in the critical path. This well-optimized prioritization phase leads to an observable minimization in the makespan of the applications. In the processor selection phase, the DA-LPP algorithm implements the improved insertion-based policy which effectively utilizes the unoccupied leftover free time slots of the processors which improve resource utilization, further least computation cost allocation approach is followed to minimize the overall computation cost of the processors and parental prioritization policy is incorporated to further reduce the scheduling length. To demonstrate the robustness of the proposed algorithm, a synthetic graph generator is used in this experiment to generate a huge variety of graphs. Apart from the synthetic graphs, real-world application graphs like Montage, LIGO, Cybershake, and Epigenomic are also considered to grade the performance of the DA-LPP algorithm. Experimental results of the DA-LPP algorithm show improvement in performance in terms of scheduling length ratio, makespan reduction rate , and resource reduction rate when compared with other algorithms like DQWS, DUCO, DCO and EPRD. The results reveal that for 1000 task set with deadline equals to two times of the critical path, the scheduling length ratio of the DA-LPP algorithm is better than DQWS by 35%, DUCO by 23%, DCO by 26 %, and EPRD by 17%.     

A taxonomy and survey of grid resource management systems for distributed computing

The resource management system is the central component of distributed network computing systems. There have been many projects focused on network computing that have designed and implemented resource management systems with a variety of architectures and services. In this paper, an abstract model and a comprehensive taxonomy for describing resource management architectures is developed. The taxonomy is used to identify approaches followed in the implementation of existing resource management systems for very large‐scale network computing systems known as Grids. The taxonomy and the survey results are used to identify architectural approaches and issues that have not been fully explored in the research. Copyright © 2001 John Wiley & Sons, Ltd.     

网格计算中基于并行克隆遗传算法的任务分配与调度

实现网格计算的一个重要目的在于实现地理分布、异构资源的统一描述方法,提供用户虚拟的统一资源界面,并将用户提出的服务要求透明、动态地分配给最适应的资源上执行。针对目前任务调度的应用现状,提出了一种既能使资源负载均衡又能充分利用系统资源的并行克隆遗传算法,该启发式算法能显著地降低资源最优分配中的计算复杂度,使其能满足实时调度的需要。实验结果表明这种算法优于其他调度算法。     

并行机器学习算法基础体系前沿进展综述

大数据环境下,机器学习算法受到前所未有的重视。总结和分析了传统机器学习算法在海量数据场景下出现的若干问题,基于当代并行机分类回顾了国内外并行机器学习算法的研究现状,并归纳总结了并行机器学习算法在各种基础体系下存在的问题。针对大数据环境下并行机器学习算法进行了简要的总结,并对其发展趋势作了展望。     

分布式并行计算在交通网络仿真中的应用*

根据交通网络仿真的并行特征采用域分解方法设计交通并行仿真系统的框架,把交通网络分为几个子网,集群系统的每个节点机分别负责其中的一个子网,提出基于车辆数负载的网络分割算法来平衡各子网的负载量,并分析子网之间的通信机理.同时,在基于MPI 的并行计算平台上实现设计的并行仿真系统.通过实例表明,提出的并行算法能大大提高交通网络仿真的速度和效率.     

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.