ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

TÍNH TOÁN LƯỚI
ĐỀ TÀI: TÌM HIỂU TÍNH TOÁN
SONG SONG
GVHD: PGS. TS. Nguyễn Phi Khứ
Thực hiện: Trịnh Quốc Hùng - CH1101088
Thành phố Hồ Chí Minh - Tháng 07 Năm 2013
Tính Toán Lưới
NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN

Mục lục
Tìm hiểu tính toán song song Trang 2
Tính Toán Lưới
Tìm hiểu tính toán song song Trang 3
Tính Toán Lưới
1. Tổng quan về tính toán song song
1.1. Tính toán tuần tự
- Một vấn đề được chia thành một dãy rời rạc các chỉ thị (Instruction – lệnh máy
tính) mà máy tính có thể hiểu để thực hiện.
- Máy tính thực hiện các chỉ thị theo thứ tự mà chúng xuất hiện.
- Chỉ có duy nhất một chỉ thị được thực hiện tại một thời điểm.
- Các phần mềm ứng dụng đều được viết cho các máy tính tuần tự.
Máy tính tuần tự là loại máy tính thực hiện các lệnh một cách tuần tự và tại mỗi
thời điểm chỉ một chỉ thị duy nhất được thực hiện. Cách tính toán tuần tự trên máy
đơn nguyên có thể minh họa bởi hình 1.1
Hình 1.1 Mô tính toán tuần tự
1.2. Tính toán song song
Tính toán song song là quá trình tính toán gồm nhiều tiến trình được kích hoạt
đồng thời và cùng tham gia tính toán giải quyết một vấn đề, và nói chung phải thực
hiện trên các hệ thống đa bộ xử lí.
- Một vấn đề cần tính toán được phân hoạch thành các phần tính toán rời rạc,
các phần này lại có thể tính toán được đồng thời (song song).
- Từng phần của phân hoạch lại được chia nhỏ thành chuỗi các chỉ thị và được
thực hiện tuần tự.
- Các chỉ thi của từng phần thực hiện đồng thời trên các CPU khác nhau.

Quan niệm đơn giản nhất, tính toán song song là việc sử dụng đồng thời nhiều
máy tính được kết nối thành mạng hoặc chỉ trên một máy tính nhưng có nhiều hơn
hai bộ xử lý.
Tìm hiểu tính toán song song Trang 4
Tính Toán Lưới
Hình 1.2 Mô tính toán song song
Trong tính toán song song hiện nay, có hai công nghệ chính:
Thứ nhất là sử dụng các siêu máy tính với rất nhiều bộ xử lý được tích hợp bên trong
được thiết kế đồng bộ cảvềphần cứng và phần mềm. Các công nghệ được áp dụng
trong các siêu máy tính thường là các công nghệ tiên tiến làm cho giá thành của hệ
thống siêu tính tăng rất cao.Vì thế các siêu máy tính thường được sử dụng trong các
lĩnh vực mà vấn đềtính toán phức tạp, nhạy cảm và yêu cầu thời gian thực như mô
phỏng thực hiện của các động cơ máy bay, quốc phòng, vũ trụ
Cách thứ hai là kết nối các máy tính lại với nhau và cùng thực hiện bài toán. Hệ
thống các máy tính kết nối này chính là hệ thống tính toán song song phân cụm. Hệ
thống này có ưu điểm là giá thành rẻ hơn rất nhiều so với siêu máy tính có cùng sức
mạnh (do sử dụng các thiết bị thông thường) và tính linh hoạt của hệthống (sốnút, số
bộ xử lý, bộ nhớ, thiết bịmạng đều mang tính tuỳ biến cao). Sự phát triển mạnh mẽ
của mạng máy tính, các công nghệ mạng hiện nay đã lấp đi hạn chế về truyền thông
trong hệ thống máy tính song song phân cụm làm cho nó được phát triển rộng rãi. Các
lĩnh vực sử dụng hệ thống tính toán song song phân cụm thường yêu cầu tính toán các
kiến trúc song song.
1.3. Tại sao sử dụng tính toán song song?
• Tiết kiệm thời gian và / hoặc tài chính
Tìm hiểu tính toán song song Trang 5
Tính Toán Lưới
• Giải quyết được các vấn đề lớn hơn, phức tạp hơn
Nhiều vấn đề quá lớn và/hoặc quá phức tạp đến nỗi nó không thực tế hoặc không
có khả năng giải quyết chúng trên máy tính đơn, đặc biệt là bộ nhớ máy tính lại bị hạn
chế. Chẳng hạn các vấn đề:

