Full HTML for

Basic foilset Physical Optimization and Physical Computation -- CPS713 update from November 1992 Talk at Houston Keck Symposium

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

Physical Optimization applies a set of Optimization (minimization) methods motivated by physical processes to general optimization problems
These include simulated annealing, neural networks, deterministic annealing, simulated tempering and genetic algorithms
We look at general TSP, clustering in physical spaces, track finding, navigation, school class scheduling, Random field Ising Models and data decomposition and other computing optimization problems
We discuss when methods such as neural networks are effective

Table of Contents for full HTML of Physical Optimization and Physical Computation -- CPS713 update from November 1992 Talk at Houston Keck Symposium

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
1 Physical Optimization and Computation
2 Abstract of Physical Computation/Optimization Presentation
3 Physical Optimization and Computation Approaches and their Field of Origin
4 Optimization as used by Mother Nature and Physics
5 Some Overall Questions Relevant In Classisfying Optimization Problems and Methods
6 Two Types of Global Mininum and their relation to Local Minima
7 Characteristics of Some Basic Optimization Methods
8 Basic Philosophy of Physical Computation
9 Typical Formalism for Physical Optimization
10 Global and Local Minima in Temperature Dependent Free Energy
11 Comparison of Physical Optimization Methods
12 Sample Problem Illustrating Deterministic Annealing (Gurewitz and Rose)
13 A deterministic annealing approach to clustering (Gurewitz and Rose)
14 Details of Clustering Algorithm
15 Comparison of Isodata and Deterministic Annealing
16 Temperature Dependence of Deterministic Annealing
17 Temperature Lowered "below" cluster size
18 Phase Transitions in Physical Optimization Approach
19 TSP or Travelling Salesperson Problem
Classic NP-complete discrete optimization problem
20 Neural Net Compared to Elastic Net
21 Generalized Elastic Network
(Simic's derivation of Durbin and Willshaw's Elastic Net for TSP)
22 Terms in Neural and Elastic Net Energy Functions
23 General Structure of Physical Optimization
24 Comparison of Strategy in Elastic and Strategy
25 Physical Model Underlying Elastic Net
26 Typical TSP Solution with Elastic Net
27 Deterministic Annealing versus Multistate Neurons
28 Elastic Net for Navigation
29 Physical Optimization Formulation of Navigation Problems
30 Results of a Simple Two Vehicle Navigation Problem
31 Results of a Simple Four Vehicle Navigation Problem
32 Deterministic Annealing for Navigation
33 General Comments on Physical Optimization for Navigation
34 Physical Optimization in Computational Chemistry
35 Some Applications of Deterministic Annealing
36 Simulated Tempering -- a New Approach to Monte Carlo Optimization/Simulated Annealing
37 The Conventional Simulated Annealing and its Problems for Random Field Ising Models
38 Key Idea in The Tempering Approach
39 RFIM with Simulated Tempering
40 RFIM with Simulated Tempering
41 Some Scheduling Problems in NASA
42 Physical Computation Formulation of University Class Scheduling Problems
43 Hard Constraints in University Class Scheduling
44 Soft(er) Constraints
45 Soft(er) Constraints -- Continued
46 Approaches to Complexity
47 Computing as a set of Maps
48 Computing is "just" an optimization problem but what should we optimize?
49 General Issues for Physical Optimization in Computing
50 Physical Optimization in the Execution of Programs
51 Use of Physical Optimization in High Performance Fortran
52 Typical Example of Data Mapping Problem
53 Next slide is also page 26 of aus talk a
Features of Data to Processor Space Mapping:
54 Data Allocation Approaches
55 Computing as a Physics Problem
56 Mapping Problem: Criteria
57 Decomposition of an Arch onto 16 Processors in a Hypercube
58 Comparison of Parallel Data Decomposition Algorithms
59 Comparison of Parallel Data Decomposition Algorithms
60 MultiScale Methods in Parallel Data Decomposition
61 Mapping Times for Multiscale Algorithms
62 One can get Different Answers from Heuristics depending on Initial Labelling
63 Note: Lesson from 1990 CRPC workshop on TSP at Rice
64 An Irregular Decomposition for Fluid Flow
65 Comparison of Neural Networks for TSP and Data Decomposition
66 NP Completeness and Neural Networks In Summary
67 Optimization in Program Preparation / Code Generation
68 Track Finding Posed as a Problem
69 Track Finding when there are a lot of tracks
70 Neural Networks for Track Finding
71 Track Finding in Intermediate Cases
72 Original Data Set Used by Gurewitz and Rose
73 Results of Deterministic Annealing applied to Dirty Dataset
74 Conclusions on Physical Optimization for Track Finding
75 Conclusions in Physical Optimization
76 Goodbye! Many Choices - Which is best When?

