Nature of Parallelism
Introduction
The development of an efficient software application on a parallel
computer takes at least an order of magnitude more time than it
would on a sequential system.
- Programming Paradigms.
- Other issues.
- HPC Software.
Programming Paradigms - principal types
- Data Parallelism (geometric).
- Functional Parallelism (procedural).
- Farm parallelism (task)
Data Parallelism
- Divide data up amoungst processors.
- Process different data segments in parallel
- Communicate boundary information, if necessary.
Functional Parallelism
- Decompose algorithm into different sections.
- Assign sections to different processors.
Farm Parallelism
- Pool of similar task to process.
- Farm of "worker" processors.
- "workers" process tasks from pool.
Nature of Parallelism
When developing and producing codes to exploit parallel computers a number of
fundamental factors need to be taken into account.
Other Issues:
- Load Balancing.
- Scalability.
- Speed-up.
- Efficiency.
Load balancing
This is the assignment of tasks to the processors of the system so as to keep
each processor busy most of the time.
- A mapping problem in which we need to find an optimal assignment of tasks
to processors.
In static load balancing tasks are assigned to processors at the
beginning of the execution according to a fixed schedule.
In dynamic load balancing tasks are assigned as the computation proceeds.
Scalability.
This is the ability of a program to exhibit good speed-up as the number of
processors used is increased.
We achieve this by:
- Minimising the amount of data communicated.
- Exploit data locality - effective data distribution strategy.
- Load balancing the problem being solved.
- Minimising data contention costs.
- Minimising synchronisation costs.
Speed-up - Amdahl's Law
- Used to estimate the potential speed-up in a parallel algorithm.
- Potential speed-up is limited by the sequential part of a computer
program.
- s - Serial time
Speed-up
- Used to estimate the relative program performance as the number processors
increases.
- Ambiguous measurement - best serial time versus parallel program running
on one processor...
- Speed-up provides an indication of the effective number of processors
utilised.
- T(n) - Time on n processors
Efficiency
- Used as a measure of the effective hardware use.
- T(n) - Time on n processors
HPC Software
- System Software - software that is used to manipulate, control and monitor
the hardware.
- Software Development Tools - software that is used by an applications
developer to produce executable programs.
- Applications Software - software that describes the behaviour of an
application.
Montry-Worlton Iceberg Metaphor
Software Development Tools
- Compilers
- Fortran/C
- Libraries
- numerical/graphical
- Debuggers
- break-point/post-mortem
- Monitoring/profiling
- hot spots/comms patterns
- IDA
- reduce data dependancies
- Automatic Parallelisers
- aid parallelisation
Programming Paradigms
- Message Passing
- Conventional languages (Fortran 77, C, ...).
- Message passing via libraries - PARMACS, PVM, MPI, ...
- User defines data partitioning and message passing calls.
- Flexible and efficient, but difficult to do.
- Data Parallel
- Extensions to existing languages - DAP Fortran, CM-Fortran, HPF...
- Some user definition of data partitioning, rest done by compiler.
- Needs regular decomposition of data, but easier to program in.
Submitted by Mark Johnston
Last updated 6 April 1995