- Dự báo thời tiết, bão, động đất, sóng thần, mô hình sinh thái, …
- Máy dò tìm web/CSDL để xử lý hàng triệu triệu giao dịch trên một giây
(công cụ tìm kiếm web/CSDL xử lý hàng triệu giao dịch/giây)
- …
• Cung cấp tính đồng thời
• Sử dụng tài nguyên phi cục bộ
Sử dụng tài nguyên tính toán trên một mạng diện rộng, hoặc thậm chí Internet
khi tài nguyên tại nơi tính toán tài nguyên đang khan hiếm, không đủ. Ví dụ:
• Những hạn chế khi tính toán tuần tự
o Tốc độ truyền - tốc độ của một máy tính tuần tự phụ thuộc trực tiếp vào tốc độ
chuyển dữ liệu qua phần cứng. Giới hạn tốc độ tuyệt đối là tốc độ của ánh sáng
(30 cm/nanosecond) và hạn chế sự lan truyền (băng thông) của dây đồng (9
cm/nanosecond). Để tăng tốc độ cần phải tăng số lượng các phần tử xử lý,
o Các giới hạn về công nghệ tiểu họa vi xử lý (miniaturization – processor
technology) là cho phép tăng số lượng bóng bán dẫn được đặt trên một chip.
Tuy nhiên, ngay cả với các thành phần cấp độ phân tử hoặc nguyên tử thì một
giới hạn cũng sẽ được đạt đến dù các thành phần nhỏ đến thế nào đi nữa.
o Các hạn chế về kinh tế - làm một bộ xử lý đơn càng nhanh thì càng đắt tiền.
o Các kiến trúc máy tính hiện tại đang ngày càng dựa vào khả năng song song
hóa phần cứng để cải thiện hiệu suất như:
 Có nhiều đơn vị thực hiện
 Dùng các chỉ lệnh đường ống (Pipelined instructions)
 Đa nhân (Multi-core)
Tìm hiểu tính toán song song Trang 6
Tính Toán Lưới
Một vấn đề được thực hiện song song sẽ có các ưu/nhược điểm cơ bản sau:
Ưu điểm:
- Có thể kết thúc công việc sớm hơn,
- Chi phí có thể ít hơn nhiều,
-

Nhược điểm:
- Tăng tính phức tạp cho hệ thống.
- Tăng chi phí cho nhân lực vì phải tăng nhân lực
- Tăng chi phí mua các thiết bị.
- Tăng chi phí lắp đặt hệ thống.
Trong 20 năm qua, sự phát triển mạnh của các mạng (network), hệ thống phân tán
và kiến trúc đa xử lý (thậm chí là máy tính để bàn) đã cho thấy rõ song song là xu
hướng của tính toán. Trong thời gian đó, các siêu máy tính đã tăng hơn 1000 lần về
hiệu xuất, và sẽ tiếp tục trong tương lai.
Tìm hiểu tính toán song song Trang 7
Tính Toán Lưới
Tính toán song song hiện đang được sử dụng rộng rãi trên thế giới trong nhiều ứng
dụng lớn
Nguồn: Top500.org
Tìm hiểu tính toán song song Trang 8
Tính Toán Lưới
Nhà cung cấp:
Tìm hiểu tính toán song song Trang 9
Tính Toán Lưới
Phần lớn các siêu máy tính trên thế giới là các cụm phần cứng được sản xuất bởi một
số ít các nhà cung cấp nổi tiếng
Nguồn: Top500.org
2. Các mô hình máy tính song song
Micheal Flynn chia kiến trúc máy tính song song như hình sau:
2.1. Đơn chỉ thị đơn dữ liệu (SISD - Single Instruction Single Data)
− Dùng cho máy tính đơn nguyên tuần tự - không song song
− Đơn chỉ thị: mỗi thời điểm chỉ dùng một chỉ có một chỉ thị đang được xử lý bởi
CPU trong một chu kỳ đồng hồ nào đó. Chẳng hạn, hình 2.1, chu kỳ đồng hồ
thứ nhất load, chu kỳ đồng hồ thứ hai load, … , chu kỳ đồng hồ cuối cùng
Store

