Thiết kế giải thuật song song
Mở đầu................................................................................................3
Chơng I Tổng quan về tính toán song song .......................7
1. 1 Kiến trúc Von Neumann ..........................................................7
1. 2. Phân loại Flynn........................................................................7
1. 3 Các kiến trúc bộ nhớ máy tính song song..............................9
1. 3. 1 Bộ nhớ dùng chung ................................................................................9
1. 3. 2 Bộ nhớ phân tán ..................................................................................10
1. 3. 3 Bộ nhớ kết hợp .....................................................................................11
1. 4 Các mô hình lập trình song song..........................................11
1. 4. 1 Lập trình bộ nhớ dùng chung ..............................................................11
1. 4. 2 Truyền thông điệp ................................................................................12
1. 4. 3 Mô hình song song dữ liệu....................................................................12
1. 4. 4 Mô hình hớng đối tợng..........................................................................13
1. 4. 5 Mô hình logic ........................................................................................13
1. 5 Truyền thông trong mô hình Multicomputer .......................13
...........................................................................................................15
Chơng 2 Thiết kế Giải Thuật song song...............................16
2. 1 Mô hình thiết kế......................................................................16
2. 2 Phơng pháp thiết kế................................................................17
2. 3 Phân rã ..................................................................................19
2. 3. 1. Phân rã theo miền...............................................................................20
2. 3. 2 Phân rã chức năng ...............................................................................21
2. 3. 3 Các vấn đề cần quan tâm ....................................................................23
2. 4 Truyền thông..........................................................................23
2. 4. 1 Truyền thông cục bộ............................................................................24
2. 4. 2 Truyền thông toàn cục.........................................................................25
2. 4. 3 Các vấn đề cần quan tâm ....................................................................27
2. 5 Tích tụ.....................................................................................27
2. 5. 1Gia tăng kích thớc tác vụ.......................................................................28
2. 5. 2 Duy trì khả năng linh động....................................................................31

4. 1. 1 Thời gian tính toán ...............................................................................51
4. 1. 2 Thời gian truyền thông .........................................................................51
4. 1. 3 Thời gian rỗi (Idle)................................................................................53
4. 2 Tăng tốc và hiệu quả. ...........................................................53
4. 3 Tính qui mô.............................................................................54
Chơng 5 giải hệ phơng trình tuyến tính...............................56
5. 1 Tách A = L*U dựa theo giải thuật khử Guassian..................56
5. 1. 1 Giải thuật song song theo hàng ...........................................................59
5. 1. 2 Giải thuật song song theo cột...............................................................61
5. 1. 3 Giải thuật song song hai chiều.............................................................62
5. 1. 4 Khử Gauss với kỹ thuật lựa chọn phần tử xoay ...................................64
5. 2 Giải hệ phơng trình với ma trận hệ số tam giác...................65
5. 2. 1 Giải thuật song song tích tụ theo hàng................................................67
5. 2. 2 Giải thuật song song tích tụ theo cột...................................................70
5. 2. 3 Giải thuật song song hai chiều ............................................................73
5. 3 Thực thi giải thuật...................................................................75
5. 3. 1 Xây dựng chơng trình............................................................................75
5. 3. 3 Các hạn chế và hớng phát triển chơng trình.........................................78
..........................................................................................................78
Kết luận...........................................................................................79
...........................................................................................................79
Tài liệu tham khảo .......................................................................80
Vũ Trung Hiếu Tin3-K42 2
Thiết kế giải thuật song song
Mở đầu
áy tính điện tử là một trong những phát minh vĩ đại nhất của thế kỷ 20,
vừa ra đời sau chiến tranh thế giới hai nhng nó đã phát triển một cách
nhanh chóng và có sức sống mãnh liệt. Trong những thập niên 60, nền tảng
để thiết kế máy tính số đều dựa trên mô hình của John von Newman với một
đơn vị xử lý đợc nối với một vùng lu trữ làm bộ nhớ và tại một thời điểm chỉ có

