PRAM MEMORY ALLOCATION AND INITIALIZATION
Date
1992-08-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Two useful and practical techniques for managing memory on
a parallel random access machine (PRAM) are presented. One is a
scheme for an nlog n processor EREW PRAM that dynamically
allocates and deallocates at most n records in O(log n)
time. The other is a simulation of a PRAM with initialized memory by
one with uninitialized memory. A CREW PRAM variant of the technique
justifies the assumption that memory can be assumed to be
appropriately initialized with no asymptotic increase in time but a
factor of n increase in space. An EREW PRAM solution incurs a
factor of O(log n) increase in time but only a constant factor
increase in space.
Description
Keywords
Computer Science