TỔNG QUAN VỀ TÍNH TOÁN SONG SONG
I. Tổng quan thuật toán song song
1. Khái niệm thuật toán song song
Tính toán song song hay xử lý song song: là quá trình xử lý thông tin trong đó nhấn
mạnh việc nhiều đơn vị dữ liệu được xử lý đồng thời bởi một hay nhiều bộ xử lý để giải
quyết một bài toán.
Siêu máy tính: là những máy tính đa năng thông thường có tốc độ tính toán vô cùng
lớn. Chúng chia làm hai loại:
- Máy tính song song dựa trên bộ vi xử lý : được thiết kế với rất nhiều bộ xử lý có
tốc độ vừa phải.
- Siêu máy tính truyền thống (supercomputer) : ít bộ xử lý hơn nhưng tốc độ của
mỗi bộ xử lý đó lại cực cao.
Song song về dữ liệu (data parallelism): Là cơ chế sử dụng nhiều đơn vị xử lý thực
hiện cùng một thao tác trên nhiều đơn vị dữ liệu .
Song song điều khiển (control parallelism) : là cơ chế trong đó nhiều thao tác khác
nhau tác động lên nhiều đơn vị dữ liệu khác nhau một cách đồng thời.
Dây chuyền (pipeline) : là cơ chế chia công việc thành nhiều chặng nối tiếp, mỗi
chặng được thực hiện bởi một bộ phận khác nhau. Đầu ra của bộ phận này là đầu vào của
bộ phận tiếp theo.
Tăng tốc : tăng tốc của thuật toán song song là tỉ số giữa thời gian thực hiện trong tình
huống xấu nhất của thuật toán tuần tự tốt nhất và thời gian thực hiện cũng công việc đó
của thuật toán song song.

2. Các mức độ song song
Tăng tốc =
Thời gian thực hiện trong tình huống xấu nhất
theo thuật toán tuần tự nhanh nhất
Thời gian thực hiện trong tình huống xấu nhất
của thuật toán song song đang xét
Giả sử có 10 công việc từng đôi một khác nhau thì ta giao cho 10 máy làm, ta có mức
song song cao nhất, và chúng ta gọi là mức chương trình song song. Mỗi công việc ta lại

Độ phức tạp thời gian tồi nhất (hay đơn giản là độ phức tạp thời gian) của thuật toán
song song giải quyết bài toán P
n
với kích thước đầu vào n là một hàm f(n) cho thời gian
lớn nhất từ lúc bắt đầu thực hiện thuật toán trên một hay nhiều bộ xử lý đến lúc kết thúc
thuật toán bởi một hay nhiều bộ xử lý với bất kỳ bộ dữ liệu nào.
Các thuật toán song song được thực hiện trên một tập các bộ xử lý nên đòi hỏi việc
truyền dữ liệu giữa chúng. Vì thế nó bao hàm hai hoạt động khác nhau. Một hoạt động là
tính toán (như các phép toán số học hay logic) được thực hiện một cách cục bộ trên một
bộ xử lý, hoạt động khác là gửi dữ liệu giữa các bộ xử lý. Trong thuật toán song song một
bước cơ bản là một tập các hoạt động cơ bản có thể được thực hiện một cách đồng thời
bởi một tập các bộ xử lý – độ phức tạp thời gian của một bước cơ bản là hằng số hay
O(1). Độ phức tạp thời gian của thuật toán song song được xác định bởi việc đếm số
bước cơ bản và số bước chuyển giao dữ liệu, trong đó thời gian chuyển giao dữ liệu tại
mỗi bước phụ thuộc vào mô hình liên kết giữa các bộ xử lý. Một số tài liệu còn gọi độ
phức tạp thời gian của thuật toán song song là độ sâu.
Độ phức tạp thời gian của thuật toán song song phụ thuộc vào mô hình tính toán song
song được sử dụng một cách tốt nhất trên số lượng bộ xử lý. Vì thế, khi đưa ra độ phức
tạp thời gian của thuật toán song song cần thiết đưa ra số lượng lớn nhất bộ xử lý cần sử
dụng như một hàm của kích thước dữ liệu đầu vào n, và gọi là độ phức tạp số bộ xử lý
của thuật toán. Việc tổng hợp và phân tích một thuật toán song song dưới mô hình có P
bộ xử lý (P là một số nguyên cố định và P > 1) được gọi là mô hình song song có giới
hạn. Ngược lại, mô hình song song không giới hạn là khi mà chúng ta có và được phép
tùy ý sử dụng một số lượng bộ xử lý không giới hạn .
Thuật toán song song thực hiện trên mô hình P bộ xử lý được gọi là P-song song. Nếu
thuật toán P-song song cho bài toán kích thước n đòi hỏi t(n) bước song song thì được gọi
là P-có thể tính toán trong thời gian t. Chúng ta giả sử rằng một thuật toán song song A
giải quyết bài toán kích thước n với P bộ xử lý.Nếu tồn tại đa thức F sao cho ∀n , P ≤
F(n) , thì số lượng bộ xử lý được gọi là cận đa thức, ngược lại thì không có cận đa thức.
Thuật toán song song có giới hạn là thích hợp trong thực tế. Tuy nhiên, các thuật toán

