Parallel Algorithms and Their Complexity

6.1 Parallel Algorithms.

Parallel algorithms are designed to be executed on multiprocessor or multithreaded systems to speed up computations. They split a task into independent subtasks that can be executed simultaneously. The complexity analysis of parallel algorithms requires considering both time and space complexity, as well as factors like speedup, efficiency, and scalability.

Main Concepts of Parallel Algorithms:

• Parallelism: Dividing a task into multiple subtasks that can be executed concurrently.
• Speedup: The ratio of the execution time of a sequential algorithm to the execution time of a parallel algorithm.
• Efficiency: The ratio of speedup to the number of processors.
• Scalability: The ability of a parallel algorithm to effectively utilize an increasing number of processors.

Advantages of Parallel Algorithms:

• Execution Speedup: Completing tasks faster by parallelizing work.
• Efficient Resource Use: Optimizing the use of processors and cores.
• Solving Large Tasks: Handling large data volumes and complex computations that are impossible or very slow on a single processor.

Time Complexity of Parallel Algorithms:

The time complexity of parallel algorithms is measured considering the time taken to execute all parallel subtasks and synchronization among them. It includes:

• Theoretical Time Complexity: Ideal execution time on an infinite number of processors.
• Actual Time Complexity: Execution time considering constraints on the number of processors and synchronization overhead.

Space Complexity of Parallel Algorithms

The space complexity of parallel algorithms considers the memory required to store data and context for each parallel process. It's also important to consider the communication overhead between processors.

6.2 Example of a Parallel Algorithm

Parallel Merge Sort:

Divides an array into subarrays, sorts them in parallel, and then merges them.

Time Complexity: O(n*log(n)/p), where n is the size of the array, p is the number of processors.

from multiprocessing import Pool

def merge_sort_parallel(arr, num_processes=None):
    if len(arr) <= 1:
        return arr
    if num_processes is None:
        num_processes = Pool()._processes
    with Pool(processes=num_processes) as pool:
        size = len(arr) // 2
        left, right = arr[:size], arr[size:]
        left, right = pool.map(merge_sort_parallel, [left, right])
        return merge(left, right)
            
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
            
# Example of use
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

But we're more interested in analyzing its "efficiency."

6.3 Analysis of Parallel Algorithms

Main Concepts:

1. Speedup Analysis:
   • The ratio of the execution time of a sequential algorithm to the execution time of a parallel algorithm.
   • Speedup = T_seq / T_par, where T_seq is the execution time of the sequential algorithm, T_par is the execution time of the parallel algorithm.
2. Efficiency:
   • Evaluation of the processor usage efficiency.
   • Efficiency = Speedup / P, where P is the number of processors.
3. Amdahl's Law:
   • Determines the maximum speedup attainable when parallelizing a task.
   • Speedup_max = 1 / (S + (1 - S) / P), where S is the fraction of the task that is sequential, P is the number of processors.
4. Gustafson's Law:
   • Determines speedup taking into account the size of the task as the number of processors increases.
   • Speedup = P - α * (P - 1), where P is the number of processors, α is the fraction of the task that is sequential.

6.4 Examples of Parallel Algorithms and Their Complexity

Example 1: Parallel Merge Sort

Description: Parallel merge sort divides an array into subarrays, sorts each subarray in parallel, and then merges the sorted subarrays.

Complexity Analysis:

• Time Complexity: O((n log n) / P), where P is the number of processors.
• Space Complexity: O(n) for storing intermediate data.

Example 2: Parallel Search in an Array

Description: The task of finding an element in an array is divided into multiple subtasks, each executed in parallel on a separate processor.

Complexity Analysis:

• Time Complexity: O(n / P), where P is the number of processors.
• Space Complexity: O(1), if the same array is used.

Example 3: Parallel Matrix Multiplication

Description: Matrices are divided into blocks, and each pair of blocks is multiplied in parallel on different processors.

Complexity Analysis:

• Time Complexity: O(n^3 / P), where P is the number of processors.
• Space Complexity: O(n^2) for storing intermediate results.

6.5 Implementation of Parallel Algorithms

Tools and Libraries:

1. OpenMP:
   • A library for C, C++, and Fortran, providing tools for developing multithreaded applications.
2. MPI (Message Passing Interface):
   • A standard for parallel programming on distributed systems, supporting message exchange between processes.
3. CUDA:
   • A platform and API from NVIDIA for developing parallel programs using graphics processors (GPU).
4. Threading and multiprocessing in Python:
   • Modules for creating multithreaded and multiprocess programs in Python.

Parallel algorithms significantly speed up computations by parallelizing tasks across multiple processors or cores. The complexity analysis of parallel algorithms includes assessing speedup, efficiency, and using Amdahl's and Gustafson's laws to understand the maximum speedup achievable with parallelization.

Parallel algorithms are used in various fields, from sorting and searching to complex mathematical computations, requiring the use of specialized tools and libraries for implementation.

Important! Don't get too carried away with parallel algorithms. First, due to Amdahl's law, they're not as efficient as they seem. Second, today servers with 30 processors handle 3000 requests per minute, and we still have n tasks for 1 processor, not 1 task for n processors.

Third, real tasks that need to be sped up through multiprocessor solutions have moved to GPUs (graphics cards) and are coded in low-level languages like C.