Granularity of Parallel Systems

Granularity of Parallel Systems

• Granularity is a measure of the amount of work (or computation) performed by a task.
• It can also be defined as the ratio of computation time to communication time, wherein:
  • Computation time is the time required to perform the computation of a task.
  • Communication time is the time required to exchange data between processors.

Calculating Granularity

• Granularity (G) can be calculated as: G = Tcomp / Tcomm
• Granularity is usually measured in terms of the number of instructions executed in a particular task.
• Alternatively, it can be specified in terms of the execution time of a program, combining the computation time and communication time.

Types of Parallelism

Fine-grained Parallelism

• A program is broken down into a large number of small tasks.
• These tasks are assigned individually to many processors.
• The amount of work associated with a parallel task is low and the work is evenly distributed among the processors.
• Example: The system of neurons in our brain.

Coarse-grained Parallelism

• A program is split into large tasks.
• A large amount of computation takes place in processors.
• This might result in load imbalance, where certain tasks process the bulk of the data while others might be idle.
• Advantage: Low communication and synchronization overhead.
• Example: Message-passing architecture.

Medium-grained Parallelism

• A compromise between fine-grained and coarse-grained parallelism.
• Task size and communication time are greater than fine-grained parallelism and lower than coarse-grained parallelism.
• Example: General-purpose parallel computers.

Effects of Granularity in Parallel and Distributed Computing

• Using fewer processors can improve performance of parallel systems.
• Scaling down a parallel system means using fewer than the maximum possible number of processing elements to execute a parallel algorithm.
• Optimal performance is achieved between the two extremes of fine-grained and coarse-grained parallelism.