hay mainframe. Từ đó, để năng cao hiệu năng của các bộ xử lý đơn ngời ta có
ý định giảm thời gian chu kỳ lệnh.
Tuy nhiên với công nghệ VLSI kết hợp với những tiến bộ kiến trúc cho
phép máy tính đơn có khả năng tính toán cao, thực hiện hàng trăm triệu
phép tính trên một giây nhng điều này vẫn cha đáp ứng đợc các thách thức
khoa học với các bài toán nh mô hình thời tiết và môi trờng toàn cầu, tính
toán chu trình đại dơng. vũ trụ học và thiên văn học, y học và mô hình các x-
ơng và cơ quan con ngời, phản ứng hoá học và hạt nhân. v. v.
Ngày nay, các ứng dụng có tính thơng mại đang tác động đến việc phát
triển máy tính song song bởi những ứng dụng này yêu cầu xử lý số lợng lớn
dữ liệu theo các cách thức phức tạp. Ví dụ nh cơ sở dữ liệu song song, khai
Vũ Trung Hiếu Tin3-K42 3
Thiết kế giải thuật song song
phá dữ liệu, tìm kiếm dầu mỏ, chuẩn đoán dới sự trợ giúp của máy tính trong
y học, quản lý của các công ty kinh doanh, tổ chức đa quốc gia, công nghệ
multimedia và video trên mạng. v. v.
Nguyên nhân chính hạn chế trong việc phát triển máy tính đơn có tốc
độ cao là do sự hạn chế vật lý của IC, chúng ta không thể gia tăng mãi khả
năng tích hợp các linh kiện bán dẫn trên cùng một chíp và tốc độ truyền tải
tín hiệu của mạch điện bị hạn chế không vợt quá tốc độ ánh sáng.
Để tăng cờng sức mạnh tính toán giải quyết các bài toán lớn có độ tính
toán cao, ngời ta phát triển theo hớng kiến trúc máy tính, với ý tởng kết hợp
nhiều bộ xử lý vào trong một máy tính mà ngời ta hay gọi là máy tính song
song Multiprocessor hoặc kết hợp sức mạnh tính toán của nhiều máy tính dựa
trên kết nối của mạng cục bộ đã có, ngời ta gọi là máy tính song song
Multicomputer. Điều này đã đợc Daniel Slotnick ở trờng đại học Illinois thực
hiện với thiết kế hai máy tính song song là máy Solomon đợc xây dựng bởi
công ty Westinghouse Electric Company vào đầu những năm 1960 và sau đó
vào đầu những năm 1970, máy tính ILLIAC IV đợc lắp ráp tại công ty
Burroughs Corporation. Tại trờng đại học Carnegie-Mellon, hai máy tính song

Ngoài việc có sức mạnh tính toán nhanh, máy tính song song có khả
năng lu trữ lớn với mô hình bộ nhớ phân tán và khả năng chịu hỏng tốt hơn
máy tính đơn bộ xử lý. Đối với máy tính đơn, khi bộ xử lý bị sự cố thì cả hệ
thống dừng hoạt động còn các máy tính song song vẫn có thể thực hiện công
việc khi một vài bộ xử lý hay máy tính có sự cố. Việc bảo đảm độ tin cậy cao
có tầm quan trọng khi sử dụng máy tính trong các lĩnh vực mà sự cố có thể
xảy ra thảm hoạ nh điều khiển phóng vệ tinh, kiểm soát và điều khiển các nhà
máy điện nguyên tử. . v. v.
Tuy nhiên, để khai thác đợc sức mạnh tiềm tàng trong các máy tính
song song lớn yêu cầu sự phát triển và kết hợp hợp lý của kiến trúc, hệ điều
Vũ Trung Hiếu Tin3-K42 4
Thiết kế giải thuật song song
hành, ngôn ngữ lập trình và giải thuật, phần mềm tính toán song song. Bởi vì
giải thuật tuần tự không còn phù hợp nữa khi thực hiện trên máy song song,
nên việc xây dựng, thiết kế giải thuật song song là điều quan trọng từ đó có
thể phân rã công việc trên các phần tử xử lý khác nhau. Việc phân rã có thể
đợc tiến hành theo hai cách, phân rã theo miền và phân rã theo chức năng.
Tiếp theo là mã hoá công việc đó theo một ngôn ngữ hỗ trợ việc tính toán
song song và hệ điều hành điều khiển hoạt động tính toán phải có sự hỗ trợ.
Nếu trong quá trình tính toán mà lựa chọn không tốt kiến trúc song song sẽ
làm cho hiệu quả thực hiện giảm đi.
Để xây dựng một giải thuật song song ta phải có sự phân tích bài toán
hoặc giải thuật tuần tự, từ đó cho phép ta có kết luận có thể song song bài
toán hay không. Nếu đợc, ta sẽ tiếp tục xây dựng giải thuật bằng cách phân
rã bài toán ra thành các công việc nhỏ, xây mối liên hệ giữa các công việc,
quyết định đợc có thể song song đợc những tác vụ nào, sau đó ấn định vào
mô hình máy tính song song cụ thể. Trong khi xây dựng có thể có nhiều ph-
ơng hớng thiết kế khác nhau tạo ra các giải thuật khác nhau. Việc đánh giá
hiệu quả của từng giải thuật cho phép ta quyết định giải thuật nào sẽ đợc áp
dụng dựa trên mô hình hiệu năng. Để đánh giá tốt hiệu quả giải thuật, chúng

