Full HTML for

Basic foilset Complex Systems and Parallel Computing -- CPS713 update from Decemember 1992 Talk at ANU Conference on Complex Systems

Given by Geoffrey C. Fox at CPSP713 Case studies in Computational Science on Spring Semester 1996. Foils prepared 15 March 1996
Outside Index Summary of Material

Parallel Computers for the Simulation of Complex Systems
  • Teraflop Performance
  • Virtual Reality
  • Software Standards
  • "Global metacomputer"
Complex Systems for the theory of Computer and Network Architecture
  • Physical Analogies Space, Time, Temperature, Phase Transitions
  • Problem Architecture
  • A Theory of Parallel Computing?
Complex Systems for new Computational Methodologies
  • Physical Computation
  • Neural Networks..........
  • Simulated Annealing and Tempering

Table of Contents for full HTML of Complex Systems and Parallel Computing -- CPS713 update from Decemember 1992 Talk at ANU Conference on Complex Systems

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
1 Complex Systems and Parallel Computing
Australian International Conference on Complex Systems
Australian National University
Canberra, Australia
December 14-16, 1992
Geoffrey C. Fox
2 The Three Themes of Lecture: Parallel Computers and Complex Systems
3 Issues in Parallel Computers for the Simulation of Complex Systems
4 Standard Performance Graph Heading to 1 to 10 Teraflops by year 2000
5 When will parallel computing take over?
6 The President's High Performance Computing and Communication Initiative (HPCCI)
7 Challenges and Status of Parallel Computing
8 High Performance Fortran Overview
9 HPF computational model
10 Example of Fortran-90D source code: Gaussian Elimination
11 HPF directives
12 Data Alignment and Distribution Directives
13 Examples of Alignments (1)
14 Examples of Distributions (1)
15 For More Information on HPF
16 FORTRAN-90D
The First Implementation of HPF
(NPAC, Syracuse University)
Current Status
17 Common Software needed for Heterogeneous Local Area Network
(Ethernet - FIDDI - HIPPI - FCS ......)
18 Importance of MetaProblems
19 Hybrid Problem Structure for Command and Control
20 The Mapping of Heterogeneous Problems onto Heterogeneous Computer Systems
21 SIMCITY is an interesting PC based complex system simulation.
22 Implementation of Complex System Simulation
23 AVS as System Integration Tool
24 Parallel AVS - Planned Project at NPAC
25 Architecture of Parallel AVS System
26 VR Operating Shells
27 Components of Proposed Televirtuality Server at NPAC
28 A Theory of Parallel Computing based on Complex Systems
29 Computing as a set of Mapping Problems
30 Complex Systems to give a theory of computing
31 Parallel Computing is "just" an optimization problem, even if we can't agree on what to optimize
32 Concurrent Computation as a Mapping Problem -I
33 Concurrent Computation as a Mapping Problem - II
34 Computation as a map of a set of Complex Systems
35 Domain Decomposition and Complex Systems ?
36 Physical Analogy for Complex Computer
37 The Physical Space/TimeAnalogy for a General Problem
38 Some Temporal Properties of Computation
39 General Space Time Complex System Picture for Problem to Computer Mapping
40 Computer Languages and Space - Time Properties
41 Information Dimension of a General Complex System
42 Performance of a Parallel Computer
43 Hierarchical Multicomputer
Spatial and Temporal Decomposition
44 Shared or Hierarchical Memory Computer
45 Comparison of Cache and Distributed Memory Communication Overhead
46 Extension of Space-Time Picture to treat Hierarchial memory and caches etc.
47 Space-Time Decompositions for the concurrent one dimensional wave equation
48 Typical Example of Mapping an Irregular Bunch of Grid Points
49 Use of Physical Optimization in High Performance Fortran
50 Physics Analogy for Load Balancing
51 Complex System SHLSoft governed by Hamiltonian = Execution Time
52 Decomposition of an Arch onto 16 Processors in a Hypercube
53 PHYSICS ANALOGY FOR STATIC AND DYNAMIC LOAD BALANCING
54 General definition of temperature TS of a complex system
55 Particle dynamics problem on a four node system
56 Instantaneous Energy Distribution for Time Dependent Domain Decomposition and Block Scattered Distributions
57 Time Averaged Energy for Adaptive Particle Dynamics Problem
58 A general theory of computation
59 HISTORICALLY ONE OF THE MOTIVATIONS FOR THE RESEARCH WAS TO
" AUTOMATE" THE KNOWN FOLD ALGORITHM
60 The String Formalism for Dynamic Computations
61 Loosely Synchronous Static and Adaptive Problems in the String Picture
62 An initial approach to computational string dynamics or equivalently the
Construction of the Energy Function
63 Full String Dynamics as an Interacting Field Theory
64 Complex systems suggest new computational methodologies
65 Physical Optimization and Computation Approaches and their Field of Origin
66 Genetic Algorithms for Data Decomposition
67 Three Major Genetic Operators
68 MultiScale Methods in Parallel Data Decomposition
69 Results of Various Physical Optimization Methods for Data Decomposition
70 A similar but Larger Problem
71 Some Overall Questions Relevant In Classisfying Optimization Problems and Methods
72 Two Types of Global Mininum and their relation to Local Minima
73 Typical Formalism for Physical Optimization
74 Global and Local Minima in Temperature Dependent Free Energy
75 Comparison of Physical Optimization Methods
76 Some Applications of Deterministic Annealing
77 Simulated Tempering -- a New Approach to Monte Carlo Optimization/Simulated Annealing
78 The Conventional Simulated Annealing and its Problems for Random Field Ising Models
79 Key Idea in The Tempering Approach
80 Goodbye! Many Choices - Which is best When?