Tìm hiểu tính toán song song Trang 10
Tính Toán Lưới
Hình 2.1. Ví dụ về đơn chỉ thị, đơn luồng dữ liệu
− Đơn luồng dữ liệu: chỉ có một dữ liệu đang được sử dụng như đầu vào trong
một chu kỳ đồng hồ nào đó. Chẳng hạn , hình 1.8, chu kỳ đồng hồ thứ nhất A,
chu kỳ đồng hồ thứ hai B, … , chu kỳ đồng hồ cuối A
− Thực hiện theo tiền định, nghĩa là công việc được hoạch định rõ ràng khi lập
trình (tĩnh), trong qúa trình thực thi các câu lệnh và dữ liệu không bị thay đổi.
− Đây là loại máy tính lâu đời nhất và thậm chí cho đến ngày nay vẫn là loại máy
tính phổ biến nhất.
2.2. Đơn chỉ thị đa dữ liệu (SIMD - Single Instruction Multiple Data)
− Đơn chỉ thị: Tất cả các bộ vị xử lý p1, p2, …, pn cùng thực thi cùng một chỉ
thị tại cùng một chu kỳ đồng hồ đã cho. Chẳng hạn, hình 2.1, chu kỳ đồng hồ
thứ nhất, n bộ xử lý này cùng có một chỉ thị là load, chu kỳ đồng hồ thứ hai, n
bộ xử lý cùng có một chỉ thị là load, … , chu kỳ đồng hồ thứ 4, n bộ xử lý cùng
có một chỉ thị là Store,…
− Đa luồng dữ liệu: Mỗi bộ xử lý có thể hoạt động trên một phần tử dữ liệu khác
với dữ liệu của bộ xử lý khác - có nhiều dữ liệu đang được sử dụng như đầu
vào trong một chu kỳ đồng hồ nào đó. Chẳng hạn, hình 2.1, chu kỳ đồng hồ thứ
nhất A(1), A(2), …, A(n); chu kỳ đồng hồ thứ hai B(1), B(2), …, B(n) ; … ,
chu kỳ đồng hồ thứ 4 là C(1), C(2), …, C(n); …
− Loại máy tính này rất phù hợp cho các vấn đề chuyên ngành được đặc trưng
bởi mức đồng bộ cao, chẳng hạn như xử lý đồ họa hoặc hình ảnh,….
− Đồng bộ và thực hiện tiền định.
− Hai kiến trúc bộ xử lý hay được sử dụng nhất trong trường hợp này là: Bộ xử
lý mảng và xử lý kiểu đường ống vectơ
Máy tính kiến trúc SIMD chỉ có một CU để điều khiển nhiều PE thực hiện theo
một luồng lệnh. CU phát lệnh điều khiển tới tất cả các PE, các PE này cùng thực hiện
Tìm hiểu tính toán song song Trang 11
Tính Toán Lưới

một phép toán trên các mục dữ liệu khác nhau, nghĩa là mỗi PE có một luồng dữ liệu
riêng. Như vậy SIMD cho phép các Pi khác nhau (hoặc ALU khác nhau) làm cùng
một phép tính trên các toán hạng khác nhau. Máy tính SIMD có hỗ trợ cách xử lý
vector, nghĩa là gán mỗi thành phần của một vector cho các Pi để thực hiện tính toán
đồng thời. Cấu trúcbản của SIMD như hình 2.2
Hình 2.2.a. Kiến trúc kiến trúc SIMD
Hình 2.2.b Đơn chỉ thị, đa luồng dữ liệu
2.3. Da dữ liệu đơn dòng lệnh (MISD - Multiple Instruction Single
Data)
− Một dòng dữ liệu duy nhất được đưa vào các đơn vị đa xử lý.
− Mỗi đơn vị xử lý hoạt động trên các dữ liệu một cách độc lập thông qua các
luồng chỉ thị độc lập khác nhau
− Rất ít ví dụ thực tế của lớp các máy tính song song kiểu này.
Kiến trúc MISD được chia làm hai nhóm cơ bản:
− Thứ nhất, nhóm máy tính yêu cầu có các công việc khác nhau, các phần tử xử
lý khác nhau có thể nhận những chỉ lệnh khác nhau để thực hiện trên một mục
dữ liệu.
Tìm hiểu tính toán song song Trang 12
Tính Toán Lưới
− Thứ hai, nhóm máy tính có các luồng dữ liệu được chuyển tuần tự theo dãy các
PE liên tiếp. Hoạt động của máy tính theo kiến trúc này giống như hệ tuần
hoàn nên còn được gọi là hệ tâm thu, hình 2.3
Hình 2.3. Kiến trúc kiến trúc MISD
2.4. Đa dữ liệu đa dòng lệnh (MIMD – Multiple Instruction Multiple
Data)
Hiện nay, các loại phổ biến nhất của máy tính song song. Hầu hết máy tính hiện
đại đều thuộc vào loại này.
− Đa chỉ thị: mỗi bộ xử lý có thể được thực hiện một
dòng chỉ thị khác với các dòng chỉ thị của các bộ xử lý khác.
− Đa dữ liệu: mỗi bộ xử lý có thể làm việc với một