Chơng 4 đề cập đến mô hình hiệu năng đánh giá hiệu quả của giải
thuật song song sau khi thiết kế và phân tích tính qui mô của giải thuật.
Những đánh giá này sẽ giúp cho ngời thiết kế có khả năng chọn lựa giải thuật
trong công đoạn thiết kế.
Chơng 5 sẽ đi sâu thiết kế giải thuật song song cho bài toán giải hệ ph-
ơng trình tuyến tính theo phơng pháp tách LU. Mô phỏng một số giải thuật và
thử nghiệm một số bài toán giải hệ.
Vũ Trung Hiếu Tin3-K42 6
Thiết kế giải thuật song song
Chơng I Tổng quan về tính toán song song

Trong chơng này đề cập sơ lợc đến các vấn đề cơ bản trong tính toán
song song nh phân loại kiến trúc song song của Flynn, kiến trúc bộ nhớ, mô
hình lập trình song song. v. v. v, qua đây sẽ đa đến cái nhìn tổng quan để
định hớng khi thiết kế giải thuật.
1. 1 Kiến trúc Von Neumann

Hơn 40 năm qua, hầu hết các máy tính đều thiết kế dựa theo mô hình
phổ biến đợc biết đến nh máy Von Neumann. Tên máy tính đợc đặt theo tên
nhà toán học ngời Hungarian Jon Von Neumann.
Máy tính Von Neumann sử dụng khái niệm chơng trình lu trữ ( stored-
program), CPU sẽ thực hiện theo dãy các phép toán đọc, ghi trên bộ nhớ do
chơng trình lu trữ chỉ định.
Hình 1. 1: Mô tả kiến trúc Von Neumann
Đối với kiến trúc Von Neumann thì bộ nhớ đợc sử dụng để lu trữ cả lệnh
cho chơng trình lẫn dữ liệu. Lệnh chơng trình là dữ liệu đã đợc mã hoá, chơng
trình sẽ dựa vào đây để thực hiện, còn dữ liệu đơn giản chỉ là thông tin đợc
chơng trình sử dụng. Khi đó CPU sẽ lấy các lệnh hay dữ liệu từ bộ nhớ, giải
mã các lệnh và sau đó thực hiện tuần tự các lệnh này.
1. 2. Phân loại Flynn

đơn CPU. Hình 1. 3. Mô tả kiến trúc SISD
Đơn dòng lệnh đa dòng dữ liệu ( SIMD). Với kiến trúc này, tất cả các
đơn vị xử lý sẽ thực hiện cùng một lệnh tại bất kỳ chu kỳ đồng hồ nào nhng
mỗi đơn vị này có thể thao tác trên một phần tử dữ liệu khác nhau. Trong
kiến trúc này thờng có một đơn vị điều khiển lệnh ( Control Unit ), có mạng
kết nối bên trong giữa các đơn vị xử lý, có băng thông rất lớn và mảng rất lớn
các đơn vị lệnh có dung lợng rất nhỏ. Kiến trúc này đặc biệt phù hợp cho các
bài toán có mức độ đồng đều cao nh trong lĩnh vực xử lý ảnh. Kiến trúc này
là cơ sở xây dựng các máy tính song song kiểu bộ xử lý mảng ( array
processor) nh Connection Machine CM-2, Maspar MP-1, MP-2.