(m). Cách thứ
hai là phân tách một thuật toán, mỗi bước của nó được phân tách thành các bước nhỏ hơn
theo một cách nào đó sao cho chúng được thực hiện với một số lượng bộ xử lý nhỏ hơn.
4.2. Cận trên và cận dưới
Thuật toán song song nhanh nhất được biết để giải quyết bài toán cho ta cận trên của
tính toán đó. Nếu một ai đó thiết kế ra một thuật toán nhanh hơn thuật toán nhanh nhất
trước đó để giải quyết cùng một bài toán thì chúng ta nói rằng cận trên mới đã được thiết
lập cho việc tính toán lời giải của bài toán đó. Cận dưới xác định độ phức tạp của bài
toán, nghĩa là nó đưa ra lượng thời gian tối thiểu để giải quyết bài toán sử dụng một thuật
toán song song tùy ý.
4.3. Chi phí, tăng tốc, và hiệu quả của thuật toán song song
Tăng tốc và hiệu suất : xét bài toán với thuật toán tuần tự tốt nhất có thời gian T
s
,
thuật toán song song T
p
; số bộ xử lý là P. Khi đó:
Tăng tốc = T
s
/T
p
Hiệu suất = T
s
/(PT
p
)
Tăng tốc luôn nhỏ hơn số bộ xử lý, cố gắng đạt tới bằng nên hiệu suất đạt cùng lắm là
1.
4.4. Các kĩ thuật cho việc nâng cao hiệu quả của thuật toán song song
- Giảm số lượng bộ xử lý

việc trao đổi giá trị với nhau thông qua các ô nhớ (bởi trên thực tế chúng chẳng có ô nhớ
chung nào cả!). Các máy tính muốn trao đổi dữ liệu với nhau thì phải thông qua các lệnh
gửi-nhận mà MPI cung cấp. Đó là môi trường đảm nhận nhiệm vụ truyền tải dữ liệu qua
mạng. Mỗi máy tính muốn tham gia vào hệ thống MPI phải được cài thêm một trình
thường trú, gọi là Driver-MPI. Nó gửi/nhận dữ liệu truyền theo đường mạng rồi chuyển
đến nơi qui định.
1.2 Khái niệm mạng ảo.
Mục đích của MPI là tạo ra một môi trường gửi-nhận dữ liệu thân thiện, cho phép
chúng ta soạn thảo và thử trình MPI chỉ trên một máy, để sau đó chạy nó trên một mạng
máy tính – có thể có cấu trúc rất phức tạp. Để làm việc này MPI cho phép mô phỏng một
mạng ảo chỉ trên một máy tính. Độc trình của chúng ta sẽ chạy trên các máy ảo này (vẫn
theo nguyên tắc trên mỗi máy chạy một trình). MPI bảo đảm để về mặt hình thức máy ảo
hoàn toàn tương đương với máy thật. Điểm lưu ý là các độc trình trên cùng một máy thật
thì dùng chung đĩa cứng.
Cho dù là trên cùng một máy, nhưng các độc trình không thể trực tiếp trao đổi dữ liệu
cho nhau (vì chúng chạy trên các máy ảo khác nhau). Hoàn toàn giống như các máy tính
độc lập trong mạng, các chúng chỉ có thể trao đổi dữ liệu với nhau thông qua môi trường
MPI.
Thông thường người ta viết và chạy thử trình trên một máy tính, khi ấy sẽ có sự phân
biệt giữa giữa trình và máy tính. Tuy nhiên, khi sử dụng trên một mạng gồm nhiều máy
tính thì, thường là, trên mỗi máy chỉ chạy có một trình. Vì vậy, mỗi khi không có khả
năng xảy ra nhầm lẫn, chúng ta sẽ dùng từ máy tính với hàm ý chỉ trình chạy trên nó.
1.3 Cấu trúc một trình MPI
Cấu trúc khái quát của một trình MPI chạy trên nhiều máy bao gồm 2 phần. Phần thứ
nhất là việc mỗi máy tự “nhận biết” đoạn trình mà mình cần thực hiện, và phần thứ hai là
thủ tục gửi-nhận dữ liệu cho nhau.
Sơ đồ như sau:
#include <stdlib.h>
#include <stdio.h>
#include <mpi.h>

