Library Automation and Digital Archive
LONTAR
Fakultas Ilmu Komputer
Universitas Indonesia

Pencarian Sederhana

Find Similar Add to Favorite

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
Lokasi : Perpustakaan Fakultas Ilmu Komputer
Nomor Panggil ID Koleksi Status
SEM-212 TERSEDIA
Tidak ada review pada koleksi ini: 55462
ABSTRACT

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).

ABSTRACT