Design and performance evaluation of load distribution strategies for multiple divisible loads on heterogeneous linear daisy chain networks

In this paper, we consider the problem of scheduling multiple divisible loads on heterogeneous linear daisy chain networks. Our objective is to design a load distribution strategy such that the total processing time of a set of loads is minimized. We assume that the set of loads are resident in one of the farthest end processors, which has a scheduler that will distribute the load to the other processors in the network. When distributing a load from the set, the distribution pattern of the previous load has to be taken into consideration to ensure that no processors are left idle and there are no collisions in the communication links. We design single and multi-installments strategies to achieve the above objective. We derive certain important conditions to determine whether an optimum solution exists. We propose two heuristic strategies when an optimum solution is unattainable. Using all the above strategies, we conduct four different simulation experiments to track the performance of strategies under several real-life situations. We conducted four different simulation experiments based on the two heuristic strategies to identify the best combination suitable for our multiple-loads distribution strategy. We also run simulations for a homogeneous system to quantify the performance under 3 different policies, that is, when the loads are (a) unsorted, (b) sorted with smallest load first (SLF) and (c) sorted with largest load first (LLF). A detailed analysis of the simulation results is presented and based on these, recommendations are made for the choice of strategies. Finally, we compare the performance of a single-load distribution strategy against the multiple-loads distribution strategy designed in this paper to quantify the exact performance gain that can be achieved. Illustrative examples are also provided for ease of understanding.     

异构机群系统上带返回信息的可分负载多轮调度算法

针对处理机具有不同的计算速度、通信能力的异构机群计算环境,以及实际应用中许多问题的求解在处理完任务后向中心处理机节点返回处理结果信息的情形,通过允许计算和通信操作重叠执行,采取FIFO调度策略和多次并行分配计算任务的方法,提出一种带返回结果信息的调度轮数可变的可分负载多轮调度算法.实验结果表明,该算法对于处理具有返回结果信息的应用的调度性能优于UMR可分负载多轮调度算法,并且可以获得近似最优的调度轮数.     

异构分层无线网络中基于业务和逗留时间的动态流量均衡算法

在异构分层无线网络中使用有效的流量均衡技术，可以给更多的移动用户提供服务。现有的流量均衡算法主要针对同种无线网络，因而不能直接用于异构无线网络。本文提出了一种适用于异构无线网络的基于业务和逗留时间的动态流量均衡算法，该算法首先根据移动模型计算移动用户在小区内的逗留时间，然后基于小区呼叫到达率和重叠覆盖小区的流量状态来确定一个周期内转移的非实时性呼叫数量，最后依据逗留时间门限值将重负载小区中满足条件的呼叫转移到轻负载的重叠覆盖小区中。为降低切换呼叫掉线率，还对异构网间的呼叫切换策略做了改进。仿真实验结果表明．本算法在新呼叫阻寒率和切换呼叫掉线率等性能指标上比传统方法有显著提高．     

Memetic Algorithms for Parallel Code Optimization

Discovering the optimum number of processors and the distribution of data on distributed memory parallel computers for a given algorithm is a demanding task. A memetic algorithm (MA) is proposed here to find the best number of processors and the best data distribution method to be used for each stage of a parallel program. Steady state memetic algorithm is compared with transgenerational memetic algorithm using different crossover operators and hill-climbing methods. A self-adaptive MA is also implemented, based on a multimeme strategy. All the experiments are carried out on computationally intensive, communication intensive, and mixed problem instances. The MA performs successfully for the illustrative problem instances.     

PORTING REGULAR APPLICATIONS ON HETEROGENEOUS WORKSTATION NETWORKS: PERFORMANCE ANALYSIS AND MODELING

Abstract

Heterogeneous networks of workstations and/or personal computers (NOW) are increasingly used as a powerful platform for the execution of parallel applications. When applications previously developed for traditional parallel machines (homogeneous and dedicated) are ported to NOWs, performance worsens owing in part to less efficient communications but more often to unbalancing.

