Ứng dụng lập trình song song với MPI trong bài
toán nhân hai ma trận
Lê Phước Khiêm, Trần Quốc Lịnh, Phan Minh Nhật,
Nguyễn Thái Hùng, Võ Đăng Khoa, and Đinh Hoàng Văn Bửu Thịnh
Tóm tắt nội dung Bài báo này giới thiệu những kiến thức cơ bản về
tính toán song song và lập trình song song. Ngoài ra còn trình bày khái
niệm về MPI (Message Passing Interface), những nguyên tắc lập trình
song song với MPI. Sử dụng thư viện hàm MPI lập trình minh họa bài
toán nhân hai ma trận bằng thuật toán Fox. Rút ra những kết luận về
thời gian chạy chương trình bằng giải thuật tuần tự và bằng giải thuật
song song.
Key words: MPI, thuật toán Fox, lập trình song song, nhân ma trận
1 Giới thiệu
Sự phát triển và mở rộng phạm vi ứng dụng của công nghệ thông tin luôn gặp
phải hai thách thức lớn đó là không gian nhớ và tốc độ xử lí của máy tính. Một
số bài toán do thực tiễn và nghiên cứu lý thuyết đặt ra đòi hỏi phải xử lý nhanh
trên một cơ sở dữ liệu đồ sộ, đặc biệt là trong các lĩnh vực trí tuệ nhân tạo,
nhận dạng, xử lí ảnh, điều khiển tự động, mô phỏng, các bài toán dự báo. . . mà
các phương pháp và công cụ tính toán truyền thống không thể đáp ứng được.
Trong những trường hợp ấy, ta có thể tìm cách phân rã bài toán thành những
bài toán có kích thước và quy mô dữ liệu nhỏ hơn. Tuy nhiên điều đó không
phải bao giờ cũng có thể thực hiện. Xử lí song song (parallel processing) là một
trong những giải pháp giúp ta có thể xử lý tình huống nêu trên. Hiện nay có rất
nhiều chuẩn hỗ trợ lập trình song song như MPI hỗ trợ lập trình song song trên
bộ nhớ phân tán, OpenMP hỗ trợ lập trình trên bộ nhớ chia sẽ chung, Pthread
hỗ trợ lập trình luồng . . . Trong khuôn khổ bài báo này chỉ giới thiệu về MPI và
ứng dụng MPI vào lập trình song song bài toán nhân hai ma trận bằng thuật
toán Fox. Phần tiếp theo giới thiệu tổng quan về xử lý song song và tại sao cần
thiết phải xử lý song song Phần 3 sẽ giới thiệu tổng quan về MPI trong đó cho
biết MPI là gì, nguyên tắc lập trình MPI . Phần 4 sẽ mô tả bài toán nhân hai
ma trận bằng thuật toán Fox và ứng dụng MPI trong việc giải quyết bài toán.

3.2 Mô hình lập trình message passing
Mô hình lập trình message passing được phát triển dựa trên ý tưởng lập trình
song song. Trong đó bài toán được chia thành nhiều phần nhỏ, mỗi phần được
giải quyết trên một processor với bộ nhớ riêng. Các phần này sẽ giao tiếp với
nhau qua một hoặc nhiều mạng để cùng nhau giải quyết vấn đề của bài toán.
Ứng dụng lập trình song song với MPI trong bài toán nhân hai ma trận 3
[5]
Hình 1. Mô hình lập trình message passing
3.3 Các giao thức trong MPI
– Giao thức point to point
Giao thức point to point là giao thức đơn giản nhất trong truyền thông điệp.
Một thông điệp được truyền từ một processor tới một processor và chỉ hai
processor này mới biết được thông tin trong thông điệp đó
– Giao thức collective
Giao thức collective cho phép nhiều processor trao đổi thông điệp cùng nhau.
3.4 Nguyên tắc lập trình MPI
– Tất cả chương trình sử dụng MPI phải bắt đầu với hàm MPI_Init và kết
thúc với hàm MPI_Finalize và MPI_Init chỉ được gọi một lần duy nhất
trong toàn bộ chương trình.
3.5 Các hàm MPI thường dùng
4
Tên hàm Ý nghĩa
MPI_Init() Khởi tạo bộ môi trường thực thi MPI, hàm này phải được gọi
trước tất cả các hàm MPI khác, và chỉ được gọi một lần.
MPI_Finalize() Dùng để kết thúc môi trường thực thi MPI. Hàm này phải được
gọi cuối cùng trong tất cả các hàm MPI
MPI_Comm_size(
MPI_COMM_WORLD,
&size)
Xác định số lượng tiến trình tham gia vào một bộ giao