dòng dữ liệu khác với các dòng dữ liệu của các bộ xử lý khác.
Việc thực hiện các chỉ thị có thể được đồng bộ hoặc không đồng bộ, tiền định hoặc
không tiền định.
Hình 2.4.a Các kiến trúc máy tính xử lý song
Kiến trúc MIMD còn được gọi là máy đa bộ xử lý, mỗi bộ xử lý có thể thực hiện
bởi luồng lệnh và luồng dữ liệu riêng.
Tìm hiểu tính toán song song Trang 13
Tính Toán Lưới
Hình 2.4.b Kiến trúc kiến trúc MIMD
MIMD có bộ nhớ chung, các bộ xử lý của MIMD đều có bộ nhớ riêng, nhưng
được phép truy cập vào bộ nhớ chung khi cần, do vậy giảm được các thao tác trao đổi
giữa các bộ xử lý trong hệ thống, xem hình 2.4.b.
Tìm hiểu tính toán song song Trang 14
Tính Toán Lưới
3. Các mô hình lập trình song song
Một số mô hình lập trình song song phổ biến được liệt kê dưới đây:
- Chia sẻ bộ nhớ (Shared Memory)
- Luồng, tiến trình (Thread)
- Truyền thông báo (Massage Passing)
- Dữ liệu song song (Data Parallel)
- Hỗn hợp (Hybrid)
Các mô hình lập trình song song tồn tại như một trừu tượng hóa trên cả phần cứng
và kiến trúc bộ nhớ.
Khó diễn tả cụ thể mô hình này cho một loại máy cụ thể hoặc một kiến trúc bộ nhớ
nào đó. Trong thực tế, bất kỳ mô hình nào trong các mô hình này đều có thể (về mặt
lý thuyết) được thi hành trên bất kỳ phần cứng cơ bản nào.
Vấn đề quan trọng trong lập trình song song là phải tận dụng được khả năng tính
toán của các bộ xử lý. Có hai cách tiếp cận để tận dụng các bộ xử lý:
1. Phát triển những ngôn ngữ lập trình cho phép thể hiện được việc thực
hiện song song ở mức thuật toán, ví dụ như Fortran, C,

2. Xây dựng những chương trình dịch đủ mạnh để nhận dạng được các
phân chia chương trình thành các đoạn có thể thực hiện song song hay tuần tự -
với loại chương trình dịch này có thể dùng cho tự động song song.
Hai cách tiếp cận trên bổ sung cho nhau cho phép chúng ta sử dụng tốt nhất các bộ
xử lý, nếu áp dụng một cách thì dĩ nhiên là sẽ không hiệu quả bằng.
Ngoài tiết cận để tận dụng các bộ xử lý, thì các cách tiếp cận trong lập trình
song song như sau đây cũng đóng vai trò rất quan trọng:
1. Lập trình song song kiểu SIMD với bộ nhớ chia sẻ, trong đó truy cập bộ nhớ là
đồng bộ.
2. Lập trình song song kiểu MIMD với bộ nhớ chia sẻ, trong đó truy cập bộ nhớ là
dị bộ.
3. Lập trình song song kiểu MIMD với bộ nhớ phân tán, trong đó truy cập bộ nhớ
là dị bộ.
Tìm hiểu tính toán song song Trang 15
Tính Toán Lưới
4. Lập trình song song kiểu SPMD với bộ nhớ chia sẻ, trong đó truy cập bộ nhớ là
dị bộ.
5. Lập trình song song kiểu SPMD với bộ nhớ phân tán, trong đó truy cập bộ nhớ
là dị bộ.
6. Lập trình song song kiểu MPMD với bộ nhớ chia sẻ, trong đó truy cập bộ nhớ
là dị bộ.
3.1. Mô hình chia sẻ bộ nhớ (Shared Memory Model)
Trong mô hình lập trình chia sẻ bộ nhớ, các tác vụ chia sẻ với nhau một không
gian địa chỉ chung, ở đó các tác vụ đọc và ghi không đồng bộ.
Các cơ chế khác nhau như khóa / semaphores (cờ hiệu) có thể được sử dụng để
kiểm soát (hoặc điều khiển) truy cập vào bộ nhớ chia sẻ.
Một lợi thế của mô hình này theo quan điểm của lập trình viên thì khái niệm
"sở hữu" dữ liệu là đang thiếu, do đó, không cần thiết phải định rõ việc truyền dữ liệu
giữa các tác vụ. Do vậy việc lập trình thường đơn giản hơn.
Một số bất lợi quan trọng về hiệu năng, đó là nó khó hiểu hơn và khó quản lý