Outside Index Summary of Material

HTML version of Basic Foils prepared 15 March 1996

Foil 1 Complex Systems and Parallel Computing
Australian International Conference on Complex Systems
Australian National University
Canberra, Australia
December 14-16, 1992
Geoffrey C. Fox

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
gcf@nova.npac.syr.edu
http://www.npac.syr.edu
315.443.2163
HTML version of Basic Foils prepared 15 March 1996

Foil 2 The Three Themes of Lecture: Parallel Computers and Complex Systems

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Parallel Computers for the Simulation of Complex Systems
  • Teraflop Performance
  • Virtual Reality
  • Software Standards
  • "Global metacomputer"
Complex Systems for the theory of Computer and Network Architecture
  • Physical Analogies Space, Time, Temperature, Phase Transitions
  • Problem Architecture
  • A Theory of Parallel Computing?
Complex Systems for new Computational Methodologies
  • Physical Computation
  • Neural Networks..........
  • Simulated Annealing and Tempering
HTML version of Basic Foils prepared 15 March 1996

Foil 3 Issues in Parallel Computers for the Simulation of Complex Systems

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Can one use the 1 ----->10 TERAFLOP machines which will be available in the middle to late 1990's ?
What software do you need ?
What about virtual reality and distributed metacomputers ?
HTML version of Basic Foils prepared 15 March 1996

Foil 4 Standard Performance Graph Heading to 1 to 10 Teraflops by year 2000

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 5 When will parallel computing take over?

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
When it has enough headroom (e.g. a factor of ten better "performance"/"cost-performance" than existing technology)
  • Definition of headroom confused as parallel machines much harder to use and so hard to decide on vlue to a given organization
nCUBE-1, CM-2 were comparable or perhaps a factor of 2 ... 4 better in cost-performance than conventional supercomputers
  • Enough to show "Parallel Computing Works"
  • not enough to "takeover"
DECmpp, IBM SP1, INTEL Paragon, CM-5, nCUBE-2 are (perhaps) a factor of ten better than competitive sequential (vector) machines
  • They can "takeover" ?
HTML version of Basic Foils prepared 15 March 1996

Foil 6 The President's High Performance Computing and Communication Initiative (HPCCI)

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
$2.9 billion over 5 years
The Grand Challenges
  • Enabled by teraflop computers and important to economy or fundamental research
    • Global warming - NOAA
    • Oil reservoir and environmental simulation - DOE
    • Structural and aerodynamic calculations - NASA
    • Earth observing satellite - data analysis - NASA
    • Human genome - NIH, DOE
    • Quantum chromodynamics - Fundamental Physics
    • Gravitational waves from black holes - Fundamental Physics
    • Molecular modeling - Fundamental Chemistry
Nearly all have industrial payoff but technology transfer NOT funded by HPCCI
HTML version of Basic Foils prepared 15 March 1996