Outside Index Summary of Material

HTML version of Basic Foils prepared 15 March 1996

Foil 1 Physical Optimization and Computation

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Geoffrey C. Fox
Syracuse University
315.443.2163
Third Keck Symposium on Computational Biology
Houston, Texas - Nov. 1, 1992
HTML version of Basic Foils prepared 15 March 1996

Foil 2 Abstract of Physical Computation/Optimization Presentation

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Physical Optimization applies a set of Optimization (minimization) methods motivated by physical processes to general optimization problems
These include simulated annealing, neural networks, deterministic annealing, simulated tempering and genetic algorithms
We look at general TSP, clustering in physical spaces, track finding, navigation, school class scheduling, Random field Ising Models and data decomposition and other computing optimization problems
We discuss when methods such as neural networks are effective
HTML version of Basic Foils prepared 15 March 1996

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

From Physical Optimization and Physical Computation 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 4 Optimization as used by Mother Nature and Physics

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Nature is often solving optimization problems
  • On long term, evolution of species
  • On short term, interpretation of visual and other sensor information
Physics laws can usually be formulated as variational (optimization) problems
We can also - and indeed this should be the norm? - combine methods
  • e.g. nature uses a bunch of different approachs for optimizing human race:
  • Genetic algorithms evolve people over long time period
  • Expert systems for high level reasoning
  • Learning networks and ? for intermediate level vision
  • optimization networks for low level vision
HTML version of Basic Foils prepared 15 March 1996

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

From Physical Optimization and Physical Computation 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 6 Two Types of Global Mininum and their relation to Local Minima

From Physical Optimization and Physical Computation 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 7 Characteristics of Some Basic Optimization Methods

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Different methods have different trade offs
  • Robustness, accuracy, speed, suitability for parallelization,
  • problem size dependence
Neural networks do simple things on large data sets and parallelize easily
Expert systems do complex things on small data sets and parallelize with difficulty
Combinatorial Optimization
  • Finds exact minima in a time that is exponential in problem size. However in particular cases, e.g. TSP, very clever special techniques make this quite practical - solve exactly 104 ® 105 city problem if we can parallelize
Physical Optimization
  • Finds approximate minima in a time that is sometimes only linear log(linear) in system size.
  • Sometimes we only want approximate minima
HTML version of Basic Foils prepared 15 March 1996

Foil 8 Basic Philosophy of Physical Computation

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
As computers get more powerful, we need to solve larger problems and physical computation methods get more attractive
  • Thermodynamics studies bulk properties of large systems independent of irrelevant microscopic detail
  • Physical computation can solve 1000 times bigger problems on 1000 times bigger machines
  • Whereas combinatorial method can't do much that much better as only logarithmic not linear improvement
Illustrates that "computer science" benefits from broad intellectual base that includes biology and physics as well as mathematics and electrical engineering
HTML version of Basic Foils prepared 15 March 1996

Foil 9 Typical Formalism for Physical Optimization

From Physical Optimization and Physical Computation 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 10 Global and Local Minima in Temperature Dependent Free Energy

From Physical Optimization and Physical Computation 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 11 Comparison of Physical Optimization Methods

From Physical Optimization and Physical Computation 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 12 Sample Problem Illustrating Deterministic Annealing (Gurewitz and Rose)

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
The Test Problem (x=real center)
HTML version of Basic Foils prepared 15 March 1996

