Mbius立方体互连网络上的圈嵌入算法

图嵌入技术是研究多处理器互连网络模拟其它网络的能力的重要技术．文中讨论了近年提出的一类互连网络——Ｍｏｂｉｕｓ立方体上的圈嵌入性质．Ｍｏｂｉｕｓ立方体是超立方体的变型，它们具有一些比超立方体更优越的性质，如ｎ维Ｍｏｂｉｕｓ立方体Ｍｎ的直径大约是ｎ维超立方体的一半，其期望距离大约是ｎ维超立方体的２３等．文中证明了Ｍｏｂｉｕｓ立方体另一个比超方体优越的性质，即任一长度为ｌ（４≤ｌ≤２ｎ）的圈能以扩张ｌ嵌入ｎ维Ｍｏｂｉｕｓ立方体Ｍｎ（ｎ≥２），并给出了构造过程，从而也证明Ｍｎ对环网络的模拟能力比超立方体的高（超立方体不含奇长圈）．     

关于p－m度的分裂

本文讨论多项式时间多一可化归度（ｐ－ｍ度）的分裂间题．主要结果是：存在非零的ｐ－ｍ度ａ，对任何自然数ｎ≥１当ａ分裂成ｎ＋１个度ａ₀，ａ₁，…，ａ_n的并时，其中至少有ｎ对（ａ_i，ａ_j）（ｉ≠ｊ；ｉ，ｊ≤ｎ）不是极小对．从而推广了Ａｍｂｏｓ－Ｓｐｉｅｓ中关于存在非零ｐ—ｍ度ａ不能分裂成一个极小对的结果．     

基于散列和归并技术的有效并行排序方法

本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法：将长度为ｎ的待排序数据划分成ｐ个长度为ｎ／ｐ的子序列，引入散列技术并行地对这ｐ个子序列的数据进行二次散列排序，这一阶段所需的平均时间为Ｏ（ｎ／ｐ）；最后并行地将ｐ个有序子序列归并成一个长度为ｎ的有序序列，归并阶段所需的时间为Ｏ（ｎ－ｎ／
／ｐ）。整个排序算法的并行执行代价为Ｏ（ｎｐ）。本排序方法可以拓以网络并行机群环境。     

关于排列集p（n,r）的几种有效算法

本文在按字典排序的前提下，给出了生成排列集ｐ（ｎ，ｒ）的枚举算法，为建立ｐ（ｎ，ｒ）与它的反相集合的映射及逆映射，提供了一对编解码算法；在此编解码算法的基础上，为建立ｐ（ｎ，ｒ）与ｚ＝｛１，２，…，│ｐ（ｎ，ｒ）│｝之间的一一映射关系，还给出了相应的排序和逆排序算法。实际上，我们给出的这些算法，与已知的算法相比，更具有普遍性和优越性。     

Moebius立方体互连网络上的圈嵌入算法

图嵌入技术是研究多处理互连网络模拟其它网络的能力的重要技术，文中讨论了近年提出的一类互连网络－Ｍｏｕｂｉｕｓ立体体上的圈嵌入性质，Ｍｏｕｂｉｕｓ立方体是超立方体的变型，它们具有一些比超立文体更优越的性质，如ｎ维Ｍｏｅｂｉｕｓ立体体Ｍｎ的直径大约是ｎ维超立体的一半，其期望距离大约是ｎ维超立方体的２／３等，文中证明了Ｍｏｅｂｉｕｓ立方体另一个比超方体优越的性质，即任一长度为ｌ（４≤ｌ≤２＾ｎ）的圈能以     

LogP模型上一类蝶式计算的通信策略

本文研究ＬｏｇＰ模型上一类蝶式计算中的通信问题。以ＦＦＴ的并行计算为例，通过仔细安排消息的发送顺序，使得由有限带宽引起的延迟与局部计算重叠，在ｇ－ｌｏｇｇ＋１≤ｌｏｇｐ（ｐ为处理器数，ｇ为带宽因子）的条件下，只要输入长度ｎ满足最基本的要求（ｎ≥２ｐ＾２），ｇ便被完全隐含于局部计算中，算法时间复杂度可达到最优。最后与文献［１］的结果比较，分析了它们的优缺点及各自的适用范围。     

最长公共子充列问题的改进快速算法

