Tiểu luận: Tính toán song song – Parallel Computing
LỜI NÓI ĐẦU
Việc sử dụng các tài nguyên dùng chung ngày càng phổ biến, việc lưu trữ và xử lý dữ
liệu lớn càng được quan tâm, đã đưa nhu cầu tính toán trong lĩnh vực khoa học, công nghệ
ngày càng cao. Từ đó các giải pháp nhằm tăng tốc độ tính toán đã được ra đời. Ban đầu,
người ta thường sử dụng tăng tốc độ CPU để thu được kết quả tính toán nhanh, tuy nhiên
trong quá trình tăng tốc độ xung của CPU các nhà sản xuất đã gặp phải vấn đề về nhiệt độ
của CPU sẽ quá cao và các giải pháp tản nhiệt khí đã đến mức tới hạn không thể đáp ứng
được khả năng làm mát khi CPU hoạt động ở xung quá cao như vậy. Vì vậy việc gia tăng
xung hoạt động của CPU không sớm thì muộn cũng sẽ đi vào bế tắc.
Trước tình hình này, các nhà nghiên cứu vi xử lý đã chuyển hướng sang phát triển
công nghệ đa lõi, đa luồng với cơ chế xử lý song song trong các máy tính nhằm tăng hiệu
năng và tiết kiệm năng lượng. Lập trình song song có thể giải quyết được các bài toán với
thời gian xử lý nhanh chóng.
Qua môn học điện toán lưới và đám mây, người viết đã được tìm hiểu về các kỹ thuật
song song hóa để cải thiện thời gian tính toán cho các bài toán, trong đó lập trình song
song xem như là công cụ mạnh. Người viết xin gửi lời cảm ơn chân thành đến PGS.TS
Nguyễn Phi Khứ trường Đại học Công Nghệ Thông Tin và các quí Thầy Cô đã tận tình
giảng dạy, giúp đỡ để người viết hiểu thêm và hoàn thành tiểu luận này.
Mặc dù đã rất nỗ lực, cố gắng nhưng kiến thức còn hạn chế nên bài viết không thể
bao quát hết những kiến thức đã học, mục đích chủ yếu tiểu luận này là để ứng dụng kỹ
thuật song song hóa vào một vài giải thuật để tăng hiệu năng chương trình.
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 1
Tiểu luận: Tính toán song song – Parallel Computing
NHẬN XÉT CỦA GIẢNG VIÊN

GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 2
Tiểu luận: Tính toán song song – Parallel Computing
MỤC LỤC
LỜI NÓI ĐẦU 1
NHẬN XÉT CỦA GIẢNG VIÊN 2
MỤC LỤC 3
Ph n 1. C S LÝ THUY Tầ Ơ Ở Ế 4
1.1 Tính toán song song 4
1.2. So sánh XLTT và XLSS 5
1.2 Ki n trúc h th ng song songế ệ ố 6
1.3. Mô t phân lo i ki n trúc c a Flynnả ạ ế ủ 6

1.3 Các mô hình l p trình song songậ 10
1.4 Ki n trúc máy tính song songế 13
1.4. S p x p theo nguyên lý hình ngắ ế ố 14
1.5 Hi u qu tính toán song songệ ả 15
Ph n 2. L P TRÌNH SONG SONG TRONG CSHARPầ Ậ 18
2.1 Task Parallel Librabry (TPL) 18
2.2 Parallel Language INtegrated Query (PLINQ) 26
Ph n 3. L P TRÌNH SONG SONG V I MPIầ Ậ Ớ 29
3.1 C b n v truy n thông đi pơ ả ề ề ệ 29
3.2 MPI 30
KẾT LUẬN 44
TÀI LIỆU THAM KHẢO 45
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 3
Tiểu luận: Tính toán song song – Parallel Computing
Phần 1. CƠ SỞ LÝ THUYẾT
1.1 Tính toán song song
1.1.1 Giới thiệu
Trong những thập niên 60, nền tảng để thiết kế máy tính đều dựa trên mô hình của
John Von Neumann (Hình 1.1. ), với một đơn vị xử lý được nối với một vùng lưu trữ làm
bộ nhớ và tại một thời điểm chỉ có một lệnh được thực thi.
Hình 1.1. Mô tả kiến trúc Von Neumann
Với những bài toán yêu cầu về khả năng tính toán và lưu trữ lớn thì mô hình kiến
trúc này còn hạn chế. Để 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 đưa ra kiến trúc mới, với ý tưởng kết hợp nhiều bộ xử lý vào trong
một máy tính, mà hay gọi là xử lý 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 mạng (gọi là máy tính song song -
multicomputer).
Ngày nay các chương trình chúng ta đang sử dụng thông thường là các chương trình
được viết theo các giải thuật tuần tự, nghĩa là một bài toán được giải quyết thông qua một
chuỗi các câu lệnh tuần tự, thường thì bài toán này sẽ được thực hiện trên một máy tính