In this paper, we address the problem of the efficient porting to heterogeneous NOWs of data-parallel applications originally developed using the SPMD paradigm for homogeneous parallel systems with regular topology like ring.

To achieve good performance, the computation time on the various machines composing the NOW must be as balanced as possible. This can be obtained in two ways: by using an heterogeneous data partition strategy with a single process per node, or by splitting homogeneously data among processes and assigning to each node a number of processes proportional to its computing power. The first method is however more difficult, since some modifications in the code are always needed, whereas the second approach requires very few changes.

We carry out a simplified but reliable analysis, and propose a simple model able to simulate performance in the various situations. Two test cases, matrix multiplication and computation of long-range interactions, are considered, obtaining a good agreement between simulated and experimental results.

Our analysis shows that an efficient porting of regular homogeneous data-parallel applications on heterogeneous NOWs is possible. Particularly, the approach based on multiple processes per node turns out to be a straightforward and effective way for achieving very satisfying performance in almost all situations, even dealing with highly heterogeneous systems.     

一种面向异构众核处理器的并行编译框架

异构众核处理器是面向高性能计算领域处理器发展的重要趋势,但其更为复杂的体系结构使得编程难的问题更加突出.针对这一问题,基于开源编译器Open64,提出了一种面向异构众核处理器的并行编译框架,将程序自动转换为异构并行程序.该框架主要包括4个模块：任务划分模块用来识别适合进行加速计算的程序段,实现了嵌套循环的多维并行识别方法;数据布局模块完成数据在主存和SPM之间的布局,实现了数组边界分析和指针范围分析;传输优化模块实现了数据传输合并、传输外提、打包传输、数组转置等多种数据传输优化方法;收益评估模块在构建代价模型的基础上实现了一种动静结合的收益评估方法.并且,基于SW26010处理器,对该编译框架进行了实现,测试结果表明,该编译框架能够实现一些程序以面向异构众核结构的并行变换,且获得较好的加速效果.     

异构系统中负载平衡扩散算法的加速方法

目前,很多单位与组织都有连接着数百台工作站和微机的局域网,并将它们作为一个机群系统使用.在这样的异构系统上动态负载平衡是提高性能的一个重要方法.扩散方法是同构系统的动态负载平衡算法.将散算法扩展到异构系统中,对异构系统中速度不同的处理机的位置与扩散收敛速度的关系进行了研究,提出了加速扩散算法的收敛速度的优化方法.初步实验证明,该方法能通过合理安排处理机,加快扩散算法的速度.     

Heterogeneous pipelined square-root Kalman Filter algorithm for the MMSE-OSIC problem

This paper describes a pipelined parallel algorithm for the MMSE-OSIC decoding procedure proposed in V-BLAST wireless MIMO systems, for heterogeneous networks of processors. It is based on a block version of the square-root Kalman Filter algorithm that was initially devised to solve the RLS problem. It has been parallelized in a pipelined way obtaining a good efficiency and scalability. The optimum load balancing for this parallel algorithm is dynamic, but we derive a static load balancing scheme with good performance.     

KMBox:基于Linux内核改造的进程异构冗余执行系统

随机化技术防御进程控制流劫持攻击, 是建立在攻击者无法了解当前内存地址空间布局的基础之上, 但是, 攻击者可以利用内存信息泄露绕过随机化防御获得 gadget 地址, 向程序注入由 gadget 地址构造的 payload, 继续实施控制流劫持攻击, 窃取敏感数据并夺取或破坏执行软件的系统。目前, 异构冗余执行系统是解决该问题的方法之一, 基本思想是同一程序运行多个多样化进程, 同时处理等效的程序输入。随机化技术使冗余的进程对恶意输入做出不同的输出, 同时正常功能不受影响。近年来,一些符合上述描述的系统已经被提出, 分析进程异构冗余执行系统的表决设计可以发现, 基于 ptrace 的实现方法会引入大量的上下文切换, 影响系统的执行效率。率先直接修改内核设计出一种进程异构冗余执行系统, 表决过程完全在内核中完成, 冗余的进程独立地采用内存地址空间随机化技术, 构建相互异构的内存地址空间布局, 在与内存信息泄露相关的系统调用处进行表决,发现泄露信息不一致, 阻断进程控制流劫持攻击。即使攻击者跳过内存信息泄露进行漏洞利用, 异构内存空间布局也使得注入由 gadget 地址构造的 payload 无法同时在冗余的进程中有效, 阻断进程控制流劫持攻击。实现了原型系统 KMBox, 实验证明该系统能够有效抵御进程控制流劫持攻击, 性能相较于基于 ptrace 的进程异构冗余执行系统有所提高。     