现在几个最常用的解决最长公共子序列（ＬＣＳ）问题的算法的时间复杂度分别是Ｏ（ｐｎ）,Ｏ（ｎ（ｍｐ））。这里Ｍ、ｎ为两个待比较字符串的长度,Ｐ是最长公共子串的长度。给出一种时间复杂度为Ｏ（ｐ（ｍｐ））,空间复杂度为Ｏ（ｍ＋ｎ）的算法。与以前的算法相比,不管在Ｐ〈〈ｍ的情况下,还是在Ｐ接近Ｍ时,这种算法都有更快的速度。     

完全欧几里德距离变换的最优算法

欧几里德距离变换（ＥＤＴ）对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离，应用于图象分析，计算机视觉，在本文之前，该问题的最好复杂度为Ｏ（ｎ＾２ｌｏｇｎ）。本文提出了一个复杂度为Ｏ（ｎ＾２）的算法，使复杂度达到最优，该算法可以并行化，在有ｒ个处理单元的ＥＲＥＷＰＲＡＭ计算模型上，若ｒｌｏｇｒ≤２２／６ｎ，则时间复杂度为Ｏ（ｎ／ｒ）否则为Ｏ（ｎｌｏｇｒ）。     

Z^＊pq中离散对数问题的安全谓词

本文讨论了Ｚ＾＊ｎ（ｎ＝ｐｑ，ｐ和ｑ未知）中离散对数问题的一些基本概念及问题本身的难度；定义了Ｚ＾＊ｎ中离散对数问题中关于判断主平方根的谓词Ｂｎ，ａ（ｘ），证明了谓词Ｂｎ，ａ（ｘ）即为Ｚ＾＊ｎ中离散对数问题的安全谓词。     

多项式族左扇区稳定的最大摄动区间

已知多项式ｐ（ｓ，ｒ）＝ｘ∑ｉ＝０ａｉ（ｒ）ｓ＾ｉ。其中诸系数ａｉ（ｒ）（ｉ＝０，１，…，ｎ）为参量ｒ的多项式函数且ｐ（ｓ，０）是左扇区稳定的多项式，本文给出ｒ的最大摄动区间以使对这区间中的所有ｒ．多项式ｐ（ｓ，ｒ）都是左扇区稳定的，     

Study on Parallel Computing

In this paper, we present a general survey on parallel computing. The main contents include parallel computer system which is the hardware platform of parallel computing, parallel algorithm which is the theoretical base of parallel computing, parallel programming which is the software support of parallel computing. After that, we also introduce some parallel applications and enabling technologies. We argue that parallel computing research should form an integrated methodology of ＂architecture algorithm programming application＂. Only in this way, parallel computing research becomes continuous development and more realistic.     

基于PRAM并行模型最大值查找的方法与改进

随着多处理器的出现,并行技术受到了广泛的关注,成为了加速处理问题速度的重要技术.但是使用并行技术在加速计算的同时也带来了对处理器数量需求的急剧提升,并行成本的显著增加.针对这一问题,通过研究基于PRAM （Parallel Random Access Machine）下的3种最大值查找并行算法中的不足,提出了一种比平衡树算法,快速查找法,双对数深度树方法并行成本（cost）更优的基于数据划分方法的最大值查找并行算法.基于数据划分方法的最大值查找算法有效的解决了现有并行方法中处理器工作量分配不均,对处理器需求过大,实现条件苛刻等问题.为此后类似并行算法降低并行成本提供一个方向.     

The Hydra Parallel Programming System

The Hydra Parallel Programming System, a new parallel language extension to Java, and its supporting software are described. It is a fairly simple yet powerful language designed to address a number of areas that have not received much attention. One of these areas is the recompilation of parallel programs at runtime to allow a parallel program to adapt to the architecture it is executing on. The first version of this software system focuses on smaller Symmetric Multiprocessing and compatible architectures which are becoming more common. This particular class of machines has a great need for more options in the area of parallel programming among the vastly popular Java language programmers. Hydra programs will run as sequential Java on machines that do not have the parallel support or do not have an implemented Hydra runtime system without requirement of any modifications to the program. This paper describes the language, compares it with other languages (specifically with JOMP, an OpenMP implementation for Java), presents a brief discussion on compiling and executing Hydra programs, presents some sample benchmarks and their performance on three platforms, and concludes with a discussion of issues and future directions for Hydra. Copyright © 2007 John Wiley & Sons, Ltd.     