đơn với một BXL. Tính toán song song là một bước tiếp theo và là tất yếu của sự phát
triển của khoa học máy tính. Tính toán song song, đó là sự giải quyết bài toán dựa trên sự
thực thi một cách đồng thời của nhiều tài nguyên máy tính. Tài nguyên máy tính bao gồm:
- Một máy tính với nhiều BXL
- Nhiều máy tính đơn BXL kết nối với nhau
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 4
Tiểu luận: Tính toán song song – Parallel Computing
- Kết hợp cả hai loại trên
Tính toán song song được sử dụng để giải quyết các vấn đề phức tạp yêu cầu thời
gian tính toán lớn hoặc làm việc với khối lượng dữ liệu lớn như: các bài toán dự báo thời
tiết,các vấn đề khoa học như khai phá dữ liệu, trí tuệ nhân tạo, xử lý ảnh ba chiều (3-D),
mô phỏng các hệ thống lớn. Hầu hết các bài toán này, những máy tính xử lý tuần tự đều
không đáp ứng được yêu cầu về thời gian và khối lượng công việc.
1.1.2 Xử lý song song
Mặc dù tốc độ tính toán của các BXL tăng nhiều qua từng năm, nhưng do giới hạn
vật lý nên khả năng tính toán của chúng không thể tăng mãi. Nếu muốn tăng khả năng tính
toán thì chúng ta phải khai thác được khả năng xử lý song song. Xử lý song song là quá
trình xử lý gồm nhiều tiến trình được kích hoạt đồng thời và cùng tham gia giải quyết một
bài toán trên hệ thống có nhiều bộ xử lý.
Hình 1.2. Mô tả xư lý song song
Sự khác nhau cơ bản giữa xử lý song song và xử lý tuần tự:
1.2. So sánh XLTT và XLSS
Xử lý tuần tự Xử lý song song
Mỗi thời điểm chỉ thực hiện được 1 phép
toán
Mỗi thời điểm chỉ thực hiện được nhiều
phép toán
Thời gian thực hiện phép toán chậm Thời gian thực hiện phép toán nhanh
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 5
Tiểu luận: Tính toán song song – Parallel Computing

1.1.3 Máy tính song song
Máy tính song song (MTSS) là một tập các bộ xử lý (BXL) (thường là cùng một
loại) kết nối với nhau theo một kiểu nào đó để có thể hợp tác với nhau cùng hoạt động và
trao đổi dữ liệu với nhau.
1.2 Kiến trúc hệ thống song song
Một trong những phân loại kiến trúc máy tính song song được biết đến nhiều nhất là
phân loại của Flynn, được sử dụng từ năm 1966. Michael Flynn dựa vào đặc tính về số
lượng bộ xử lý, số chương trình thực hiện, cấu trúc bộ nhớ, … để phân máy tính thành bốn
loại dựa trên sự biểu hiện của cặp khái niệm: dòng lệnh (Instruction stream) và dòng dữ
liệu (Data stream), mỗi loại nằm trong một trong hai trạng thái đơn (single) hoặc đa
(multiple) được thể hiện trong bảng sau:
1.3. Mô tả phân loại kiến trúc của Flynn
Dòng lệnh
(Instruction stream)
Dòng dữ liệu
(Data stream)
Loại kiến trúc
Trạng thái đơn
(single)
Trạng thái đơn
(single)
SISD
Single Instruction Single Data
Trạng thái đơn
(single)
Trạng thái đa
(multiple)
SIMD
Single Instruction Multiple Data
Trạng thái đa

