Thuật toán song song và độ phức tạp của chúng

6.1 Thuật toán song song.

Thuật toán song song được thiết kế để thực thi trên các hệ thống đa xử lý hoặc đa luồng nhằm tăng tốc độ tính toán. Chúng chia nhỏ nhiệm vụ thành các nhiệm vụ con độc lập có thể được thực hiện đồng thời. Phân tích độ phức tạp của các thuật toán song song yêu cầu tính toán cả độ phức tạp thời gian và không gian, cũng như các yếu tố như tốc độ, hiệu quả và khả năng mở rộng.

Các khái niệm chính về thuật toán song song

• Tính song song: Phân chia nhiệm vụ thành nhiều nhiệm vụ con, có thể thực thi đồng thời.
• Tăng tốc (Speedup): Tỉ lệ thời gian thực thi của thuật toán tuần tự so với thời gian thực thi của thuật toán song song.
• Hiệu quả (Efficiency): Tỉ lệ tăng tốc so với số lượng bộ xử lý.
• Khả năng mở rộng (Scalability): Khả năng của thuật toán song song sử dụng hiệu quả số lượng bộ xử lý tăng dần.

Ưu điểm của thuật toán song song:

• Tốc độ thực thi: Hoàn thành nhiệm vụ nhanh hơn nhờ phân chia công việc.
• Sử dụng tài nguyên hiệu quả: Tối ưu hóa việc sử dụng bộ xử lý và lõi.
• Giải quyết các nhiệm vụ lớn: Khả năng xử lý lượng dữ liệu lớn và các tính toán phức tạp, không thể hoặc rất chậm trên một bộ xử lý.

Độ phức tạp thời gian của thuật toán song song

Độ phức tạp thời gian của thuật toán song song được đo lường với thời gian tiêu tốn để thực thi tất cả các nhiệm vụ con song song và đồng bộ hóa giữa chúng. Nó bao gồm:

• Độ phức tạp thời gian lý thuyết: Thời gian lý tưởng thực thi trên số lượng bộ xử lý vô hạn.
• Độ phức tạp thời gian thực tế: Thời gian thực thi có tính đến giới hạn số lượng bộ xử lý và chi phí đồng bộ hóa.

Độ phức tạp không gian của thuật toán song song

Độ phức tạp không gian của thuật toán song song tính đến lượng bộ nhớ cần thiết để lưu trữ dữ liệu và ngữ cảnh của mỗi quá trình song song. Cần phải cân nhắc cả chi phí liên lạc giữa các bộ xử lý.

6.2 Ví dụ về thuật toán song song

Sắp xếp sáp nhập song song (Parallel Merge Sort):

Chia mảng thành các mảng con, sắp xếp chúng song song và sau đó hợp nhất.

Độ phức tạp thời gian: O(n*log(n)/p), trong đó n là kích thước mảng, p là số lượng bộ xử lý.

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
            
# Ví dụ sử dụng
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

Nhưng chúng ta sẽ quan tâm không chỉ đến bản thân thuật toán mà còn đến phân tích "hiệu quả" của nó.

6.3 Phân tích thuật toán song song

Các khái niệm chính:

1. Phân tích tăng tốc (Speedup):
   • Tỉ lệ thời gian thực thi của thuật toán tuần tự so với thời gian thực thi của thuật toán song song.
   • Speedup = T_seq / T_par, nơi T_seq — thời gian thực thi của thuật toán tuần tự, T_par — thời gian thực thi của thuật toán song song.
2. Hiệu quả (Efficiency):
   • Đánh giá hiệu quả sử dụng bộ xử lý.
   • Efficiency = Speedup / P, nơi P là số lượng bộ xử lý.