NOW系统上的并行快速排序算法

介绍了在NOW系统上的并行快速排序算法的设计与实现，分析了影响算法性能的因素及改进方法，最后给出了该算法对字符串排序的并行效率为49．15％。     

基于COW系统的并行求和算法研究

针对并行求和问题,在Linux环境下组建了一个COW系统,并介绍了在COW系统上的并行求和算法的设计和实现,分析了影响算法性能的因素并提出改进方法,最后给出了并行求和算法在改进前后的实验数据。实验结果表明,当n=2000000时,用改进的算法在两台联想启天4000上测得并行求和效率为80%,而算法改进前在相同的条件下测得并行效率为66.7%,并行效率明显提高。     

近优可扩展性：一种实用的可扩展性度量

良好的可扩展性是并行算法和并行机设计人员追求的一项重要性能指标,以往的可扩展模型都只是孤立地考虑了问题的某个侧面,比如某种性能或最大可利用资源,而没有从整体上进行权衡。这些可扩展模型可以满足计算机研究人员的需要,因为他们关注于更高的效率和利用率。但应用科学家更强调短小的执行时间。文中提出的近优可扩展模型,它同时考虑了并行系统的效率和执行两个因素。在一个典型MPP上的两个算法实例分析表明,该可扩展模型不仅可以描述并行算法的可扩展能力,而且,当按照适当的可扩展曲线扩展时,可以使得执行时间接近量短,而效率不低,这对算法和并行机的最优匹配有指导作用,同时有益于并行算法设计和改进。     

关于并行随机数发生器的若干算法

１．引 言 随机数发生器是 Ｍｏｎｔｅ Ｃａｒｌｏ模拟方法的最基本工具．并行计算机的出现和发展,为并行 Ｍｏｎｔｅ Ｃａｒｌｏ方法的研究提供了有力的工具．Ｍｏｎｔｅ Ｃａｒｌｏ方法本身具有很强的并行性,但是,要把在串行计算机上使用Ｍｏｎｔｅ Ｃａｒｌｏ方法程序移植到并行计算机上运行,首先就需要解决随机数发生器的并行化问题．针对各类不同的并行计算机结构,可以构成不同的并行随机数发生器的算法． 乘同余发生器是应用最广泛的随机数发生器之一,无论是在串行计算机上,还是在并行计算机上都具有极大的影响和深人的应用．…     

基于异构多核的CCA并行构件模型

并行构件技术的出现提高了并行软件的开发效率,但现有的并行构件技术缺乏对异构多核平台的支持.为了提高并行构件程序在异构平台上的执行性能,扩展CCA(通用构件体系结构)并行构件模型支持CCA异构并行构件,提出了一种异构的CCA并行构件模型.使用管理者—工人模式调度CCA异构并行构件内的计算任务到异构多核平台上加速执行.在CCA构件工具包的基础上实现了支持扩展CCA并行构件模型的编译系统和运行时框架.在CELL BE和GPU两种异构多核处理器上进行的实验证明了提出的方法比原始的CCA构件程序具有较优的性能.提出的并行构件模型应用在并行程序开发中可以提高并行程序的性能.     

基于面向方面和运行时反射技术的并行框架

针对使用并行库JOMP的程序在性能方面存在的不足,提出一个可以分离并行逻辑和功能逻辑的并行框架。该框架对程序中需要并行处理的部分进行标记,采用面向方面和运行时反射技术实现被标记部分的处理,其中面向方面技术用于实现并行逻辑的分离和编织,运行时反射技术用于获取运行时被标记部分的相关信息,以并行库(waxberry)的方式实现了该并行框架。使用基准测试程序JGF套件中的三个测试程序对并行库进行了测试,实验结果表明,应用该并行库的程序可以获得较好的性能。     

非结构粘性直角网格并行算法建立与应用

开展了基于粘性直角非结构网格的并行CFD解算软件的开发研究,工作分两部分：网格分区实现和解算器并行实施,文章介绍了关于CFD解算器并行的实施情况,给出了并行过程中的操作流程,并对一些关键问题进行了讨论。并行计算结果表明项目所采用的并行途径和方法有效,计算结果可靠。