We use the formula for parallel runtime based on Amdahl's Law: \( T(p) = T_s \cdot ((1-f) + \frac{f}{p}) \).

Substitute the given values:

\( 15 = 60 \cdot ((1-f) + \frac{f}{6}) \)

\( \frac{15}{60} = 1 - f + \frac{f}{6} \)

\( 0.25 = 1 - \frac{5f}{6} \)

\( \frac{5f}{6} = 1 - 0.25 = 0.75 \)

\( f = \frac{0.75 \cdot 6}{5} = \frac{4.5}{5} = 0.9 \)

90% of the execution time is parallelized.

We use the formula for speedup: \( SU(p) = \frac{1}{(1-f) + \frac{f}{p}} \).

We want a speedup of 5, and we know \(f=0.9\):

\( 5 = \frac{1}{(1-0.9) + \frac{0.9}{p}} \)

\( 5 = \frac{1}{0.1 + \frac{0.9}{p}} \)

Take the reciprocal of both sides:

\( 0.1 + \frac{0.9}{p} = \frac{1}{5} = 0.2 \)

\( \frac{0.9}{p} = 0.2 - 0.1 = 0.1 \)

\( p = \frac{0.9}{0.1} = 9 \)

9 parallel processing units are needed.

This phenomenon is called Super-linear speedup.

The likely reason is related to cache effects. With multiple cores, the total available cache memory increases. If the program's working set fits better into the aggregated cache of the parallel system compared to the sequential execution (which might have suffered from frequent cache misses), memory access latency significantly decreases, leading to performance improvements beyond simple scaling.

class condition_variable {
    void notify_one();
    void wait();
};
class mutex {
    void lock();
    void unlock();
};
template <typename E> class queue {
public:
    void push(E element) {
        // L1: Acquire lock before modifying shared data
        mutex.lock();

        queue.push_back(element);

        // L2: Release lock after modification.
        // Done before notify for efficiency (allows woken thread to acquire lock sooner).
        mutex.unlock();

        cv.notify_one();
    }

    E pop() {
        // L3: Acquire lock before checking condition or waiting
        mutex.lock();

        // Wait while the queue is empty (must hold the lock)
        while (queue.empty()) {
            // Assumes wait() correctly handles atomic release/reacquire of the associated mutex.
            cv.wait();
        }

        // Lock is held, queue is not empty.
        E element = queue.front();
        queue.pop_front();

        // L4: Release the lock
        mutex.unlock();

        return element;
    }

private:
    std::deque<E> queue;
    mutex mutex;
    condition_variable cv;
};

• L1 (`mutex.lock()` in `push`): Required to ensure exclusive access to the shared `queue` before modification (`push_back`), preventing data races.
• L2 (`mutex.unlock()` in `push`): Required to release the lock after the critical section is complete.
• L3 (`mutex.lock()` in `pop`): Required before checking the shared condition (`queue.empty()`) and is a prerequisite for correctly calling `cv.wait()`.
• L4 (`mutex.unlock()` in `pop`): Required to release the lock after the element has been successfully removed from the queue.

The code lacks Exception Safety. If an operation within the critical section (e.g., `queue.push_back()` potentially throws `std::bad_alloc`) throws an exception, the corresponding `mutex.unlock()` call is skipped. This leaves the mutex permanently locked, causing a deadlock for any other thread that tries to acquire the lock.

This is avoided in the C++ standard library by using RAII (Resource Acquisition Is Initialization) wrappers, such as `std::lock_guard<std::mutex>` or `std::unique_lock<std::mutex>`. These wrappers guarantee that the mutex is automatically unlocked when the scope is exited, regardless of whether it's a normal return or an exception was thrown.

• Line 19 (a): Non-deterministic. `a` is a shared variable, and its value at this point depends on the non-deterministic order in which threads have executed the critical section before thread 4.
• Line 21 (b): 6. Thread 4 gets a private copy of `b` initialized to 2 (`firstprivate`). Inside the critical section, it executes `b += 4`, so its private `b` becomes 6.
• Line 23 (c): Non-deterministic. `c` is `lastprivate` but not `firstprivate`, so each thread's private copy is uninitialized. The output is the result of adding 4 to an indeterminate value.