(multiple)
Trạng thái đơn
(single)
MISD
Multiple Instruction Single Data
Trạng thái đa
(multiple)
Trạng thái đa
(multiple)
MIMD
Multiple Instruction Multiple Data
1.2.1 Kiến trúc SISD (đơn dòng lệnh dơn luồng dữ liệu)
Máy tính SISD chỉ có một CPU, ở mỗi thời điểm thực hiện một chỉ lệnh và chỉ đọc,
ghi một mục dữ liệu. Tất cả các máy tính SISD chỉ có một thanh ghi (register) được gọi là
bộ đếm chương trình, được sử dụng để nạp địa chỉ của lệnh tiếp theo và kết quả là thực
hiện theo một thứ tự xác định của các câu lệnh.
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 6
Tiểu luận: Tính toán song song – Parallel Computing
.
Hình 1.1. Mô hình SISD
Hình 1.2. Ví dụ mô hình SISD
1.2.2 Kiến trúc SIMD (đơn dòng lệnh da luồng dữ liệu)
Máy tính SIMD có một đơn vị điều khiển để điều khiển nhiều đơn vị xử lý thực hiện theo
một luồng các câu lệnh. CPU phát sinh tín hiệu điều khiển tới tất cả các phần xử lý, những
bộ xử lý này cùng thực hiện một phép toán trên cấc mục dữ liệu khác nhau, nghĩa là mỗi
bộ xử lý có luồng dữ liệu riêng.
Hình sau đây mô tả mô hình SIMD, với
IS: Instruction Stream PU: Processing Unit
LM: Local Memory DS: Data Stream
Hình 1.3. Mô hình SIMD

GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 7
Tiểu luận: Tính toán song song – Parallel Computing
Hình 1.4. Ví dụ mô hình SIMD
Mô hình SIMD còn được gọi là SPMD, đơn chương trình và đa dữ liệu. Đây chính là mô
hình máy tính phổ biến có trên thị trường như: DAP và Connection Machine CM-2
1.2.3 Kiến trúc MISD (đa dòng lệnh đơn luồng dữ liệu)
Máy tính loại MISD có thể thực hiện nhiều chương trình (nhiều lệnh) trên cùng một mục
dữ liệu (ngược với máy tính loại SIMD).
Hình sau đây mô tả mô hình MISD, với
IS: Instruction Stream PU: Processing Unit CU: Control Unit
LM: Local Memory DS: Data Stream
Hình 1.5. Mô hình MISD
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 8
Tiểu luận: Tính toán song song – Parallel Computing
Hình 1.6. Ví dụ mô hình MISD
1.2.4 Kiến trúc MIMD (đa dòng lệnh đa luồng dữ liệu)
Máy tính loại MIMD gọi là đa bộ xử lý, trong đó mỗi bộ xử lý có thể thực hiện những
luồng lệnh (chương trình) khác nhau trên các luồng dữ liệu riêng. Hầu hết các hệ thống
MIMD đều có bộ nhớ riêng và cũng có thể truy cập vào bộ nhớ chung khi cần, do vậy
giảm thiểu được thời gian trao đổi dữ liệu giữa các bộ xử lý trong hệ thống. Đây là loại
kiến trúc phức tạp nhất, nhưng nó là mô hình hỗ trợ xử lý song song cao nhất và đã có
nhiều máy tính được thiết kế theo kiến trúc này, ví dụ: BBN Butterfly, Alliant FX, iSPC
của Intel,
Hình 1.7. Mô hình MIMD
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 9
Tiểu luận: Tính toán song song – Parallel Computing
Hình 1.8. Ví dụ mô hình MISD
Một vài nhận xét:
- Theo Flynn: có hai họ kiến trúc quan trọng cho các máy tính song song: SIMD và
MIMD. Những kiến trúc khác có thể xếp theo hai mẫu đó.