Tên Kiểu dữ liệu C tương đương
MPI_CHAR signed char
MPI_DOUBLE double
MPI_FLOAT Float
MPI_INT Int
MPI_LONG Long
MPI_LONG_DOUBLE long double
MPI_SHORT Short
MPI_UNISIGNED_CHAR unsigned char
MPI_UNISIGNED unsigned int
MPI_UNSIGNED_LONG unsigned long
MPI_UNSIGNED_SHORT unsigned short
4 Bài toán nhân ma trận và thuật toán Fox
4.1 Bài toán nhân hai ma trận với thuật toán tuần tự
Định nghĩa bài toán nhân hai ma trận rất đơn giản. Cho ma trận A có kích
thước m x n, và ma trận B có kích thước n x p. Ma trận C có kích thước m x p
là kết quả của phép toán nhân ma trận A và B có phần tử ở hàng thứ i cột thứ
j được xác định bởi:
c
ij
=
n

k=1
a
ik
b
kj
Cách giải quyết trực tiếp trên một máy tính là dùng các vòng lặp:
for (i=0; i<n; i++)

3: Range x=p.dim(0);
4: Range y=p.dim(1);
5: while on(p) do
6: float [[#,#, , ]] a = new float [[x,y,B,B]];
7: float [[#,#, , ]] b = new float [[x,y,B,B]];
8: float [[#,#, , ]] c = new float [[x,y,B,B]];
9: float [[#,#, , ]] temp = new float [[x,y,B,B]];
10: for k=0 p-1 do
11: while over(Location i=x|:) do
12: float [[,]] sub = new float [[B,B]];
13: Adlib.remap(sub, a[[i, (i+k)%P, z, z]]);
14: while over(Location j=y|:) do
15: matmul(c[[i, j, z, z]], sub, b[[i, j, z, z]]);
Ứng dụng lập trình song song với MPI trong bài toán nhân hai ma trận 7
16: end while
17: end while
18: //Cyclic shift ’b’ in ’y’ dimension
19: Adlib.shift(tmp, b, 1, 0, 0); // dst, src, shift, dim, mode;
20: Adlib.copy(b, tmp);
21: end for
22: end while
23: end procedure
Ở thuật toán này thời gian được tính:
T
p
=
n
3
p
+ 2t

thông tin từ kho dữ liệu khổng lồ hay giúp giảm bớt những rũi ro trong cuộc
sống đồng thời tìm kiếm những giải pháp tốt đẹp cho tương lai thì con người
bắt buộc phải dùng những chương trình máy tính để thực hiện. Nhưng với tốc
độ xử lí cùng bộ nhớ của máy tính có hạn thì việc lập trình truyền thống sẽ khó
thực hiện và không đem lại kết quả như mong muốn. Do đó lập trình song song
là một lựa chọn tối ưu cho bài toán của thời đại.
Tài liệu
1. http://www.hpjava.org/reports/structuredSPMD/javad/node27.html
2. Pgs.TS Trần Cao Đệ. Slide tính toán song song. 2008
3. Wolfgang Baumann Writing Message-Passing Parallel Programs with MPI. The Uni-
versity of Edinburgh
4. http://www.software.unn.ac.ru
5. http://vi.wikipedia.org/wiki/MPI
LẬP TRÌNH SONG SONG VỚI OPENMP
Nguyễn Trung Việt, Nguyễn Minh Toàn, Hà Lê Ngọc Dung,
Trịnh Trần Nguyễn, Trần Huỳnh Anh, Phan Ngọc Diễn
[email protected], [email protected], [email protected]
[email protected], [email protected], [email protected]
Tóm tắt nội dung Bài viết này trình bày một cách tổng quan về lập
trình song song với OpenMP, những ưu điểm của mô hình lập trình song
song với mô hình tuần tự. Dùng bài toán tìm số số nguyên tố trong một
giới hạn cho trước để minh họa cho phần lý thuyết đã nghiên cứu, với
những bộ số thực nghiệm khác nhau đã cho ra thời gian chênh lệch giữa
thực thi song song và tuần tự khác nhau. Trong xử lý công việc, thời
gian thực thi của một chương trình được lập trình song song luôn ít hơn
so với lập trình tuần tự. Qua nghiên cứu cho thấy lập trình song song
không phải là khái niệm mới và nó đang là xu thế của những lĩnh vực
ứng dụng công nghệ thông tin, đặc biệt là những lĩnh vực cần xử lý
những dữ liệu có kích thước lớn với một khoảng thời gian giới hạn.
Từ khóa: Lập trình song song, OpenMP

thường được thực thi với ba đến bốn chỉ thị.
OpenMP giúp cho việc lập trình song song một cách dễ dàng, cung cấp khả năng
song song hóa chương trình tuần tự mà không dùng đến thư viện thông điệp
OpenMP được sử dụng để giải quyết các vấn đề giới hạn về thời gian và có khối
lượng dữ liệu lớn như: dự báo thời tiết, mô phỏng tai nạn xe hơi, dự báo dòng
chảy thủy triều
1.3 Mô hình lập trình song song OpenMP
Có nhiều mô hình lập trình song song như: mô hình chia sẽ bộ nhớ (Shared
Memory Model), song song hóa dựa trên cơ chế luồng (Thread based parallelism),
mô hình song song hiện (Explicit Parallelism), mô hình Fork-Join OpenMP sử
dụng mô hình Fork-Join để thực thi công việc song song.
Hình 1. Mô hình Fork-Join
Trong mô hình này, tất cả các chương trình song song đều bắt đầu thực thi
như một tiến trình đơn gọi là luồng chủ (master thread). Luồng chủ sẽ thực thi
tuần tự cho tới khi gặp vùng song song đầu tiên.Luồng chủ tạo nhóm các luồng
để chia sẻ thực hiện các công việc song song (FORK), khi hoàn thành đoạn mã
trong vùng song song, luồng song song sẽ được đồng bộ và kết thúc, luồng chủ
sẽ thực hiện tiếp công việc còn lại (JOIN).
1.4 Các chỉ thị trong OpenMP
Chỉ thị trong OpenMP xuất hiện như một câu "comment" trong mã nguồn và
được bỏ qua trong quá trình thực thi trừ khi được gắn cờ biên dịch (compiler
flag) báo hiệu việc "bật" hoặc "tắt" trình biên dịch OpenMP, chỉ thị được cho
dưới dạng:
# pragma omp directive-name [clause ] newline
– # pragma omp: yêu cầu bắt buộc đối với mọi chỉ thị OpenMP C/C
++
.
– directive-name: là tên của chỉ thị phải xuất hiện sau # pragma omp và đứng
trước bất kì mệnh đề nào.
– [clause ]: các mệnh đề này không bắt buộc trong chỉ thị.

– Viết mã trên môi trường lập trình song song.
– Thiết kế chương trình phụ thuộc vào: nền tảng phần cứng, cấp độ song song,
bản chất của bài toán.
1.8 Trình biên dịch OpenMP
OpenMP được biên dịch thông qua những chỉ thị biên dịch nhúng trong mã
nguồn C/C
++
hoặc Fortran. Bài toán minh họa trong phần sau sử dụng trình
biên dịch Visual C
++
2010, .NET Framework 4.0
2 Bài toán đếm số số nguyên tố
Dãy số nguyên tố là vô hạn. Bài toán đặt ra là đếm số số nguyên tố trong khoảng
giới hạn cho trước. Một yêu cầu khác là tìm giải thuật tối ưu hoặc chấp nhận
được để thực hiện yêu cầu.
Ví dụ: đếm số số nguyên tố từ 2 đến 5.000.000
2.1 Thuật toán
Bao gồm 2 phần:
– Hàm kiểm tra số nguyên tố:
Ý tưởng: ý tưởng đầu tiên để kiểm tra một số m có phải là số nguyên tố hay
không là kiểm tra xem m có ước thuộc [2, m −1]. Tuy nhiên chỉ cần xét ước
của m trong [2,
√
m], vì nếu m là hợp số thì m chắc chắn có ước số không
vượt quá
√
m.
Một số phương pháp khác để xác định số nguyên tố: Kiểm tra theo xác suất,
Các phép kiểm tra tất định, Các phương pháp lý thuyết số , tuy nhiên các
phương pháp trên thực tế không phải là tối ưu.

Dữ liệu được lấy từ file text “taptintest.txt”, trong đó mỗi dòng là một số
nguyên dương N (không giới hạn số lớn nhất). Chương trình đọc từng dòng, lấy
ra số nguyên dương N và thực hiện phép toán đếm các số nguyên tố có trong
khoảng từ 0 đến N.
VD: Trong file “taptintest.txt”, ta nhập vào các dòng sau:
10000
25000
Chương trình sẽ đếm các số nguyên tố có trong khoảng từ 0 đến 10000; từ 1
đến 25000; từ 1 đến 50000; từ 1 đến 70000.
Cách thức thu thập dữ liệu
Chương trình đánh giá hiệu quả của giải thuật song song so với giải thuật tuần
tự dựa trên tiêu chí thời gian theo đơn vị mili giây (một phần nghìn giây), theo
công thức sau:
T
th
= T
bd
− T
kt
– T
th
: Thời gian chương trình trả về kết quả đếm số nguyên tố có trong [2,N].
– T
bd
: Thời gian của hệ thống tại thời điểm bắt đầu vòng lặp for.
– T
kt
: Thời gian của hệ thống tại thời điểm kết thúc vòng lặp for chạy từ [2,N]
và trả về kết quả
Với mỗi số nguyên N, chương trình chạy thuật toán tuần tự, ghi lại thời gian

Tài liệu
1. Lâm Thị Ngọc Châu. Giáo trình Toán rời rạc 3. (2005)
2. Trần Cao Đệ. Phân tích và Thiết kế Giải thuật nâng cao.(2012)
3. http://people.sc.fsu.edu/~jburkardt/cpp_src/openmp/openmp.html