一种纳米计算结构上的(m,n)选择网络  

(m,n)-selection networks on a nanocomputing architecture

作　　者：鄢超[1] 陈国良[1] 宋彬[1] 沈一飞[1] 

机构地区：[1]中国科学技术大学计算机科学技术系,安徽合肥230027

出　　处：《中国科学技术大学学报》2006年第2期202-207,共6页JUSTC

基　　金：国家"863"计划(2001AA111041;2002AA104560)资助

摘　　要：通过分析一种新的结构模型——Cell MatrixTM,以及在其上实现的(m,n)选择网络,在晶格结构上实现比较器单元,然后构建互连网络连接各级比较器,从而实现了平衡分组选择网络.实验用晶格开销数目和晶格延迟时间数来衡量算法实现的复杂度,给出了该网络的开销(均是多项式级),具有良好的使用性.该模型上算法的实现过程以及开销分析,体现了Cell MatrixTM结构上计算的便捷性与独特性.Parallel sorting and selection are fundamental in the design of parallel algorithms. There are mature theories about them and new results are continually produced. A new architecture, Cell Matrix^TM and the realization of （m, n）-selection networks were introduced. Cell Matrix^TM is a two-dimensional parallel architecture composed of homogenous cells. It is convenient both for manufacturing and realization of software and hardware on it. Together with its scalability, this architecture is a good choice for future nanocomputers. An （m,n）-selection network, composed of layer of the Batcher＇s comparators, chooses the m smallest or largest numbers from n numbers. Comparators are first realized on cells and then interconnect networks link each layers of comparators to form a balanced group selection network. The complexity of algorithms can be measured by the number of cells and the number of cell delays and cells and delays of a selection network are both polynomial. The realization and analysis reveal the convenience and unique programming style of the Cell Matrix^TM. Based on the research, some ideas are given of future work.

关 键 词：CELL Matrix^TM Batcher比较器 (m n)选择网络 平衡分组选择网络 

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