- Mục tiêu của xử lý song song là khai thác đến mức tối đa các khả năng sử dụng của
các thiết bị phần cứng nhằm giải quyết nhanh những bài toán đặt ra trong thực tế.
- Kiến trúc phần cứng là trong suốt đối với người lập trình.
- Trong kiến trúc tuần tự có thể tận dụng tốc độ cực nhanh của BXL để thực hiện xử
lý song song theo nguyên lý chia sẻ thời gian và chia sẻ tài nguyên.
- Những chương trình song song trên máy đơn BXL có thể thực hiện được nếu có
HĐH cho phép nhiều tiến trình cùng thực hiện, nghĩa là có thể xem hệ thống như là
đa bộ xử lý.
1.3 Các mô hình lập trình song song
1.3.1 Lập trình bộ nhớ dùng chung
Lập trình bộ nhớ dùng chung hay còn gọi là lập trình chia sẻ bộ nhớ. Trong mô hình
này được thiết kế cho máy tính xử lý song song (multiprocessors), các tác vụ chia sẻ không
gian địa chỉ dùng chung, được đọc/ghi một cách không đồng bộ. Một số kỹ thuật được
dùng trong lập trình bộ nhớ dùng chung như khoá (locks) hay cờ (semaphores) được sử
dụng để điều khiển truy nhập đến bộ nhớ dùng chung. Truyền thông giữa các tác vụ thông
qua các biến dùng chung.
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 10
Tiểu luận: Tính toán song song – Parallel Computing
Hình 1.9. Mô tả lập trình giữa các tác vụ dùng chung bộ nhớ
1.3.2 Lập trình truyền thông điệp
Trong máy tính song song cung cấp kỹ thuật truyền thông điệp để 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.10. Mô hình lập trình truyền thông giữa hai tác vụ trên hai máy tính
1.3.3 Mô hình song song dữ liệu
Trong mô hình song song dữ liệu, 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 nhưng 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 song song dữ liệu thiết kế chủ yếu dành cho máy tính song song kiểu bộ xử
lý mảng.
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 11
Tiểu luận: Tính toán song song – Parallel Computing
Hình 1.11. Mô hình lập trình song song dữ liệu
1.3.4 Mô hình hướng đối tượng
Trong mô hình hướng đối tượng 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 thông
qua gửi và nhận giữa các đối tượng. Các mô hình lập trình hiện nay đều xây dựng các đối
tượng từ mức thấp như tiến trình, tác vụ, hàng đợi và cờ tín hiệu đến mức cao như mô-đun
chương trình.
Các ngôn ngữ lập trình song song hướng đối tượng như: CORBA, DCE, JAVA,
C/C++.
1.3.5 Mô hình logic
Dựa trên cơ sở logic tiên đề, lập trình logic phù hợp cho xử lý trí thức giải quyết cơ
sở tri thức lớn. Mô hình này chấp nhận một chiến lược tìm kiếm ẩn và hỗ trợ song song
trong xử lý suy luận logic. Một câu hỏi được trả lời nếu hợp với các sự kiện được tìm thấy
trong cơ sở dữ liệu. Hai sự kiện hợp nhau nếu tiền đề của chúng và các đối kết hợp là như
nhau. Xử lý việc hợp và thống nhất có thể được song song dưới các điều kiện chắc chắn.
Mô hình này được áp dụng song song cho các ứng dụng trí tuệ nhân tạo.
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 12
Tiểu luận: Tính toán song song – Parallel Computing
1.4 Kiến trúc máy tính song song
1.4.1 Máy tính truy cập ngẫu nhiên song song
Chứa một đơn vị điều khiển CU, một bộ nhớ chung, một tập không giới hạn các BXL. Mỗi
BXL lại có bộ nhớ riêng và có một chỉ số duy nhất được sử dụng để xác định địa chỉ trong
quá trình trao đổi các tín hiệu và quản lý các ngắt. Tất cả các BXL đều chia sẻ bộ nhớ
chung với yêu cầu không bị giới hạn. Các câu lệnh có thể bắt đầu thực hiện ở bất kỳ thời
điểm nào, ở bất kỳ vị trí nào của bộ nhớ (riêng hoặc chung).

Hình 1.12. Mô hình máy tính song song kiểu PRAM
1.4.2 Kiến trúc MISD theo nguyên lý hình ống
Bộ xử lý hình ống chính là bộ xử lý kiểu MISD. Nguyên lý hình ống (pipeline): dựa trên
nguyên tắc:
- Phân đoạn hoặc chia nhỏ một tiến trình thành một số tiến trình con để thực hiện
trong các pha liên tiếp.
- Mỗi một giai đoạn của một tiến trình được thực hiện tuần tự. Sau khi thực hiện
xong một pha thì bắt đầu thực hiện giai đoạn của tiến trình tiếp theo.
- Mỗi pha thực hiện xong sẽ truyền kết quả cho pha tiếp theo.
Tóm lại, theo nguyên lý hình ống: Khi một giai đoạn công việc đang thực hiện thì một giai
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 13
Tiểu luận: Tính toán song song – Parallel Computing
đoạn khác có thể nạp dữ liệu vào, và dữ liệu vào của giai đoạn này có thể là kết quả của
giai đoạn trước nó.
Ví dụ sau đây cho thấy khác biệt giữa thực hiện tuần tự và hình ống của 2 tiến trình gồm 4
giai đoạn:
Giả sử một tiến trình được chia thành 4 giai đoạn:
- Thực hiện tuần tự 2 tiến trình phải qua 8 giai đoạn:
- Thực hiện theo hình ống chỉ cần thực thi phải qua 8 giai đoạn:
- Tổng thời gian tính toán tuần tự là: 2 * (S1 + S2 + S3+ S4)
- Tổng thời gian tính toán hình ống là: S1 + S2 + S3 + S4 + S4
Có thể sử dụng n tiến trình kết hợp theo nguyên lý hình ống để sắp xếp mảng a[n]. Hệ
thống được chia thành hai pha: Pha chẵn và pha lẻ. Pha chẵn: Các tiến trình được đánh số
chẵn so với những tiến trình tiếp theo (tiến trình có số lẻ), nếu nó giữ phần tử lớn hơn thì
đổi dữ liệu với tiến trình đó. Pha lẻ: Các tiến trình có số lẻ hoạt động tương tự như trên.
Ví dụ: Cho n = 8 và dãy số ban đầu là 6, 2, 8, 5, 1, 3, 4, 7. Kết quả sắp xếp theo
nguyên lý hình ống được thể hiện ở sau:
1.4. Sắp xếp theo nguyên lý hình ống
Tiến
trình

