Lập trình phân tán và song song (tiếng Anh Distributed and Parallel Programing) là viết các chương trình thực thi trên một hệ thống máy tính phân tán hoặc thực thi trên nhiều máy tính hoặc trên một máy tính với nhiều bộ xử lý một cách đồng thời. Lập trình song song và lập trình phân tán cho phép tận dụng sức mạnh của các hệ thống phần cứng đa lõi. Việc giải quyết bài toán được chia thành các bài toán nhỏ hơn, cho đến khi các chỉ thị giải bài toán sơ cấp được thực thi cùng một lúc trên các bộ xử lý. Lập trình song song tương tự như lập trình tương tranh nhưng hiệu quả hơn về thời gian xử lý.

Tiến trình (Process)

Tiến trình có thể hiểu đơn giản là chương trình đang chạy trong máy tính. Ví dụ, chương trình máy tính được viết bằng ngôn ngữ lập trình như C sau khi biên dịch và chạy chương trình, hệ điều hànhsẽ khởi tạo một tiến trình có số hiệu PID (process ID) với một không gian nhớ cụ thể. Mỗi tiến trình có khả năng tạo và quản lý luồng, trong đó có ít nhất một luồng chính (main thread). Tiến trình sẽ dừng (nghĩa là chương trình dừng) khi luồng chính này ngừng hoạt động.

Luồng (thread)

Một chương trình, phần mềm ứng dụng bất kỳ phải thực hiện nhiều tác vụ như nhận và xử lý các sự kiện từ người dùng, lưu trữ dữ liệu xuống ổ cứng v.v. Các tác vụ này phải truy cập đồng thời vào cùng một tài nguyên hệ thống, được cấp phát cho chương trình. Tiến trình thực thi chương trình có cơ chế đồng bộ các tác vụ bằng cách tạo và quản lý các luồng chạy bên trong tiến trình. Trên thực tế, nhiều luồng trong tiến trình có thể chạy đồng thời, nên các tiến trình có khả năng đa nhiệm thông qua cơ chế xử lý nhiều luồng.

Các luồng trong tiến trình cũng được cấp phát vùng nhớ riêng (gọi là stack) để lưu các biến riêng của luồng đó. Mỗi Stack khoảng từ 1MB đến 2MB, tùy cấu hình máy tính. Ngoài ra, các luồng có thể chia sẻ vùng nhớ chung (gọi là heap) của tiến trình. Khi tiến trình tạo quá nhiều luồng có thể dẫn đến tình trạng quá tải bộ nhớ (stack overflow).

Xử lý tương tranh (Concurrency)

Là khả năng phân chia và điều phối thực hiện các tác vụ trong một khoảng thời gian sao cho tại mỗi thời điểm chỉ có một tác vụ được xử lý. Ví dụ trên máy tính cá nhân, chúng ta có thể chạy nhiều chương trình đồng thời, mỗi chương trình chạy là một tiến trình và hệ điều hànhsẽ thực hiện việc điều phối để các tiến trình thực hiện đồng thời dù máy tính chỉ có CPU với một lõi xử lý

Xử lý song song (Parallelism)

Là khả năng phân chia và điều phối thực hiện nhiều tác vụ tại cùng 1 thời điểm trên máy tính có bộ xử lý đa lõi hay trên 1 cụm nhiều máy tính. Mỗi lõi CPU có thể xử lý một tác vụ đơn giản tại một thời điểm. Khi số lõi CPU nhiều, có thể xử lý nhiều tác vụ một cách song song, cùng lúc trên các lõi CPU. Trong mô hình xử lý song song, mỗi lõi của CPU vẫn có thể xảy ra quá trình xử lý tương tranh. Tuy cả hai mô hình đều đề cập việc xử lý nhiều tác vụ trong cùng một thời điểm, mô hình xử lý tương tranh và mô hình xử lý song song là khác nhau. Trong mô hình song song, các tác vụ được thực hiện bởi các luồng khác nhau, chạy song song. Vì vậy số luồng được tạo ra phụ thuộc số lõi CPU (khuyến cáo chỉ nên tạo số luồng cỡ 2 lần số lõi CPU). Khi thực thi chương trình, nếu tạo quá nhiều luồng, sẽ không làm chương trình chạy nhanh hơn, mà còn gây ra lỗi.

Máy tính song song

Được thiết kế, tổ chức các tài nguyên nhằm tối ưu hiệu năng chương trình song song (tăng tốc độ tính toán, tăng khả năng chịu lỗi) bằng cách sử dụng nhiều bộ xử lý hay nhiều máy tính đồng thời. Các kiểu máy tính song song gồm:

• Hệ thống đa xử lý bộ nhớ chia sẻ (shared memory multiprocessors) là một hệ thống máy tính có hai hoặc nhiều đơn vị xử lý trung tâm (CPU) chia sẻ truy cập vào một bộ nhớ (RAM) chung.

• Hệ thống đa xử lý bộ nhớ phân tán (distributed memory multiprocessors) là một hệ thống máy tính có hai hoặc nhiều đơn vị xử lý trung tâm (CPU), mỗi CPU có một bộ nhớ riêng

• MIMD (Multiple Instruction stream, Multiple Data stream): cho phép nhiều lệnh khác nhau được thực hiện đồng thời với các dữ liệu khác nhau.

