[Next] [Previous] [Top]

Decompositon

Decompositon

• Converting a sequential program to a parallel equivalent

• A number of standard techniques or paradigms are available
  • sequential job farming or trivial decompostition

  • functional decomposition

  • data parallel
    • geometric

    • task farming

    • scattered spatial

Sequential Job Farming

Trivial decomposition

• Also known as replication

• Run the sequential version on each processor with
  • independent input files

  • independent output files

  • no interaction between the programs

• cf. running a batch job many times on a sequential machine

• Execution time is the time of the longest process

• Easy to implement

• Can be very efficient

Functional Decomposition

• Split the program into its functional sections and run each on a different processor

• Diagrammatic representation shows the program in the form of a pipeline

• Data flows from stage to stage down the pipeline

• Start up and shutdown times can significant on short runs

• Parallelism limited to number of stages

• Stages need to be balanced

• Further decomposition may be applied to each stage

Geometric Decomposition

• Similar processing on very many data items

• Distribute data for parallel processing and collect the results

• One item per processor
  • good for SIMD

  • poor for MIMD - communciation costs too high

• Clump data items into grains
  • optimum grain size is machine dependent

  • one grain per processor

  • slowest grain limits speedup

An Unbalanced Problem

Data Decomposition

Scattered spatial decomposition

• Unbalanced data set

• Allocate a randomly selected group of data grains to each processor

• Each processor should have an average workload

• Static load balancing

• Many more grains than processors

• Increased communications

• Therefore there is a trade-off between improved load balancing and increased communications overheads

Task Farm

• Unbalanced data set

• Source or master process partitions main task and allocates work to slave processors

• Worker/slave repeatedly
  • requests a grain of work

  • receives a grain

  • processes the grain

  • sends results to sink

• Sink combines partial results

• Dynamic load balancing

• Tasks must be processed independently

• Problems arise if
  • grains size not balanced to communications time

  • long latency between processing small grains

• Grains may be buffered

• There will be an unbalanced processor load once all the grains have been distributed

Decomposition

Techniques Summary