Pha
P0 P1 P2 P3 P4 P5 P6 P7
0 6
↔
2 8
↔
5 1
↔
3 4
↔
7
1 2 6
↔
5 8
↔
1 3
↔
4 7
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 14
Tiểu luận: Tính toán song song – Parallel Computing
2 2
↔
5 6
↔
1 8
↔
3 4
↔
7
3 2 5

↔
1 6
↔
3 8
↔
4 7
4 2
↔
1 5
↔
3 6
↔
4 8
↔
7
5 1 2
↔
3 5
↔
4 6
↔
7 8
6 1
↔
2 3
↔
4 5
↔
6 7
↔

8
7 1 2 3 4 5 6 7 8
Ở pha thứ 6 và pha thứ 7, không có cặp nào cần đổi chỗ nên giải thuật có thể dừng và
cho kết quả dãy đã sắp xếp.
Giả thiết dữ liệu được lưu trữ ở những tiến trình chẵn là B và những tiến trình lẻ là A.
Giải thuật song song theo hình ống được mô tả trong mô hình truyền thông điệp như sau:
Pha chẵn
P
i
, i = 0, 2, ,n – 2 (chẵn) P
i
, i = 1, 3, ,n - 3 (lẻ)
recv(&A, P
i+1
);
send(&B, P
i+1
);
if( A > B ) B = A;
send(&A, P
i-1
);
recv(&B, P
i-1
);
if( A > B ) A = B;
Pha lẻ
P
i
, i = 1, 3, ,n – 3 (lẻ) P

i
, i = 0, 2, ,n - 2 (chẵn)
recv(&A, P
i+1
);
send(&B, P
i+1
);
if( A > B ) B = A;
send(&A, P
i-1
);
recv(&B, P
i-1
);
if( A > B ) A = B;
Giải thuật này có độ phức tạp O(n).
1.5 Hiệu quả tính toán song song
1.5.1 Thời gian tính toán
Thời gian tính toán của giải thuật song song là thời gian dành để thực hiện tính toán.
Đối với giải thuật tuần tự thì thời gian này chỉ phụ thuộc vào kích thước của bài toán
nhưng với tính toán song song thì việc tính toán lặp trên các tác vụ có thể có. Do đó thời
gian tính toán sẽ phụ thuộc vào số tác vụ thực hiện. Đối với mô hình bộ nhớ chung thì số
lượng bộ xử lý cũng ảnh hưởng đến tốc độ thực thi trên mỗi bộ xử lý.
Thông thường có thể xác định bằng thời gian thực hiện tuần tự cộng với bất kỳ thời
gian nào thêm vào do thực hiện song song. Chẳng hạn như thời gian tính toán lặp lại cùng
một công việc trên các tác vụ.
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 15
Tiểu luận: Tính toán song song – Parallel Computing
1.5.2 Thời gian truyền thông

Thời gian truyền thông của một giải thuật là thời gian các tác vụ dành để gửi và nhận
thông điệp. Có hai loại truyền thông cần xác định: Truyền thông giữa hai tác vụ trên hai bộ
xử lý khác nhau và truyền thông giữa hai tác vụ cùng nằm trên cùng bộ xử lý. Thông
thường thời gian truyền bên trong bộ xử lý lớn hơn nhiều so với thời gian truyền giữa hai
bộ xử lý, nhất là đối với mô hình máy tính song song.
Trong mô hình máy tính song song lý tưởng thì chi phí để gửi một thông điệp giữa
hai tác vụ định vị trên bộ xử lý khác nhau phụ thuộc vào hai tham số sau:
Thời gian khởi tạo thông điệp: t
s
là thời gian cần thiết để khởi tạo truyền thông
Thời gian truyền dữ liệu: t
w
là thời gian cần thiết để truyền đi dữ liệu có kích thước
một word (2 byte). t
w
được xác định bởi băng thông vật lý của kênh truyền thông kết nối
bộ xử lý nguồn và đích.
Công thức tính thời gian gửi thông điệp có kích thước L (đơn vị là word) là:
T
msg
= t
s
+ L t
w

