Thuật toán song song

Parallel Algorithms

Definition: Parallel algorithms are designed to take advantage of multiple processing units or cores to solve a problem faster than a sequential algorithm.

Types of Parallelism:

• Data Parallelism: Divide the data into smaller chunks and process each chunk in parallel.
• Pipelining: Break down the task into a series of stages and process each stage in parallel.
• Task Parallelism: Divide the task into smaller sub-tasks and execute each sub-task in parallel.

Characteristics of Parallel Algorithms:

• Scalability: The ability of the algorithm to take advantage of an increasing number of processing units.
• Speedup: The ratio of the time taken by the sequential algorithm to the time taken by the parallel algorithm.
• Efficiency: The ratio of the speedup to the number of processing units.

Parallel Algorithm Design:

• Parallelization: Identify the parts of the algorithm that can be parallelized.
• Synchronization: Coordinate the execution of parallel tasks to ensure correct results.
• Communication: Manage the exchange of data between parallel tasks.

Parallel Algorithm Examples:

• Matrix Multiplication: Divide the matrix into smaller blocks and perform multiplication in parallel.
• Sorting: Use parallel sorting algorithms such as parallel merge sort or parallel quicksort.
• Linear Algebra: Use parallel algorithms for solving linear systems, eigenvalue decomposition, and singular value decomposition.

Challenges in Parallel Algorithm Design:

• Load Balancing: Ensure that each processing unit has a similar amount of work to do.
• Synchronization Overhead: Minimize the time spent on synchronizing parallel tasks.
• Communication Overhead: Minimize the time spent on exchanging data between parallel tasks.

Parallel Computing Models:

• Shared Memory Model: Multiple processing units share a common memory space.
• Distributed Memory Model: Each processing unit has its own memory space and communicates with others through message passing.
• Hybrid Model: Combination of shared and distributed memory models.

Các Thuật Toán Đồng Bộ

• Thuật toán đồng bộ được thiết kế để tận dụng nhiều đơn vị xử lý hoặc lõi để giải quyết vấn đề nhanh hơn thuật toán tuần tự.

Phân Loại Đồng Bộ

• Đồng Bộ Dữ Liệu: Chia dữ liệu thành các khối nhỏ và xử lý mỗi khối đồng bộ.
• Đồng Bộ Ống Dẫn: Chia công việc thành một loạt các giai đoạn và xử lý mỗi giai đoạn đồng bộ.
• Đồng Bộ Nhiệm Vụ: Chia công việc thành các nhiệm vụ nhỏ và thực thi mỗi nhiệm vụ đồng bộ.

Đặc Điểm Của Thuật Toán Đồng Bộ

• Tính khả mở rộng: Khả năng của thuật toán tận dụng lợi thế của số lượng đơn vị xử lý tăng lên.
• Tốc độ tăng: Tỷ lệ thời gian của thuật toán tuần tự so với thời gian của thuật toán đồng bộ.
• Hiệu suất: Tỷ lệ tốc độ tăng so với số lượng đơn vị xử lý.

Thiết Kế Thuật Toán Đồng Bộ

• Đồng bộ hóa: Xác định các phần của thuật toán có thể được đồng bộ hóa.
• Đồng bộ hóa: Tính toán và điều khiển việc thực thi của các nhiệm vụ đồng bộ để đảm bảo kết quả đúng.
• Trao đổi dữ liệu: Quản lý việc trao đổi dữ liệu giữa các nhiệm vụ đồng bộ.

Ví dụ Thuật Toán Đồng Bộ

• Nhân Ma trận: Chia ma trận thành các khối nhỏ và thực hiện nhân đồng bộ.
• Sắp xếp: Sử dụng thuật toán sắp xếp đồng bộ như sắp xếp hợp nhất song song hoặc sắp xếp nhanh song song.
• Ðại Số Tuyến: Sử dụng thuật toán đồng bộ để giải quyết hệ tuyến, phân hủy giá trị riêng, và phân hủy giá trị đặc biệt.

Thách Thức Trong Thiết Kế Thuật Toán Đồng Bộ

• Cân bằng tải: Đảm bảo rằng mỗi đơn vị xử lý có lượng công việc giống nhau.
• Chi phí Đồng bộ hóa: Tối thiểu hóa thời gian dành cho đồng bộ hóa các nhiệm vụ đồng bộ.
• Chi phí Trao đổi dữ liệu: Tối thiểu hóa thời gian dành cho trao đổi dữ liệu giữa các nhiệm vụ đồng bộ.

Mô hình Máy Tính Đồng Bộ

• Mô hình bộ nhớ chung: Nhiều đơn vị xử lý chia sẻ một không gian bộ nhớ chung.
• Mô hình bộ nhớ phân tán: Mỗi đơn vị xử lý có không gian bộ nhớ riêng và trao đổi với nhau qua truyền thông tin nhắn.
• Mô hình lai: Kết hợp của mô hình bộ nhớ chung và mô hình bộ nhớ phân tán.

Mô hình PRAM (Parallel Random Access Machine)

• PRAM là một mô hình tính toánsong song, trong đó nhiều bộ xử lý (processors) có thể truy cập một bộ nhớ chung (shared memory) cùng một lúc.
• Mô hình PRAM bao gồm các đặc điểm sau:
  • Số lượng bộ xử lý là vô hạn (unbounded).
  • Bộ nhớ chung là vô hạn (unbounded).
  • Tất cả các bộ xử lý có thể truy cập bộ nhớ chung trong 1 chu kỳ (1 cycle).
  • Các bộ xử lý có thể thực hiện các操作 số học và logic khác nhau song song.

Các loại PRAM

• Exclusive Read Exclusive Write (EREW): chỉ có một bộ xử lý được phép đọc hoặc ghi vào cùng một ô nhớ tại một thời điểm.
• Concurrent Read Exclusive Write (CREW): nhiều bộ xử lý có thể đọc cùng một ô nhớ, nhưng chỉ có một bộ xử lý được phép ghi vào ô nhớ đó.
• Concurrent Read Concurrent Write (CRCW): nhiều bộ xử lý có thể đọc và ghi vào cùng một ô nhớ tại cùng một thời điểm.

Đặc điểm của PRAM

• Tất cả các bộ xử lý có thể truy cập bộ nhớ chung.
• Tất cả các bước thực thi của bộ xử lý được đồng bộ (synchronized).
• Mỗi bộ xử lý có một id duy nhất, gọi là pid (processor id).
• Các bộ xử lý có thể được chỉ đạo thực hiện các tác vụ khác nhau dựa trên pid của chúng.

Ứng dụng của PRAM

• PRAM được sử dụng để thiết lập một giới hạn dưới cho thời gian chạy của các vấn đề.
• Các thuật toán được thiết kế cho PRAM có thể được triển khai trên các máy tính song song thực tế, nhưng sẽ phải chịu thêm chi phí về giao tiếp và tài nguyên.

SPMD và MPMD

• SPMD (Single Program Multiple Data): các bộ xử lý thực thi cùng một chương trình với các dữ liệu khác nhau.
• MPMD (Multiple Program Multiple Data): các bộ xử lý có thể thực thi các chương trình khác nhau với các dữ liệu khác nhau.

Mô hình Random Access Machine (RAM)

• RAM là một mô hình tính toán tuần tự.
• Mô hình RAM gồm các đặc điểm sau:
  • Bộ nhớ có M ô nhớ, trong đó M là một số lớn hữu hạn.
  • Truy cập bộ nhớ có thể được thực hiện trong một đơn vị thời gian.
  • Các thao tác được thực thi tuần tự, không song song.