高性能稀疏矩阵向量乘的程序设计综述

稀疏矩阵向量乘(SpMV)广泛应用于科学计算、图计算、数据分析等领域,是自现代计算机诞生以来经久不衰且挑战依旧的研究热点。本文系统回顾了20世纪70年代以来稀疏矩阵向量乘程序设计的发展脉络和各阶段的代表性工作;分析比较了这一领域4条技术路线,即人工程序设计、自动调优器、稀疏编译器和自动程序设计器,在当今的流行方法;并在此基础上对高性能稀疏矩阵向量乘程序设计的研究趋势做出预测,力图给学习者和研究者带来有益的知识与启示。

HPP:一种支持高性能和效用计算的体系结构

为了同时做到应对千万亿次高性能计算的技术挑战和满足数据中心(data center)未来的主要应用模式效用计算(utility computing)的需求,提出了一种称为HPP(Hyper Parallel Processing)的高性能计算机体系结构.HPP的主要特征是全局地址空间(global address space)和单一操作系统映像的超节点(hyper node).HPP结合了MPP的可扩展性,DSM的高效通信和机群的普及化的优点,为高性能计算和效用计算都提供了许多创新研究的机会.基于HPP体系结构,实现了一个曙光5000高性能计算机的原型系统,初步验证了它的可行性.

曙光2000超级计算机系统软件的设计

曙光 2 0 0 0超级计算机系统采用可扩展机群体系结构 ,是通用的超级并行计算机 ,可支持科学与工程计算、网络服务和数据处理应用 .该文介绍了曙光 2 0 0 0系统软件设计采用的 SU MA技术路线 ,即在通信软件、可扩展文件系统和服务器聚集的设计上体现可扩展性 ,在可靠性设计和可修复性功能上体现高可用性 ,在单一控制点和系统的管理软件的设计上体现可管理性 ,在单一系统映像、集成化并行环境和傻瓜界面的设计上体现好用性 .文章详细阐述了系统软件的设计和关键技术 ,包括通信系统、COSMOS可扩展文件系统、管理软件和用户界面与工具 ,还对系统软件中存在的问题和改进方法进行了探讨 .

曙光1000大规模并行计算机系统软件的设计

曙光１０００是基于消息传递的大规模并行计算机系统．本文介绍曙光１０００系统软件的设计目标、重要的微核心、用户空间服务、客户／服务模型和标准用户界面的设计思想，实现技术路线，以及组织结构，并详细阐述了系统诊断与监控，系统管理，并行程序开发环境与工具和调试器的设计．对大规模并行处理系统的系统软件存在的问题进行了探讨．

支持网格的机群操作系统的设计

机群操作系统面临着网格计算对其提出的资源共享、协同工作和自治管理的挑战 ,现有的扁平结构的机群操作系统不能够适应这种需求 .提出了一种基于服务的机群操作系统 DCOS,采用层次型结构和面向对象的设计思想 ,从多个角度为网格系统提供支持 .讨论了远程过程调用、系统状态侦测、实时检查点。

PHPC：一种普及型高性能计算机

高性能计算的一个发展方向是可扩展系统,当前主要是研究千万亿次计算的关键技术;另一个发展方向是普及型系统,为此我们提出了PHPC(personal high performance computer)的一组技术.PHPC的主要特征是:适合办公室环境、规模化产品、用户为中心的使用模式、面向生产率的编程模式.面向普及的个人高性能计算机提供了许多创新研究的机会.基于PHPC的思想,我们给出了称为KD-50-Ⅱ的龙芯万亿次个人高性能计算机的设计,初步验证了PHPC的可行性.

Dagger:一种散耦合的网格计算机体系结构

计算机系统面临着网格计算对其提出的资源共享、协同计算和应用服务的挑战 ,现有的计算机系统的体系结构不能够很好地适应这种需求 提出一种基于散耦合思想的网格计算机系统的体系结构 ,称之为DAGGER(De coupledAr chitecturewithGrid keyandGridEnablingResource) ,采用 8个基本概念构成网格计算机 。

曙光3000超级服务器设计的关键问题研究

曙光3000超级服务器是基于SMP机群体系结构的通用计算机系统,具有可扩展性、可用性、可管理性和高可用性的技术特点.该文着重介绍曙光3000系统设计中的若干关键问题,包括与SMP机群体系结构相关的可扩展性问题、系统软件中重要的可用性设计、底层通信的多种应用支持设计和机群管理系统的跨平台支持设计.另外还论述了超级服务器设计中存在的问题和作者的看法.

采用有效切分的负载平衡

