.png){kind=icon}
.png){kind=icon}
Return
List ranking on processor arrays
.png){kind=icon}
PRE
AI
DOI：10.1016/S0164-1212(00)00069-8.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
List ranking finds for each cell in a linked list the number of cells that precede it in the list. This paper presents a work-efficient list-ranking algorithm for fine-grained processor arrays. This algorithm runs on an array of n/ log(2) n processors with the expected run-time of O(log(2) n). As list ranking is highly communication intensive, the proposed algorithm is able to reduce communication cost among processors by assigning sublists, instead of arbitrary cells, of a linked list to each processor. The proposed algorithm is also capable of keeping all processors busy during the whole list-ranking process in order to utilize all processors efficiently. (C) 2000 Elsevier Science Inc. All rights reserved.
Keywords:
parallel algorithm
list ranking
work-efficient PRAM algorithm
processor array
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.1
Papers:
5.4K
Citations:
8.4K
Organization
No organization information available