Hình 1. 4. Mô tả kiến trúc SISD
Vũ Trung Hiếu Tin3-K42 8
Thiết kế giải thuật song song
Đa dòng lệnh đơn dòng dữ liệu ( MISD). Kiến trúc này cho phép một
vài lệnh cùng thao tác trên cùng một dữ liệu. Có rất ít máy tính song song
dựa trên kiến trúc này.
Có hai cách để mô tả cách tổ chức của MISD. Cách thứ nhất đợc xét
đến các lớp máy yêu cầu các đơn vị xử lý riêng nhận các lệnh riêng biệt xử lý
trên cùng một dữ liệu. Cách thức thứ 2 đợc xét đến lớp các máy tính, trong đó
dữ liệu chuyển qua một dãy các đơn vị xử lý.
Đa dòng lệnh đa dòng dữ liệu (MIMD). Hiện nay, đây là kiến trúc song
song phổ biến nhất với mỗi bộ xử lý có thể thực hiện một dòng lệnh và một
dòng dữ liệu khác nhau. Hầu hết các máy tính supercomputer, máy tính
Multicomputer và Multiprocessor đều đợc xây dựng dựa trên kiến trúc này.

Hình 1. 4 Mô tả kiến trúc MIMD

1. 3. 2 Bộ nhớ phân tán
Cũng nh kiến trúc dùng chung, kiến trúc phân tán có nhiều dạng nhng
chia sẻ một đặc điểm chung là hệ thống bộ nhớ phân tán yêu cầu một mạng
truyền thông kết nối giữa bộ nhớ bộ xử lý. Hình 1. 6 Mô tả kiến trúc bộ nhớ phân tán
Mỗi bộ xử lý đều có bộ nhớ cục bộ riêng, địa chỉ bộ nhớ không ánh xạ
tới các bộ xử lý khác, bởi vậy không có khái niệm không gian địa chỉ toàn cục
ngang qua tất cả bộ xử lý. Các bộ xử lý sẽ thao tác độc lập trên bộ nhớ riêng
của nó. Sự thay đổi dữ liệu tạo ra đối với bộ nhớ riêng không ảnh hởng đến bộ
Vũ Trung Hiếu Tin3-K42 10
Thiết kế giải thuật song song
nhớ của các bộ xử lý khác, bởi vậy không có sự đụng độ do truy nhập đồng
thời từ nhiều bộ xử lý.
Khi một bộ xử lý cần truy nhập đến dữ liệu trong bộ xử lý khác hoặc hai
bộ xử lý cần trao đổi dữ liệu cho nhau thì cần có truyền thông giữa chúng qua
mạng kết nối.
Thuận lợi của kiến trúc này là bộ nhớ khả chuyển với số lợng bộ xử lý,
gia tăng số lợng bộ xử lý và kích thớc bộ nhớ tỷ lệ với nhau. Chí phí xây dựng
máy tính không lớn, có thể dùng hệ thống mạng máy tính sẵn có. Tuy nhiên,
kiến trúc này sẽ khó khăn cho ngời lập trình bởi cần có những công đoạn thực
hiện truyền thông giữa các máy tính khi trao đổi dữ liệu, việc ánh xạ cấu trúc
dữ liệu hiện có lên kiến trúc bộ nhớ của máy tính và thời gian truy nhập dữ liệu
không đồng bộ.
1. 3. 3 Bộ nhớ kết hợp
Ngày nay, các máy tính song song lớn nhất và nhanh nhất cung cấp cả
kiến trúc bộ nhớ chung và phân tán. Mô hình này hình thành dựa theo việc
liên kết nhiều máy tính song song kiến trúc bộ nhớ chung thành máy tính lớn
hơn thông qua mạng truyền thông.

( message passing) để trao đổi giữa các tác vụ. Hai tác vụ nằm trên hai máy
khác nhau có thể trao đổi với nhau bằng kỹ thuật truyền thông điệp trên mạng
kết nối. Các thông điệp có thể là các lệnh, dữ liệu, tín hiệu đồng bộ hay ngắt.
Hai mô hình truyền thông điệp đợc thực thi và sử dụng là đồng bộ hay không
đồng bộ.

Hình 1. 9 Mô tả truyền thông giữa hai tác vụ trên hai máy tính khác nhau
Hiện nay, PVM và MPI là hai mô hình lập trình song song điển hình sử
dụng kỹ thuật mày.
1. 4. 3 Mô hình song song dữ liệu