Foil 7 Challenges and Status of Parallel Computing

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Hardware trends imply that all computers (PC's--->Supercomputers) will be parallel by the year 2000
  • Up to now parallel computers are from small start-up companies (except Intel Supercomputer Division)
  • Recently Cray, Convex (HP), Digital, IBM have announced massively parallel computing initiatives
  • Several architectures "work" but only one : Distributed memory MIMD multicomputer is known to scale from one to very many processors on general problems
Software is challenge and could prevent/delay hardware trend that suggests parallelism will be a mainline computer architecture
  • first we must get systems software correct
  • then applications software
HTML version of Basic Foils prepared 15 March 1996

Foil 8 High Performance Fortran Overview

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Data Parallelism
  • Fortran90 provides a number of features, notably array syntax, that make it possible for a compiler to detect parallelism. However, with existing compiler technology, to exploit full capability of concurrent systems, new language features are necessary to define data dependency and locality.
High Performance
  • Addressed primarily by proposed data distribution features and new intrinsic functions.
Code Tuning
  • optional, explicit message passing support for MIMD machines
Validation
  • a benchmarking suite is being prepared by NPAC, Syracuse University
HTML version of Basic Foils prepared 15 March 1996

Foil 9 HPF computational model

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
The underlying intuition behind HPF computational model is that
  • an operation on two or more data object is likely to be carried out much faster if they all reside on the same processor
  • it may be possible to carry out many such operations concurrently if they can be performed on different processors
The main mechanism for achieving parallelism in HPF is the data partition annotation of HPF. Distribution of control is derived from the data distribution, using the owner compute rule: each assignment is executed by the processor(s) that own the assigned variable. (However, a compiler may relax the owner rule, in order to improve performance.)
HTML version of Basic Foils prepared 15 March 1996

Foil 10 Example of Fortran-90D source code: Gaussian Elimination

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 11 HPF directives

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
An HPF directive has the form of a comment line:
!HPF$ hpf-directive
A goal of the design is that HPF directives should be consistent with Fortran 90 syntax in the following strong sense: if HPF were to be adopted as a part of a future Fortran standard, the only change necessary to convert an HPF program would be to remove the comment character and directive prefix from each directive.
There is a clear separation between directives that serves as specification statements and directives that serve as executable statements ( in the sense of the Fortran standard). Specification statements are carried out on entry to a program unit; after these, executable statements are carried out.
HTML version of Basic Foils prepared 15 March 1996

Foil 12 Data Alignment and Distribution Directives

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Model of the allocation of data objects to processor memories is that there is a two-level mapping of data objects to abstract processors. Data objects (typically array elements) are first aligned with an abstract indexing space called a template; a template is then distributed onto a recilinear arrangement of abstract processors. The implementation then uses the same number, or perhaps some smaller number, of physical processors to implement these abstract processors. This mapping of abstract processors to physical processors is implementation dependent.
HTML version of Basic Foils prepared 15 March 1996

Foil 13 Examples of Alignments (1)

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
!HPF$ TEMPLATE B (N, N)
!HPF$ ALIGN X3 (I, J) with B (I, J-1)
!HPF$ ALIGN X4 (I, J) with B (I-1, J+2)
HTML version of Basic Foils prepared 15 March 1996

Foil 14 Examples of Distributions (1)

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
!HPF$ TEMPLATE A (N, N), B (N, N), C (N, N)
!HPF$ DISTRIBUTE A (BLOCK, *)
!HPF$ DISTRIBUTE B (*, BLOCK )
!HPF$ DISTRIBUTE C (BLOCK, BLOCK )
HTML version of Basic Foils prepared 15 March 1996

Foil 15 For More Information on HPF

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
The final draft of the HPF proposal is available via anonymous ftp from
  • minerva.npac.syr.edu (public/HPFF)
  • titan.cs.rice.edu (public/HPFF/draft)
  • ftp.gmd.de (hpf-Europe)
  • theory.tc.cornell.edu (pub)
  • think.com (public/HPFF)
E-mail servers
  • softlib@cs.rice.edu (send hpf-vxx.ps)
  • netlib@research.att.com (send hpf-vxx.ps from hpff)
  • netlib@ornl.gov (send hpf-vxx.ps from hpf)
HPFF mailing list
  • hpff-request@cs.rice.edu (to join)
  • hpff@cs.rice.edu (to submit)
  • hpff-info@cs.rice.edu (for general information)
  • hpff-comments@cs.rice.edu (to submit comments on the HPF draft)
HTML version of Basic Foils prepared 15 March 1996

Foil 16 FORTRAN-90D
The First Implementation of HPF
(NPAC, Syracuse University)
Current Status

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Alpha version: demonstrated at SUPERCOMPUTING '92 in Minneapolis, MN
  • one- and two-dimensional BLOCK, CYCLIC and BLOCK-CYCLIC distributions
  • FORALL statement
  • full run-time support for regular communications
  • PARTI (ICASE) primitives for irregular communications
  • intrinsic library
Now running on nCUBE2, iPSC/860 and network of SUN workstations
beta release: June 1993
alliance with industry to develop commercial compiler for HPF, optimized for specific architectures
next target: heterogeneous networks
HTML version of Basic Foils prepared 15 March 1996

Foil 17 Common Software needed for Heterogeneous Local Area Network
(Ethernet - FIDDI - HIPPI - FCS ......)

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 18 Importance of MetaProblems

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
High Performance Fortran is only suitable for data parallel problems whose data structure is an array.
  • Will extend e.g. to tree or irregular graph
But complex systems can be complicated!
For instance, Image Processing, Data Fusion, Multidisciplinary Design have several modules.
  • Each can be data parallel
HTML version of Basic Foils prepared 15 March 1996

Foil 19 Hybrid Problem Structure for Command and Control

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Si: Satellite with: Image processing Kalman filter Stereo match
FCi: Fire Control platform with loosely synchronous target-weapon pairing algorithm
E: Overall Asynchronous expert system
HTML version of Basic Foils prepared 15 March 1996

Foil 20 The Mapping of Heterogeneous Problems onto Heterogeneous Computer Systems

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
The analogy between metaproblems and metacomputers
HTML version of Basic Foils prepared 15 March 1996

Foil 21 SIMCITY is an interesting PC based complex system simulation.

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Can use teraflop computers to make such "games" more realistic.
Heirarchy of Complexity
Virtual Class e.g. weather or cortex model
Virtual Class room
Virtual Laboratory realistic SIMCITY; combines several classes
Virtual School ....
Experience virtual classes ---> school with "Virtual Reality"
HTML version of Basic Foils prepared 15 March 1996

Foil 22 Implementation of Complex System Simulation

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Complex System Simulation requires
  • ===> Support of many adaptively linked modules
  • ===> Interpreter not compiler
  • ===> Link to Virtual Reality
Possible Implementation
HTML version of Basic Foils prepared 15 March 1996

Foil 23 AVS as System Integration Tool

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Basic Features
  • dataflow model for distributed computing
  • AVS program = network of AVS modules, controlled by the AVS kernel via the RPC mechanism
  • AVS module = C/Fortran program, conforming to AVS interface specification
  • strong visualization and 3D graphics support
  • visual editing tools for AVS networks
Highlights
  • easy to use and to port existing applications to the AVS framework
  • growing popularity in research community
  • growing volume of public domain modules, maintained by the International AVS Center at the NCSC
Flaws
  • poor interactivity (best for complex, static visualization, but not for simulation or animation)
  • lack of organization principle to bookkeep dataflow modules (not an object-oriented system)
  • lack of support for High Performance Computing
  • not an Open Systems software (2 competitive commercial products: AVS, Explorer (SGI); 2 public domain systems: apE and Khoros)
HTML version of Basic Foils prepared 15 March 1996

Foil 24 Parallel AVS - Planned Project at NPAC

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Forms of parallelism in the AVS model:
  • intramodular data parallelism (e.g. image processing or PDE modules) for single AVS kernel
  • intermodular functional parallelism (single kernel)
  • multi-user/kernel/department functional parallelism
NPAC Approach
  • Develop 'standard' library of data parallel modules in High Performance Fortran for regular problems (matrix, algebra, PDEs, imaging)
  • develop hierarchical/clustering algorithms for automatic decomposition of large AVS dataflow networks into a network of independent AVS subsystems
  • unify existing tools for the user-level hierarchical functional organization with the automated tools for the network decomposition
  • unify top-down approach for the single user network decomposition with the bottom-up approach for the multi-user network integration
HTML version of Basic Foils prepared 15 March 1996

Foil 25 Architecture of Parallel AVS System

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 26 VR Operating Shells

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 27 Components of Proposed Televirtuality Server at NPAC

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
modern parallel systems (CM-5, nCUBE2, DECmpp, Intel Touchstone)
High Performance Fortran and Concurrent C++ software environment (compilers, interpreters, runtime support)
parallel Oracle + SGI front-ends
expert system (RT/AI from Intellisys, Inc.)
Clusters of DEC/IBM/SUN workstations on the Ultra-Net / FCS / HIPPI / ATM (?) based gigabit/sec LAN
visualization front-ends (AVS/Explorer, Khoros/apE)
multimedia front-ends
VR front-ends (BOOM, Convolvotron, DataGloves, PROvision and Sense8 systems, new consumer VR products)
MOVIE as integration/infrastructure software
HTML version of Basic Foils prepared 15 March 1996

Foil 28 A Theory of Parallel Computing based on Complex Systems

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Use Complex Systems to describe
Problems
Computers
Networks
And their Interaction
HTML version of Basic Foils prepared 15 March 1996

Foil 29 Computing as a set of Mapping Problems

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
A hierarchy of mapping problems
We would like to optimize the overall mapping
HTML version of Basic Foils prepared 15 March 1996

Foil 30 Complex Systems to give a theory of computing

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Both problems and computer are
Collections of homogeneous or heterogeneous basic entities with some sort of static or dynamic connection between them
Modeling involves mapping one "complex problem" into another
Simulation or parallel computing involves map Complex problem ---> Complex Computer
What parameters of these two underlying complex systems control effectiveness of map?
HTML version of Basic Foils prepared 15 March 1996

Foil 31 Parallel Computing is "just" an optimization problem, even if we can't agree on what to optimize

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Execution time - main focus of HPCC community?
User happiness - main focus of software engineering community
HTML version of Basic Foils prepared 15 March 1996

Foil 32 Concurrent Computation as a Mapping Problem -I

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
2 Different types of Mappings in Physical Spaces
Both are static
  • a) Seismic Migration with domain decomposition on 4 nodes
  • b)Universe simulation with irregular data but static 16 node decomposition
  • but this problem would be best with dynamic irregular decomposition