负载平衡是影响分布式处理效率的关键。对于静态的负载平衡,特别是数值计算中的负载平衡已有不少研究成果,但是对于并行组合搜索等人工智能问题,由于负载的动态特性,现有的负载平衡算法的实际效果并不好。本文讨论动态的负载平衡,着重分析负载平衡对并行组合搜索效率的影响。本文的结果表明,任务切分的有效性是影响负载平衡时间开销的重要因素。我们在共享存储型多处理机ENCORE Multimax 520上模拟分布式计算,把有效切分策略应用于求解N皇后问题的并行深度优先搜索算法和求解旅行推销员问题的并行分枝限界算法中,获得了比已有结果更好的并行效率。

并行文件系统的设计

在大规模并行处理巨型机（ＭＰＰ）的设计中，提高Ｉ／Ｏ性能同提高计算能力和通信能力同样重要．并行文件系统（ＰＦＳ）在多个Ｉ／Ｏ结点的多个磁盘上，分布文件系统和文件的磁盘块，将文件读写在计算结点转化成多个对物理块的直接Ｉ／Ｏ请求，利用预读、预分配、磁盘缓冲区和异步Ｉ／Ｏ增加Ｉ／Ｏ的井发性，在特定的文件使用模式下，也是ＭＰＰ应用的主要Ｉ／Ｏ模式，获得很高的Ｉ／Ｏ效率．

Mach的I／O系统

ＭａｃｈＩ／Ｏ系统采用了和ＵＮＩＸ完全不同的概念和结构。Ｍａｃｈ设备管理围绕端口和存储对象这两个Ｍａｃｈ基本概念进行，提供了方便的ＲＰＣ用户界面。Ｍａｃｈ３．０的Ｉ／Ｏ系统新进展将Ｉ／Ｏ管理作为用户Ｓｅｒｖｅｒ对待。本文介绍了Ｍａｃｈ设备管理机制、“设备独立”的驱动程序的构造原理及其例子、在用户空间对设备的直接控制方法和引进新概念后设备管理的性能情况。

优先队列的并行插入和删除

优先队列广泛地使用在许多并行算法中(例如,多处理机调度和某些组合优化算法)。在这些算法中,共享优先队列的存取冲突限制了加速比的提高。本文提出一种链表优先队列的并行插入和删除方法,具有较小并行开销和较大的并行度,并且保证和串行存取算法的优先顺序完全一致,即删除操作返回已经插入和正在插入的所有元素中的最佳元素。同时,我们还介绍了目前性能最好的堆的并行插入和删除算法,并对准和链表结构并行插入和删除算法的性能和适用范围进行了比较,进一步提出了散列结构的优先队列。在ENCORE Multimax520多处理机上的实验结果验证了我们的理论分析结果:使用链表结构的并行分枝限界算法性能上可获得很大提高。

Transputer网络上分布式组合搜索的效率

Ｔｒａｎｓｐｕｔｅｒ网络是一种典型的消息传送型多处理机系统，无论是传统的数值计算，还是人工智能的动态非确定搜索问题，都可以得到加速处理。本文研究如何在Ｔｒａｎｓｐｕｔｅｒ网络上高效地实现分布式组合搜索。针对搜索的动态非确定性，我们提出一种异步通讯模式，以及Ｔｒａｎｓｐｕｔｅｒ上并行搜索的负载平衡算法。我们实现了最佳优先和启发式导向的深度优先两种策略的分布式分枝限界算法（Ｂｒａｎｃｈ－ａｎｄ－Ｂｏｕｎｄ），应用于求解旅行推销员问题（ＴＳＰ），在１６个Ｔｒａｎｓｐｕｔｅｒ上获得了较好的并行效率。

Mach端口管理及其应用

端口是Ｍａｃｈ操作系统最基本的概念。本文分析了Ｍａｃｈ端口的实现机制和使用方法，以及Ｍａｃｈ３．０系统服务器对端口的支持。还介绍了在Ｍａｃｈ３．０系统初启过程中端口的管理。

处理器芯片敏捷设计方法:问题与挑战

现有处理器芯片设计主要使用性能导向的设计方法,基于多步骤反复迭代的EDA技术进行性能-面积-功耗综合优化,导致极高的研发成本、周期及技术门槛.借鉴面向对象软件设计思想,以敏捷度(开发周期、开发成本和复杂度)为新的导向指标,在兼顾性能和可靠性的前提下,提出以面向对象体系结构(object-oriented architecture,OOA)设计范式为基础的处理器敏捷设计方法.OOA设计方法旨在通过设计范式、语言与EDA工具,实现通用处理器CPU和专用处理器XPU体系结构细粒度对象的易分解、易组合和易扩展.详细梳理了OOA各技术领域的研究现状,并深入探讨了现有处理器设计方法向OOA设计目标转化存在的诸多挑战.

计算机体系结构模拟器技术和发展

对计算机体系结构模拟器的技术和发展历程进行评述,从速度、精度和灵活性三个方面对领域需求和相关技术做了分类总结,分析了上述三个方面的难点并从模拟器实现和使用两个层面介绍了现有的解决方案;给出了模拟器目前面临的困境及下一步发展趋势;对体系结构模拟器的开发和使用给出几点建议。