Foil 13 A deterministic annealing approach to clustering (Gurewitz and Rose)

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
For each data point x there is an energy Ex(j) for its association with the cluster Cj. The probability that x belongs to cluster Cj is:
where Zx is the partition function
and Fx is the free energy
The total free energy is:
HTML version of Basic Foils prepared 15 March 1996

Foil 14 Details of Clustering Algorithm

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Use The Squared Distance Energy
Optimizing the free energy:
yields the solution for the centers of the clusters:
Note 1/b1/2 is distance scale at which clusters are observed
  • High temperature (small b) corresponds to coarse spatial resolution
HTML version of Basic Foils prepared 15 March 1996

Foil 15 Comparison of Isodata and Deterministic Annealing

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Isodata is "greedy" algorithm likely to find local minima
HTML version of Basic Foils prepared 15 March 1996

Foil 16 Temperature Dependence of Deterministic Annealing

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
More clusters Emerge as temperature is lowered and one looks at system with better resolution
HTML version of Basic Foils prepared 15 March 1996

Foil 17 Temperature Lowered "below" cluster size

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 18 Phase Transitions in Physical Optimization Approach

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
The clustering problem - like any good physical system - exhibits phase transitions as one lowers the temperature
HTML version of Basic Foils prepared 15 March 1996

Foil 19 TSP or Travelling Salesperson Problem
Classic NP-complete discrete optimization problem

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Can be viewed as constrained clustering which approach "derives" elastic net from deterministic annealing
HTML version of Basic Foils prepared 15 March 1996

Foil 20 Neural Net Compared to Elastic Net

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Classical Neural Network Approach to TSP
    • hip= 1 : city p visited at time i
    • = 0 : otherwise
    • With Constraint that
    • for each i only one hip nonzero
Elastic net (roughly)
    • hi = p multistate neuron
    • (actually position in space of cities)
Simic showed how neural network (Hopfield-Tank) and elastic net came from making different mean field approximations to the same physical free energy
HTML version of Basic Foils prepared 15 March 1996

Foil 21 Generalized Elastic Network
(Simic's derivation of Durbin and Willshaw's Elastic Net for TSP)

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Review of TSP Application in neural variables
HTML version of Basic Foils prepared 15 March 1996

Foil 22 Terms in Neural and Elastic Net Energy Functions

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Typical Hopfield Tank Energy Functions
Typical Elastic Net Energy Functions
HTML version of Basic Foils prepared 15 March 1996

Foil 23 General Structure of Physical Optimization

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Energy = Real Goal (S d)
    • + (*)
    • + (**)
Consider a physical system with this energy function at temperature T
Minimize F = free energy = E - TS as T ® 0
Use "mean field" approximation to make annealing deterministic
HTML version of Basic Foils prepared 15 March 1996

Foil 24 Comparison of Strategy in Elastic and Strategy

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Hopfield-Tank Neural Network
  • Apply physical procedure to full F where we allow h's to vary over all 0,1 values with constraints (*), (**) enforced by penalty functions
Simic's Derivation of Elastic Net
  • Let h vary over a restricted space where we choose to satisfy some of the constraints exactly.
  • In TSP, one can choose either (*) or (**)
  • Remarkable this converts
  • neural picture into a
  • particle dynamics problem
HTML version of Basic Foils prepared 15 March 1996

Foil 25 Physical Model Underlying Elastic Net

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 26 Typical TSP Solution with Elastic Net

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Showing Temperature dependence of Path
HTML version of Basic Foils prepared 15 March 1996

Foil 27 Deterministic Annealing versus Multistate Neurons

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
In elastic net use x ( i ) ( position in city space at time i )
Equivalently consider a multistate neuron hi taking values in space x
Binary neurons ---> Ising model
Multistate neurons ---> Potts model ( if discrete x ) or continuous spin model ( x continuous)
HTML version of Basic Foils prepared 15 March 1996

