"Eugene Miya N." <eugene@NYU.ARPA> (01/08/87)
Newsgroups: comp.arch
Reply-To: eugene@nike.UUCP (Eugene Miya N.)
Organization: NASA Ames Research Center, Moffett Field, CA.
Keywords: parallel processing, distributed processing
It is time once again for me to poll members of computer architecture
community. This is part of my maintenance activity for my
multiprocessor/parallel processor bibliography. Let me know what you
think students of parallel processing should be reading. This year I
want to try a different survey tact. I am posting the existing list
and will take comments about additions, corrections, further
annotations, etc.
--eugene miya [note mail address at the bottom of this posting]
Reference:
%A E. N. Miya
%T Multiprocessor/Distributed Processing Bibliography
%J Computer Architecture News
%I ACM SIGARCH
%V 13
%N 1
%D March 1985
%P 27-29
%K Annotated bibliography, computer system architecture, multicomputers,
multiprocessor software, networks, operating systems, parallel processing,
parallel algorithms, programming languages, supercomputers,
vector processing, cellular automata, fault-tolerant computers
%X Notice of this work. Itself. Quality: no comment.
$Revision$ $Date$
The criterion: the papers (or texts) should be required reading for any
1st year graduate level class on computer architectures. No rag articles.
Suggest up to 10 require papers/texts. The ten numeric favorites
get "required" put into their keyword fields, the rest (up to 100) get
"recommended." I retain some editorial license.
Observations of past years selections: there are fewer papers on
software (than hardware), most required readings are of the few systems
which are actually implemented. Some notable texts are lacking. Real
experience is still lacking. Surprisingly, few AI oriented required
readings (like connectionism [yes, I have those previously posted
things]). Oh, yes, also weak on parallel algorithms and the like.
Note on the use of the material below. This material is posted once
yearly in hopes of refining it, improving it, culling it, what ever.
I DO NOT RECOMMEND THAT YOU USE THE COPYWRITTEN ANNOTATION except for
personal use. DO NOT FURTHER POST IT as reference material without
acknowledging you received it from me (it could get both of us in
trouble. Prentice-Hall only wants to get its due royality (which the US
Government has paid). Don't let it come after you for further
royalities. What this means:
Strip out annotation if you use these citations for external
publication. {I know this is all complicated.}
Cite where you got this (especially, year, because this list changes).
1) It's only fair. It keeps me funded and out of trouble.
2) Yes I know it's a hassle but less than the publisher on my
back.
Toss it out next January/February, because it will change.
So what can I use it for? Plenty: reading lists for your graduate class,
more complete citations (note use of the full author's name in many
cases). Learn what others are reading, etc. What's a citation of your
source? I don't know, say something like "Yearly posting of Requests for
Parallel Processing Citations" by yours truly.
Availability of complete bibliography: FTP`able via ARPAnet upon receipt
on a letterhead acknowledging copyrights. Mag tape (tar) available
from COSMIC: NASA's software distribution Center located at the
University of Georgia. [Note there is an institutional handling fee.]
Source files total abut 4 MBs now.
Don't ask for UUCP; Don't ask for hardcopy: It's 2 MBs in size. And it
violates copyright (for the complete bib).
Special format tapes available on special request: IBM EBCDIC or VMS
Backup [does not include source files]. Maybe your site already has it?
Ask me.
SO NOW, TELL ME WHAT YOU THINK PEOPLE SHOULD BE READING ON THIS TOPIC?
The original survey started from the text:
%A M. Satyanarayanan
%T Multiprocessors: A Comparative Study
%I Prentice-Hall
%D 1980
===================================================================
Required readings
%A K. E. Batcher
%T STARAN Parallel Processor System Hardware
%J Proceedings AFIPS National Computer Conference
%D 1974
%P 405-410
%K Required
%X This paper is reproduced in Kuhn and Padua's (1981, IEEE)
survey "Tutorial on Parallel Processing."
%A David J. DeWitt
%A Raphael Finkel
%A Marvin Solomon
%T The CRYSTAL Multicomputer: Design and Implementation Experience
%I University of Wisconsin-Madison
%R Computer Sciences Technical Report #553
%D September 1984
%K Required
%X A good current overview of the Crystal project. The first part reads like
the C.mmp retrospective by Wulf [1980] et al. They suffered from the same
problems as CMU: small address space, reliability, and they also pushed
the software the software forward to the next stage of problems.
%A Robert H. Kuhn
%A David A. Padua, eds.
%T Tutorial on Parallel Processing
%I IEEE
%D August 1981
%K Required
%X This is a collection of noted papers on the subject, collected for
the tutorial given at the 10th conference (1981) on Parallel Processing.
It eases the search problem for many of the obscure papers.
Some of these papers might not be considered academic, others are
applications oriented. Data flow is given short coverage. Still, a
quick source for someone getting into the field.
Where ever possible, paper in this bibliography are noted as being in this
text.
%A G. J. Lipovski
%A A. Tripathi
%T A reconfigurable varistructure array processor
%J Proc. 1977 Int. Conf. on Parallel Processing
%D August 1977
%P 165-174
%K Required, U Texas, TRAC
%A R. M. Russell
%T The Cray-1 Computer System
%J Communications of the ACM
%V 21
%P 63-72
%D 1978
%K Required,
%X The original paper describing the Cray-1.
This paper is reproduced in Kuhn and Padua's (1981, IEEE)
survey "Tutorial on Parallel Processing."
%A Richard J. Swan
%A S. H. Fuller
%A Daniel P. Siewiorek
%T Cm* \(em A Modular, Multi-Microprocessor
%J Proceedings AFIPS National Computer Conference
%I AFIPS Press
%V 46
%D 1977
%P 637-644
%K CMU, required
%X This paper is reproduced in Kuhn and Padua's (1981, IEEE)
survey "Tutorial on Parallel Processing."
%A Philip C. Treleaven
%A David R. Brownbridge
%A Richard P. Hopkins
%T Data-Driven and Demand-Driven Computer Architecture
%J Computing Surveys
%V 14
%N 1
%D March 1982
%P 93-143
%K Required,
CR Categories and Subject Descriptors: C.0 [Computer System Organization]:
General - hardware/software interfaces; system architectures;
C.1.2 [Processor Architecture]:
Multiple Data Stream Architectures (Multiprocessors);
C.1.3 [Processor Architecture]: Other Architecture Styles
- data flow architectures; high level language architectures;
D.3.2 [Programming Languages]: Language Classifications - data-flow
languages; macro and assembly languages; very high-level languages
General Terms: Design
Additional Key Words and Phrases: Demand = driven architecture,
data = driven architecture
%X * The aim of this paper is to identify the concepts and relationships
that exist both within and between the two areas of research of
data-driven and demand-driven architectures.
%A W. A. Wulf
%A C. G. Bell
%T C.mmp \(em A multi-mini processor
%J Proc. Fall Joint Computer Conference
%V 41, part II
%I AFIPS Press
%C Montvale, New Jersey
%D December 1972
%P 765-777
%K multiprocessor architecture and operating systems
Required,
parallel processing,
%X This paper describes the original design of C.mmp and discusses issues such
as its viability and the feasibility of building it using a minimum of
custom-built hardware. The final C.mmp design differs significantly from the
design described here, but the paper is worth reading for the picture of the
designers' original motives.
Text reproduced with the permission of Prentice-Hall \(co 1980.
-----------------------------------------------------------------------
The recommended readings are:
%A W. B. Ackerman
%T Data flow languages
%J Computer
%V 15
%N 2
%D February 1982
%P 15-25
%K Recommended,
special issue on data flow,
%X Very good summary of data flow, and changes made to
traditional languages to accommodate parallelism [e.g. outlawing side-effects]
%A George B. Adams, III
%A Howard Jay Siegel
%T A survey of fault-tolerant multistage networks and comparison to the
extra stage cube
%J Seventeenth Hawaii Conference on System Sciences
%D January 1984
%P 268-277
%K Recommended,
%A Sudhir R. Ahuga
%A Charles S. Roberts
%T An Associative/Parallel Processor for Partial Match Retrieval Using
Superimposed Codes
%J Proceedings of 7th Annual Symposium on Computer Architecture
%C La Baule, France
%D May 1980
%P 218-227
%K Recommended, Bell Laboratories
%A Gregory R. Andrews
%A Fred B. Schneider
%T Concepts and Notations for Concurrent Programming
%J Computing Surveys
%V 15
%N 1
%P 3-43
%O 133 REFS. Treatment BIBLIOGRAPHIC SURVEY, PRACTICAL
%D March 1983
%i University of Arizona, Tucson
%r CS Dept. TR 82-12
%d Sept. 1982. (To appear in \fIComputing Surveys.\fP)
%K Recommended,
parallel processing programming
OS parallel processing concurrent programming language notations
processes communication synchronization primitives
%A Bruce W. Arden
%A Hikyu Lee
%T A Regular Network for Multicomputer Systems
%J IEEE Transactions on Computers
%V C-31
%N 1
%D January 1982
%P 60-69
%K Moore bound, multicomputer system, multitree structured (MTS) graph,
regular,
recommended,
Multicomputer systems
%X
Reproduced in the 1984 tutorial: "Interconnection Networks for parallel
and distributed processing" by Wu and Feng.
%A J. Backus
%T Can Programming be Liberated from the von Neumann Style?
A Functional Style and its Algebra of Programs
%J Communications of the ACM
%V 16
%N 8
%D August 1978
%P 613-641
%K Recommended
%A Utrpal Banerjee
%A Shyh-Ching Chen
%A David J. Kuck
%A Ross A. Towle
%T Time and Parallel Processor Bounds for FORTRAN-like Loops
%J IEEE Transactions on Computers
%V C-28
%N 9
%P 660-670
%D September 1979
%K Recommended,
Analysis of programs, data dependence, Fortran-like loops, parallel
computation, processor bounds, program speedup, recurrence relations,
time bounds,
Parallel processing
%A George H. Barnes
%A Richard M. Brown
%A Maso Kato
%A David J. Kuck
%A Daniel L. Slotnick
%A Richard A. Stokes
%T The ILLIAC IV Computer
%J IEEE Transactions on Computers
%V C-17
%N 8
%D August 1968
%P 746-757
%K Recommended,
array, computer structures, look-ahead, machine language, parallel processing,
speed, thin-film memory, multiprocessors,
%X This was the original paper on the ILLIAC IV when it was proposed as
a 256 processing element machine, a follow on to the SOLOMON. It was a
very ambitious design.
%A Kenneth E. Batcher
%T Design of a Massively Parallel Processor
%J IEEE Transactions on Computers
%V C-29
%N 9
%D September 1980
%P 836-840
%K Recommended, MPP,
multiprocessors, parallel processing,
%X This paper is reproduced in Kuhn and Padua's (1981, IEEE)
survey "Tutorial on Parallel Processing."
Also reprinted in the text compiled by Kai Hwang:
"Supercomputers: Design and Application," IEEE, 1984.
%A Jay P. Boris
%A Niels K. Winsor
%T Vectorized Computation of Reactive Flow
%E Garry Rodrigue
%B Parallel Computations
%I Academic Press
%D 1982
%P 173-215
%K
recommended
%X Mentions programming style as an important consideration.
Has some of the best advise regarding guidelines (Section VI.) in
programming parallel supercomputers (KISS philosophy).
%A W. J. Bouknight
%A S. A. Denenberg
%A D. E. McIntyre
%A J. M. Randall
%A A. H. Sameh
%A D. L. Slotnick
%T The ILLIAC IV System
%J Proceedings of the IEEE
%V 60
%N 4
%D April 1972
%P 369-388
%K Recommended,
multiprocessors, parallel processing,
%A J. B. Dennis
%T First Version of a Data Flow Language
%E B. Robinet
%B Programming Symposium: Proceedings, Colloque sur la Programmation,
%S Lecture Notes in Computer Science
%V 19
%D April 1974
%P 362-376
%K Recommended,
%A Jack B. Dennis
%T Data Flow Supercomputers
%J Computer
%V 13
%N 11
%D November 1980
%P 48-56
%K Recommended,
multiprocessors, parallel processing, data flow,
%X Covers basic data flow, the idea of activity templates, single assignment
and so on.
Also reprinted in the text compiled by Kai Hwang:
"Supercomputers: Design and Application," IEEE, 1984.
%A D. D. Gajski
%A D. A. Padua
%A D. J. Kuck
%A R. H. Kuhn
%T A Second Opinion on Data Flow Machines and Languages
%J Computer
%V 15
%N 2
%D Feb. 1982
%P 15-25
%K Recommended,
%X (SKS) or why I'm afraid people won't use FORTRAN.
This paper should only be read (by beginners) in conjunction with a
pro-dataflow paper for balance: maybe McGraw's "Physics Today" May 1984.
Also reprinted in the text compiled by Kai Hwang:
"Supercomputers: Design and Application," IEEE, 1984.
%X * Due to their simplicity and strong appeal to intuition, data flow
techniques attract a great deal of attention. Other alternatives,
however, offer more hope for the future.
%A Daniel Gajski
%A David Kuck
%A Duncan Lawrie
%A Ahmed Sameh
%T Cedar \(em a large scale multiprocessor
%J Proceedings of the 1983 International Conference on Parallel Processing
%I IEEE
%D August 1983
%P 524-529
%K Recommended,
U Ill, MIMD, Parafrase, multi-level parallelism, multiprocessor systems,
parallel processing,
%A W. M. Gentleman
%T Some complexity results for matrix computations on parallel processors
%J Journal of the ACM
%V 25
%N 1
%D January 1978
%P 112-115
%K Recommended
%A A. Gottlieb
%A R. Grishman
%A C. P. Kruskal
%A K. P. McAuliffe
%A L. Rudolph
%A M. Snir
%T The NYU Ultracomputer \(em Designing a MIMD, Shared-Memory Parallel
Machine
%J Proceedings of 9th Annual International Symposium on Computer
Architecture, SIGARCH Newsletter
%V 10
%N 3
%D April 1982
%P 27-42
%K Recommended,
%A Ching-Tien Ho
%A S. Lennart Johnsson
%Z Yale
%T Distributed Routing Algorithms for Broadcasting and
Personalized Communication in Hypercubes
%J Proceedings of the 1986 International Conference on Parallel Processing
%I IEEE
%D August 1986
%P 640-648
%K Hypercube architecture, Intel iPSC-7d, spanning tree,
multiple spanning binomial tree, balanced spanning trees,
performance measurement, experimental results, parallel algorithms,
%X Recommended. Outstanding paper at the ICPP.
%A R. W. Hockney
%A C. R. Jesshope
%T Parallel Computers
%I Adam Hilger Ltd
%C Bristol, England
%D 1981
%K Recommended
%X Older text covering architectures, programming and algorithms.
Classifies Cray-1, CYBER 205, and FPS AP-120B as pipelined computers,
ICL DAP and Burroughs BSP under arrays. Has good coverage of software
and algorithms.
%A R. Michael Hord
%T The ILLIAC IV: The First Supercomputer
%I Computer Science Press
%D 1982
%K recommended
%X A collection of papers dealing with the ILLIAC IV. These papers include
reminisces and applications on the ILLIAC.
It is slightly apologetic in tone.
%X Describes in detail the background of the Illiac IV,
programming and software tools, and applications. The chapters are a
little disjointed, and the instruction set is
not well explained or motivated.
%A Tsutomu Hoshino
%A Tomonori Shirakawa
%A Takeski Kamimura
%A Takahisa Kageyama
%A Kiyo Takenouchi
%A Yoshio Oyanagi
%A Toshio Kawai
%T High parallel processor array "PAX" for wide scientific applications
%J Proceedings of the 1983 International Conference on Parallel Processing
%I IEEE
%D August 1983
%P 95-105
%K Recommended,
(PACS), 128 processors (PAX-128)
numerical algorithms
%A H. T. Kung
%T Why systolic architectures?
%J Computer
%V 15
%N 1
%D Jan. 1982
%P 37-46
%K Recommended,
multiprocessors, parallel processing, systolic arrays
%X * Systolic architectures, which permit multiple computations for
each memory access, can speed execution of compute-bound problems
without increasing I/O requirements.
reconfigured to suit new computational structures; however, this
capability places new demands on efficient architecture use.
%A Butler W. Lampson
%T Atomic transactions
%E B. W. Lampson
%E M. Paul
%E H. J. Siegel
%B Distributed Systems \(em Architecture and Implementation
(An Advanced Course)
%S Lecture Notes in Computer Science
%V 105
%I Spring-Verlag
%D 1981
%P 246-265
%K Recommended,
%A Duncan H. Lawrie
%T Access and alignment of data in an array processor
%J IEEE Trans. on Computers
%V C-24
%N 12
%D Dec. 1975
%P 1145-1155
%K Alignment network, array processor, array storage, conflict-free access,
data alignment, indexing network, omega network, parallel processing,
permutation network, shuffle-exchange network, storage mapping,
switching network
recommended, U Ill, N log N nets,
%X This paper is reproduced in Kuhn and Padua's (1981, IEEE)
survey "Tutorial on Parallel Processing."
Reproduced in the 1984 tutorial: "Interconnection Networks for parallel
and distributed processing" by Wu and Feng.
%A Neil R. Lincoln
%T Technology and Design Tradeoffs in the Creation of a Modern
Supercomputer
%J IEEE Transactions on Computers
%V C-31
%N 5
%D May 1982
%P 349-362
%K Architecture, parallelism, pipeline, supercomputer, technology,
vector processor,
recommended, Special issue on supersystems
%X Architectural survey of the STAR-100, Cyber 203/205 line
Also reprinted in the text compiled by Kai Hwang:
"Supercomputers: Design and Application," IEEE, 1984, pp. 32-45.
%A Stephen F. Lundstrom
%A George H. Barnes
%J Proceedings of the 1980 International Conference on Parallel Processing
%D August 1980
%T A Controllable MIMD Architecture
%P 19-27
%K Architecture
%K Recommended,
%X This paper is reproduced in Kuhn and Padua's (1981, IEEE)
survey "Tutorial on Parallel Processing."
This paper describes the proposed FMP "Flow Model Processor" follow on to
the Burroughs Scientific processor. The FMP was to have 512 processors
and 521 memory modules connected by an Omega network. The software
was to include a DOALL construct for FMP parallel FORTRAN, DOMAINS for
index sets.
%A James R. McGraw
%T The VAL Language: Description and Analysis
%J ACM Transactions on Programming Languages and Systems
%V 4
%N 1
%D January 1982
%P 44-82
%K Design, Languages
Categories: D.3.2 [Programming Languages]: Language classifications-
applicative languages; data-flow languages; VHL; D.3.3
[Programming Languages]: Language Constructs - concurrent programming
structures; D.4.1 [Operating Systems]: process management -
multiprocessing/multiprogramming
recommended
%A Elliott Organick
%T A Programmer's Guide to the Intel 432
%I McGraw-Hill
%D 1982
%K Recommended,
%A J. A. Rudolph
%A K. E. Batcher
%T A productive implementation of an associative array processor: STARAN
%E D. P. Siewiorek
%E C. G. Bell
%E A. Newell
%B Computer Structures: Principles and Examples
%I McGraw-Hill
%D 1982
%P 317-331
%K Recommended
%A M. Satyanarayanan
%T Multiprocessors: A Comparative Study
%I Prentice-Hall
%D 1980
%K Recommended,
%X Survey text on multiprocessors including: IBM 370/168 (AP), CDC 6600,
Univac 1100, Burroughs 6700, Honeywell 60/66, DEC-10, C.mmp, and Cm*.
It has an excellent bibliography which was published in IEEE as the
book was excerpted.
%A Michael A. Scott
%T A Framework for the Evaluation of High-Level Languages for Distributed
Computing
%R TR #563
%I Computer Science Dept., Univ. of Wisc.
%C Madison, WI
%D October 1984
%K Recommended
%X An excellent survey of the issues on concurrent languages:
communication, synchronization, naming, and so forth.
%A Howard J. Siegel
%A S. Diane Smith
%T Study of Multistage SIMD Interconnection Networks
%J Proceedings of 5th Annual Symposium on Computer Architecture
%D 1978
%K Purdue University, recommended
%P 223-229
%A Howard J. Siegel
%T Interconnection networks for SIMD machines
%J Computer
%V 12
%N 6
%D June 1979
%P 57-65
%K Recommended,
%X A good survey paper on processor memory interconnects.
This paper was reproduced in Kuhn and Padua's (1981)
"Tutorial on Parallel Processing."
%A Howard J. Siegel
%A Leah J. Siegel
%A F. C. Kemmerer
%A P. T. Mueller, Jr.
%A H. E. Smalley, Jr.
%A S. Diane Smith
%T PASM: A Partitionable SIMD/MIMD System for Image Processing and Pattern
Recognition
%J IEEE Transactions on Computers
%V C-30
%N 12
%D December 1981
%P 934-947
%K Recommended, Purdue U
Image processing, memory management, MIMD machines,
multimicroprocessor systems, multiple-SIMD machines, parallel processing,
partitionable computer systems, PASM, reconfigurable computer systems,
SIMD machines
%A Howard Jay Siegel
%A Robert J. McMillen
%A P. T. Mueller, Jr.
%T A survey of interconnection methods for reconfigurable parallel processing
systems
%J AFIPS Proc. of the NCC
%V 48
%D 1979
%P 529-542
%K Purdue U, recommended
%A Burton J. Smith
%T A pipelined, shared resource MIMD computer
%J Proceedings of the International Conference on Parallel Processing
%I IEEE
%C Bellaire, Michigan
%D August 1978
%P 6-8
%K Recommended,
multiprocessor architecture and operating systems, general purpose
architectures
%X One of the first papers on the Denelcor Heterogeneous Element Processor
(HEP) after major design had been completed.
This paper was reproduced in Kuhn and Padua's (1981)
"Tutorial on Parallel Processing."
%A J. Tsoras
%T The Massively Parallel Processor (MPP) Innovation in High Speed Processors
%J AIAA Computers in Aerospace Conference
%V III
%D October 1981
%K Recommended,
%A I. Watson
%A J. Gurd
%T A practical data flow computer
%J Computer
%V 15
%N 2
%D February 1982
%P 51-57
%K Recommended,
special issue on data flow,
%X * Based on a tagged dynamic data flow model, this prototype machine has
eight unusual matching functions for handling incoming data tokens at
its computational nodes.
%A Richard W. Watson
%T Distributed system architecture model
%E B. W. Lampson
%E M. Paul
%E H. J. Siegel
%B Distributed Systems \(em Architecture and Implementation
(An Advanced Course)
%S Lecture Notes in Computer Science
%V 105
%I Spring-Verlag
%D 1981
%P 10-43
%K Recommended,
%A Richard W. Watson
%T IPC interface and end-to-end protocols
%E B. W. Lampson
%E M. Paul
%E H. J. Siegel
%B Distributed Systems \(em Architecture and Implementation
(An Advanced Course)
%S Lecture Notes in Computer Science
%V 105
%I Spring-Verlag
%D 1981
%P 140-190
%K Recommended,
%A William A. Wulf
%A Roy Levin
%A Samuel P. Harbison
%T HYDRA/C.mmp: An Experimental Computer System
%I McGraw-Hill
%D 1981
%K Recommended,
CMU, C.mmp, HYDRA OS,
multiprocessor architecture and operating systems
%X A detailed description of the philosophy, design, and implementation of
Hydra, similar in a sense to Organick's monograph on Multics. Highly
recommended to anyone desiring an understanking of multiprocessor operating
systems in general and Hydra in particular.
Text reproduced with the permission of Prentice-Hall \(co 1980.
%X * Describes the architecture of C.mmp, and details the goals, design, and
performance of HYDRA, its capability based OS.
>From the Rock of Ages Home for Retired Hackers:
--eugene miya
NASA Ames Research Center
eugene@ames-aurora.ARPA
"You trust the `reply' command with all those different mailers out there?"
{hplabs,hao,nike,ihnp4,decwrl,allegra,tektronix,menlo70}!ames!aurora!eugene