Nếu lượng dữ liệu truyền là nhỏ thì thời gian khởi tạo chiếm phần lớn, còn khi lượng
dữ liệu lớn thì thời gian truyền sẽ chiếm tỷ trọng cao, điều này được thể hiện qua hình sau:
Hình 1.1. Mô tả mối quan hệ các tham số tính thời gian truyền thông
Thông thường t
s

và t
w
là các thông số được tính toán phụ thuộc vào cụ thể kiến trúc
máy tính song song. Tuy nhiên đối với mô hình máy tính song song thực tế, cần phân tích
sự ảnh hưởng của hai kỹ thuật định đường truyền thông là lưu trữ và chuyển tiếp (store and
forward), chuyển mạch kênh (circuit-switched) cũng như ảnh hưởng của tranh chấp băng
thông trên đường truyền giữa các bộ xử lý.
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 16
Tiểu luận: Tính toán song song – Parallel Computing
Trong sơ đồ của cơ chế lưu trữ và chuyển tiếp, thời gian cần thiết để gửi một thông
điệp từ một bộ xử lý tới một bộ xử lý khác tăng tuyến tính với số bước nhảy mà thông
điệp phải tạo ra để đến được đích. Ngược lại, thời gian cần thiết để gửi một thông điệp từ
một bộ xử lý tới một bộ xử lý khác trong lược đồ chuyển mạch là phụ thuộc rất ít với
khoảng cách giữa các bộ xử lý.
Do đó có thể phát triển thành các công thức sau:
- Đối với truyền thông định đường theo cơ chế lưu trữ và chuyển tiếp:
T
msg
= ( t
s
+ t
w
L) D
Với D là khoảng cách giữa nút nhận và gửi trong bước định đường.
- Đối với truyền thông định đường theo cơ chế chuyển mạch kêmh:
T
msg
= t
s
+ t

w
L – t
h
D
Với D là khoảng cách giữa nút nhận và gửi trong bước định đường T
h
là chi phí gia
tăng cho mỗi bước định đường.
Trong thực tế, t
h
thường rất nhỏ, có thể bỏ qua được. Khi xem xét đến sự tranh chấp
băng thông truyền trên mạng kết nối thì công thức tính được thay đổi như sau:
T
msg
= t
s
+ t
w
S L
Trong đó S là số bộ xử lý gửi đồng thời trên cùng một đường dây.
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 17
Tiểu luận: Tính toán song song – Parallel Computing
Phần 2. LẬP TRÌNH SONG SONG TRONG CSHARP
2.1 Task Parallel Librabry (TPL)
2.1.1 Task
Chương trình cần lấy dữ liệu từ database, nó sẽ truy vấn đến database thông qua
LINQ, sau đó được đưa đến các thư viện chứa các Task (Task Parallel Library- viết tắt là
TPL). Tại đây chương trình sẽ được chia nhỏ thành các tác vụ và được lập lịch hoạt động
(task sheduling). Kết quả ta thu được các threads và các threads này sẽ được sử lý đồng
thời. Nếu chương trình không cần lấy dữ liệu từ database, ta sẽ thao tác trực tiếp và trực

tiếp tạo ra các task.

Hình 1.1. Mô hình máy tính song song kiểu PRAM
Như đã trình bày ở trên, mô hình lập trình song song sẽ chia nhỏ chương trình ra thành các
tác vụ nhỏ (task). Để sử dụng TPL ta cần thêm không gian tên System.Threading.Task,
NET Framework 4 cung cấp cho ta rất nhiều cách để khai báo và khởi tạo 1 Task.
// use an Action delegate and a named method
Task task1 = new Task(new Action(printMessage));
// use a anonymous delegate
Task task2 = new Task(delegate { printMessage(); });

GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 18
Tiểu luận: Tính toán song song – Parallel Computing
// use a lambda expression and a named method
Task task3 = new Task(() => printMessage());
// use a lambda expression and an anonymous method
Task task4 = new Task (() => { printMessage();} );
Mỗi một task khi ta khai báo sẽ được máy tính biên dịch và chạy đồng thời. Tuy nhiên ta
cũng có thể định thời gian hoạt động cho các task.
• Hủy bỏ một task : trong không gian tên System.Thread ta sử dụng phương thức
CancellationTokenSource để hủy bỏ một task. Việc hủy bỏ một tác vụ được sử
dụng đến khi chương trình đang hoạt động mà ta muốn can thiệp và dừng 1 tác
dụng nào đó lại.
• Tác vụ chờ : khi ta không muốn một tác vụ nào đấy thực hiện ngay, mà chờ đợi
1 khoảng thời gian nhất định. Ta sẽ sử dụng phương thức Thread.Sleep() và
Thread.SleepWait().
Ta cũng có thể bắt 1 Task thực hiện sau khi tất cả các task khác đã thực hiện xong
hoặc chờ đợi sau bao lâu bằng việc sử dụng phương thức Task.Wait();
2.1.2 Vòng lặp song song (Parallel loops)
Như chúng ta đã biết các vòng lặp tuần tự thông thường như for, do while, chương