dữ liệu cục bộ hơn, vì:
- Việc lưu giữ dữ liệu cục bộ cho bộ xử lý làm việc trên đó, bộ xử lý này sẽ
chiếm giữ bộ nhớ truy cập, nên cần phải làm tươi (mới) lại bộ nhớ cache và
đường truyền bus khi có nhiều bộ xử lý sử dụng chung dữ liệu.
- Việc kiểm soát dữ liệu cục bộ sẽ rất khó và ngoài tầm kiểm soát của người
lập trình chưa có trình độ cao cần thiết.
- Trên nền tảng bộ nhớ chia sẻ, trình biên dịch chương trình chuyển các
biến của người lập trình vào các địa chỉ bộ nhớ thực, đó là địa chỉ vật lý toàn
cục.
- Không có những bổ sung cơ bản nào cho bộ nhớ phân tán đang tồn tại.
Tuy nhiên, như đã đề cập trước đó, các cách tiếp cận KSR ALLCACHE cung
cấp cách thức dữ liệu của bộ nhớ chia sẻ ngay cả khi bộ nhớ vật lý của máy
tính này được phân tán.
3.2. Lập trình chia sẻ bộ nhớ dựa vào tiến trình
Tìm hiểu tính toán song song Trang 16
Tính Toán Lưới
Tạo lập và huỷ bỏ tiến trình
Yêu cầu đầu tiên của xử lý song song là khả năng tạo ra một số tiến trình cần thiết
cho bài toán và khả năng huỷ bỏ tiến trình khi phần việc xử lý song song kết thúc để
giải phóng các tài nguyên mà các tiến trình đã chiếm giữ và không cản trở hoạt động
của những tiến trình khác.
Để thêm N tiến trình, chúng ta dùng lệnh:
id = create_process (N);
Lệnh này tạo thêm N tiến trình và cả một tiến trình cha (chủ) nữa để thực hiện câu
lệnh đó, kết quả là có N+1 tiến trình như nhau được tạo ra và mỗi giá trị của id được
gán tương ứng cho một tiến trình.
Để sử dụng các tiến trình đã được tạo ra, chúng ta có thể viết ra các chương trình
song song có dạng:
id = create_process(N);
Switch (id) {

Case 0 : … do NhiemVu
0
…; Break;
Case 1 : … do NhiemVu
1
…; Break;
Case 2 : … do NhiemVu
2
…; Break;
………
Case N : … do NhiemVu
N
…; Break;
}
Sau khi các công việc trên thực hiện xong, chúng ta muốn một tiến trình (như một
tiến trình chủ) tiếp tục thực hiện phần việc tuần tự còn lại, còn những tiến trình khác
kết thúc. Khi đó chúng ta viết:
join_process (N, id)
Chỉ tiến trình tương ứng với giá trị id còn tiếp tục hoạt động, những tiến trình còn
lại kết thúc sau lời gọi hàm trên. Tuy nhiên, nếu ta đặt sau nó một câu lệnh nào đó thì
lệnh này sẽ không được thực hiện cho đến khi tất cả các tiến trình đều thực hiện câu
lệnh join_process(). Sau đó chỉ còn lại một tiến trình hoạt động, do vậy vấn đề xử lý
song song không xuất hiện mà xử lý tuần tự.
Vấn đề là khả năng các tiến trình được tạo lập có thể nhìn thấy dữ liệu của nhau
như thế nào? Một mặt một tiến trình có thể muốn giữ một phần dữ liệu cục bộ cho
riêng mình, không cho những tiến trình khác nhìn thấy/truy cập tới những dữ liệu đó.
Tìm hiểu tính toán song song Trang 17
Tính Toán Lưới
Mặt khác, nó cũng muốn trao đổi thông tin với các tiến trình khác. Do đó, xử lý vấn
đề che giấu hay chia sẻ thông tin như thế nào còn tuỳ thuộc vào mô hình mà chúng ta

áp dụng: dựa vào tiến trình hay luồng.
- Các tiến trình trong UNIX được sử dụng như các đơn vị tính toán độc lập, theo
mặc định, việc tính toán và cập nhật bộ nhớ của một tiến trình “không” sẽ không cho
các tiến trình khác nhìn thấy.
- Đối với các luồng, tất cả các thông tin, theo mặc định, là nhìn thấy được. Do vậy,
trong mô hình này cần phải cố gắng rất nhiều mới che giấu được thông tin khi cần
thiết.
Một số hàm điều phối vấn đề chia xẻ bộ nhớ.
Khi muốn sử dụng bộ nhớ chung, ta cần phải xin cấp phát bộ nhớ và sau khi sử
dụng xong phải giải phóng chúng. Người lập trình phải có nhiệm vụ giải phóng phần
bộ nhớ chia sẻ một khi chúng không còn sử dụng. Có hai hàm cơ bản được sử dụng ở
đây là:
- Hàm cấp phát bộ nhớ shared(m , &id): hàm này giống như malloc(), nhưng cấp
phát m byte bộ nhớ chia sẻ cho tiến trình id.
- Hàm giải phóng bộ nhớ free_shm(): giải phóng phần bộ nhớ đã được cấp phát.
3.3. Lập trình chia sẻ bộ nhớ dựa vào luồng
1. Trong mô hình lập trình song song dựa vào luồng, một tiến trình trình đơn
có thể có nhiều cách thực hiện đồng thời.
Tìm hiểu tính toán song song Trang 18
Tính Toán Lưới
2. Perhaps the most simple analogy that can be used to describe threads is the
concept of a single program that includes a number of subroutines: Lý luận đơn
giản nhất được dùng để mô tả các luồng là xét một chương trình chính a.out
bao gồm một số chương trình con, hình 4.1.2-1.
The main program a.out is scheduled to run by the native operating system. a.out
loads and acquires all of the necessary system and user resources to run. Hình 3.3
Chương trình chính a.out bao gồm một số chương trình con
- Chương trình chính a.out được lập lịch để chạy bằng hệ điều hành
gốc.
- Chương trình a.out tải và giành tất cả các tài nguyên cần thiết để

