面向互联网的计算资源共享平台容错机制研究

描述了面向互联网的计算资源共享平台下的新型容错机制.该框架采用服务器端、调度节点,志愿机的层次网络体系结构,把调度节点的主-从备份容错与志愿机端的面向子任务的容错结合起来,保证了系统的最终计算结果不受影响.通过运行电力系统潮流计算的并行程序,对该系统的稳定性与可扩展性进行实验,小规模测试验证了该容错机制的正确性与高效性.     

一种片上网络的低延迟容错算法

为解决片上网络容错问题,利用端到端模式设计一种低延迟可靠传输算法。该算法利用发送端主动发送冗余数据包获得较小的延迟,将数据分成包集以提高链路利用率,进一步降低延迟。发送端只在收到接收端对当前包集的确认后才发送下一个包集的数据,由此保证高可靠性。通过不断发送数据包及端到端的反馈保证传输的正确性。NS-2仿真实验结果证明,该算法延迟低,片上通信可靠性高,可以有效处理传输过程中的瞬时错误。     

MEPaxos:低延迟的共识算法

共识问题作为分布式计算中最重要的基本问题之一,被广泛应用在状态机复制、原子广播、领导者选举等领域。解决共识问题的算法通常存在单领导者性能瓶颈、响应延迟受命令冲突的影响等问题。针对这些问题,在非拜占庭故障下的异步分布式系统中,提出了一种低延迟的共识算法MEPaxos(modified Egalitarian Paxos)。首先,提出了系统平均延迟的计算方法;然后,引入超时机制对二阶段提交算法进行改进;接着,根据系统平均延迟计算结果,利用改进的二阶段提交算法自动选择平均延迟较小的算法模式执行;最后,在亚马逊弹性计算云(elastic compute cloud,EC2)平台上将此算法与当前共识算法进行实验对比分析,结果表明,MEPaxos算法下,系统延迟性能得到了提升。     

基于树型层次结构的计算资源共享与聚集

提出并描述了一个基于树型层次结构的计算资源共享与聚集系统(tree-based layered sharing and aggregation,TLSA).TLSA系统由对等网络环境下的空闲节点组成,形成一个类似B树的层次结构,使在节点加入和退出的时候可以自动的维持平衡.树型结构的网络拓扑通过自组织的可用性协议来维护,保证了系统的比较低的消息通信量和平衡的处理器负载.通过内部的资源发现协议,节点可以寻找到系统中最近最合适的空闲计算资源来完成大量的子任务.通过模拟测试结果表明对于大规模的子任务,TLSA可以在很短的时间内寻找到空闲资源,而且网络消息通信量不超过O(logmN),具有低消息通信量、非集中性、可扩展性、自组织等特性.     

超级计算环境容错机制

中国科学院超级计算环境是整合了包括总中心、分中心和所级中心计算资源的3层架构超级计算环境.为提升超级计算环境的可靠性,提供稳定、可靠的计算服务,其容错机制的研究成为超级计算环境的一个研究重点.在对容错基本思想及各类计算机容错技术进行充分调研的基础上,提出一种适用于超级计算环境的容错框架,依据该框架给出了不同层次的容错方案,并对不同层次的容错开销进行了分析和比较,验证了不同层次容错方案对应用程序所带来的影响.     

因特网上基于.NET的通用计算资源共享环境

为了高效与方便地聚集异构环境下的网络资源,提出一种基于.NET的通用计算资源共享环境GCRSE。GCRSE在体系结构上利用了节点功能角色的方式,由服务器功能实体、自愿机功能实体和客户机功能实体组成。它利用.NET的Web services技术,通过网页的方式提交、执行与传输并行分布式应用相关的任务和子任务。在编程模型上支持普通的主—从模式的编程模式和具有子任务递归迭代的分治模式编程。自愿机端的心跳消息和面向子任务的容错方式可以达到可靠性高的效果。GCRSE的测试环境通过局域网内的若干台自愿机组成,选择了具有数据依赖的分布式旅行商(TSP)问题进行测试,结果表明对于分布式计算中大量的子任务GCRSE环境可以很快地完成,具有高效性、可扩展性和通用性的特点。     