trình sẽ phải chạy tuần tự từng vòng lặp cho đến khi gặp lệnh kết thúc. Như vậy sẽ rất tốn
thời gian, trong khi CPU của chúng ta vẫn còn đang rảnh rỗi (chờ thực hiện xong vòng lặp
này rồi mới thực hiện vòng lặp tiếp theo). Để khắc phục điều này, mô hình lập trình song
song cho phép chúng ta thực hiện song song các vòng lặp. Thay vì phải thực hiện lần lượt
các vòng lặp, CPU có thể thực hiện được đồng thời nhiều vòng lặp cùng lúc. Từ đó giúp
tiết kiệm thời gian.
2.1.2.1 Parallel.For()
Phương thức Parallel.For() với 3 tham số đầu vào, tham số đầu chỉ chỉ số bắt đầu tác vụ,
tham số thứ 2 chỉ chỉ số kết thức, và mục thứ 3 chỉ tác vụ cần thực hiện
Parallel.For(0, 10, index => {
Console.WriteLine("Task ID {0} processing index: {1}",
Task.CurrentId, index);
});
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 19
Tiểu luận: Tính toán song song – Parallel Computing
Ví dụ sau đây, phương thức GenerateMD5Hashes với việc sử dụng vòng lặp tuần tự và
song song:
- Sequential for Version
private static void GenerateMD5Hashes()
{
var sw = Stopwatch.StartNew();
var md5M = MD5.Create();
for (int i = 1; i <= NUM_MD5_HASHES; i++)
{
byte[] data =
Encoding.Unicode.GetBytes(
Environment.UserName + i.ToString());
byte[] result = md5M.ComputeHash(data);
string hexString = ConvertToHexString(result);
Console.WriteLine("MD5 HASH: {0}", hexString);

}
Debug.WriteLine("MD5: " + sw.Elapsed.ToString());
}
- Parallel for Version
private static void ParallelGenerateMD5Hashes()
{
var sw = Stopwatch.StartNew();
Parallel.For(1, NUM_MD5_HASHES + 1, (int i) =>
{
var md5M = MD5.Create();
byte[] data =Encoding.Unicode.GetBytes(Environment.UserName + i.ToString());
byte[] result = md5M.ComputeHash(data);
string hexString = ConvertToHexString(result);
Console.WriteLine("MD5 HASH: {0}", hexString);
});
Debug.WriteLine("MD5: " + sw.Elapsed.ToString());
}
2.1.2.2 Parallel.ForEach
Vòng lặp ForEach() : sử dụng phương thức Parallel.ForEach(), vòng lặp này linh hoạt hơn
so với vòng lặp trước, nhờ việc cho phép cải biên dữ liệu đầu vào.
Xét ví dụ :
List<string> dataList = new List<string> {
"the", "quick", "brown", "fox", "jumps", "etc" };
Parallel.ForEach(dataList, item => {
Console.WriteLine("Item {0} has {1} characters", item, item.Length);
});
Cấu trúc câu lệnh trên khá giống với cấu trúc câu lệnh của lập trình tuần tự. Tuy nhiên ta
không nên hiểu nhầm các vòng lặp này sẽ được thực hiện một cách tuần tự. Nó chỉ biểu
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 20
Tiểu luận: Tính toán song song – Parallel Computing

diễn dưới dạng này. Còn việc thực hiện song song là do trình biên dịch và CPU đảm
nhiệm.
Ví dụ sau đây, phương thức ParallelParitionGenerateMD5Hashes với việc sử dụng vòng
lặp tuần tự và song song:
private static void ParallelPartitionGenerateMD5Hashs()
{
var sw = Stopwatch.StartNew();
Parallel.ForEach(Partitioner.Create(1, NUM_MD5_HASHS + 1), range =>
{
var md5M = MD5.Create();
Debug.WriteLine("MD5 Range ({0}, {1}. TimeOfDay before inner loop starts:
{2})",range.Item1, range.Item2,DateTime.Now.TimeOfDay);
for (int i = range.Item1; i < range.Item2; i++)
{
byte[] data =
Encoding.Unicode.GetBytes(Environment.UserName + i.ToString());
byte[] result = md5M.ComputeHash(data);
string hexString = ConvertToHexString(result);
Console.WriteLine("MD5 HASH: {0}", hexString);
}
});
Debug.WriteLine("MD5: " + sw.Elapsed.ToString());
}
Theo sau ForEach, được chia thành 13 partition, trong mỗi partition sẽ được chạy song
song.
2.1.3 Parallel.Invoke
Các phương thức được chạy song song bằng cách sử dụng Invoke trong Parallel. Hai bài
toán sau đây cho ta thấy rõ việc song song sử dụng Parallel.invoke
2.1.3.1 Bài toán 1: using Parallel.invoke parallel, to view result output different
namespace Task_ResultDif

