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 |
