Thuật toán song song

Trong khoa học máy tính, thuật toán song song (hay còn gọi là thuật toán đồng thời) là thuật toán tương phản với thuật toán truyền thống tuần tự kiểu (nối tiếp) hay thuật toán tuyến tính. Thuật toán song song có thể thực hiện từng mẩu nhỏ công việc tại một thời điểm trên nhiều thiết bị xử lý khác nhau sau đó tổng hợp lại để lấy kết quả cuối cùng.^[1]

Một số thuật toán dễ dàng chia thành các mẩu công việc con để thực hiện theo cách này. Ví dụ, chia nhỏ công việc để tìm tất cả dãy số từ 1 đến 1000 số nào là số nguyên tố có thể thực hiện bằng cách gán tập con của dãy số cho các tiến trình con, sau đó tổng hợp kết quả có được. Tương tự, thuật toán song song có thể áp dụng cho bài toán tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị liên thông với số đỉnh từ lớn đến khá lớn (có thể lên đến 1 triệu đỉnh). Mục đích của thuật toán song song là tăng tốc và giảm thời gian khả năng thực hiện các bài toán cụ thể.

Tham khảo

1. Blelloch, Guy E.; Maggs, Bruce M. “Parallel Algorithms”. USA: School of Computer Science, Carnegie Mellon University. |ngày truy cập= cần |url= (trợ giúp)

Liên kết ngoài

• Designing and Building Parallel Programs page at the US Argonne National Laboratories