Trong mô hình này, hầu hết các công việc song song đều tập trung
thực hiện các phép toán trên một tập dữ liệu. Tập dữ liệu này thờng đợc tổ
chức trong một cấu trúc dữ liệu thông dụng nh mảng hoặc khối.
Một tập tác vụ sẽ làm việc trên cùng cấu trúc dữ liệu nhng mỗi tác vụ sẽ
làm việc trên một phần dữ liệu khác nhau với cùng phép toán. Mô hình này
thiết kế chủ yếu dành cho máy tính song song kiểu bộ xử lý mảng (array
processor)
Vũ Trung Hiếu Tin3-K42 12
Shared Memory
Task A
Task C
Task B
Thiết kế giải thuật song song

Hình 1. 10 Mô tả mô hình song song dữ liệu
1. 4. 4 Mô hình h ớng đối t ợng

Trong mô hình này, ánh xạ các đơn vị thực hiện vào các đối tợng. Các
đối tợng đợc tạo ra và thao tác theo cách tự động, việc xử lý đợc thực hiện

theo kiểu DMA đợc khởi tạo.

Vũ Trung Hiếu Tin3-K42 13
Thiết kế giải thuật song song
Hình1. 11 Mô tả cơ chế định đờng store and forward
Ngợc lại, đối với các mô hình máy tính song song thế hệ thứ hai, chẳng
hạn nh Intel iPSC/2
TM
, và nCUBE 2, có cơ chế định đờng message chuyển
mạch. Chẳng hạn nh mỗi nút trong mô hình iPSC/2 và iPSC/860 có một Card
con logic định đờng gọi là module kết nối trực tiếp (Direct Connect Module).
Các module kết nối trc tiếp thiết lập một mạch từ nút nguồn đến nút đích. Mỗi
lần mạch đợc thiết lập, message truyền trong một dạng đợc pipeline từ nút
nguồn tới nút đích mà không có một nút trung gian nào lu message này. Khi
một message đợc truyền từ một nút tới một nút không liền kề thì không cần
ngắt CPU của các nút trung gian và chỉ tác động vào các module kết nối trực
tiếp. Hình dới đây mô tả cơ chế này.
Vũ Trung Hiếu Tin3-K42 14
Processor 1
Processor 1
Y
Processor 1
T Y
Processor 1
R T Y
Processor 2
E
Processor 2
E R
Processor 2

Memory
Direct-Connect
Routing Module
80386
Numeric
Coprocessor
Memory
Direct-Connect
Routing Module
80386
Numeric
Coprocessor
Memory
Direct-Connect
Routing Module
Thiết kế giải thuật song song
Hình 1. 12 Mô tả các module kết nối trực tiếp trên máy tính Intel iPSC/2
hỗ trợ cơ chế định đờng message.
Cơ chế truyền thông khác nhau sẽ ảnh hởng rất nhiều đến tính toán chi
phí truyền thông trong khi thiết kế giải thuật.
Sau chơng đầu tiên, ta đã tìm hiểu đợc sơ bộ các kỹ thuật tổ chức giải
thuật tính toán song song khác nhau phụ thuộc vào mô hình máy tính cụ thể.
Những tìm hiểu này là cơ sở đi vào lĩnh vực tính toán song song, tạo bớc nền
trớc khi đi vào thiết kế giải thuật song song trong chơng sau.

Vũ Trung Hiếu Tin3-K42 15
Thiết kế giải thuật song song
Chơng 2 Thiết kế Giải Thuật song song
Trong chơng này đề cập đến phơng pháp thiết kế giải thuật song song
cho bài toán, quá trình thiết kế không dễ dàng để có thể rút gọn thành công

Bởi vì các tác vụ giao tác với nhau sử dụng kỹ thuật kênh truyền mà
không quan tâm đến việc định vị tác vụ, do đó kết quả tính toán bởi một ch-
Vũ Trung Hiếu Tin3-K42 16
Thiết kế giải thuật song song
ơng trình không phụ thuộc vào nơi mà tác vụ thực hiện. Các giải thuật phải đ-
ợc thiết kế và thực thi mà không quan tâm đến số lợng bộ xử lý trên máy tính
song song sẽ thực hiện bài toán. Thông thờng việc thiết kế bài toán sẽ tạo ra
số tác vụ lớn hơn nhiều so với số bộ xử lý, điều này sẽ làm cho giải thuật đạt
đợc khả năng linh động cao và có thể xen kẽ giữa tính toán và truyền thông
để tăng hiệu năng.
Các kênh truyền kết nối giữa các tác vụ có thể hoặc không tơng ứng với
đờng kết nối giữa các bộ xử lý trong mạng. Hai tác vụ trao đổi dữ liệu thông
qua kênh truyền có thể đợc ấn định tới:
Trên cùng một bộ xử lý, khi đó không cần truyền thông trên mạng.
Nằm trên hai bộ xử lý đợc kết nối trực tiếp, khi đó chỉ truyền thông trực
tiếp giữa hai bộ xử lý.
Nằm trên hai bộ xử lý không kết nối trực tiếp, khi đó yêu cầu định đờng
message trên mạng.