thực thi nhiệm vụ của nó.
- a.out performs some serial work, and then creates a number of tasks
(threads) that can be scheduled and run by the operating system concurrently.
Chương trình a.out thực hiện một số công việc tuần tự trước, và sau đó tạo ra
một số tác vụ (luồng), có thể được lập lịch và chạy đồng thời.
- Each thread has local data, but also, shares the entire resources of a.out .
Mỗi thread có dữ liệu địa phương riêng của nó, nhưng cũng có, dùng chung tài
nguyên của a.out. This saves the overhead associated with replicating a
program's resources for each thread. Điều này giúp tiết kiệm chi phí “vô ích”
liên quan với việc nhân bản các tài nguyên của chương trình để cung cấp cho
các thread. Each thread also benefits from a global memory view because it
shares the memory space of a.out . Mỗi thread cũng có lợi vì nó chia sẻ không
gian bộ nhớ của a.out.
Tìm hiểu tính toán song song Trang 19
Tính Toán Lưới
- A thread's work may best be described as a subroutine within the main
program.Công việc của một thread có thể được mô tả như là một chương trình
con trong chương trình chính. Một Any thread can execute any subroutine at
the same time as other threads.thread bất kỳ có thể thực hiện chương trình con
đồng thời với các thread khác.
- Threads communicate with each other through global memory (updating
address locations). This requires synchronization constructs to insure that more
than one thread is not updating the same global address at any time. Các
threads giao tiếp với nhau thông qua bộ nhớ toàn cục. Điều này đòi hỏi phải
xây dựng cấu trúc đồng bộ để bảo đảm rằng không có nhiều hơn một thread
đang cập nhật cùng địa chỉ toàn cục tại bất kỳ thời điểm nào.
- Threads can come and go, but a.out remains present to provide the
necessary shared resources until the application has completed. Các threads có
thể đến và đi, nhưng a.out vẫn còn hiện diện để cung cấp các tài nguyên được
chia sẻ cần thiết của nó cho đến khi ứng dụng đã hoàn thành.

- Threads are commonly associated with shared memory architectures and
operating systems. Các thread thường liên kết với kiến trúc bộ nhớ chia sẻ và
hệ điều hành.
Implementations: Ghi chú
- From a programming perspective, threads implementations commonly
comprise: Từ góc nhìn lập trình, triển khai Thread thường bao gồm:
1. A library of subroutines that are called from within parallel source code
Một thư viện của chương trình con được gọi là từ bên trong mã nguồn song
song.
2. A set of compiler directives imbedded in either serial or parallel source
code Một tập các chỉ thị nhúng trong trình biên dịch mã nguồn song song
hoặc tuần tự.
In both cases, the programmer is responsible for determining all parallelism.
Trong cả hai trường hợp, các lập trình viên có trách nhiệm xác định tất cả các
xử lý song song.
Tìm hiểu tính toán song song Trang 20
Tính Toán Lưới
- Threaded implementations are not new in computing.Thread không phải là
mới trong tính toán. Historically, hardware vendors have implemented their
own proprietary versions of threads. Trong lịch sử, các nhà cung cấp phần cứng
đã triển khai thực hiện các phiên bản của của họ về thread. Những bổ sung
These implementations differed substantially from each other making it
difficult for programmers to develop portable threaded applications.Những bổ
sung khác biệt nhau gây ra khó khăn cho các lập trình viên phát triển các ứng
dụng về threads.
- Các cố gắng để chuẩn hóa đã đưa ra hai bổ sung rất khác nhau của luồng là:
Các luồng POSIX và OpenMP (POSIX Threads and OpenMP).
• POSIX Threads POSIX Threads
1. Library based; requires parallel coding Dựa vào các thư viện; đòi hỏi
viết mã song song.