Foil 28 Elastic Net for Navigation

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Can be applied to single or multiple vehicle problem
Note temperature T allows large changes at high T
e.g. to jump over a large obstacle,
T is again physical scale
Neural Net variables hi(x,t) are redundant
Elastic Net (string) variables xi(t)
HTML version of Basic Foils prepared 15 March 1996

Foil 29 Physical Optimization Formulation of Navigation Problems

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
New effect: >1 (2 in fact) Lagrange multipliers
exp[-b1 E1 -b2 E2] bi = bi(T)
In this problem, goal (E1) easy to satisfy but constraints (E2) hard
At high temperatures make E2 go away
  • b2/b1 ® 0 as T ® ¥ implies that E1 = 0
(elastic string of zero length) is global minimum
Decrease temperature and gradually "switch on" constraint such that as T-> 0, constraint is rigorously enforced
    • Choose b2/b1 ® ¥ as T ® 0
e.g. b1 = 1/T b2 = 1/T2
HTML version of Basic Foils prepared 15 March 1996

Foil 30 Results of a Simple Two Vehicle Navigation Problem

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Neural Networks From Gurewitz-Rose-Fox
HTML version of Basic Foils prepared 15 March 1996

Foil 31 Results of a Simple Four Vehicle Navigation Problem

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Neural Networks From Gurewitz-Rose-Fox
HTML version of Basic Foils prepared 15 March 1996

Foil 32 Deterministic Annealing for Navigation

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
(Ghandi, Fox unpublished)
HTML version of Basic Foils prepared 15 March 1996

Foil 33 General Comments on Physical Optimization for Navigation

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Most work on navigation concentrates on exact methods (combinatorial optimization) for a few degrees of freedom
Physical optimization allows very many vehicles to be navigated
  • Air traffic control
  • Land vehicles
  • Robot manipulators
  • Looks very promising for multiple manipulator problem which is otherwise intractable
But we must use elastic net - neural networks gave us right general idea, but too many constraints
HTML version of Basic Foils prepared 15 March 1996

Foil 34 Physical Optimization in Computational Chemistry

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Hamiltonian (used) = Hamiltonianbasic (i.e. that given by Nature) +
HC = Hamiltonian ( Constraints from experimental measurements or chemical knowledge)
Then can either Evolve system by Monte Carlo
or equivalently HC is minimized by Simulated Annealing
Or one can Evolve system by Newton's Laws
or equivalently HC is minimized by Deterministic Annealing
HTML version of Basic Foils prepared 15 March 1996

Foil 35 Some Applications of Deterministic Annealing

From Physical Optimization and Physical Computation 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 36 Simulated Tempering -- a New Approach to Monte Carlo Optimization/Simulated Annealing

From Physical Optimization and Physical Computation 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 37 The Conventional Simulated Annealing and its Problems for Random Field Ising Models

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 38 Key Idea in The Tempering Approach

From Physical Optimization and Physical Computation 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 39 RFIM with Simulated Tempering

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Showing that multiple "global" minima are visited
HTML version of Basic Foils prepared 15 March 1996

Foil 40 RFIM with Simulated Tempering

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Showing that stuck in a local minim
HTML version of Basic Foils prepared 15 March 1996

Foil 41 Some Scheduling Problems in NASA

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Schedule observations on planetary orbiter subject to physical constraints of power, which instruments near each other, etc. dynamically (new "moon" discovered ---> change schedule). Several hundred people devoted to this at JPL .
Similar space telescope problem
There is a major scheduling problem in shuttle operations
Originally NASA hoped to turn shuttle around in ~2 weeks. Actually takes ~4 months
In orbiter processing facility
  • 60,000 technician hours
  • 10,000 tasks
    • 50% generic
    • 50% mission specific
  • maybe >1 shuttle to share critical teams
HTML version of Basic Foils prepared 15 March 1996

Foil 42 Physical Computation Formulation of University Class Scheduling Problems

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Peterson and Soderberg, Lund applied physical optimization to scheduling smaller high school problems
Currently Syracuse University spends ~3 weeks scheduling freshmen classes. (the time critical case)
Variables are "multi-state" neurons x i
Student (preferences) are the "quanta" of force acting on particles i. These particles move in space of ( classroom, time slot ).
This is thesis topic of Saleh ElMohammed
HTML version of Basic Foils prepared 15 March 1996

