一类广函数——纵横矩阵加工广函数  

A Kind of Wide-Function: The Vertical-Horizontal Array Processing Wide-Function

作　　者：高庆狮[1] 胡玥[1] 

机构地区：[1]北京科技大学信息学院计算机系

出　　处：《计算机学报》2005年第11期1767-1777,共11页Chinese Journal of Computers

基　　金：国家自然科学基金(60083008);中国科学院计算技术研究所创新经费支持项目(20016250)资助

摘　　要：提出具有某些相同算法特征的广函数的概念,并且具体讨论了纵横矩阵加工广算法这一类广算法的定义和定理,直接推导出这类广算法的串行、倍增并行、纵横并行、多维并行等各种不同的算法.进一步以Bitonic排序问题和包括一阶递推方程在内的一类一阶递推方程的求解这两种十分不同的问题为例,把它们化成为纵横矩阵加工广函数,就可以自然地得到各自的不同的各种并行算法.并以(m,N)选择问题为例说明,一旦发现它是纵横矩阵加工广函数,就容易得到该问题的常数效率新算法,而不是并行台数增大时,效率趋向于0.A new concept, wide-function, with some computing characteristic is proposed in this paper. For example, Bitonic Sort problem proposed by K. E. Batcher and a General Class of Recurrence Equation proposed by P. M. Kogge and H. S. Stone are two very different kinds of problem, but they can be transformed into the same kind of wide-function called vertical-horizontal array wide-function. In this paper, some definitions and theorems about this kind of wide-function are discussed. And several algorithms, such as sequential algorithm, doubling parallel algorithm, vertical-horizontal parallel algorithm, k-dimension parallel algorithm, etc. , of this kind of wide-function, including a general class of recurrence equation and Bitonic sort problem are discussed also. In this paper, authors also take （m,N） selection algorithm as an example, some new optimal algorithms with constant efficiency O（1） can be got easily when it is found that is a vertical-horizontal array wide- function.

关 键 词：并行算法 广函数 递归方程 合并 Bitonic排序 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]