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

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

通过分析一种新的结构模型——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.