Parallel Computing Programming Paradigms

Geoffrey Fox, October 1993 This talk was given at two workshops: one at NASA Icase July 1993 and one at NCSA to Supercomputer Center Consultants as a CRPC Outreach in October 1993. The talk attempts to describe a global view of Programming Paradigms from the point of view of the user. In the Icase talk, this material was integrated with a discussion of parallel computer architectures but at NCSA this material was presented separately by Chien from Illinois. The integrated material is available as the course notes for CPS615. We describe different languages and the support of data parallel, task parallel and message passing. These concepts are described from point of view of problem(user) software and machine. We try to define what sort of software is needed for what sort of problems on what sort of machines. This discussion of High Performance Fortran is essentially correct but has been updated in our resource http://www.npac.syr.edu/hpfa.
The slides (Click on number for individual slide, or text for slideshow):

.1=..Parallel computing programming paradigms - software and problems - abstract.
.2=..Data parallelism as a universal source of parallelism.
.3=..What is data parallelism or domain decomposition.
.4=..Three examples of data parallelism - regular finite difference, particle dynamics, computer chess.
.5=..Two more examples of data parallelism - irregular finite elements, multi-target tracking.
.6=..Structures of problems and parallel software approaches.
.7=..Theory, modeling and computation as mappings between complex systems.
.8=..Five problem architectures.
.9=..Regular synchronous problem architecture.
10=..Irregular loosely synchronous problem.
11=..Asynchronous problem architecture.
12=..The metaproblem architecture - an example of agile manufacturing.
13=..Multidisciplinary analysis and design (Some of the components of agile manufacturing) - mapping of a metaproblem onto a metacomputer.
14=..Further examples of metaproblems - Atmospheric science and computational electromagnetics.
15=..BMC3IS and decision support - a dual use metaproblem.
16=..The heterogeneous metaproblem components for command and control.
17=..Which of the five problem architectures does high performance FORTRAN support.
18=..A reminder of the five problem architectures.
19=..
20=..Table mapping problem classes into appropriate parallel computer architectures.
21=..Layers of software and the stages in mapping problems onto computers.
22=..The concept of complex systems as the basis of a theory of computing.
23=..Parallel computing is ÒjustÓ an optimization problem.
24=..Complex systems in the strategies of mapping problems onto computers.
25=..From problem to specification to layered software; examples of five classes of complex systems.
26=..Categories of industrial applications of parallel computing - abbreviations used in tables.
27=..Industrial applications 1-5 of parallel computing.
28=..Industrial applications 6-12 of parallel computing.
29=..Industrial applications 12-17 of parallel computing.
30=..Issues in parallel computing software.
31=..Conclusions of May 1993 Pittsburgh grand challenge meeting.
32=..What does one need to know about problem structure to produce good parallel software?
33=..Components of software systems for distributed memory parallel computers - I - O/S, I/O, debugging.
34=..Components of software systems for distributed memory parallel computers - II - advantages and disadvantages.
35=..Contrasts between parallel and distributed computing.
36=..Portable scalable languages.
37=..Why extend existing sequential languages - FORTRAN, C.
38=..FORTRAN or C plus message passing - Features.
39=..FORTRAN or C plus message passing - Advantages and disadvantages.
40=..Data parallel FORTRAN - Features.
41=..Data parallel FORTRAN (C, C++, ADA, LISP) - advantages and disadvantages.
42=..Architecture of Virtual machine (programming model) versus architecture of real machine.
43=..What software systems are suitable for what problem architectures.
44=..Software systems and problem characteristics for synchronous and asynchronous problem architectures.
45=..Software systems and problem characteristics for loosely synchronous problem architectures.
46=..Possible programming paradigms and software systems for the five problem architectures.
47=..A two dimensional plot of temporal and spatial problem characteristics labeled by natural computer architecture.
48=..Two types of parallel extensions to FORTRAN and C.
49=..
50=..Motivation and inputs to the design of HPF language.
51=..What problem features should a complete parallel software system include - which can HPF express.
52=..What are possible features in an extended high performance FORTRAN HPF+.
53=..Table summarizing HPF features and extensions HPF+ for some application classes.
54=..Some synchronous problems expressible in HPF - I.
55=..Some synchronous problems expressible in HPF - II.
56=..Some embarrassingly parallel problems expressible in HPF.
57=..Loosely synchronous problems expressible in HPF - Molecular dynamics and unstructured finite elements.
58=..Region Identification in image processing and HPF.
59=..Clustering algorithms for statistical physics and HPF.
60=..Clustering in a spin system simulation near a critical point.
61=..Some multiphase loosely synchronous problems which need HPF extensions.
62=..Multiphase problem examples - particle in the cell, irregularly coupled structured meshes.
63=..Very hard loosely synchronous problems for extended HPF - direct sparse matrix solution, fast multipole for particle dynamics.
64=..Overview of O(N log N) parallel Barnes Hut algorithms for astrophysical particle dynamics.
65=..Example of the Barnes-Hut tree.
66=..Parallel Simulation of cosmological model 8,000,000 Òparticles.
67=..137,000 object galaxy formed in parallel simulation of cosmological model.
68=..Speed up of Barnes-Hut algorithm on 1-512 node nCUBE-1 as function of number of particles.
69=..Summary of issues in the relation of problem (Virtual Machine) and computer architectures and associated programming paradigms.
70=..What should a good parallel language express?
71=..The map of problem onto computer performed in two or three stages.
72=..Problem and machine architectures and message passing programming paradigms.
73=..Real and virtual machines viewed as tightly coupled sparsely connected complex systems.
74=..Real and virtual machines viewed as loosely coupled fully connected complex systems
75=..Different virtual machines used by HPF computer and HPF interpreter.
76=..Software integration - coarse grain task parallelism - metaproblems - use of AVS.
77=..Issues in using AVS for general coarse grain software integration.
78=..A generic AVS dataflow environment implemented on a distributed heterogeneous computing network.
79=..Stock option price modeling as a case study in use of AVS for software integration - summary.
80=..CM-5, DECmpp and workstation network integrated with AVS for stock option pricing.
81=..The AVS front end for previous simulation.
82=..The AVS front end for computational electromagnetic (CEM) distributed simulation.
83=..Computational electromagnetism as an AVS case study - summary.
84=..The EM scattering problem and physical parameters for system components.
85=..The HPFDC (High Performance Distributed Computing) network and the decomposition of CEM into modules.
86=..CEM modules decomposed over the HPDC network.
87=..AVS front end for the NASA data assimilation grand challenge - Kalmar filters to combine weather data and models.
88=..The HPDC network for data assimilation and the decomposition of problem components.
89=..Summary of outstanding issues in programming paradigms.
90=..HPANDF and common data parallelism for FORTRAN, C, C++, ADA.
91=..Metaproblems versus metacomputers - high level or low level virtual machine.
92=..Some issues in functionality needed by software integration systems.
93=..AVS v. PVM . PVM v. MPI v. Multimedia data transport standards.
94=..FORTRAN-M v. AVS. Should task parallelism be integrated into language.

InfoWarehouse Management team