Why Parallel Computing?

From 1986 to 2003, microprocessor performance increased by an average of over 50% per year. This unprecedented increase meant that users and developers could simply wait for the next generation of processors to get a drastic improvement in their applications’ performance.

However, starting in 2003, the performance improvement of single processors (single-core) slowed down significantly, dropping to an increase of less than 4% annually in the 2015-2017 period. This difference is dramatic: at a 50% annual rate, performance increases almost 60-fold in 10 years; at a 4% rate, it increases by a factor of only 1.5.

1.1 The Need for Ever-Increasing Performance

The massive increase in computing power we have enjoyed for decades has been the engine of progress in fields like science, the Internet, and entertainment (e.g., human genome decoding, medical imaging, search engines, etc.). However, we cannot settle for this. As our computing power increases, so does the complexity of the problems we can seriously consider solving. Among these:

• Climate Modeling: More accurate models that include interactions between the atmosphere, oceans, and landmasses.
• Protein Folding: The study of the configurations of complex molecules (linked to diseases like Alzheimer’s or Parkinson’s) is limited by current computational power.
• Drug Discovery and Data Analysis: DNA sequencing, data generated by particle colliders (like CERN), all areas where massive amounts of data require massive computing power.

1.2 Why Are We Building Parallel Systems?

For years, the increase in processor performance was driven by the increase in transistor density on integrated circuits (historically linked to Moore’s Law). By shrinking transistors, it was possible to increase their frequency (clock speed).

However, as transistor speed increases, so does their power consumption. Most of this power is dissipated as heat. If an integrated circuit overheats, it becomes unreliable. In the first decade of the 21st century, air-cooled integrated circuits reached their physical limits of thermal dissipation (Power Wall or Thermal Wall).

Consequently, the hardware industry radically changed course: instead of developing ever-faster monolithic processors, manufacturers began placing multiple complete processors (cores) on a single integrated circuit. These processors are known as multicore systems.

Implications for Software

This architectural change has a fundamental consequence for developers: simply adding more cores does not magically improve the performance of serial programs (written for a single processor). A serial program running on a $p$-core machine will take the same amount of time it would take on a single-core system.

1.3 Why We Must Write Parallel Programs

Researchers have had very limited success in developing compilers capable of automatically converting serial programs (written in C, C++, or Java) into efficient parallel programs.

Although it is possible to automatically parallelize simple constructs (like independent for loops), the approach fails when seeking true efficiency. Optimal parallelization is often not achieved by translating a serial algorithm step-by-step, but by devising a completely new parallel algorithm.

Example: The Global Sum

Suppose we need to compute $n$ values and sum them together. The following interactive editor shows the serial approach. Try running it:

First Parallel Approach (Naïve)

If we have $p$ cores and $p \le n$, we can divide the work: each core computes a partial sum of about $n/p$ values. At the end, the partial sums must be recombined. If we delegate the work to a “master core” (e.g., core 0), it will have to receive and sum the remaining $p-1$ partial sums:

// Pseudocode for recombination (executed by Core 0)
if (I'm the master core) {
    sum = my_sum;
    for each core other than myself {
        receive value from core;
        sum += value;
    }
} else {
    send my_sum to the master;
}

Criticality: The master core must perform $p-1$ receive and add operations. If $p = 1000$, the master will do $999$ additions. The work is not well distributed!

Second Parallel Approach (Tree Structure)

Instead of making the master do all the work, the cores can pair up to sum the partial results in parallel, halving the number of active cores at each phase (logarithmic reduction algorithm).

If we have 8 cores, the steps are:

1. Odd cores send to the preceding even core (1 sends to 0, 3 to 2, 5 to 4, 7 to 6).
2. Cores 2 and 6 send to cores 0 and 4.
3. Core 4 sends to core 0, which gets the final sum (95).

flowchart TD
  subgraph P1["Phase 1: 4 parallel additions"]
      direction LR
      C0_1(("0: 8")) -->|Receives 19| C0_2(("0: 27"))
      C1_1(("1: 19")) -.->|Sends| C0_2

      C2_1(("2: 7")) -->|Receives 15| C2_2(("2: 22"))
      C3_1(("3: 15")) -.->|Sends| C2_2

      C4_1(("4: 7")) -->|Receives 13| C4_2(("4: 20"))
      C5_1(("5: 13")) -.->|Sends| C4_2

      C6_1(("6: 12")) -->|Receives 14| C6_2(("6: 26"))
      C7_1(("7: 14")) -.->|Sends| C6_2
  end

  subgraph P2["Phase 2: 2 parallel additions"]
      direction LR
      C0_2 -->|Receives 22| C0_3(("0: 49"))
      C2_2 -.->|Sends| C0_3

      C4_2 -->|Receives 26| C4_3(("4: 46"))
      C6_2 -.->|Sends| C4_3
  end

  subgraph P3["Phase 3: 1 parallel addition"]
      C0_3 -->|Receives 46| C0_4(("0: 95"))
      C4_3 -.->|Sends| C0_4
  end

Performance Analysis (Deep Dive): While the first method requires $\mathcal{O}(p)$ operations on the master, the reduction tree takes only $\mathcal{O}(\log_2 p)$ phases. If $p = 1000$ cores:

• Naïve Approach: $999$ sequential operations on the master.
• Tree Structure: $\approx 10$ phases (since $2^{10} = 1024$). An improvement by a factor of almost 100!

However, as is evident, the logic required to implement the tree in source code is significantly more complex than the single serial line sum += x;. For this reason, writing parallel programs requires careful design by the developer.