2. 2 Phơng pháp thiết kế
Hầu hết các bài toán lập trình đều có một vài lời giải song song. Phơng
án tốt nhất có thể khác so với phơng án đợc đề nghị bởi các giải thuật tuần tự
đang tồn tại. Phơng pháp thiết kế đa ra ở đây có xu hớng tiếp cận ban đầu
trên mô hình độc lập với máy tính song song, vấn đề đựợc chú trọng là tính
đồng thời và các khía cạnh thiết kế trên kiến trúc máy tính cụ thể đợc đề cập
sau trong tiến trình thiết kế. Phơng pháp này hình thành lên tiến trình thiết kế
gồm có 4 công đoạn: phân rã, truyền thông, tích tụ và ánh xạ. Trong hai công
đoạn đầu, chúng ta chú trọng vào tính đồng thời và linh động, tìm kiếm để
khám phá giải thuật với những tiêu chuẩn này. Trong hai công đoạn sau, thứ
3 và 4, chuyển tập trung sang tính cụ bộ và các vấn đề liên quan đến hiệu

tiến trình song song mức cao, với nhiều vấn đề liên quan đợc xem xét đồng
thời. Mặc dù chúng ta tìm kiếm để tránh quay lui nhng việc đánh giá từng
phần hoặc toàn bộ thiết kế có thể yêu cầu thay đổi quyết định thiết kế đợc tạo
ra trong các công đoạn trớc đó.
Chi tiết của bốn công đoạn sẽ đợc trình bày trong các mục tiếp theo,
trong đó sẽ tìm hiểu sâu về công đoạn và vấn đề cần quan tâm khi thiết kế
giải thuật.
2. 3 Phân rã

Mục đích của công đoạn này là khám phá đến mức tối đa khả năng
song song của bài toán, do đó chú trọng đến việc định nghĩa một tập lớn các
Vũ Trung Hiếu Tin3-K42 19
Thiết kế giải thuật song song
tác vụ nhỏ không có sự liên kết, đợc gọi là các tác vụ fine-grain. Khi đó, khối l-
ợng công việc đợc thực hiện thông qua truyền thông giữa các tác vụ là không
có.
Khi phân rã một giải thuật, ngời thiết kế đầu tiên thờng chú trọng nhất
về dữ liệu kết hợp với một bài toán, sau đó xác định một phân rã thích hợp
cho dữ liệu và công việc cuối cùng là kết hợp tính toán với dữ liệu nh thế nào.
Kỹ thuật này đợc gọi là phân rã theo miền ( domain decomposition). Một cách
tiếp cận khác là phân rã tính toán đợc thực hiện đầu tiên và sau đó kết hợp dữ
liệu với tính toán - đợc gọi là phân rã theo chức năng( functional
decomposition).
2. 3. 1. Phân rã theo miền
Thông thờng, hớng tiếp cận này quan tâm đến phân chia dữ liệu của
bài toán. Nếu có thể, chúng ta phân chia dữ liệu thành các phần nhỏ có kích
thớc xấp xỉ nhau. Tiếp theo phân chia tính toán đợc thực hiện. Thông thờng là
kết hợp mỗi phép toán với phần dữ liệu mà phép toán thao tác trên đó. Việc
phân chia này thờng đem lại một số lợng lớn tác vụ, mỗi tác vụ bao gồm một
số dữ liệu và một tập các phép toán thực hiện trên dữ liệu này. Khi phép toán

