A practical interconnection network RP(k) and its routing algorithms

Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-al     

并行计算模型

1.引言为提高系统性能,并行机系统设计者在体系结构上采用了多种新技术,然而目前并行软件(包括系统软件和应用软件)的研究和开发远远落后于体系结构的进步,即体系结构上的进步并未充分反映到并行软件的设计中。相比之下,串行计算和串行软件的研究是成功的,原因之一在于有一个简单而又代表了串行计算主要性能特征的计算模型(Random Ac-cess Machines,RAM)。而并行计算缺少这样一个简单、被广泛接受并在并行计算中起同等重要作用的模型。“确定少量的并行计算模型以作为程序设计语言的自然基础,并有助于高性能硬件的实现”,这一课题仍是国际公认的并行处理中具挑战性课题之一。     

适合在分布存储大规模并行处理系统上应用的块ADI算法

提出了适合在分布存储的大规模并行处理系统上应用的块ＡＤＩ算法，实现了计算和通讯的局部化，大大减少了通讯花费。在曙光１０００计算机上的数值试验表明，块ＡＤＩ算法比传统的ＡＤＩ方法具有更高的并行计算效率。     

并行计算性能的“双流”分析

The generalized speed-up is estimated according to the "double-stream" analyses. The term"decreasing ratio" is used to describe the influence of the hierarchical memory and the characteristics of parallel application on the performance. The optimization principles for parallel computation are also given.     

一种异步BSP模型及其程序优化技术

基于BSP模型，该文提出了异步计算模型（CSA－BSP）。该模型更准确地描述了并行机的性能参数，引导用户编写高效率的并行程序，在CSA－BSP模型下，两个进程异步执行的位置至多相差p-1个超步；基于程序的执行时间，作者分析了BSP、A－BSP和CSA－BSP程序的效率，得出CSA－BSP程序的效率是最高的，在曙光并行机上，用“红黑格法”和“矩阵乘法”进行了验证，和BSP模型相比，这两个CSA－BSP程序的效率分别提高20％和37％；同时，其进程执行时间和最大可以降低8％，因此，按照CSA－BSP模型编程对于提高程序效率和改善系统的吞吐率，都有良好的效果。     

并行计算时间模型和并行机系统性能

本文重点从共享存储器式并行机系统体系结构中的新技术和并行软件系统的新特点分析了影响并行算法和应用程序性能的各种因素，并提出改进的并行计划时间的模型，给给出了提高并行算法和软件性能的原则和实例。     

并行计算时间模型研究

本文系统地总结和探讨了共享和分布式存储环境下的并行计算时间模型。微观上，结合并行机结构特征和通信机制，揭示了延长算法运行时间的关键因素，并据此提出一些优化原则和效率评价准则，能辅助用户修改并行算法达到最优性能；宏观上，给出了基本消息传递的常用通信原语类型和部分原语操作时间经验公式，能辅助用户选择最优通信原语和问题粒度，正确预测程序的运行时间和性能。     

基于HPM模型的CoSMPs系统的算法并行与优化

首先，基于并行计算模型HPM，分析了多机机群系统的体系结构特点，从并行性和局部性(存储与通信特性)两方面分析影响并行应用软件性能的主要因素，讨论应用软件并行与优化的相关问题；分析了纯MPI和MPI SMP(或OMP)制导两种编程模式在性能上的优点与不足。然后，讨论了在GoSMFs系统上对并行应用软件进行优化的方法。最后，对两种不同的通信模式(循环交换、边界交换)在CoSMPs；系统上的性能进行讨论，并在多机机群系统的实例——DW3000超级服务器上进行优化；通过计算实例——矩阵乘法和解偏微分方程的五点格式算法加以验证，实算结果和理论分析一致。     

Cache性能与程序优化

超高速缓存是目前用来提高计算机性能的关键技术之一，而算法和程序优化对ｃａｃｈｅ性能的发挥起着重要作用。文中，我们提出一个提高ｃａｃｈｅ性能的优化方法，基本思想是用“加边”法改变ｃａｃｈｅ映射图象而减少冲突以提高ｃａｃｈｅ利用率。