2. Specified by the IEEE POSIX 1003.1c standard (1995). Được xác định
bởi tiêu chuẩn IEEE POSIX 1003.1c (1995).
3. C Language only Chỉ sử dụng ngôn ngữ C
4. Commonly referred to as Pthreads. Thường được gọi là Pthreads.
5. Most hardware vendors now offer Pthreads in addition to their
proprietary threads implementations. Bây giờ hầu hết các nhà cung cấp
phần cứng, cung cấp các Pthreads để bảo đảm quyền sở hữu của họ.
6. Very explicit parallelism; requires significant programmer attention to
detail. Song song thực sự (tường minh) đòi hỏi lập trình viên rất chú ý thật
chi tiết.
• OpenMP OpenMP
1. Compiler directive based; can use serial code Dựa vào chương trình
biên dịch; có thể sử dụng mã tuần tự
2. Jointly defined and endorsed by a group of major computer hardware
and software vendors. The OpenMP Fortran API was released October 28,
1997. Cùng được xác định và xác nhận bởi một nhóm các phần cứng máy
tính lớn và các nhà cung cấp phần mềm. Các OpenMP Fortran API đã được
phát hành ngày 28 tháng 10 năm 1997. The C/C++ API was released in late
1998. C / C + + API đã được phát hành vào cuối năm 1998.
Tìm hiểu tính toán song song Trang 21
Tính Toán Lưới
3. Portable / multi-platform, including Unix and Windows NT platforms
Nền tảng của nó là cả Unix và Windows NT
4. Available in C/C++ and Fortran implementations Có thể sử dụng các bổ
sung của C / C + + và Fortran.
5. Có thể sử dụng rất dễ dàng và đơn giản-làm gia tăng tính song song
• Microsoft has its own implementation for threads, which is not related to the
UNIX POSIX standard or OpenMP. Microsoft đã có bổ sung thêm các threads,
mà không liên quan đến chuẩn UNIX POSIX hay OpenMP.
Thông tin chi tiết:

• POSIX Threads tutorial: computing.llnl.gov/tutorials/pthreads
• OpenMP tutorial: computing.llnl.gov/tutorials/openMP
3.4. Mô hình truyền thông báo (Message Passing Model)
• Các mô hình truyền thông báo có những đặc điểm sau
đây:
- Một tập các tác vụ có sử dụng bộ nhớ cục bộ riêng
của chúng trong thời gian tính toán. Nhiều công
việc có thể nằm trên cùng một máy vật lý cũng như qua một số máy tùy ý.
- Các tác vụ trao đổi dữ liệu thông qua truyền thông bằng cách gửi và nhận
thông báo.
- Chuyển giao dữ liệu thường đòi hỏi hợp tác thực hiện bởi quá trình. Ví dụ,
một hoạt động gửi phải kết hợp với thao tác nhận.
• Từ quan điểm lập trình, truyền thông báo nói chung bao gồm một thư viện các
chương trình con được nhúng trong mã nguồn. Lập trình viên có trách nhiệm
xác định tất cả vấn đề cần xử lý song song.
• Trong lịch sử, một loạt các thông báo qua các thư viện đã có sẵn từ những năm
1980. Những bổ sung khác làm công việc lập trình phát triển các ứng dụng.
• Năm 1992, diễn đàn MPI đã được thành lập với mục tiêu chính là thiết lập một
giao diện chuẩn cho việc thực hiện truyền các thông báo.
• Phần 1 của truyền thông báo (Message Passing Interface (MPI)) đã được phát
hành vào năm 1994. Phần 2 (MPI-2) đã được phát hành vào năm 1996. Cả hai
đặc tả MPI có sẵn trên web tại
Tìm hiểu tính toán song song Trang 22
Tính Toán Lưới
• MPI bây giờ là những tiêu chuẩn công nghiệp "de facto” để gửi đi, thay thế hầu
như tất cả các thông báo khác qua việc triển khai sử dụng cho công việc sản
xuất. Phần lớn, nếu không phải tất cả các nền tảng của tính toán song song phổ
biến cung cấp ít nhất một thực hiện MPI. Một vài trong số chúng cung cấp việc
thực hiện đầy đủ MPI.
• Đối với kiến trúc bộ nhớ chia sẻ, những bổ sung cho MPI không sử dụng mạng