HTML version of Basic Foils prepared 15 March 1996

Foil 33 Concurrent Computation as a Mapping Problem - II

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Different types of Mappings -- A very dynamic case without any underlying Physical Space
c)Computer Chess with dynamic game tree decomposed onto 4 nodes
HTML version of Basic Foils prepared 15 March 1996

Foil 34 Computation as a map of a set of Complex Systems

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 35 Domain Decomposition and Complex Systems ?

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
All successful parallel computers with:
  • Many nodes (massively parallel)
  • High Performance (excludes architectures like dataflow) Have obtained parallelism from "data parallelism" or "domain decomposition"
This is just the mapping of data ("spatial domain") of complex problem onto spatial structure of complex computer Whether architecture SIMD MIMD Distributed or Shared Memory
HTML version of Basic Foils prepared 15 March 1996

Foil 36 Physical Analogy for Complex Computer

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Space is either
  • Number of nodes of parallel computer
or at a different resolution
  • Number of memory locations
Time is either
  • measured by cycle time of node
or at a different resolution (on CISC computers)
  • measured by machine instructions
HTML version of Basic Foils prepared 15 March 1996

Foil 37 The Physical Space/TimeAnalogy for a General Problem

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
(The correspondence implied by theory of complex systems)
Problems have a data domain- "SPACE"
and the computation involves work done on the elements of this domain; label this work by - "TIME"
Examples
  • Simulation of a 3D physical system
    • SPACE = "SPACE"
    • TIME = "TIME"
    • e.g. Wave equation in seismic exploration
    • or motion of missiles after launch
  • Full matrix operations (Inversion, multiplication)
    • MATRIX elements = "SPACE"
    • Label of ROWS eliminated or multiplied = "TIME"
  • Gauss Seidel (SOR) Iterative approach to solving sparse matrix problems
    • Set of nonzero matrix elements = "SPACE"
    • ITERATION COUNT = "TIME"
