基于消息传递的并行计算环境:MPI与PVM的比较

本文对在分布式计算中广泛应用的二种并行计算环境ＭＰＩ（Ｍｅｓｓａｇｅ Ｐａｓｓｉｎｇ Ｉｎｔｅｒｆａｃｅ）和ＰＶＭ（Ｐａｒａｌｌｅｌ Ｖｉｒｔｕａｌ Ｍａｃｈｉｎｅ）进行了比较。从ＭＰＩ和ＰＶＭ的设计思想出发,在可移植性、任务控制和分配、资源管理、容错、安全通信的上下文和多线程、通信方式、名字服务和消息句柄八个方面分析了它们各自的功能特点。     

基于消息传递模型的众核拓扑重配置容错方法

系统故障恢复时间是众核系统容错的一项重要指标.为加快系统故障恢复,在基于消息传递模型的众核系统中提出一种快速的拓扑重配置容错方法.首先根据物理拓扑故障情况为每个核心定义映射区域,利用匈牙利算法快速构建初始解;然后通过限制交错映射的发生,采用禁忌搜索在初始解的基础上快速优化,获得最终重配置映射解;最后根据重配置映射解更新各运算节点上的节点映射关系表完成拓扑重配置,实现众核系统的核级容错.实验结果表明,该方法能够快速找到优化的拓扑重配置方案并成功地完成系统恢复,具有较低的容错时间开销.     

基于集群的代谢网络计算平台研究

在生物代谢网络研究中,为提供面向多用户的高性能计算服务,开发了基于Linux计算机集群的代谢网络模拟Web计算平台.该平台以集群为密集计算后台,以重建心肌细胞能量代谢网络为算例,采用集中式任务调度模型、加权结合轮询法的负载平衡技术以及消息传递接口并行编程模型,实现了对多用户并发任务的处理.通过实例应用和调度监控,验证了该平台在代谢网络模拟中的可用性,以及集群服务器并行处理多任务的有效性.     

消息传递界面PVM和MPI的现状与发展趋势

ＰＶＭ和ＭＰＩ是目前国际上最有影响的两种消息传递并行计算环境，两者都能在ＭＰＰ和工作站网络上运行。由于设计背景和侧重点不同，使得这两种界面既有共同点，又各具特色。文中就性能和发展趋势对两者进行叙述和比较，可供并行程序开发者选择并行计算环境时参考。     

基于数据重平衡的AUC优化Boosting算法

接收者操作特性(Receiver operating characteristics, ROC)曲线下面积(Area under the ROC curve, AUC)常被用于度量分类器在整个类先验分布上的总体分类性能. 原始Boosting算法优化分类精度,但在AUC度量下并非最优. 提出了一种AUC优化Boosting改进算法,通过在原始Boosting迭代中引入数据重平衡操作,实现弱学习算法优化目标从精度向AUC的迁移. 实验结果表明,较之原始Boosting算法,新算法在AUC度量下能获得更好性能.     

基于HDFS的海量视频数据重分布算法

基于视频数据的分布式计算与基于文本类型数据的分布式计算存在很大的差异。视频数据本身是非结构化的,并且对于同样大小的视频,若其内容不同会导致任务执行消耗的时间也不同。对于简单的结构化数据,HDFS默认的负载均衡器能够解决负载均衡的问题。但是视频文件存在热点访问以及复杂度不一致的问题。使用HDFS默认的数据分布机制不能很好地解决计算负载均衡问题。因此提出了一种基于HDFS的海量视频数据重分布算法。首先对视频文件的访问次数以及历史视频分析对视频文件的访问时间进行记录;然后对数据进行量化之后将其加权作为该视频文件的负载度;最后使用文件置换手段将负载高的视频与低的视频进行置换,直到每个节点的负载达到均衡为止。实验结果表明,使用提出的数据重分布算法可以减少海量视频数据的处理时间。     

基于对象的消息传递

文中设计和实现了一个对象之间的消息传递系统,它比传统的对象之间的消息传递具有更好的灵活性和健壮性,充分体现了面向对象程序设计的特点。     

数据不规则问题并行计算的负载平衡策略的研究

