文章基本信息

标题：An Efficient List-Ranking Algorithm on a Reconfigurable Mesh with Shift Switching
本地全文：下载
作者：Young-Hak Kim
期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2007
卷号：7
期号：6
页码：209-214
出版社：International Journal of Computer Science and Network Security
摘要：The parallel list-ranking is a difficult problem because of its extreme sequential property and irregularity. Given a linked list of n nodes, the proposed algorithm runs in O(1) time on the reconfigurable mesh of size n��n with shift switching. We improve the time complexity by a factor of O(logn/loglogn) as compared to the previous result using the same architecture. Our result also is improved over a logarithm factor in AT2 as compared to the previous algorithms using two dimensional processor arrays with reconfigurable buses.
关键词：List ranking; Reconfigurable mesh/bus; Shift switching