để thực hiện công việc của mình.
2. Biện pháp thứ hai là “chuyền cờ”. Theo phương pháp này có một chiếc “cờ” được
chuyền từ máy này đến máy khác theo số hiệu tăng dần. Chỉ máy nào nhận được
cờ thì mới được thực hiện tiếp các lệnh của mình.
1.5 Các phương pháp gửi-nhận cơ bản
Bản chất của việc gửi dữ liệu từ một máy tính này sang một máy tính khác là việc
truyền một dãy xung điện qua dây dẫn. Xung điện này chuyển tải nội dung của một ô nhớ
đặc biệt – “port” của máy “A” sang “port” của máy “B”. Cùng lúc ấy một chương trình
chuyên dụng của máy “B” được kích hoạt để vận chuyển dữ liệu ấy tới nơi qui định. Như
vậy vào thời điểm máy “A” gửi dữ liệu thì máy “B” phải hoạt động. Trường hợp ngược
lại mà “B” vẫn muốn nhận được dữ liệu thì những dữ liệu ấy phải được một máy “C” nào
đó khác nhận vào hộ.
Về nguyên lý chỉ có thể có hai kiểu gửi-nhận:
1. Gửi trực tiếp – transient: “A” gửi, “B” nhận. Nếu “B” không nhận thì những dữ
liệu này sẽ bị mất.
2. Gửi gián tiếp – persistence: “A” gửi vào “C”, “B” nhận từ “C”. Máy “C” phải liên
tục hoạt động.
Mỗi kiểu gửi nói trên có thể được thực hiện theo một trong hai phương án sau:
1. Gửi không đồng bộ – asynchorous. “A” đẩy luôn dữ liệu cho “B” mà không cần
biết là “B” có nhận được dữ liệu không. Nếu B chưa sẵn sàng nhận thì dữ liệu sẽ
bị mất.
2. Gửi đồng bộ – synchronous. Trước khi gửi dữ liệu, thì “A” tự tạo ra và gửi tín hiệu
đồng bộ cho “B”. Các tín hiệu này có khuôn dạng nhất định và được gửi đi gửi lại
cho tới khi nào B nhận được mới thôi (như vậy nếu có mất thì không phải là mất
dữ liệu cần gửi mà chỉ là các tín hiệu đồng bộ). Tín hiệu đồng bộ hóa báo cho B
biết các thông tin cần thiết như dung lượng dữ liệu sẽ gửi cho nó. Khi “A” nhận
được tín hiệu hồi âm của B báo cho biết là B đang chờ để nhận dữ liệu do nó gửi,
“A” chuyển ngay khối dữ liệu ấy cho “B” – đủ dung lượng như đã thông báo. Về
nguyên tắc “A” được giải phóng ngay sau khi bắt đầu gửi (để đi thực hiện lệnh
khác,) nhưng vì việc gửi là việc của nó nên thời gian ấy cũng là thời gian mà nó

Lệnh này dùng để gửi dữ liệu từ một máy này đến một máy khác. Lệnh MPI_Send chỉ
có thể kết thúc nếu khối dữ liệu được chuyển xong. Từ điều này suy ra rằng: máy “A” gửi
dữ liệu cho “B” thì “B” phải nhận vào đã nhận xong rồi, “B” mới có thể gửi cái gì đấy
lại cho “A”, nếu nó thật sự muốn gửi ngược lại cho “A”!
Điều này được minh họa trong sơ đồ sau.
Nếu máy “A” và “B” mỗi máy đều có dữ liệu để ở sendbuf của mình, và muốn truyền
chúng cho nhau. Qui trình chuyển diễn ra tuần tự như sau: “A” gửi dữ liệu cho “B”, “B”
nhận vào và để ở recvbuf trong máy của mình. Sau đó “B” chuyển dữ liệu của mình (để ở
sendbuf trong máy của “B”) cho “A”, và “A” lại nhận và để ở recvbuf trong máy của nó.
2.2 Lệnh MPI_Recv
Lệnh này dùng để nhận dữ liệu từ một tiến trình khác, ví dụ như tiến trình “A” nào đó,
gửi cho. Một khi chưa có dữ liệu, tức là “A” chưa thực hiên lệnh gửi dữ liệu MPI_Send
để gửi dữ liệu cho nó, thì nó sẽ phải chờ.
2.3. Lệnh MPI_Ssend
Lệnh MPI_Ssend gửi dữ liệu từ một tiến trình này đến một tiến trình khác.
Để thực hiện được công việc gửi bằng lệnh MPI_Ssend, trước hết tiến trình gửi – “A”
phát tín hiệu cho “B” thông báo là có một lượng dữ liệu cần gửi cho nó và xin phép gửi.
Tiến trình “A” sẽ phải chờ cho tới khi nào “B” gửi lại tín hiệu cho phép. Khi “A” nhận
được tính hiệu cho phép báo là “B” đang sẵn sàng nhận dữ liệu thì dòng dữ liệu được
truyền từ “A” sang “B”. Chỉ khi nào tiến trình “B” nhận xong dữ liệu thì lệnh gửi
MPI_Ssend của tiến trình “A” nới được coi là kết thúc. Và chỉ khi ấy các lệnh tiếp theo
sau lệnh gửi của “A” và lệnh nhận của “B” mới được xử lý.
So với lệnh gửi MPI_Send thì gửi bằng lệnh MPI_Ssend sẽ tiêu tốn thời gian hơn. Điều
này xảy ra là do quá trình đồng bộ hóa, tức là tiến trình gửi “A” chẳng những phải chờ để
được tiến trình nhận “B” cho phép, mà còn phải chờ tới thời điểm MPI chuyển được khối
dữ liệu vào vùng đệm hệ thống của “B”.
3. Chiến lược phân việc cho máy tính

Receiv β from
“1”