• Line 27 (a): 29. The `critical` section ensures that the updates to the shared `a` are atomic. After the loop, `a` will be its initial value (1) plus the sum of all thread numbers from 0 to 7. Sum = (7*8)/2 = 28. Final value = 1 + 28 = 29.
• Line 29 (b): 2. The original variable `b` is not affected by modifications to the `firstprivate` copies within the parallel region.
• Line 31 (c): Non-deterministic. The `lastprivate` clause copies the value from the private `c` of the thread that executed the last iteration (thread 7). Since that private copy was uninitialized, the final value of `c` is indeterminate.

• Static Scheduling: Iterations are divided into chunks and assigned to threads in a fixed (static) manner before the loop begins.
  • Use Case (UMA): Preferred for loops where each iteration takes roughly the same amount of time (a balanced workload), as it has the lowest scheduling overhead.
• Dynamic Scheduling: Iterations are assigned to threads in smaller chunks dynamically as threads finish their current work and become available.
  • Use Case (UMA): Preferred for loops where iteration execution time varies significantly (an unbalanced workload), as it provides better load balancing at the cost of higher scheduling overhead.

On a NUMA (Non-Uniform Memory Access) system, memory access latency is lower for local memory than for remote memory (on another socket). A `dynamic` schedule assigns iterations to threads as they become available, without regard for data locality. This can frequently result in a thread being assigned an iteration that operates on data located in a remote NUMA node, forcing it to perform slow, high-latency remote memory accesses, which causes significant performance overhead.

Vector width = 256 bits.
Data element size = 16 bits.

Vector Length (VL) = Vector Width / Element Size = 256 / 16 = 16.

The expected speedup is 16x.

The problem is a Loop-Carried Flow Dependence.

Explanation: The statement `c[i] = a[i-1] - b[i-1];` in iteration `i` reads the value of `a[i-1]`. This value was written by the statement `a[i] = b[i] / d;` in the *previous* iteration (`i-1`). This dependency across iterations prevents the loop from being vectorized directly, as vectorization requires iterations to be independent.

We use Loop Distribution (also known as Loop Fission) to separate the dependent statements into two loops.

void operation_distributed(float *a, float *b, float *c, float d, int size)
{
    // Loop 1: Calculates 'a'. This loop has no cross-iteration dependencies.
    for (int i = 1; i < size; i++) {
        a[i] = b[i] / d;
    }
    
    // Loop 2: Calculates 'c'. This loop is also vectorizable as all 'a' values are now computed.
    for (int i = 1; i < size; i++) {
        c[i] = a[i-1] - b[i-1];
    }
}

#include <immintrin.h>

// Assuming __mmask8 is defined, as implied by the masked intrinsics.
// For AVX-512, this is part of the header. For AVX2, one might need a typedef.
typedef unsigned char __mmask8;

void operation_vec(float *a, float *b, float *c, float d, int size) {
    const int VL = 8; // Vector Length for float on 256-bit registers
    int i;

    // --- Vectorized computation of 'a' ---
    __m256 a256, b256, d256, zero256;

    // Broadcast scalar 'd' into a vector
    d256 = _mm256_set1_ps(d);
    // Create a zero vector to use as a source for masked loads
    zero256 = _mm256_setzero_ps();

    // Main vector loop, starting from i=1
    for (i = 1; i < size; i += VL) {
        // Determine how many elements remain to be processed in this iteration
        int remaining = size - i;
        
        // Create a mask for the remaining elements.
        // If remaining >= VL, all lanes are active (0xFF).
        // Otherwise, create a bitmask for the 'remaining' lanes.
        __mmask8 mask = (remaining >= VL) ? 0xFF : (__mmask8)((1U << remaining) - 1);

        // Load unaligned data from b, masked. Inactive lanes get zero from zero256.
        b256 = _mm256_mask_loadu_ps(zero256, mask, &b[i]);

        // Perform the division, masked. Inactive lanes in 'a256' will be zero.
        a256 = _mm256_mask_div_ps(zero256, mask, b256, d256);

        // Store the result to a, unaligned and masked. Only active lanes are written.
        _mm256_mask_storeu_ps(&a[i], mask, a256);
    }

    // --- Sequential computation of 'c' (as requested) ---
    for (i = 1; i < size; i++) {
       c[i] = a[i-1] - b[i-1];
    }
}