• SIMD (Single Instruction stream, Multiple Data stream): cho phép một lệnh được thực hiện đồng thời với các dữ liệu khác nhau (còn gọi là kiến trúc xử lý mảng).

• MISD (Multiple Instruction stream, Single Data stream): cho phép nhiều lệnh khác nhau được thực hiện đồng thời với cùng một dữ liệu.

• Cụm máy tính (cluster computer): nhiều máy tính được kết nối qua mạng chuyên dụng (thường là mạng cục bộ) và cho phép hệ thống hoạt động giống như một máy tính duy nhất. Tuy có nhiều máy tính, nhưng được kết nối và cùng nhau thực hiện các hoạt động, nên tạo ra ấn tượng giống như chỉ một hệ thống duy nhất (máy ảo). Hiện nay, có nhiều thư viện lập trình song song được sử dụng khá phổ biến như: MPI với C/C++, OpenMP với C/C++, v.v….

Lập trình song song với MPI (Message Passing Interface)

MPI là một bộ thư viện hỗ trợ cho việc lập trình kiểu truyền thông điệp. Thư viện MPI bao gồm các thủ tục khởi tạo môi trường, phân chia các xử lý vào các đoạn mã song song. Mỗi đoạn được chạy trên một tiến trình, các thủ tục trao đổi thông điệp và đồng bộ hóa các tiến trình. Các tác vụ MPI có thể chạy đồng thời trên cùng một bộ xử lý hoặc trên các bộ xử lý khác nhau. Trong một chương trình ứng dụng, lập trình viên phải đưa thêm một số lệnh điều khiển, gọi đến các hàm/thủ tục của bộ thư viện MPI, nhằm phân chia các tác vụ và chỉ ra (bằng câu lệnh) cách các tiến trình trao đổi thông điệp và đồng bộ hóa.

Lập trình song song với OpenMP

OpenMP là một thư viện cung cấp giao diện lập trình ứng dụng (API) được sử dụng để điều khiển các luồng, hỗ trợ việc lập trình song song kiến trúc bộ nhớ chia sẻ. Thành phần của OpenMP bao gồm: (i)các biến môi trường (Environment Variables) (ii) các chỉ thị biên dịch (Compiler Directives) (iii) các thư viện thực thi (Runtime Library Routines). Để viết chương trình song song với OpenMP, lập trình viên bắt đầu bằng cách viết một chương trình tuần tự trên ngôn ngữ gốc như C/C++, sau đó thêm vào các chỉ thị (pragma) của OpenMP vào những phần mong muốn được xử lý song song. Việc chia sẻ và đồng bộ các tác vụ được OpenMP điều phối thực hiện.

Lập trình song song với PVM (Parallel Virtual Machine)

PVM cung cấp môi trường phần mềm để gửi/nhận thông báo cho các hệ máy tính thuần nhất và cả không thuần nhất. PVM có một tập hợp các hàm thư viện được viết bằng C/C++ hoặc Fortran. Tập các máy tính được sử dụng trong mạng phải được định nghĩa theo các mức ưu tiên để chạy các chương trình. Điều này được thực hiện trên tập máy ảo song song PVM.

Tính toán song song được quan tâm từ khá sớm từ cuối những năm 1950 và ngày càng phát triển cùng với sự phát triển các siêu máy tính trong những năm 60-70 của thế kỷ 20. Siêu máy tính thông thường được thiết kế, chế tạo dựa trên kiến trúc đa bộ xử lý sử dụng bộ nhớ chia sẻ. Vào giữa những năm 1980, dự án xây dựng siêu máy tính với các bộ vi xử lý Intel 8086/8086 ra đời. Hệ thống với các bộ xử lý song song này đã đạt kỷ lục về tốc độ tính toán và giữ vị trí hàng đầu cho đến năm 1997 với sự ra đời của thế hệ siêu máy tính mới. Sự phát triển của công nghệ cụm máy tính vào những năm 1980 và ngày nay là các máy tính cá nhân đa lõi cũng tạo điều kiện thuận lợi cho sự phát triển và ứng dụng cửa tính toán song song trong nhiều lĩnh vực đời sống.

Lập trình song song nói riêng và tính toán song song nói chung được áp dụng một cách rộng rãi và hiệu quả trong các bài toán tính toán có kích thước lớn trong tính toán động lực học, dự báo thời tiết, mô hình hóa và mô phỏng các hệ thống lớn, xử lý thông tin, xử lý ảnh, trí tuệ nhân tạo, tự động hóa sản xuất Cùng với sự bùng nổ của thông tin, sự phức tạp trong các bài toán ứng dụng thực tế và sự phát triển liên tục của công nghệ đặc biệt là phần cứng, lập trình song song cùng các giải thuật song song ngày càng đóng vai trò quan trọng trong các lĩnh vực ứng dụng rộng khắp trong đời sống.

Tài liệu tham khảo

1. Barry Wilkinson, C. Michael Allen. Parallel Programming - Techniques and Applications Using Networked Workstations and Parallel Computer. Prentice Hall.2nd Edition (2004).
2. Joseph JaJa. Introduction to Parallel Algorithms. Addison-Wesley Professional, 1 edition (April 3, 1992).
3. Andrews, Gregory R., Foundations of Multithreaded, Parallel, and Distributed Programming, Addison–Wesley, ISBN 978-0-201-35752-3 (2000).