lưới truyền thông cho công việc. Thay vào đó, chúng sử dụng chung bộ nhớ
(bộ nhớ nhân bản) vì lý do hiệu năng.
Thông tin chi tiết:
• MPI tutorial: computing.llnl.gov/tutorials/mpi
3.5. Mô hình dữ liệu song song (Data Parallel Model)
• Mô hình dữ liệu song song có các đặc tính sau:
- Hầu hết các công việc song song tập trung
vào việc thực hiện các thao tác trên một tập
dữ liệu. Tập dữ liệu thường tổ chức thành
một cấu trúc chung, như là bảng, mảng
hoặc khối.
- Một tập các tác vụ cùng làm công việc trên
cùng một cấu trúc dữ liệu giống nhau, tuy
nhiên, mỗi tác vụ hoạt động trên một phân vùng khác nhau của cùng một
cấu trúc dữ liệu.
- Các tác vụ thực hiện các thao tác giống nhau trên cùng một phân vùng
công việc của chúng, ví dụ, "cộng thêm 4 đến mọi phần tử mảng".
- Trên các kiến trúc bộ nhớ chia sẻ, tất cả các tác vụ có thể có quyền truy cập
vào cấu trúc dữ liệu thông qua bộ nhớ toàn cục. Trên các kiến trúc bộ nhớ
phân phối cấu trúc dữ liệu được phân ra và tồn tại như một "khối" trong bộ
nhớ cục bộ của từng tác vụ.
Chú ý
• Lập trình với các dữ liệu mô hình song song thường được thực hiện bằng cách
viết một chương trình với dữ liệu có cấu trúc song song. Các cấu trúc có thể
Tìm hiểu tính toán song song Trang 23
Tính Toán Lưới
gọi đến một thư viện chương trình con dữ liệu song song với hoặc, các chỉ thị
trình biên dịch được công nhận bởi một trình biên dịch dữ liệu song song.
• Fortran 90 và 95 (F90, F95): ISO / ANSI mở rộng tiêu chuẩn cho Fortran 77.
( />Thừa kế tất cả mọi thứ của Fortran 77, ngoài ra còn có một số bổ sung:

- Định dạng mã nguồn mới; các bổ sung vào tập ký tự
- Bổ sung cấu trúc chương trình và lệnh
- Bổ sung mới – các phương pháp và các đối
- Bổ sung con trỏ và cấp phát bộ nhớ động
- Bổ sung xử lý Array (mảng được coi như các đối tượng)
- Bổ sung chức năng nội tại mới chức năng đệ quy
- Nhiều tính năng mới khác
Các phần bổ sung sẵn sàng sử dụng cho các nền tảng song song.
( />• High Performance Fortran (HPF): Phần mở rộng để Fortran 90 để hỗ trợ lập
trình dữ liệu song song.
- Chứa mọi thứ trong Fortran 90
- các chỉ thị để cho trình biên dịch cần phân phối dữ liệu như thế nào
- Khẳng định việc cải thiện tính tối ưu của các mã được tạo ra
- Bổ sung các cấu trúc dữ liệu song song (bây giờ là một phần của Fortran 95)
Các phần bổ sung sẵn sàng sử dụng cho các nền tảng song song.
• Compiler Directives: Cho phép người lập trình xác định việc phân phối và sắp
xếp dữ liệu. Các bổ sung cho Fortran sẵn sàng sử dụng cho các nền tảng song
song
phổ biến nhất các
• Thực hiện phân phối bộ nhớ của mô hình này thường có trình biên dịch chuyển
đổi chương trình vào mã tiêu chuẩn với các cuộc gọi đến một thông báo qua
thư viện (KH & ĐT thường) để phân phối các dữ liệu cho tất cả các quá trình.
Tất cả các thông báo được thực hiện qua invisibly để các lập trình viên.
• Mô hình khác
Tìm hiểu tính toán song song Trang 24
Tính Toán Lưới
Các mô hình lập trình song song bên cạnh những cái trước đây đã đề cập chắc
chắn tồn tại, và sẽ tiếp tục tiến triển cùng với sự thay đổi của thế giới phần cứng và
phần mềm của máy tính. Chỉ có ba trong số những mô hình phổ biến hơn được đề
cập ở đây.

3.6. Mô hình hỗn hợp (Hybrid)
- Trong mô hình này, có hai hay
nhiều mô hình lập trình song song
nào đó được kết hợp lại.
- Hiện nay, một ví dụ phổ biến
của một mô hình lai là sự kết hợp
của mô hình truyền thông báo
(MPI) với mô hình hoặc mô hình
tiến trình (POSIX threads) hoặc mô
hình bộ nhớ được chia sẻ (OpenMP) Thread. Mô hình lai này dẫn đến nhu cầu
tăng môi trường phần cứng chung cho các máy SMP được kết mạng.
- Một ví dụ khác của mô hình lai là sự kết hợp dữ liệu song song với truyền
thông báo. Như đã đề cập ở phần mô hình dữ liệu song song trước đó, các bổ sung dữ
liệu song song (F90, HPF) trên các kiến trúc bộ nhớ phân phối sử dụng truyền thông
báo để truyền dữ liệu giữa các tác vụ, làm rõ ràng (minh bạch) hơn cho lập trình viên.
Đơn chương trình - Đa dữ liệu (SPMD):
- SPMD thực sự là một mô hình lập trình "bậc cao" có thể được xây dựng
dựa trên tổ hợp nào đó của các mô hình lập trình song song đã đề cập trước
đó.
- Một đơn chương trình được thực hiện đồng thời bởi tất cả các tác vụ .
- Tại bất kỳ thời điểm nào, các tác vụ cũng có thể cùng thực hiện các chỉ thị
như nhau hay khác nhau trong cùng một chương trình.
- Các chương trình SPMD thường có những thứ cần thiết được lập trình trong
đó để cho phép các tác vụ khác nhau có thể rẽ nhánh hoặc thực hiện có điều
kiện chỉ những phần của chương trình chúng được thiết kế để thực thi. Đó
Tìm hiểu tính toán song song Trang 25