{
class Program
{
static void Main(string[] args)
{
Parallel.Invoke(
() =>
{
Console.WriteLine("1.Green");
},
() =>
{
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 21
Tiểu luận: Tính toán song song – Parallel Computing
Console.WriteLine("2.Red");
},
() =>
{
Console.WriteLine("3.Purple");
},
() =>
{
Console.WriteLine("4.Yellow");
}
);
}
}
}
- Ở đây, thử chạy ở lần thứ 1, kết quả như sau:
- Tiếp tục với lần chạy thứ 2, ta có kết quả như sau:

Mô hình sau đây có thể biểu diễn cho việc chạy trên 1 logical core
Hình 1.2. Mô hình chạy 1 logical core
Mô hình sau đây có thể biểu diễn cho việc chạy trên 4 logical core
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 22
Green
Red
Purple
Yellow
Green
Red
Purple
Yellow
Tiểu luận: Tính toán song song – Parallel Computing
Hình 1.3. Mô hình chạy 4 logical core
Hình 1.4. Hình ảnh CPU chạy 4 logical core
2.1.3.2 Bài toán 2: Encryption with 100 Unicode string using AES and MD5
- Sequential
class Program
{
private const int NUM_AES_KEYS = 800000;
private const int NUM_MD5_HASHES = 100000;
static void Main(string[] args)
{
var sw = Stopwatch.StartNew();
GenerateAESKeys();
GenerateMD5Hashes();
Debug.WriteLine(sw.Elapsed.ToString());
// Display the results and wait for the user to press a key
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 23
Tiểu luận: Tính toán song song – Parallel Computing

Console.ReadLine();
}
private static string ConvertToHexString(Byte[] byteArray)
{
// Convert the byte array to hexadecimal string
var sb = new StringBuilder(byteArray.Length);
for (int i = 0; i < byteArray.Length; i++)
{
sb.Append(byteArray[i].ToString("X2"));
}
return sb.ToString();
}
private static void GenerateAESKeys()
{
var sw = Stopwatch.StartNew();
var aesM = new AesManaged();
for (int i = 1; i <= NUM_AES_KEYS; i++)
{
aesM.GenerateKey();
byte[] result = aesM.Key;
string hexString = ConvertToHexString(result);
Console.WriteLine("AES KEY: {0} ", hexString);
}
Debug.WriteLine("AES: " + sw.Elapsed.ToString());
}
private static void GenerateMD5Hashes()
{
var sw = Stopwatch.StartNew();
var md5M = MD5.Create();
for (int i = 1; i <= NUM_MD5_HASHES; i++)

{
byte[] data =
Encoding.Unicode.GetBytes(
Environment.UserName + i.ToString());
byte[] result = md5M.ComputeHash(data);
string hexString = ConvertToHexString(result);
Console.WriteLine("MD5 HASH: {0}", hexString);
}
Debug.WriteLine("MD5: " + sw.Elapsed.ToString());
}
}
Thời gian để chạy tuần tự
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 24
Tiểu luận: Tính toán song song – Parallel Computing
Hình 1.5. Mô hình AES, MD5 tuần tự
- Parallel
Parallel.Invoke(
() => GenerateAESKeys(),
() => GenerateMD5Hashes());
Thời gian để chạy song song
Hình 1.6. Mô hình AES, MD5 song song
2.1.4 AsParallel
Với AsParallel, ta có thể thực hiện tính toán song song. Bài toán sau đây cho thấy 2 cách
tính tổng mảng theo cách tuần tự và song song.
static void Main(string[] args)
{
const int m = 10000;
var intArray = Enumerable.Range(0, short.MaxValue).ToArray();
var s1 = Stopwatch.StartNew();
for (var i = 0; i < m; i++)

{
SumDefault(intArray);
}
s1.Stop();
GVHD: PGS.TS Nguyễn Phi Khứ HVTH: Nguyễn Ngọc Vọng – CH1301118 25