Approaches to Parallel Programming, Levels of Parallelism

Approaches to Parallel Programming

  • A sequential program is one that runs on a single processor and has a single line of control.
  • To make many processors collectively work on a single program, the program must be divided into smaller independent chunks so that each processor can work on separate chunks of the problem.
  • The program decomposed in this way is a parallel program.
  • A wide variety of parallel programming approaches are available.
  • The most prominent among them are the following.
  • Data Parallelism
  • Process Parallelism
  • Farmer-and-worker model
  • The above said three models are suitable for task-level parallelism. In the case of data-level parallelism, the divide-and-conquer technique is used to split data into multiple sets, and each data set is processed on different PEs using the same instruction.
  • This approach is highly suitable to processing on machines based on the SIMD model.
  • In the case of Process Parallelism, a given operation has multiple (but distinct) activities that can be processed on multiple processors.
  • In the case of Farmer-and-Worker model, a job distribution approach is used, one processor is configured as master and all other remaining PEs are designated as slaves, the master assigns the jobs to slave PEs and, on completion, they inform the master, which in turn collects results.
  • These approaches can be utilized in different levels of parallelism.

Levels of Parallelism

  • Levels of Parallelism are decided on the lumps of code ( grain size) that can be a potential candidate for parallelism.
  • The table shows the levels of parallelism.
  • All these approaches have a common goal
    • To boost processor efficiency by hiding latency.
    • To conceal latency, there must be another thread ready to run whenever a lengthy operation occurs.
  • The idea is to execute concurrently two or more single-threaded applications. Such as compiling, text formatting, database searching, and device simulation.