Performance of work-optimal PRAM simulation algorithms on coated meshes



: Leppanen V

Publisher: CAMBRIDGE UNIV PRESS

: 1995

: Computer Journal

: COMPUTER JOURNAL

: COMPUT J

: 38

: 10

: 801

: 810

: 10

: 0010-4620

DOI: https://doi.org/10.1093/comjnl/38.10.801


We study the effect of varying the multithreading level of processors in work-optimal PRAM simulation algorithms on coated meshes. A coated mesh consists of a mesh connected routing machinery and P processor & memory pairs that form a coat on the routing machinery. The algorithms studied are based on greedy routing, sorting, improved virtual leveled network technique, combining queues method, and synchronization wave. Our results show that increasing the multithreading level considerably improves the simulation cost. The cost can be decreased below 5 routing steps per P simulated PRAM processors. In case of one algorithm, even costs 1.1...2 are achieved.



Last updated on 2025-13-10 at 12:29