cận này thành công, sẽ phân chia quá trình tính toán thành các tác vụ riêng
rẽ. Sau đó ta sẽ tiến hành kiểm tra yêu cầu dữ liệu cho những tính toán của
tác vụ này. Khi yêu cầu dữ liệu riêng rẽ nhau thì phân chia là hoàn toàn, còn
không thì có thể yêu cầu vận chuyển dữ liệu giữa các tác vụ để tránh lặp lại
dữ liệu. Việc lặp lại dữ liệu sẽ đợc giải quyết thông qua việc phân rã theo
miền.
Hình 2. 4 Mô tả phân rã bài toán theo chức năng
Một ví dụ quen thuộc cho phơng pháp phân rã theo chức năng là bài
toán mô hình tính toán thời tiết. Xác định thời tiết thông qua việc tổng hợp dữ
liệu từ các mô hình thành phần là : mô hình khí quyển ( Atmospheric Model),
mô hình thuỷ học(Hydrology Model ), mô hình mặt đất( Land Surface Model)
và mô hình đại dơng( Ocean Model).
Vũ Trung Hiếu Tin3-K42 21
Thiết kế giải thuật song song
Hình 2. 5 Mô tả phân rã chức năng trong mô hình tính toán thời tiết

Khi đó, mỗi thành phần chức năng có thể xem nh là một tác vụ riêng
biệt và tiếp tục đợc song song bởi phân rã theo miền đối với dữ liệu tơng ứng
cho từng tác vụ. Các mũi tên biểu hiện sự trao đổi dữ liệu giữa các thành phần
trong suốt thời gian tính toán chẳng hạn nh mô hình khí quyển tạo ra ra dữ
liệu về tốc độ gió sẽ đợc sử dụng trong tính toán của mô hình đại dơng, mô
hình đại dơng tạo ra dữ liệu về nhiệt độ mặt biển sẽ đợc sử dụng trong mô
hình khí quyển.
Đối với hầu hết các giải thuật song song thì phân rã theo miền hình
thành cơ bản cho giải thuật. Phân rã chức năng chỉ đợc đánh giá là cách nhìn
khác về bài toán, bổ xung cho phơng pháp phân rã theo miền. Tuy nhiên đối
với các bài toán phức tạp thì phân rã theo miền cũng đóng vai trò quan trọng
nh là một kỹ thuật để cấu trúc chơng trình, đơn giản hoá bài toán phức tạp
bằng tập các bài toán đơn giản hơn, liên kết với nhau. Phân rã chức năng sẽ
giảm bớt đợc đáng kể chi phí thiết kế. Giải thuật song song tốt sẽ kết hợp đợc

(edges). Khi thực hiện duyệt theo thứ tự trớc, giải thuật sẽ tiến hành một cách
hệ thống thông qua tất cả các cạnh của cây.
Thực tế, giải thuật duyệt cây dọc theo mỗi cạnh hai lần, lần thứ nhất từ
đỉnh cha tới đỉnh con, sau đó thì duyệt ngợc lại. Nếu chia mỗi cây thành hai
cây, một cây ứng với duyệt từ trên xuống còn cây kia ứng với duyệt trở lại. Khi
đó, bài toán duyệt cây sẽ chuyển sang bài toán duyệt một danh sách liên kết
đơn, bài toán này có thể phân rã để thực hiện song song đợc.

Hình 2. 6 Mô tả phơng pháp phân rã bài toán tính số đỉnh cây duyệt theo thứ
tự trớc
2. 3. 3 Các vấn đề cần quan tâm
Trong công đoạn này, ta nên đa ra một hoặc nhiều hớng phân rã cho
một bài toán. Trớc khi tiến hành đánh giá các yêu cầu truyền thông, ta nên
xem xét các vấn đề đợc liệt kê dới đây để tránh gặp phải những sai sót không
dễ nhận ra trong quá trình thiết kế.
Hầu hết công việc của bài toán khoa học và kỹ thuật lớn thờng đợc
hoàn thành trong một số đoạn mã, ngời ta thờng gọi đó là các hotspots
của bài toán. Khi phân rã bài toán, ta lên chú trọng vào các đoạn mã
này, bỏ qua các đoạn mã chiếm thời gian CPU không đáng kể.
Phân chia bài toán thành các tác vụ với số lợng lớn hơn nhiều so với
số bộ xử lý. Nếu không, sự linh hoạt khi áp dụng vào mô hình cụ thể sẽ
không có.
Tránh yêu cầu tính toán và lu trữ d thừa. Bởi nếu không sẽ không có
khả năng mở rộng đối với các bài toán lớn hơn.
Ta có thể so sánh đợc kích thớc của các tác vụ, nếu không sẽ khó
khăn khi ta định vị số lợng ngang nhau giữa các bộ xử lý.
Số lợng tác vụ phải linh hoạt với kích thớc bài toán, nếu không có thể

