Call Number | SEM-212 |
Collection Type | Indeks Artikel prosiding/Sem |
Title | Constructive Deterministic PRAM Simulation on a Mesh-Connected Computer* Andrea Pietracaprinat |
Author | Andrea Pietracaprinat, Geppino Puccit, Jop F. Sibeyns; |
Publisher | 6th Annual ACM Symposium on Parallel Algorithms and Architecture |
Subject | |
Location |
Nomor Panggil | ID Koleksi | Status |
---|---|---|
SEM-212 | TERSEDIA |
We present a constructive deterministic simulation of a PRAM with n processors and m = n° shared variables, 1 < a < 2, on an n-node mesh-connected computer where each node hosts a processor and a memory module. At the core of the simulation is a Hierarchical Memory Organiza- tion Scheme (HMOS) that governs the distribution of the PRAM variables (each replicated into a number of copies) among the modules. The HMOS consists of a cascade of explicit bipartite graphs whose expansion properties, com- bined with suitable access and routing protocols, yield a time performance that, for a < 3/2, is close to the (√√n) bound imposed by the network's diameter, and that, for a > 3/2, is a function of a never exceeding (n5/8).