Foil 43 Hard Constraints in University Class Scheduling

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
x i must be singled valued i.e. a (teacher, class) event occupies one spacetime slot
x i = x j if i = j
A given teacher can only teach one class at a time
HTML version of Basic Foils prepared 15 March 1996

Foil 44 Soft(er) Constraints

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Each student should be allowed a "lunch class" if possible
The different meetings of a given class should be spread over a week
Each student's MWF and T Th classes should be roughly balanced
Distance constraints between classrooms -- students and Professors should not have to run between classes
HTML version of Basic Foils prepared 15 March 1996

Foil 45 Soft(er) Constraints -- Continued

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Student must meet eligibility requirements for class
Do not enroll athletes in courses that conflict with their sports practice (hard or soft constraints depending on sport)
Balance enrollment in different sections of a given class
Balance gender in Honors Seminar sections
Enroll students in all parts of a course when linked e.g. recitation and lecture
Satisfy student preferences
HTML version of Basic Foils prepared 15 March 1996

Foil 46 Approaches to Complexity

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Dynamical Systems
  • A complicated system is really only sensitive to a few parameters in a space whose dimension can be determined (perhaps not very reliably)
  • Parameters (assumed to be) governed by coupled differential equations ----> chaos
Statistical Systems
  • Don't ignore the (1023) (other) degrees of freedom but rather sum over them subject to constraints ---> maximize information, entropy ..........
Are approaches consistent?
  • Thermodynamics does show how macroscopic variables emerge from a statistical formulation. How ever only a qualitative relation between dynamical and statistical systems ?
  • "Back-propagation" neural networks unbiased parameterization
HTML version of Basic Foils prepared 15 March 1996

Foil 47 Computing as a set of Maps

From Physical Optimization and Physical Computation 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 48 Computing is "just" an optimization problem but what should we optimize?

From Physical Optimization and Physical Computation 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 49 General Issues for Physical Optimization in Computing

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Various optimizations are possible at each stage of mapping. These can be (but usually are not) formulated as minimizing
  • E = E1 (Performance) + E2 (Constraints)
This is a difficulty if constraint ensures correctness of calculation as in code generation phase of optimizing compiler for a digital computer. Then we must have E2=0 at T=0.
This "correctness" issue might not be present in generation of "programs" for neural (as opposed to digital) supercomputers.
We can study use of physical optimization in generation or execution of program
HTML version of Basic Foils prepared 15 March 1996

Foil 50 Physical Optimization in the Execution of Programs

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Both Message Routing
  • Dynamic or static decomposition
  • or scheduling of data or processes
  • need "performance" optimized
  • and are satisfied with reasonable (~ within 20% of best) answers
  • and have no difficult correctness constraints
    • Heuristics
    • Simulated Annealing
    • Neural Networks (static data)
    • Elastic Nets (messages)
  • work well
HTML version of Basic Foils prepared 15 March 1996

Foil 51 Use of Physical Optimization in High Performance Fortran

From Physical Optimization and Physical Computation 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 52 Typical Example of Data Mapping Problem

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Given: Data set and Algorithm / Solver
Assumptions: Data Parallelism Loosely Synchronous Computation model Distributed-memory MIMD multiprocessor
Definitions: Computation graph GC = (VC, EC) Multiprocessor graph GM = (VM, EM)
HTML version of Basic Foils prepared 15 March 1996

Foil 53 Next slide is also page 26 of aus talk a
Features of Data to Processor Space Mapping:

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
MAP: VC ----> VM
such that Execution time of parallel algorithm/solver is minimized
Represent mapping configuration by MAP[ vi ] = pj
HTML version of Basic Foils prepared 15 March 1996

Foil 54 Data Allocation Approaches

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Allocation problem as a graph isomorphism problem
  • - a maximum number of pairs of communicating modules fall into pairs of directly connected processors
