To search, Click below search items.

 

All Published Papers Search Service

Title

An Efficient List-Ranking Algorithm on a Reconfigurable Mesh with Shift Switching

Author

Young-Hak Kim

Citation

Vol. 7  No. 6  pp. 209-214

Abstract

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.

Keywords

List ranking, Reconfigurable mesh/bus, Shift switching

URL

http://paper.ijcsns.org/07_book/200706/20070629.pdf