An `MPI_Bsend` (Buffered Send) first copies the data to a user-managed buffer. The underlying transfer from this buffer can then use a protocol like rendezvous for large messages.

• Blocking routines (e.g., `MPI_Send`, `MPI_Recv`): The function call does not return until the operation is locally complete. This guarantees that the communication buffer is safe to be reused immediately after the call returns.
• Nonblocking routines (e.g., `MPI_Isend`, `MPI_Irecv`): The function call initiates the operation and returns immediately, before the operation is necessarily complete. The application must not reuse the communication buffer until completion is verified later using a separate call like `MPI_Wait` or `MPI_Test`.

The most direct way to emulate `MPI_Alltoall` is by using its more general vectorized version, `MPI_Alltoallv`, and setting up the parameters to describe a regular, non-vectorized communication pattern.

#include <mpi.h>
#include <stdlib.h>

int My_MPI_Alltoall(void *sendbuf, int sendcount, MPI_Datatype sendtype,
                    void *recvbuf, int recvcount, MPI_Datatype recvtype, MPI_Comm comm)
{
    int comm_size;
    MPI_Comm_size(comm, &comm_size);

    // Allocate arrays required for MPI_Alltoallv
    int *sendcounts = (int *)malloc(comm_size * sizeof(int));
    int *recvcounts = (int *)malloc(comm_size * sizeof(int));
    int *sdispls = (int *)malloc(comm_size * sizeof(int));
    int *rdispls = (int *)malloc(comm_size * sizeof(int));

    if (!sendcounts || !recvcounts || !sdispls || !rdispls) {
        return MPI_ERR_NO_MEM;
    }

    // Initialize the arrays for the regular Alltoall pattern
    for (int i = 0; i < comm_size; i++) {
        sendcounts[i] = sendcount;
        recvcounts[i] = recvcount;
        // Displacements are in terms of number of elements, not bytes
        sdispls[i] = i * sendcount;
        rdispls[i] = i * recvcount;
    }

    // Call the collective function MPI_Alltoallv
    int result = MPI_Alltoallv(sendbuf, sendcounts, sdispls, sendtype,
                               recvbuf, recvcounts, rdispls, recvtype, comm);

    // Cleanup
    free(sendcounts);
    free(recvcounts);
    free(sdispls);
    free(rdispls);

    return result;
}

#include <mpi.h>

void create_mpi_vector(MPI_Datatype *type) {
    // Create the datatype representing 2 contiguous MPI_FLOATs
    MPI_Type_contiguous(2, MPI_FLOAT, type);
    
    // Commit the datatype so it can be used in communication
    MPI_Type_commit(type);
}

#include <omp.h>
#include <mpi.h>
#include <stdlib.h>
#include <math.h>

// Assume struct vector, length(), normalize(), create_mpi_vector() are defined.

void harmonize(vector *a, vector *b, int size, int rank, int comm_size,
               int root, MPI_Comm comm) {
    // 1. Prepare custom MPI datatype
    MPI_Datatype MPI_VECTOR;
    create_mpi_vector(&MPI_VECTOR);

    int local_size = size / comm_size;
    vector *local_a = (vector *) malloc(local_size * sizeof(vector));
    vector *local_b = (vector *) malloc(local_size * sizeof(vector));

    // 2. Distribute data from root to all ranks
    MPI_Scatter(a, local_size, MPI_VECTOR, local_a, local_size, MPI_VECTOR, root, comm);
    MPI_Scatter(b, local_size, MPI_VECTOR, local_b, local_size, MPI_VECTOR, root, comm);

    // 3. Calculate local sum of lengths of A using OpenMP for parallel reduction
    float local_sum_a = 0.0f;
    #pragma omp parallel for reduction(+:local_sum_a)
    for (int i = 0; i < local_size; i++){
        local_sum_a += length(local_a[i]);
    }

    // 4. Initiate NON-BLOCKING global reduction to get the global sum
    float global_sum_a;
    MPI_Request request;
    MPI_Iallreduce(&local_sum_a, &global_sum_a, 1, MPI_FLOAT, MPI_SUM, comm, &request);

    // 5. OVERLAP: While communication happens, normalize local B using OpenMP
    #pragma omp parallel for
    for (int i = 0; i < local_size; i++){
        normalize(local_b[i]);
    }

    // 6. WAIT for communication to complete (as late as possible)
    MPI_Wait(&request, MPI_STATUS_IGNORE);

    // 7. Now that we have the global sum, calculate the average
    float avg_a = global_sum_a / size;

    // 8. Scale the normalized local B vectors by the global average, using OpenMP
    #pragma omp parallel for
    for (int i = 0; i < local_size; i++){
        local_b[i].x *= avg_a;
        local_b[i].y *= avg_a;
    }

    // 9. Gather the final results for B back to the root process
    MPI_Gather(local_b, local_size, MPI_VECTOR, b, local_size, MPI_VECTOR, root, comm);

    // 10. Cleanup
    free(local_a);
    free(local_b);
    MPI_Type_free(&MPI_VECTOR);
}