异构机群系统上基于多轮分配方式的近似串匹配并行算法

在给定正文串分配轮数的前提下,考虑处理机节点具有不同计算速度、不同通信能力的情形,根据从处理机是否允许重叠执行计算和通信操作,提出异构机群计算环境下的最优正文串多轮分配策略;同时提出一种周期性的正文串多轮分配策略并给出了相应的正文串多轮分配的闭合解,此策略可以求出最优的分配轮数.实验结果表明,正文串多轮分配策略比正文串单轮分配策略大大缩短了近似串匹配并行处理的时间,并且在正文串多轮分配策略中,当近似串匹配应用的规模较小时,分配轮数比参与近似串匹配并行处理的从处理机数更能影响近似串匹配并行处理的完成时间,反之,从处理机数对近似串匹配并行处理的完成时间影响更大.     

基于DDS的异构网络数据分发方法研究

在异构网络环境中,数据实现高效、可靠与安全的分发,面临着不同的应用环境对操作系统、通信方式、网络协议以及服务质量（ QoS）的多种要求。文中设计了一种基于DDS的,在异构网络通信中使用的数据分发系统。针对异构网络与DDS的特性,提出了异构网络数据分发系统的三层组织结构,并对每一层的具体内容,要实现的功能进行了研究。经过对异构网络中所传递的数据进行分析,结合OpenDDS本身的QoS策略推出该系统本身的QoS策略。最后,通过实验对该数据分发系统的网络延迟以及时延抖动进行了测试,表明了该系统能够有效满足异构网络之间的数据分发需求。     

Synchronisation and Load Balancing for Parallel Hierarchical Radiosity of Complex Scenes on a Heterogeneous Computer Network

In this paper we propose a SPMD parallel hierarchical radiosity algorithm relying on a novel partitioning method which may apply to any kind of architectural scene. This algorithm is based on MPI (Message Passing Interface), a communication library which allows the use of either a heterogeneous set of concurrent computers or a parallel computer or both. The database is stored on a common directory and accessed by all the processors (through NFS in case of a network of computers). As the objective is to handle complex scenes such as building interiors, to cope with the problem of memory size, only a subset of the database resides in memory of each processor. This subset is determined with the help of a partitioning into 3D cells, clustering and visibility calculations. A graph expressing visibility between the resulting clusters is determined, partitioned (with a new method based on classification of K-means type) and distributed amongst all the processors. Each processor is responsible for gathering energy (using the Gauss-Seidel method) only for its subset of clusters. In order to reduce the disk transfers due to downloading these subsets of clusters, we use an ordering strategy based on the traveling salesman algorithm. Dynamic load balancing relies on a task stealing approach while termination is detected by configuring the processors into a ring and moving a token around this ring. The parallel iterative resolution is of group iterative type. Its mathematical convergence is proven in the appendix.     

异构机群系统上近似串匹配并行算法

基于可分负载理论的最优原则,在假定正文串分配顺序固定的前提下,考虑处理机节点具有不同计算速度、不同通信能力的情况,提出一种异构机群计算环境下的最优正文串分配策略,给出最优正文串分配的闭合解。对于节点具有不同计算速度、通信能力、存储容量的异构机群系统,建立正文串最优分配的线性规划模型。针对几种特殊情况讨论正文串的最优分配顺序。实验结果表明,与平均分配正文串策略以及按照从处理机能力分配正文串策略相比,利用该策略进行近似串匹配并行处理所需时间分别缩短了10%~40%和5%~20%。     