HTML version of Basic Foils prepared 15 March 1996

Foil 38 Some Temporal Properties of Computation

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 39 General Space Time Complex System Picture for Problem to Computer Mapping

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
e.g. On a sequential computer, all aspects of problem are mapped onto "TIME" in computer
Seismograph: time dependence of earthquake mapped on spatial extent of recording paper.
HTML version of Basic Foils prepared 15 March 1996

Foil 40 Computer Languages and Space - Time Properties

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
High Performance Fortran
    • Dimension A,B (10000)
    • A=A+B
Space (elements of arrays A,B) in problem is mapped into space (i.e. arrays preserved) in Virtual Problem
---> Compiler can recognize data parallelism
---> Good parallel performance on all machines
Fortran77 Do 1 I = 1, 10000
    • 1 A(I) = A(I) + B(I)
Space in problem is mapped into time (successive iterations of DO loop) in Virtual Problem
---> Compiler has to "undo" this to recognize parallelism and generally fails
---> Good languages preserve problem architecture
HTML version of Basic Foils prepared 15 March 1996

Foil 41 Information Dimension of a General Complex System

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
d = geometric dimension for local problems
d~2 computer chips (Rent's Rule)
d=1 ALL long range force problems - whatever dimension
HTML version of Basic Foils prepared 15 March 1996

Foil 42 Performance of a Parallel Computer

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 43 Hierarchical Multicomputer
Spatial and Temporal Decomposition

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Homogeneous Multicomputer
Purely Spatial Decomposition
HTML version of Basic Foils prepared 15 March 1996

Foil 44 Shared or Hierarchical Memory Computer

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 45 Comparison of Cache and Distributed Memory Communication Overhead

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 46 Extension of Space-Time Picture to treat Hierarchial memory and caches etc.

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Both Distributed and Hierarchial memory need DATA LOCALITY in memory references
  • Minimize communication
  • Minimize cache miss
Hierarchal memory ----> "Time"
Distributed memory ----> "Space"
All overheads proportional to 1/[space-time volume] 1/d
with space and time decomposition (cf. BLAS-3 for Matrices)
High Performance Fortran expresses data locality ==> will improve performance of sequential machines
HTML version of Basic Foils prepared 15 March 1996

Foil 47 Space-Time Decompositions for the concurrent one dimensional wave equation

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 48 Typical Example of Mapping an Irregular Bunch of Grid Points

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Onto 8 Nodes
HTML version of Basic Foils prepared 15 March 1996

Foil 49 Use of Physical Optimization in High Performance Fortran

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Problem is to Find MAP in
DISTRIBUTION (MAP) in FortranD/HPF (High Performance Fortran
A user (compiler) generated data decomposition
User (compiler) supplies
What is to be distributed
"Graph" - algorithmic connection between entities to be distributed
These entities are:
  • particles
  • grid points
  • matrix elements ....... depending on problem
HTML version of Basic Foils prepared 15 March 1996

Foil 50 Physics Analogy for Load Balancing

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Label data points (members of problem spatial domain by i
Each i ---> Particle moving in space with discrete points (number of points in space = number of nodes in machine) and with topology defined by interconnection of nodes
Let problem be defined by parameters:
  • Execution time Ci for each i
  • Communication time Vi,j between data points i and j
  • (Vi,j often zero; nonzero only if i and j linked in computational graph)
HTML version of Basic Foils prepared 15 March 1996

Foil 51 Complex System SHLSoft governed by Hamiltonian = Execution Time

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Need ground state of H
HTML version of Basic Foils prepared 15 March 1996

Foil 52 Decomposition of an Arch onto 16 Processors in a Hypercube

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
from Chrisochoides
HTML version of Basic Foils prepared 15 March 1996

Foil 53 PHYSICS ANALOGY FOR STATIC AND DYNAMIC LOAD BALANCING

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
The "Particles" and "springs"/forces between them including effect of the cost of redistribution
HTML version of Basic Foils prepared 15 March 1996

Foil 54 General definition of temperature TS of a complex system

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
In a dynamic load balancing problem (time dependent system), simulated annealing will be performed concurrently on the same computer ensemble used to simulate system.
Suppose "optimal" annealing strategy used. There will be a minimum temperature TS to which it will be possible to "cool" system before time spent annealing is longer than gain due to improved load balancing.
Note TS is independent of speed of computer - it is a property of system being simulated
HTML version of Basic Foils prepared 15 March 1996

Foil 55 Particle dynamics problem on a four node system

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Block Scattered and Domain Decomposition Distributions Illustrated
HTML version of Basic Foils prepared 15 March 1996

Foil 56 Instantaneous Energy Distribution for Time Dependent Domain Decomposition and Block Scattered Distributions

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Note scattered position is independent of time
HTML version of Basic Foils prepared 15 March 1996

Foil 57 Time Averaged Energy for Adaptive Particle Dynamics Problem

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Note Domain decomposition can end up worse than block scattered after averaging
HTML version of Basic Foils prepared 15 March 1996

Foil 58 A general theory of computation

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
The particle - process analogy does not apply to
Asynchronous problems
  • Database
  • Event driven simulations
  • Phone network traffic
  • Computer chess and other AI
Loosely synchronous problems where fundamental entities move between nodes on a microscopic time scale (such problems can be called microscopically dynamic)
Example - Global sums as used in
    • DO 1 I=1, Limit 1
    • A(I) = 0
    • DO 2 J=1, Limit 2
    • 2 A(I) = A(I) + B(I,J)
Where I and J distributed over nodes of hypercube
HTML version of Basic Foils prepared 15 March 1996

Foil 59 HISTORICALLY ONE OF THE MOTIVATIONS FOR THE RESEARCH WAS TO
" AUTOMATE" THE KNOWN FOLD ALGORITHM

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 60 The String Formalism for Dynamic Computations

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Originally we used the analogy
  • Process or "entity"-----> Particle
  • Label by p -----> xp (t) POSITION
Now generalize this to
  • process or "fundamental
  • thread of computation" ------> String or worldline
  • Label by p ------> time ordered set {xp (t) }
In this new formalism our loosely synchronous microscopically static problems are represented by
HTML version of Basic Foils prepared 15 March 1996

Foil 61 Loosely Synchronous Static and Adaptive Problems in the String Picture

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Particles p1 and p2 interact with an attractive "communication force" where this force is carried by message (packets) which are the quantum of force
So loosely synchronous microscopically static problems can be described by strings that vary slowly with time and it is sufficient to slice, every now and then, at a fixed time and consider as particles
HTML version of Basic Foils prepared 15 March 1996

Foil 62 An initial approach to computational string dynamics or equivalently the
Construction of the Energy Function

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
The true problem is to minimize the length in the time direction of the string of maximum length. This can be treated directly in "full string dynamics" but here we will follow particle analogy and replace this minimax problem by a least squares formulation
Again replace exact constraints (e.g. a node can only do one or a few things at a time) by at least squares constraints
  • This in spirit of Hopfield and Tank
New terms in energy (in field theory language) corresponding to the creation or annihilation or strings
HTML version of Basic Foils prepared 15 March 1996

Foil 63 Full String Dynamics as an Interacting Field Theory

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
One uses as dynamical variables the complete strings {xp(t)} or probably better specifies them with a neural formalism inspired by Hopfield and Tank's traveling salesperson work
Sp (x,t) = 0 if p is not at x time t
Sp (x,t) = 1 if p is at x time t
with constraint S Sp (x,t) = 1 (one string in field)
The associated dynamics is that of interacting strings with usual repulsive and attractive forces plus creation and annihilation.
HTML version of Basic Foils prepared 15 March 1996

Foil 64 Complex systems suggest new computational methodologies

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Cellular Automata
Physical Computation
  • Neural Networks
  • Genetic Algorithms
  • Simulated Annealing
  • Simulated Tempering
HTML version of Basic Foils prepared 15 March 1996

Foil 65 Physical Optimization and Computation Approaches and their Field of Origin

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Examples of Physical Computation
  • Cellular Automata
  • Complex Systems
Physical (Pertaining to Nature) optimization and associated field
  • Genetic Algorithms Evolution
  • Simulated Annealing Physics(Statistical)
  • Neural Networks Biology (low level)
  • Information Theory Electrical Engineering
    • (Maximum Entropy)
    • ¥ ¥ ¥
  • Elastic Networks Physics (Determiistic)
  • Deterministic Annealing
These can be compared with
  • Heuristics Particular Problem
  • Combinatorial optimization Mathematics
  • Expert systems Computer Scienc (High level reasoning)
HTML version of Basic Foils prepared 15 March 1996

Foil 66 Genetic Algorithms for Data Decomposition

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Work of Nashat Mansour
HTML version of Basic Foils prepared 15 March 1996

Foil 67 Three Major Genetic Operators

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
A system is specified by a string of (binary) digits and evolves with a set of transitions generated by Genetic Operators
HTML version of Basic Foils prepared 15 March 1996

Foil 68 MultiScale Methods in Parallel Data Decomposition

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Parallel algorithms for
  • Genetic Algorithm
  • Simulated Annealing
  • Neural Networks
  • Are not "trivial"
  • Are not identical to sequential algorithms
Large problems (the "real world") require multiscale algorithms just as multigrid is faster than Gauss Seidel for large P.D.E.'s (take --> log Nnode, d=2,3)
HTML version of Basic Foils prepared 15 March 1996

Foil 69 Results of Various Physical Optimization Methods for Data Decomposition

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
This compares parallel Genetic(PGA), Simulated Annealing(PSA), Neural Network(PNN) and a wonderful heuristic(PRSB -recursive spectral bisection)
HTML version of Basic Foils prepared 15 March 1996

Foil 70 A similar but Larger Problem

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
This comes from work of Nashat Mansour
HTML version of Basic Foils prepared 15 March 1996

Foil 71 Some Overall Questions Relevant In Classisfying Optimization Problems and Methods

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
What is the shape of the objective function?
  • Correlated or uncorrelated minima?
Do you need the
  • exact global minimum
  • an approximate minimum
  • In this case, do you want solution to always be within some tolerance of exact solution
  • or, on the average, to be within tolerance
HTML version of Basic Foils prepared 15 March 1996

Foil 72 Two Types of Global Mininum and their relation to Local Minima

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Local minima in "physics" problems are closely correlated with true minimum
"Computer Science" grand challenges in optimization might look different
HTML version of Basic Foils prepared 15 March 1996

Foil 73 Typical Formalism for Physical Optimization

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Minimize E = E(parameters y)
y can be continuous or discrete, or a mix
Introduce a fake temperature T and set b = 1/T
  • Often T ~ distance scale at which you look at problem
Probability of state y = exp(-bE)/Z where
As b ® ¥, minimum E (ground state) dominates
Find y(T) by minimizing Free Energy
F = E - TS = -1/b log Z
HTML version of Basic Foils prepared 15 March 1996

Foil 74 Global and Local Minima in Temperature Dependent Free Energy

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Annealing tracks global minima by initializing search at temperature T by minima found at temperature T + dT
Movement at given temperature
Global Minimum moving with decreasing temperature
HTML version of Basic Foils prepared 15 March 1996

Foil 75 Comparison of Physical Optimization Methods

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Simulated annealing: find y(T) by Monte Carlo as mean over configurations at that temperature
Neural networks: y is discrete. Find y by mean field approximation
Elastic net: y is discrete, but use improved mean field including some or all constraints
Deterministic annealing: leave important y out of sum S. Find by simple iterative optimization
HTML version of Basic Foils prepared 15 March 1996

Foil 76 Some Applications of Deterministic Annealing

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
General, Travelling Salesman, Quadratic Assignment
  • Durbin and Willshaw, Frean
  • Yuille
  • Simic
Scheduling
  • Peterson and Soderberg (high school classes)
  • Johnston (Hubble Space Telescope)
Track Finding
  • Rose, (Fox, Gurewitz)
  • Ohlsson, Peterson, Yuille
Robot Path Planning, Navigation
  • Fox
Character Recognition
  • Hinton
Image Analysis
  • Geiger, Girosi
Clustering, Vector Quantization (coding), Electronic Packaging
  • Rose, et al.
HTML version of Basic Foils prepared 15 March 1996

Foil 77 Simulated Tempering -- a New Approach to Monte Carlo Optimization/Simulated Annealing

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
A new method Simulated Tempering by Marinari ( Rome, Syracuse) and Parisi (Rome)
Conventional Monte Carlo methods do not work well for Random Field Ising Model = RFIM
Spins si live on 3D lattice
si = +/-1 to be determined
Fixed Magnetic Field
hi = |h| ri
|h| = 1
ri = +/- 1 with random probability 1/2
HTML version of Basic Foils prepared 15 March 1996

Foil 78 The Conventional Simulated Annealing and its Problems for Random Field Ising Models

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 79 Key Idea in The Tempering Approach

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Add b to list of dynamical variables
b chosen out of {bm} with probability given by
  • Prob ( b, {s} ) a exp { - bm E ({s}) + gm}
b1 Increasing
b2
b3
b4
b5
Now system can move up in temperature and jump barrier
Don't have to decide on a priori annealing schedule i.e. list of bm and computer time to be spent at each bm.
HTML version of Basic Foils prepared 15 March 1996

Foil 80 Goodbye! Many Choices - Which is best When?

From Complex Systems and Parallel Computing CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Sun Feb 22 1998