Issues Identified:

1. MPI Binding is Correct: The MPI binding report is actually good. It shows `rank0` is bound to the first socket and `rank1` is bound to the second socket. This is the ideal placement for a hybrid code with 2 processes per node on a 2-socket machine.
2. Severe OpenMP Undersubscription: The main issue is `OMP_NUM_THREADS = '1'`. Each MPI process is only using a single thread, leaving the other 5 physical cores (and 17 hardware threads) on its socket completely idle.
3. Inefficient OpenMP Thread Binding: `OMP_PROC_BIND = 'MASTER'` forces all OpenMP threads to run on the same processing unit as the master thread. Even if `OMP_NUM_THREADS` were increased, this would cause massive contention instead of utilizing the available cores.
4. Restrictive Thread Limit: `OMP_THREAD_LIMIT = '4'` imposes an additional, low limit on the total number of threads that can be created, which could conflict with setting a higher `OMP_NUM_THREADS`.

How to Fix (by setting environment variables):

The goal is to make each MPI process use the 6 physical cores available on its socket. Using SMT (hyper-threading) is often not beneficial for HPC, so we target physical cores.

# Set the number of threads to match the physical cores per socket
export OMP_NUM_THREADS=6

# Define the places for threads to run on as physical cores
export OMP_PLACES=cores

# Bind threads closely to the master thread's place (within the socket)
export OMP_PROC_BIND=close

# It's good practice to remove the artificial limit
unset OMP_THREAD_LIMIT

#include <mpi.h>
#include <omp.h>

void encrypt(char *buf, int len, const char *key);
void decrypt(char *buf, int len, const char *key);

void transfer_encrypted(char *message, int len, const char* key,
                       MPI_Comm comm, int sender, int receiver, int num_partitions)
{
    MPI_Request request;
    int rank;
    int part_size = len / num_partitions;
    int tag = 0; // Define a tag for the communication

    MPI_Comm_rank(comm, &rank);

    if (rank == sender) {
        // 1. Initialize the partitioned send operation.
        // The 'count' is the size of each partition.
        MPI_Psend_init(message, num_partitions, part_size, MPI_CHAR, receiver, tag, comm, MPI_INFO_NULL, &request);

        // 2. Start the communication request.
        MPI_Start(&request);

        // 3. Encrypt partitions in parallel and mark them as ready.
        omp_set_num_threads(num_partitions);
        #pragma omp parallel shared(message, key, part_size, request)
        {
            int i = omp_get_thread_num();
            // a. Encrypt the thread's assigned partition
            encrypt(&message[i * part_size], part_size, key);
            
            // b. Signal to MPI that this partition is ready to be sent
            MPI_Pready(i, request);
        }

        // 4. Wait for the entire partitioned send to complete.
        MPI_Wait(&request, MPI_STATUS_IGNORE);

        MPI_Request_free(&request);
    } else if (rank == receiver) {
        // 1. Initialize the partitioned receive operation.
        MPI_Precv_init(message, num_partitions, part_size, MPI_CHAR, sender, tag, comm, MPI_INFO_NULL, &request);

        // 2. Start the communication request.
        MPI_Start(&request);

        // 3. Wait for ALL partitions to be received. MPI_Wait will only complete
        //    when the entire message has arrived.
        MPI_Wait(&request, MPI_STATUS_IGNORE);

        // 4. Free the request and then decrypt the fully received message.
        MPI_Request_free(&request);
        decrypt(message, len, key);
    }
}