讨论以边缘通信为特征的数据不规则问题并行计算的静态负载平衡策略。从图论的角度讨论了静态负载平衡问题,给出三个优化目标,即点集等分,最短通路和通信量最小。对于以边缘通信为特征的一般数值计算问题,论述了二维问题正方形划分总通信量最小、并行效率最高,三维问题立方体划分总通信量最小、并行效率最高的结论。基于以上结论和实际课题特点,提出一种一维优先的规则分块算法和基于自动重分块的不规则分块算法相结合的方法。实验证明,该方法实现简单,能够处理不同规模的数据不规则问题,达到较优的负载平衡和较高的通信效率,提高并行程序的整体效率．     

基于Linux的Beowulf集群的实现

中国科学院等离子体物理研究所是国内从事核聚变研究和托卡马克(Tokamak)实验的主要基地,由于实验研究的需要,有必要建立自己的大型并行计算机系统,进行托卡马克实验的数值模拟等研究课题。文章介绍了在普通PC机上利用Linux操作系统实现基于分布存储结构的Beowul集群系统的方法,同时也介绍了基于消息传递模型(Message Passing Interface,MPI)的并行程序设计方法。     

基于混合重采样的非平衡数据SVM训练方法

针对传统的SVM算法在非平衡数据分类中分类效果不理想的问题,提出一种基于分类超平面和SMOTE过采样方法(HB_SMOTE)。该方法首先对原始训练样本集使用WSVM算法找到分类超平面,然后按一定标准剔除负类中被错分的样本、靠近分类超平面的样本以及远离分类超平面的样本。在UCI数据集上的实验结果表明:与RU_SMOTE等重采样方法相比,HB_SMOTE方法对正类样本和负类样本都具有较高的分类准确率。     

基于网格的消息传递接口的实现:MPICH-G2

MPI(消息传递接口)作为一种著名的底层并行编程模型已被提出来作为网格编程的基础。描述了基于网格的消息传递接口的实现MPICH-G2,它基于MPICH和Gllobus工具包实现,在启动和管理中隐藏了异构性,具有良好的异构通讯性能。用一个例子说明如何在一个由Globus搭建的计算网格环境中通过MPICH-G2来创建和执行MPI计算。     

支持动态负载平衡的分层消息队列模型

中间件技术为解决异构分布式环境下的负载平衡问题提供了有力的工具,但传统的消息中间件负载平衡的实现较为复杂,其动态参数繁多且容易带来额外开销。提出了一种分层消息队列模型,该模型中利用队列组管理器对分布式队列进行组管理,并提供了丰富的任务分配策略。在该模型的基础上提出动态负载平衡实现方案:通过基于队列的阈值阈长模型实时监控成员队列的负载情况,采用集中式调度进行负载信息搜集和负载平衡决策,结合负载迁移和队列组管理进行过载处理。     

基于网格计算的混合负载均衡策略

根据分布式系统的静态和动态负载均衡策略的优缺点,提出了在网格计算环境下的混合负载均衡策略.为了让网络中节点在网格计算环境中有效地执行需要大量计算的复杂任务,提出了用来评估节点效率的函数,并结合模拟实验证实了在此函数下算法的优越性.     

基于联合权重超图划分的SNN负载均衡方法

大规模脉冲神经网络并行模拟是探究大脑机能的重要手段。其难点在于合理地将负载映射到并行分布式平台上,提升模拟速度。为解决该问题,提出一种基于联合权重超图划分的SNN负载均衡方法,解决并行计算中进程间计算负载与通信负载的均衡问题,提高SNN模拟速度。并使用稀疏通信的方式替代集体通信,解决事件通信过程中的数据冗余问题,提升通信效率。实验结果表明,该方法使带有STDP突触20%规模的皮质层微电路模型的模拟时间,比标准循环分配算法缩短约64.5%,比普通超图分配算法缩短约57.4%,同时事件通信数据量减少了90%以上。     

基于MPI的集群监控系统

为了有效地监控集群系统,基于消息传递接口（Message Passing Interface,MPI）并行库构建一个简单易行的并行任务模型．详细介绍该任务模型中的集群监控、节点负载均衡评估模型结构以及Linux集群数据采集．实验表明该模型配置简单、资源开销低,且对集群系统的干扰小．     

面向大规模数据接入系统的负载平衡机制