Allocation problem as a quadratic assignment problem
-
Allocation problem as a minmax problem
-
Geometry based allocation approach
  • - represent the partioning of the domain by a graph
  • - represent the parallel machine by a graph
  • - project the problem and system graphs into the 2D-euclidean space
  • - solve a planar assignment problem
  • - Iteratively improve the initial assignment
HTML version of Basic Foils prepared 15 March 1996

Foil 55 Computing as a Physics Problem

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
This optimization can also be thought of as finding ground state of a "physics" problem. The particles are "entities" (grid points) moving around in space with "# processors" discrete positions.
Repulsive force - load balance
Attractive force - communicate
HTML version of Basic Foils prepared 15 March 1996

Foil 56 Mapping Problem: Criteria

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Decompose the geometric data structures in a specified number of subdomains (substructures) so that:
  • the subdomains have the "same" number of elements or grid points
  • the interfaces amomg the subdomains is "small"
  • the number of adjacent subdomains is minimal
  • each subdomain is compact domain
Allocate the subdomains to processors, so that:
  • geometrically neighbor subdomains are allocated to neighbor processors in the interconnection network of given parallel machine, and
Decouple (color) the processors so that:
  • the local synchronization among the processors is edge contention free.
HTML version of Basic Foils prepared 15 March 1996

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

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
from Chrisochoides
HTML version of Basic Foils prepared 15 March 1996

Foil 58 Comparison of Parallel Data Decomposition Algorithms

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Recursive Bisection, Neural Network, Simulated Annealing and Genetic Algorithms
HTML version of Basic Foils prepared 15 March 1996

Foil 59 Comparison of Parallel Data Decomposition Algorithms

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Here we compare time to do mapping -- previous page describes time to execute mapped code
HTML version of Basic Foils prepared 15 March 1996

Foil 60 MultiScale Methods in Parallel Data Decomposition

From Physical Optimization and Physical Computation 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 61 Mapping Times for Multiscale Algorithms

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 62 One can get Different Answers from Heuristics depending on Initial Labelling

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Any approximate method can be dangerous when applied by
  • expert - can apply " too precisely"
  • non-expert - can apply imprecisely
HTML version of Basic Foils prepared 15 March 1996

Foil 63 Note: Lesson from 1990 CRPC workshop on TSP at Rice

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
The published exact, simulated annealing (etc.) papers have been greatly improved but
Each new heuristic for TSP shows how their method is better than published results which are not "state of the art" ....
Again many say "simulated annealing" or "genetic algorithms" too slow for data decomposition
Only true for some (naive) implementations
HTML version of Basic Foils prepared 15 March 1996

Foil 64 An Irregular Decomposition for Fluid Flow

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Roy Williams at Caltech
HTML version of Basic Foils prepared 15 March 1996

Foil 65 Comparison of Neural Networks for TSP and Data Decomposition

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Neural Networks work well for NP-complete load balancing problem but fail for formally equivalent TSP. Why?
Label data or processes by i = 1 ... M
  • and processor nodes by p = 1 .. N = 2d
The redundant choice of NM neural (binary) variables
  • h(i,p) = 1 data point i on node p
    • = 0 otherwise
Fails for same reason as for TSP
The nonredundant choice (NO constraints in E) of Mlog2N neural variables
  • i ® P(i)
  • P(i) = Sd-1 2k h(i,k) succeeds
Þ Not all NP-complete problems are created equal
HTML version of Basic Foils prepared 15 March 1996

Foil 66 NP Completeness and Neural Networks In Summary

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Neural Networks work well for data decomposition as neural variables are natural nonredundant description
In "analogous" TSP and navigation problems, constraints on redundant neural variable Þ elastic net (can view as a generalized neural net) better
Why do all methods work so well for graph partitioning when computer scientists are taught to be terrified by such NP complete problems
HTML version of Basic Foils prepared 15 March 1996

Foil 67 Optimization in Program Preparation / Code Generation

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Advice on which algorithms and which machine to use
Choose compiler transformations and strategy: loop unrolling, interchange - discrete set of choices at each of many program fragments
Given transformation, find performance on given machine
Static and Dynamic Decomposition
Local Register Assignments, peephole optimizations, pipelining, etc.
HTML version of Basic Foils prepared 15 March 1996