3. Luật Amdahl (Amdahl's Law):
   • Xác định tốc độ tối đa có thể đạt được khi thực hiện song song hóa nhiệm vụ.
   • Speedup_max = 1 / (S + (1 - S) / P), nơi S là tỷ lệ của phần nhiệm vụ tuần tự, P là số lượng bộ xử lý.
4. Luật Gustafson (Gustafson's Law):
   • Xác định tốc độ tính đến sự thay đổi kích thước nhiệm vụ khi tăng số lượng bộ xử lý.
   • Speedup = P - α * (P - 1), nơi P là số lượng bộ xử lý, α là tỷ lệ của phần nhiệm vụ tuần tự.

6.4 Ví dụ về thuật toán song song và độ phức tạp của chúng

Ví dụ 1: Sắp xếp sáp nhập song song (Parallel Merge Sort)

Mô tả: Sắp xếp sáp nhập song song chia mảng thành các mảng con, sắp xếp từng mảng con song song, sau đó hợp nhất các mảng con đã sắp xếp.

Phân tích độ phức tạp:

• Độ phức tạp thời gian: O((n log n) / P), nơi P là số lượng bộ xử lý.
• Độ phức tạp không gian: O(n) để lưu trữ dữ liệu trung gian.

Ví dụ 2: Tìm kiếm song song trong mảng (Parallel Search)

Mô tả: Nhiệm vụ tìm kiếm phần tử trong mảng được chia thành nhiều nhiệm vụ con, mỗi nhiệm vụ được thực hiện song song trên một bộ xử lý riêng lẻ.

Phân tích độ phức tạp:

• Độ phức tạp thời gian: O(n / P), nơi P là số lượng bộ xử lý.
• Độ phức tạp không gian: O(1), nếu sử dụng cùng một mảng.

Ví dụ 3: Nhân ma trận song song (Parallel Matrix Multiplication)

Mô tả: Các ma trận được chia thành các khối, và mỗi cặp khối được nhân song song trên các bộ xử lý khác nhau.

Phân tích độ phức tạp:

• Độ phức tạp thời gian: O(n^3 / P), nơi P là số lượng bộ xử lý.
• Độ phức tạp không gian: O(n^2) để lưu trữ kết quả trung gian.

6.5 Triển khai thuật toán song song

Công cụ và thư viện:

1. OpenMP:
   • Thư viện cho C, C++ và Fortran, cung cấp công cụ để phát triển ứng dụng đa luồng.
2. MPI (Message Passing Interface):
   • Tiêu chuẩn cho lập trình song song trên hệ thống phân tán, hỗ trợ truyền thông điệp giữa các tiến trình.
3. CUDA:
   • Nền tảng và API từ NVIDIA cho phát triển các chương trình song song, sử dụng bộ xử lý đồ họa (GPU).
4. Threading và multiprocessing trong Python:
   • Các mô-đun để tạo các chương trình đa luồng và đa xử lý trong Python.

Thuật toán song song cho phép tăng tốc đáng kể quá trình tính toán nhờ việc phân chia nhiệm vụ thành nhiều bộ xử lý hoặc lõi. Phân tích độ phức tạp của các thuật toán song song bao gồm việc đánh giá tốc độ, hiệu quả và sử dụng luật Amdahl và Gustafson để hiểu được tốc độ tối đa có thể đạt được khi thực hiện song song hóa.

Các thuật toán song song được ứng dụng trong nhiều lĩnh vực, từ sắp xếp và tìm kiếm đến các tính toán toán học phức tạp, và yêu cầu sử dụng công cụ chuyên dụng và thư viện để thực hiện chúng.

Quan trọng! Bạn không cần phải mải mê với các thuật toán song song. Thứ nhất, do luật của Amdahl, chúng không hiệu quả như bạn nghĩ. Thứ hai, hiện nay các máy chủ với 30 bộ xử lý xử lý khoảng 3000 yêu cầu mỗi phút, và chúng ta vẫn có n nhiệm vụ trên 1 bộ xử lý, không phải 1 nhiệm vụ cho n bộ xử lý.

Thứ ba, các nhiệm vụ thực tế cần tăng tốc nhờ đa xử lý đã chuyển sang GPU (card đồ họa), và mã của chúng được viết bằng ngôn ngữ cấp thấp như C.