producers).
Thứ hai, chỉ ra các message đợc gửi và nhận trên những kênh này.
Việc định nghĩa ra các kênh truyền sẽ làm phức tạp bài toán còn gửi
message sẽ tăng chi phí truyền thông. Bởi vậy, chúng ta tránh đa ra các
kênh và phép toán truyền thông không cần thiết. Hiệu năng có thể năng cao
bằng cách phân tán các phép toán truyền thông trên nhiều tác vụ và tổ chức
các phép toán truyền thông sao cho có thể thực hiện đồng thời.
Trong các bài toán phân rã theo miền, có thể sẽ khó khăn khi xác định
yêu cầu truyền thông bởi vì ta không nhận thấy đợc sự phụ thuộc dữ liệu
giữa các tác vụ. Sau khi thực hiện công đoạn phân rã sẽ hình thành ra tập
các tác vụ không liên kết. Tuy nhiên, sự phụ thuộc dữ liệu giữa các tác vụ
vẫn còn khi mà một số phép toán trong tác vụ này yêu cầu dữ liệu từ các tác
vụ khác. Tổ chức truyền thông một cách hiệu quả có thể đang trở thành
thách thức, thậm chí các phân rã đơn giản có thể có cấu trúc truyền thông
phức tạp. Ngợc lại, các yêu cầu truyền thông trong các giải thuật song song
đạt đợc bằng phân rã chức năng thờng là đơn giản, chúng tơng ứng với
luồng dữ liệu trao đổi giữa các tác vụ. Chẳng hạn nh bài toán mô hình thời
tiết, truyền thông tơng ứng với luồng dữ liệu liên kết giữa các thành phần của
mô hình.
Thông thờng có hai kiểu truyền thông là truyền thông cục bộ, mỗi tác
vụ truyền thông với một tập nhỏ các tác vụ khác gọi là các tác vụ kề bên của
nó, còn lại gọi là truyền thông toàn cục, yêu cầu mỗi tác vụ truyền thông với
nhiều tác vụ.
2. 4. 1 Truyền thông cục bộ

Cấu trúc truyền thông cục bộ đạt đợc khi một phép toán yêu cầu từ một
số nhỏ các tác vụ bên cạnh khác. Khi đó sẽ đơn giản để xác định các kênh
kết nối giữa tác vụ thực hiện phép toán (consumer) với các tác vụ nắm giữ dữ
liệu (producer) để tính toán và đa ra các phép toán nhận và gửi thích hợp
trong các tác vụ này.

của nhiều tác vụ. Khi phép toán đợc thực hiện, sẽ không đơn giản để nhận ra
các cặp producer/consumer. Với cách tiếp cận trên thì có thể dẫn đến quá
nhiều truyền thông hoặc hạn chế khả năng tính toán đồng thời.
Ví dụ, xem xét bài toán thực hiện phép toán rút gọn song song, rút gọn
N giá trị phân tán trên N tác vụ.
S =


=
1
0
N
i
i
X
Giả sử rằng có một tác vụ làm nhiệm tính toán tổng S, khi đó tác vụ
này cần yêu cầu các giá trị X
0
, X
1
, . . . từ các tác vụ 1, 2, . . . Bởi vậy, ta có thể
định nghĩa một cấu trúc truyền thông cho phép mỗi tác vụ truyền thông giá trị
của nó tới tác vụ tính S một cách độc lập. Tuy nhiên, tác vụ tính S chỉ có thể
nhận và tính tổng chỉ một số tại một thời điểm, nên cách tiếp cận này có độ
phức tạp O(N) về thời gian để tính tổng N số, đây không phải là giải thuật tốt.
Hình 2. 8 Mô tả truyền thông toàn cục trong bài toán tính tổng
Ví dụ trên đã mô tả hai vấn đề chung ngăn cản thực hiện song song
hiệu quả trong các giải thuật dựa trên quan điểm hoàn toàn cục bộ về truyền
thông.
Giải thuật này đợc tập trung hoá, không phân tán tính toán và