异构环境下空闲计算资源的共享与聚集

描述异构环境下的空闲计算资源共享与聚集平台DCSA。DCSA是一种通用的、可扩展与高效并行化的平台,在该环境下可以较容易地使用高级别的方式编写并行程序,把各种不同的软硬环境下的机器整合到单一的系统环境,共同完成高性能科学计算问题。DCSA的通用性得益于统一的XML文档来描述任务与计算结果及灵活的编程模型。利用一个轻量级的检查点机制与高度可配置的通信机制保证了DCSA的容错性与高效性。通过对实际并行例程的案例分析,验证了DCSA的正确性与高效性。     

多域网络环境下的计算资源共享平台的构建

描述了一个多域网络环境下的计算资源共享平台MD-CRSP(multi-domain computing resource sharing platform).MD-CRSP参考了当前网格计算平台,以中间件软件的方式把处于不同机构、私有网络区域的计算资源共享与聚集起来.MD-CRSP被设计成支持自定义的抽象组件集的形式,它对并行应用的实现可以动态的满足用户的需求.通过构建测试环境与运行并行应用程序表明,MD-CRSP具有灵活编程性、高效性,在类似的配置条件下,计算速度快于当前的一些中问件软件.     

MapReduce框架下结合分布式编码计算的容错算法

随着分布式系统规模扩大及计算复杂度增加,分布式计算的平均故障修复时间和容错计算所产生的通信开销呈现日益上升趋势.结合分布式编码计算和副本冗余技术,提出一种新的容错算法.map节点应用分布式编码计算的思想,将数据冗余分配至多个计算节点创建编码中间结果,降低计算节点在shuffle阶段的数据传输量.reduce节点通过对接...     

因特网上基于节点角色的计算资源共享平台——RB-CRSP

提出了因特网上基于节点角色的计算资源共享平台——RB-CRSP。设计时充分考虑节点的角色性和功能性,把因特网上的网络资源按照角色划分为服务器端节点、协调节点、工作机节点与客户机节点四类实体,通过配合RB-CRSP的应用编程模式,完成并行分布式计算。分析了RB-CRSP中的自适应资源调度策略,该策略考虑了节点的硬件信息与可信誉机制,实现了平台的负载均衡性;在动态的因特网环境下,利用面向工作机的容错方式保证了平台的可靠性。案例程序选择了典型的并行BenchMark程序：N皇后问题,测试结果表明,RB-CRSP可以方便聚集异构环境下的空闲计算资源,平台的性能与机器硬件条件和可靠性密切相关。     

基于Jini技术的互联网计算资源共享框架

描述了一个基于Jini技术的互联网计算资源共享框架JiniFrame,JiniFrame框架把互联网环境下的机器按照功能角色分为客户机、代理机和主机3种实体,共同协作完成并行应用的求解.JiniFrarne框架的可扩展性和跨平台性得益于基于Java的Jini技术,易用性与编程灵活性得益于框架中网络节点的组织方式与灵活的编程模型,同时支持主从模式与分治模式的编程.通过对实际分布式计算任务的案例分析与实验,表明了JiniFrame框架的正确性与高效性.     

利用结构化对等网络构造计算资源共享平台

设计和构建了一个基于结构化对等网络的计算资源共享平台DHT-CRSP。它可以把因特网上用户提交的科学计算作业高效地映射到平台中合适的工作节点上运行,通过容错和安全机制,能保证系统的可靠性和正确性。描述了DHT-CRSP中支持的两种分布式哈希表：Chord协议节点树和CAN协议空间区域;分析了DHT-CRSP中高效的资源匹配算法。通过构建评测环境,运行各种负载与作业场景下的结果表明,DHT-CRSP系统可以获得好的负载均衡性能、低的资源匹配代价,它提供了一种构建高性能的桌面网格平台的新思路。     

计算资源受限的移动边缘计算服务器收益优化策略

