Sequential vs Parallel Computing to Count Occurrences Using OpenMP (Linear Search)

parallel_count.cpp

/*
How Parallel Computing Works to Count Occurrences Using OpenMP (Linear Search)

OpenMP internally performs the following steps to parallelize the counting process:

1. Creates a team of threads (fork)
   Suppose the system has 8 cores → OpenMP creates threads:
   T0, T1, T2, T3, T4, T5, T6, T7

2. Divides loop iterations among threads (work-sharing)
   Each thread scans a portion of the array:
   - T0 checks arr[0 ... 12499999]
   - T1 checks arr[12500000 ... 24999999]
   - ...

3. Each thread keeps a private counter
   Each thread gets its own local copy:
   count_T0, count_T1, count_T2, ...

   Threads increment their local counter whenever:
   arr[i] == target

4. Reduction (join)
   OpenMP safely merges all private counters:
   total_count = count_T0 + count_T1 + count_T2 + ...

5. Threads are destroyed
   Execution returns to a single main thread.

This program compares:
- Sequential linear search
- Parallel linear search using OpenMP
and measures execution time and speedup.

Compile:
>>> g++ -fopenmp -o parallel_count parallel_count.cpp
Run:
>>> ./parallel_count
*/

#include <bits/stdc++.h>
#include <omp.h>
using namespace std;

int main()
{
    // Size of array
    const long long N = 100000000; // 100 million elements
    const int target = 5;

    vector<int> arr(N);

    // Fill array with random values [0, 9]
    for (long long i = 0; i < N; i++)
    {
        arr[i] = rand() % 10;
    }

    // ---------------------------
    // 1. Sequential Count
    // ---------------------------

    long long seq_count = 0;
    double start_seq = omp_get_wtime();

    for (long long i = 0; i < N; i++)
    {
        if (arr[i] == target)
        {
            seq_count++;
        }
    }

    double end_seq = omp_get_wtime();
    double seq_time = end_seq - start_seq;

    // ---------------------------
    // 2. Parallel Count (OpenMP)
    // ---------------------------

    long long par_count = 0;
    double start_par = omp_get_wtime();

#pragma omp parallel for reduction(+ : par_count)
    for (long long i = 0; i < N; i++)
    {
        if (arr[i] == target)
        {
            par_count++;
        }
    }

    double end_par = omp_get_wtime();
    double par_time = end_par - start_par;

    // ---------------------------
    // Print Results
    // ---------------------------

    cout << "For array of size N = " << N << "\n";
    cout << "Target value = " << target << "\n\n";

    cout << "Sequential Count: " << seq_count
         << " | Time: " << seq_time << " sec\n";

    cout << "Parallel Count:   " << par_count
         << " | Time: " << par_time << " sec\n";

    cout << "\nSpeedup = Sequential_Time / Parallel_Time = "
         << (seq_time / par_time) << "x\n";

    if (seq_count == par_count)
    {
        cout << "\nBoth counts match. Parallel execution is correct.\n";
    }
    else
    {
        cout << "\nCounts do NOT match! Something is wrong.\n";
    }

    return 0;
}


/*
Output Example:
For array of size N = 100000000
Target value = 5

Sequential Count: 10002967 | Time: 0.709 sec
Parallel Count:   10002967 | Time: 0.341 sec

Speedup = Sequential_Time / Parallel_Time = 2.07918x

Both counts match. Parallel execution is correct.
## Output varies depending on hardware and system load.
*/