REPRESENTING SHARED DATA ON DISTRIBUTED-MEMORY PARALLEL COMPUTERS

Authors
HERLEY KT
Citation
Kt. Herley, REPRESENTING SHARED DATA ON DISTRIBUTED-MEMORY PARALLEL COMPUTERS, Mathematical systems theory, 29(2), 1996, pp. 111-156
Citations number
27
Categorie Soggetti
System Science","Mathematics, Pure","Computer Science Theory & Methods",Mathematics
Journal title
Mathematical systems theory → ACNP
ISSN journal
00255661
Volume
29
Issue
2
Year of publication
1996
Pages
111 - 156
Database
ISI
SICI code
0025-5661(1996)29:2<111:RSDODP>2.0.ZU;2-H
Abstract
The problem of representing a set U corresponds to {u(1),...,u(m)} of read-write variables on an n-node distributed-memory parallel computer is considered. It is shown that U can be represented among the n node s of a variant of the mesh of trees using O((m/n) polylog(m/n)) storag e per node such that any n-tuple of variables may be accessed in O(log n(log log n)(2)) time in the worst case for m polynomial in n.