关于一种网格运行时结构的若干注记

进程是传统计算机系统的一个核心概念 ,自 196 0年出现以来一直沿用至今 进程的一个主要目的是为主体提供一种运行时结构 ,在操作系统和处理器硬件支持下 ,代表主体访问和使用各种资源 与传统的单机和并行机计算平台相比 ,网格计算机中进程所对应的概念面临新的挑战 ,包括网格资源繁杂、自主控制的条件下的单一系统映像和资源的共享与协同、与特定操作系统的松耦合、时间和空间的流动性、更高级的交互性 提出一种称为网程 (grip)的运行时结构 ,试图解决上述问题 网程运行在网格操作系统之上 ,代表网格主体 。

基于GPU的串匹配算法研究

BF算法是串匹配算法中最基础的算法,但它是串行算法,不适合图形处理器(GraphicProcessing Unit,GPU)的体系结构。结合GPU的特殊体系结构,通过数据存取方式和计算策略的改进,充分利用了GPU的并行处理能力,从而基于GPU实现了BF算法。实验结果表明基于GPU的并行算法能够取得较好的加速比,同时也给出了在现有GPU架构上有效实现通用计算的瓶颈。

基于单根I/O虚拟化的多根I/O资源池化方法

虚拟化技术在为现代数据中心提供高效的服务器整合能力和灵活的应用部署能力的同时,也对数据中心服务器的I/O系统设计提出了新的需求,现有I/O资源与服务器紧密绑定的I/O体系架构将产生成本上升、资源冗余、I/O连线复杂化等一系列问题.针对上述问题,提出了一种基于单根I/O虚拟化协议(single root I/O virtualization,SR-IOV)的多根I/O资源池化方法:基于硬件的多根域间地址和ID映射机制,实现了多个物理服务器对同一I/O设备的共享复用,有效减少单体服务器所需的设备数量和连线数量,并进一步提高服务器密度;同时提出虚拟I/O设备热插拔技术和多根共享管理机制,实现了虚拟I/O资源在服务器间的实时动态分配,提高资源的利用效率.提出的方法在可编程逻辑器件(fieid-programmable gate array,FPGA)原型系统中进行了验证,其评测表明,方法能够在实现多根I/O虚拟化共享的同时,保证各个根节点服务器获得近乎本地直连设备的I/O性能.

一种面向科学计算的数据流优化方法

传统数据流结构通过多上下文来隐藏指令等待源操作数的延迟,然而这种隐藏方式只能部分提高数据流处理器执行单元的利用率.在面向例如Stencil、FFT和矩阵乘法等典型科学应用时,传统数据流结构的执行单元利用率仍然较低.科学计算中的核心程序一般是对不同数据进行相同的操作,而且这些操作可以并行执行,数据之间没有直接依赖关系.传统数据流结构是面向通用计算的,通常采用循环来实现对不同数据的相同操作.在这些循环中,迭代是按照顺序依次执行的,这导致了传统数据流结构没有利用科学计算的并行性来提高性能.所以传统数据流结构在处理这些规则的科学应用时没有协调好数据流计算模式和科学计算特征,而数据流计算是非常适合科学计算这种类型的规则计算.基于科学计算的这些特征,该文提出了一种面向科学计算的数据流结构优化方法:循环流水优化方法.循环流水优化方法利用科学计算的分块和并行处理特征,对传统数据流结构中的上下文控制逻辑进行了改进,将科学计算中的循环采用硬件自迭代的方式实现,并将上下文切换逻辑进行了流水化,使数据流结构中的上下文以流水线方式进入执行单元阵列,从而提高计算单元的利用率.面对这种循环流水优化后的数据流结构,传统数据流结构上的指令映射算法不再适用.通过分析循环流水优化后的结构特征,该文进一步提出了一种改进的指令映射算法:LBC(Load Balance Centric)指令映射算法.LBC算法按照深度优先顺序依次映射数据流图中的所有指令,对每条指令分别计算执行单元阵列中所有位置的代价,取最小代价的位置作为最佳映射位置.LBC算法以执行单元负载均衡为核心,同时将定点指令和浮点指令分开处理,保证执行单元上的定点部件和浮点部件的负载均衡.每当映射一条指令时,LBC算法采用相邻节点传输延迟与已经映射的该类型指令数量的乘积作为负载代价,来实现计算部件的负载均衡.另外,LBC算法将网络拥堵也作为指令映射的影响因素.LBC算法将节点与所有父节点的距离之和作为传输代价,使指令间传输消息的路径最短,从而减小片上网络消息传递的跳数.实验结果表明,在处理典型科学应用时,相比于传统数据流结构,循环流水的优化方法将数据流结构的性能平均提高了4.6%.相比于传统指令映射算法SPDI和SPS,在循环流水优化后的数据流结构上,LBC指令映射算法将性能分别平均提升了182.6%和158.1%.