移动边缘计算（MEC）服务器通过向用户提供计算资源获得收益。对MEC服务器而言,如何在计算资源受限的情况下提高自身收益至关重要,为此提出一种通过优化计算任务执行次序提高MEC服务器收益的策略。首先,将MEC服务器收益最大化问题建模为以任务执行次序为优化变量的优化问题;然后提出了一种基于分支定界法的算法求解任务执行次序。仿真结果表明,采用所提算法获得的MEC服务器平均收益分别比大任务优先（LTF）算法、低延迟任务优先（LLTF）算法和先到先服务（FCFS）算法提高了11%、14%和21%。在保证卸载用户服务质量（QoS）同时,所提策略可以显著提高服务器的收益。     

计算资源共享平台中非集中式的元数据管理

提出了计算资源共享平台中的一种非集中式元数据管理方法,它利用对等网络的方式把数据和元数据分散到网络上的其他节点,而不是在后台服务器端。该方法可以在平台运行数据密集型应用时支持大容量的并行工作机读写数据,同时具有随机的访问、灵活的访问粒度、支持高负载的并行读写的特点。运用了分布式哈希表技术,把大容量元数据划分成树型结构的分段树的形式。描述了数据与元数据的读写与追加新数据的过程。测试结果表明：该方法针对3D图像渲染类数据密集型应用,在不同的工作机并行访问与读写过程中,可以获得很高的聚集带宽与平均读写带宽。     

基于Charm++运行时环境的异构计算应用容错研究

容错问题是大规模并行程序长时间运行中不可回避的问题,超级计算机中异构计算部件的加入使得该问题更加复杂。考察由CPU和GPU组成的异构并行系统中应用程序的容错,利用Charm++并行编程模型和CUDA的并行计算架构,对大规模计算宇宙学软件WIGEON进行重构。针对异构并行系统中存在的fail-stop硬件故障,设计并实现了内存检查点的应用容错机制。支持计算恢复后对产生变化的CPU/GPU资源配置进行自适应负载调整。通过在高性能计算机Mole8.5上的实验和分析,验证了异构容错方案的高效性和可行性,故障恢复时间仅需1~4 s。此外,使用分布式冗余数据改进了Charm++现有内存检查点存储模式,对比原有Double-in-Memory机制,性能未受影响,且最多降低了50%的额外内存使用量。     

Algorithm-based fault tolerance applied to high performance computing

We present a new approach to fault tolerance for High Performance Computing system. Our approach is based on a careful adaptation of the Algorithm-Based Fault Tolerance technique [K. Huang, J. Abraham, Algorithm-based fault tolerance for matrix operations, IEEE Transactions on Computers (Spec. Issue Reliable & Fault-Tolerant Comp.) 33 (1984) 518–528] to the need of parallel distributed computation. We obtain a strongly scalable mechanism for fault tolerance. We can also detect and correct errors (bit-flip) on the fly of a computation. To assess the viability of our approach, we have developed a fault-tolerant matrix–matrix multiplication subroutine and we propose some models to predict its running time. Our parallel fault-tolerant matrix–matrix multiplication scores 1.4 TFLOPS on 484 processors (cluster jacquard.nersc.gov) and returns a correct result while one process failure has happened. This represents 65% of the machine peak efficiency and less than 12% overhead with respect to the fastest failure-free implementation. We predict (and have observed) that, as we increase the processor count, the overhead of the fault tolerance drops significantly.     

Solving a vehicle routing problem with resource conflicts and makespan objective with an application in car body manufacturing

We investigate the problem of dispatching arc welding robots in car body manufacturing. Such arc welding robots receive their energy from expensive laser sources. Laser sources can be shared among the robots. However, this requires that the robots be scheduled because each laser source can only be used by one robot at a time. We want to compute the minimal number of laser sources necessary to perform all welding tasks in a given processing time. To this end, we introduce the laser-sharing problem (LSP): for a given number of laser sources, find collision-free scheduled tours for all robots through all welding jobs so that the makespan is minimized. We propose a branch-and-bound algorithm for the LSP using bounds that stem from optimal solutions to carefully selected NP-hard combinatorial subproblems. This is the first algorithm for the LSP that is able to solve industrially relevant problem scales.