异质信息网络分析与应用综述

实际系统往往由大量类型各异、彼此交互的组件构成.目前,大多数工作将这些交互系统建模为同质信息网络,并未考虑不同类型对象的复杂异质交互关系,因而造成大量信息损失.近年来,越来越多的研究者将这些交互数据建模为由不同类型节点和边构成的异质信息网络,从而利用网络中全面的结构信息和丰富的语义信息进行更精准的知识发现.特别是随着大...     

基于广域网和异构环境的ODS数据更新策略

为满足信息处理的多层次需求，为企业日常决策分析者提供即时准确的全局数据视图，出现了DB-ODS-DW 3层体系结构，其中ODS承担了承上启下的重要作用。该文就ODS中的关键技术——数据更新策略进行了深入的研究，在对比分析了ODS传统数据更新策略的基础上，提出了一种基于网络和异构环境下的ODS数据更新策略，利用XML技术实现了异构数据库环境下变化数据的更新，以及变化数据文件的高效传输，并在实际应用中获得了理想的效果。     

一种异构海量数据搜索方案

随着海量数据时代的到来,如何在异构海量数据中进行数据搜索成为一个迫切的问题。本文分析搜索技术的基本原理,比较现有的异构数据搜索方案,在此基础上,通过引入元数据技术,提出一种基于统一索引的异构海量数据搜索解决方案,并详叙基于开源技术的实现。     

Pipelines on heterogeneous systems: models and tools

We study the performance of pipeline algorithms in heterogeneous networks. The concept of heterogeneity is not only restricted to the differences in computational power of the nodes, but also refers to the network capabilities. We develop a skeleton tool that allows us an efficient block‐cyclic mapping of pipelines on heterogeneous systems. The tool supports pipelines with a number of stages much larger than the number of physical processors available. We derive an analytical formula that allows us to predict the performance of pipelines in heterogeneous systems. According to the analytical complexity formula, numerical strategies to solve the optimal mapping problem are proposed. The computational results prove the accuracy of the predictions and effectiveness of the approach. Copyright © 2005 John Wiley & Sons, Ltd.     

异构图卷积网络研究进展

现实世界中的很多场景都能用多种节点类型和边类型组成的异构网络表示。网络中蕴含着丰富语义关系,并具有实际应用价值,引起了学术界和工业界的关注。传统的方法都是基于浅层模型进行异构网络挖掘。近几年,由于图卷积网络在同构网络中表现优越,有许多学者将图卷积网络应用到异构网络的挖掘,在各个任务中都取得了优异的成绩。通过对异构图卷积网络的研究进展进行评述,来了解相关领域的发展状况。介绍了异构图卷积网络的发展,将异构图卷积网络分为基于元路径和自适应异构信息的模型进行详细介绍及归纳,并综合分析了不同的聚合方法。介绍了异构图卷积网络在推荐系统、生物化学、异常检测和自然语言处理中的应用。分析了异构图卷积网络未来面临的挑战以及值得研究的问题。     

Application Level Fault Tolerance in Heterogeneous Networks of Workstations

We have explored methods for checkpointing and restarting processes within the distributed object migration environment (Dome), a C++ library of data parallel objects that are automatically distributed over heterogeneous networks of workstations (NOWs). System level checkpointing methods, although transparent to the user, were rejected because they lack support for heterogeneity. We have implemented application level checkpointing which places the checkpoint and restart mechanisms within Dome's C++ objects. Application level checkpointing has been implemented with a library-based technique for the programmer and a more transparent preprocessor-based technique. Dome's implementation of checkpointing successfully checkpoints and restarts processes on different numbers of machines and different architectures. Results from executing Dome programs across a NOW with realistic failure rates have been experimentally determined and are compared with theoretical results. The overhead of checkpointing is found to be low, while providing substantial decreases in expected runtime on realistic systems.