Foil 68 Track Finding Posed as a Problem

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Given a bunch of measurements xm(t), find the best tracks given certain prejudice as to nature of particles or missiles
Case I: I -> 20 Tracks
    • Kalman Filter or
    • c2 method
  • Do a combinatorial search to
  • choose for each time tk which
  • measurements belong to which
  • tracks. Use c2 and various
  • heuristics to reject spurious tracks and accept good tracks
  • o Fails if many tracks or lot of noise
  • o Difficult to parallelize except on a few nodes
HTML version of Basic Foils prepared 15 March 1996

Foil 69 Track Finding when there are a lot of tracks

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Case II: Very Many Tracks
  • In one space (plus time) this tracking problem is formally equivalent to edge detection in vision.
  • In vision, measurements are the discontinuities (differentiations) of color / motion / texture etc. in an image. Edge detection involves linking this basic data into "lines" which will separate regions of image.
    • Solve by neural network method
    • h(x) = 1 if there is an edge
    • = 0 if there is no edge
    • In vision x = (x,y), tracking x = (x,t)
  • h is a field theory formalism, whereas Kalman Filter is a particle formalism
HTML version of Basic Foils prepared 15 March 1996

Foil 70 Neural Networks for Track Finding

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Analogy to Travelling Salesperson Problem:
  • Hopfield-Tank use h(x) with x = (x,t) with t labelling tour and x labelling city
  • Two critical differences
    • TSP: Only 1 tour so Hopfield-Tank very redundant and must satisfy difficult constraint
    • Vision: Many tours and indeed unknown number of tours, so less redundancy and no constraints!
TRW have implemented this approach to tracking
Neural network degrees of freedom independent of number of tracks! (Kalman filter gets difficult as number of tracks becomes large and unknown)
Neural network has essentially unlimited parallelism
Again neural networks "work" when these are natural degrees of freedom
HTML version of Basic Foils prepared 15 March 1996

Foil 71 Track Finding in Intermediate Cases

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Case III: Intermediate Number of Tracks or
Few Tracks with Dirty Data
  • Now we want to view total tour (track) as a single entity and use either annealing or elastic net methods?
  • Kalman filter fails as it uses information incrementally - adds one time slice to previous local track
  • c2 gets stuck in a local minimum - need concept of temperature to avoid false minima
  • Neural networks inefficient as too much redundancy
  • Deterministic Annealing (elastic net) is a good possibility
  • Rose has tested this
  • Note in tracking, tracks are attracted to measurements;
  • in navigation, vehicles are repelled from obstacles, otherwise identical
HTML version of Basic Foils prepared 15 March 1996

Foil 72 Original Data Set Used by Gurewitz and Rose

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
A very "dirty" data set
HTML version of Basic Foils prepared 15 March 1996

Foil 73 Results of Deterministic Annealing applied to Dirty Dataset

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
HTML version of Basic Foils prepared 15 March 1996

Foil 74 Conclusions on Physical Optimization for Track Finding

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
So not only do different problems need different methods but in a fixed problem - varying parameter values causes best method to change
Tracking is like a multiple TSP with each track like a salesman
The quality of solution needed depends on quality of data. Also as time advances, one can get new information and physical computation naturally allows time dependent data
E.g. in related navigation problems, you may start with some information about terrain and update it with new sensory data
HTML version of Basic Foils prepared 15 March 1996

Foil 75 Conclusions in Physical Optimization

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. *
Full HTML Index
Physical Optimization is a class of naturally parallel heuristics that solve "hard problems" quickly but approximately
Monte Carlo or Deterministic
Choice of variables is important
No universally "good" method even in a given problem, different methods are appropriate for different parameter values
Temperature controls a generalized multiscale approach
  • Clustering T 1/2 was distance resolution
  • Navigation 1/T controlled importance of obstacles
    • i.e. T is "resolution" in parameter space
HTML version of Basic Foils prepared 15 March 1996

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

From Physical Optimization and Physical Computation 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