当前分布式系统负载平衡算法存在问题：1）算法建立的系统中各节点角色固定,系统不具有自适应性;2）算法的通用性不高;3）负载迁移任务巨大,且负载平衡周期过长等。针对这些问题,提出了混合式负载平衡算法。首先,设计了一个分布式系统接收模型。模型将系统任务分为三层：接收层、处理层和存储层。在接收层使用了自定义的通信协议提高系统的接收性能。然后,负载平衡算法采用随机负载迁移策略,根据系统中节点的负载状态,对负载任务进行随机迁移。通过这种策略解决负载平衡周期过长和负载回迁问题。最后,通过分布式控制节点选择策略,使系统中节点具有自适应性。实验结果显示,在百万数据源以下,系统各层平均延迟处于毫秒级,系统负载平衡平均耗时在3 min以下。实验证明了所提出的负载平衡机制具有周期短、任务响应迅速等特点,能够提高分布式系统的接收性能。     

基于移动代理的并行计算动态负载平衡

为解决网络计算平台异构性问题,目前的趋势是分布式技术和并行技术的结合。动态负载平衡是使用机群进行网络并行计算的关键,而获取节点的负载信息是实现动态负载平衡的前提。给出了一种利用移动代理技术获取节点负载信息的方法,该法不仅可实现上述平衡,且可大大减少网络并行计算中的通讯开销。     

Load balancing aware scheduling algorithms for fog networks

Fog networks have attracted the attention of researchers recently. The idea is that a part of the computation of a job/application can be performed by fog devices that are located at the network edge, close to the users. Executing latency sensitive applications on the cloud may not be feasible, owing to the significant communication delay involved between the user and the cloud data center (cdc). By the time the application traverses the network and reaches the cloud data center, it might already be too late. However, fog devices, also known as mobile data centers (mdcs), are capable of executing such latency sensitive applications. In this paper, we study the problem of balancing the application load while taking account of security constraints of jobs, across various mdcs in a fog network. In case a particular mdc does not have sufficient capacity to execute a job, the job needs to be migrated to some other mdc. To this end, we propose three heuristic algorithms: minimum distance, minimum load, and minimum hop distance and load (MHDL). In addition, we also propose an ILP-based algorithm called load balancing aware scheduling ILP (LASILP) for solving the task mapping and scheduling problem. The performance of the proposed algorithms have been compared with the cloud only algorithm and another heuristic algorithm called fog-cloud-placement (FCP). Simulation results performed on real-life workload traces reveal that the MHDL heuristic performs better as compared to other scheduling policies in the fog computing environment while meeting application privacy requirements.     

Renaming in synchronous message passing systems with Byzantine failures

We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when the original namespace of the processors is unbounded, this problem cannot be solved in an a priori bounded number of rounds for , where n is the size of the network and t is the number of failures. On the other hand, for n > 3t, we present a Byzantine renaming algorithm that runs in O(lg n) rounds. In addition, we present a fast, efficient strong renaming algorithm for n > t, which runs in rounds, where N ₀ is the value of the highest identifier among all the correct processors.     

基于禁忌搜索的流式计算平台负载均衡策略

针对大数据流式计算平台原生的调度机制存在计算负载分配不均衡、资源利用率低的问题,提出异构环境下基于禁忌搜索算法的负载均衡策略,并将其应用于Apache Flink平台。首先,通过构建作业拓扑模型将流式计算作业的拓扑结构抽象为有向无环图（directed acyclic graph,DAG）,并将每个任务槽（task slot）抽象为节点,为计算节点的性能评估奠定基础;其次,通过建立性能评估模型将有向无环图中带性能权值的节点导入性能评估模型,进行归一化处理得到节点性能的优劣;再将评估参数传入禁忌调度算法（tabu search for schedule,TBS）进行作业路径优化,从而得出最优作业路径;最后,使用Flink平台提供的CustomPatitionerWrapper接口将数据分配到最优作业路径包含的节点中,完成计算负载的均衡分配,从而提升Flink平台的整体性能。实验结果表明：通过禁忌调度算法优化后的负载均衡策略与原生的Flink平台相比,平均计算延迟降低了10~20 ms,资源利用率显著提高,平均吞吐量提升约15%,有效证明了负载均衡策略的有效性和优化效果。