Offensive Security Researcher & Quantum Cryptography Analyst

Parallel Algorithm: Working, Explanation, and Concurrent Computing Design

Abdul Wahab Junaid
Parallel algorithm and working of this algorithm

Parallel algorithm and working of this algorithm

I want to walk through what a parallel algorithm is and why I think it matters so much for modern computing. A parallel algorithm is a method designed to run multiple operations at the same time, using multiple processors or cores, to solve a problem faster than a sequential algorithm could. I care about this topic because almost every modern CPU has multiple cores, and if I write only sequential code, I’m wasting most of the hardware I already own.

History and Background

I found that the theoretical foundations of parallel computing go back to the 1960s, when researchers began exploring how multiple processors could cooperate. Gene Amdahl’s 1967 paper introduced what became known as Amdahl’s Law, which quantified the limits of speedup from parallelization. Through the 1970s and 1980s, supercomputers with multiple processors became more common, and by the 2000s, as clock speeds plateaued and CPU manufacturers began adding more cores instead, parallel algorithms shifted from a specialized supercomputing topic to a mainstream necessity for everyday software.

Problem Statement

The problem parallel algorithms address is straightforward to me: a sequential algorithm uses only one processor at a time, even when many are available, leaving performance on the table. I need methods to break a computation into independent (or partially dependent) pieces that can run simultaneously, while still producing the correct final result and coordinating shared data safely.

Core Concepts

How It Works

  1. I identify parts of the problem that can be computed independently.
  2. I divide the input data or task into chunks, one per available processor/thread.
  3. Each processor works on its chunk simultaneously.
  4. When needed, processors synchronize to share intermediate results (using locks, barriers, or message passing).
  5. I combine partial results from all processors into the final answer.

Working Principle

The internal logic of parallel algorithms depends on identifying which parts of a computation are independent (no shared state, no ordering dependency) versus which parts require coordination. I try to maximize the independent portion, since that’s where actual parallel speedup comes from, while minimizing the coordination overhead, since synchronization is where performance is often lost.

Mathematical Foundation

Amdahl’s Law is the formula I always come back to. If $f$ is the fraction of a program that can be parallelized, and $p$ is the number of processors, the maximum theoretical speedup is:

$$S(p) = \frac{1}{(1-f) + \frac{f}{p}}$$

As $p \to \infty$, speedup approaches $\frac{1}{1-f}$, showing me that the sequential portion of a program caps the achievable speedup no matter how many processors I add. Gustafson’s Law offers a complementary view, accounting for growing problem sizes:

$$S(p) = p – (1-f)(p-1)$$

which better reflects real-world cases where I increase the workload as I add processors.

Diagrams

flowchart TD
    A[Problem] --> B[Divide into Sub-problems]
    B --> C[Processor 1 solves Sub-problem 1]
    B --> D[Processor 2 solves Sub-problem 2]
    B --> E[Processor 3 solves Sub-problem 3]
    C --> F[Combine/Merge Results]
    D --> F
    E --> F
    F --> G[Final Solution]

Pseudocode

function PARALLEL_SUM(array, num_threads):
    chunk_size = LENGTH(array) / num_threads
    partial_sums = ARRAY(num_threads)

    parallel for i = 0 to num_threads - 1:
        start = i * chunk_size
        end = start + chunk_size
        partial_sums[i] = SEQUENTIAL_SUM(array[start:end])

    total = 0
    for s in partial_sums:
        total = total + s
    return total

Step-by-Step Example

Suppose I want to sum the array [4, 8, 2, 9, 5, 1, 7, 3] using 4 threads.

  1. I split the array into 4 chunks of 2 elements: [4,8], [2,9], [5,1], [7,3].
  2. Thread 1 computes 4+8=12, Thread 2 computes 2+9=11, Thread 3 computes 5+1=6, Thread 4 computes 7+3=10 — all simultaneously.
  3. I combine the partial sums: 12+11+6+10 = 39.
  4. The final result, 39, matches what a sequential sum would give, but the work happened in parallel.

Time Complexity

For a problem of size $n$ with perfect parallelization across $p$ processors, time complexity drops from $O(n)$ sequentially to $O(n/p)$, plus an overhead term for combining results, often $O(\log p)$ for tree-based reductions.

Space Complexity

Space complexity typically grows to $O(n + p)$, since I need extra memory to store partial results from each of the $p$ processors in addition to the original data of size $n$.

Correctness Analysis

I consider a parallel algorithm correct if it produces the same result as its sequential counterpart regardless of the order in which threads execute, which requires that shared data be accessed safely (through proper synchronization) and that the combination step be independent of processor completion order — for example, addition is commutative and associative, so summing partial results in any order still gives the correct total.

Advantages

Disadvantages

Applications

I see parallel algorithms used in scientific simulations (weather modeling, physics simulations), image and video processing, machine learning training on GPUs, real-time rendering in games, large-scale sorting and searching, and financial modeling that requires fast Monte Carlo simulations.

Implementation in C

Here is a parallel array-sum implementation using POSIX threads in C.

#include <stdio.h>
#include <pthread.h>

#define NUM_THREADS 4
#define ARRAY_SIZE 8

int arr[ARRAY_SIZE] = {4, 8, 2, 9, 5, 1, 7, 3};
int partial_sums[NUM_THREADS];

typedef struct {
    int start;
    int end;
    int thread_id;
} ThreadArgs;

void* sum_chunk(void* arg) {
    ThreadArgs* args = (ThreadArgs*)arg;
    int sum = 0;
    for (int i = args->start; i < args->end; i++) {
        sum += arr[i];
    }
    partial_sums[args->thread_id] = sum;
    return NULL;
}

int main() {
    pthread_t threads[NUM_THREADS];
    ThreadArgs args[NUM_THREADS];
    int chunk_size = ARRAY_SIZE / NUM_THREADS;

    for (int i = 0; i < NUM_THREADS; i++) {
        args[i].start = i * chunk_size;
        args[i].end = args[i].start + chunk_size;
        args[i].thread_id = i;
        pthread_create(&threads[i], NULL, sum_chunk, &args[i]);
    }

    int total = 0;
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
        total += partial_sums[i];
    }

    printf("Total sum (computed in parallel): %d\n", total);
    return 0;
}

Sample Input and Output

Input: Array [4, 8, 2, 9, 5, 1, 7, 3] processed with 4 threads.

Output:

Total sum (computed in parallel): 39

Optimization Techniques

I improve parallel algorithm performance by minimizing shared-state access to reduce lock contention, using lock-free data structures where possible, balancing workload evenly across processors to avoid idle threads, and choosing chunk sizes that fit well within cache lines to reduce false sharing.

Common Mistakes

I often see race conditions caused by unsynchronized access to shared variables, deadlocks from improper lock ordering, over-parallelizing small tasks where thread creation overhead outweighs the benefit, and false sharing, where independent variables placed on the same cache line cause unnecessary cache invalidation between threads.

Further Reading

Exit mobile version