harris@castle.edinburgh.ac.uk (T J Harris) (04/15/91)
Here is a summary of the information I received in response to my
request for references about the PRAM model.
Specifically I'm interested in modifications to the PRAM model
that allow it to take into account aspects such as asynchrony
or network contention. I'm also concerned with the cost of simulating
PRAM algorithms on more realistic machines.
Thanks to all who contributed - especially M. Herlihy and Todd Heywood
who sent me copies of references. I'll still gladly accept any other
references on the subject.
Tim Harris
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edinburgh Parallel Computing Centre email: T.J.Harris@uk.ac.ed
University of Edinburgh, Scotland tel : (031) 650-5019
EH9 1HY fax : (031) 662-4712
=-=-=-=-=-=-=-=-=-=-=-=-PRAM Reference summary=-=-=-=-=-=-=-=-=-=-=-=-=-
M.P. Herlihy <herlihy@com.dec.crl> suggests:
J.~Aspnes and M.P. Herlihy
Wait-Free Data Structures in the Asynchronous PRAM Model.
In {\em Proceedings of the 2nd Annual Symposium on Parallel
Algorithms and Architectures}, July 1990, Crete, Greece.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Ranjan S Muttiah <muttiah@edu.purdue.ecn> from the Purdue University
Engineering Computer Network suggests:
Lookup, "Efficient // Algorithms" by Gibbons and Rytter. They have
most of the relevant references till I believe 1988. Also look up
papers by Valiant.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Kallol Kumar Bagchi <kkb@dk.auc.iesd> suggests:
book:VLSI and Parallel Computations ed by Suaya and Birtwistle
Chapter 2:Th. Aspects of Parallel Computation-Mayr
Papers of Chandra,Snir,Fortune and Wyllie,Aggarwal,Natvig,Francis et al.,
could be interesting.
the book by M.Quinn on parallel algorithms is also good.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Sarah Lesher <lesher@gov.ncifcrf> suggests:
Simon Kasif at Johns Hopkins U (Baltimore MD, I presume Comp Sci, sorry,
no email; you might try asking ar@cs.umd.edu (good luck!)) just gave
seminar on PRAMs and real // machines and constraint problems incl.
asynchronicity. I left him envelope but haven't yet received his refs
(two weeks later) so I may bug him; else I know Current Contents has recent
cites which will point back.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Gad Aharoni <gadi@il.ac.huji.shum> suggests:
Try contacting the people at the University of Saarland, Saarbruecken,
Germany - They are building one!
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Todd Heywood <heywood@top.cis.syr.edu> sent me the following:
"A Practical Hierarchial Model of Parallel Computation",
Syracuse University, Tech. reports SU-CIS-91-06 and SU-CIS-91-07,
February 1991.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Heres a few of my own favorites:
"The Scans as Primitive Parallel Operations" by Guy E. Blelloch, IEEE
Trans. Computers, V. 38, No. 11, Nov. 1989.
"Type Architectures, Shared Memory and the Corollary of Modest
Potential" by Lawrence Snyder, Ann. Rev. Comput. Sci., 1986, 1:289-317.
"Communication-Efficient Parallel Algorithms for Distributed
Random-Access Machines" by Charles E. Leiserson and Bruce M. Maggs,
Algorithmica, 1988, 3:53-77.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
--
=========================== MODERATOR ==============================
Steve Stevenson {steve,fpst}@hubcap.clemson.edu
Department of Computer Science, comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell