®¹i häc quèc gia hµ néi
tr-êng ®¹i häc khoa häc tù nhiªn
Ng« thÞ nh¹n
ThiÕt kÕ nh©n ma trËn th-a víi vÐct¬ trong
tÝnh to¸n song song vµ øng dông
luËn v¨n th¹c sÜ khoa häc
Hµ Néi - N¨m 2011
1
®¹i häc quèc gia hµ néi
tr-êng ®¹i häc khoa häc tù nhiªn
Ng« thÞ nh¹n
ThiÕt kÕ nh©n ma trËn th-a víi vÐct¬ trong
tÝnh to¸n song song vµ øng dông
Chuyªn ngµnh: B¶o ®¶m to¸n häc cho m¸y tÝnh vµ hÖ thèng tÝnh to¸n
M· sè: 60 46 35
luËn v¨n th¹c sÜ khoa häc
ng-êi h-íng dÉn khoa häc:
nguyÔn h÷u ®iÓn
Hµ Néi - N¨m 2011
2
MỤC LỤC
Trang
Trang phụ bìa .........................................................................................................................
Mục lục ...................................................................................................................................
Danh mục các ký hiệu ............................................................................................................
Danh mục các bảng ................................................................................................................
Danh mục các hình vẽ ............................................................................................................
Danh mục các thuật toán ........................................................................................................
MỞ ĐẦU .............................................................................................................................. 1
Chƣơng 1 - TỔNG QUAN VỀ XỬ LÝ SONG SONG .................................................. 12
1.1 Hệ thống song song.................................................................................................. 12
1.1.1 Khái niệm xử lý song song ............................................................................... 12
1.1.2 Kiến trúc xử lý song song ................................................................................. 12
1.2 Các thành phần của máy tính song song .................................................................. 15
1.2.1 Bộ nhớ .............................................................................................................. 15
1.2.2 Chương trình dịch và các hệ điều hành ............................................................ 17
1.3 Các mô hình lập trình song song ............................................................................. 19
1.3.1 Mô hình chia sẻ bộ nhớ .................................................................................... 19
1.3.2 Mô hình tuyến ................................................................................................... 20
1.3.3 Mô hình song song dữ liệu ............................................................................... 20
1.3.4 Mô hình truyền thông điệp ............................................................................... 21
1.4 Nguyên lý thiết kế thuật toán song song .................................................................. 22
1.4.1 Định nghĩa thuật toán song song ...................................................................... 22
1.4.2 Các giai đoạn của thiết kế thuật toán song song............................................... 22
4
1.4.3 Đánh giá độ phức tạp của thuật toán song song ............................................... 25
1.5 Lập trình song song với MPI ................................................................................... 27
1.5.1 Giao diện truyền thông điệp - MPI ................................................................... 27
1.5.2 Giới thiệu gói CCP của Microsoft .................................................................... 31
1.5.3 Lập trình MPI với VS.NET .............................................................................. 34
1.6 Kiến trúc cụm máy tính ........................................................................................... 35
Chƣơng 2 – THUẬT TOÁN SONG SONG NHÂN MA TRẬN THƢA VỚI VÉCTƠ
............................................................................................................................................ 38
2.1 Ma trận thưa ............................................................................................................. 38
2.1.1 Đặt vấn đề ......................................................................................................... 38
2.1.2 Cấu trúc dữ liệu cho ma trận thưa .................................................................... 43
2.2 Nhân ma trận thưa với véc tơ song song ................................................................. 48
2.2.1 Thuật toán song song ........................................................................................ 48
2.2.2 Phân phối ma trận ............................................................................................. 53
2.2.3 Phân phối véc tơ ............................................................................................... 60
2.2.3.1 Cận dưới địa phương cho số truyền thông cực đại ................................... 62
2.2.3.2 Phân phối các véc tơ độc lập ..................................................................... 71
2.2.3.3 Phân phối các véc tơ đồng thời ................................................................. 78
Chƣơng 3 – KẾT QUẢ THỰC NGHIỆM ..................................................................... 83
3.1 Bộ dữ liệu ................................................................................................................. 83
3.2 Kết quả ..................................................................................................................... 83
KẾT LUẬN ........................................................................................................................ 93
TÀI LIỆU THAM KHẢO .................................................................................................. 94
PHỤ LỤC ........................................................................................................................... 96
5
BẢNG THUẬT NGỮ VIẾT TẮT
Thuật ngữ
CCS
Tiếng Anh
Compressed Column Storage
Nghĩa tiếng Việt
Lưu trữ nén cột
CRS
Compressed Row Storage
Lưu trữ nén dòng
CPU
Central Processing Unit
Bộ xử lý trung tâm
HPC
High Performance Computing
Tính toán/máy tính hiệu năng cao
ICRS
Incremental Compressed Row
Storage
Lưu trữ nén dòng có gia số
JDS
Jagged Diagonal Storage
Lưu trữ đường chéo răng cưa
Multi Instruction Stream, Multi
Data Stream
Multi Instruction Stream, Single
Data Stream
Đa luồng lệnh, đa luồng dữ liệu
MPI
Message Passing Interface
Giao diện truyền thông điệp
NUMA
Non-Uniform Memory Access
Truy cập bộ nhớ không đồng thời
PRAM
Parallel Random Access Machine
Máy truy trập ngẫu nhiên song song
Đơn luồng lệnh, đa luồng dữ liệu
TCP
Single Instruction Stream, Multi
Data Stream
Single Instruction Stream, Single
Data Stream
Transmission Control Protocol
UDP
User Datagram Protocol
Giao thức gói người dùng
UMA
Uniform Memory Access
Truy cập bộ nhớ đồng thời
WS
Workstation
Máy trạm
WSC
Workstation Cluster
Cụm máy trạm
MIMD
MISD
SIMD
SISD
6
Đa luồng lệnh, đơn luồng dữ liệu
Đơn luồng lệnh, đơn luồng dữ liệu
Giao thức điều khiển truyền thông
DANH MỤC CÁC BẢNG
Trang
Bảng 3.1 Các file dữ liệu ma trận ...................................................................................... 83
Bảng 3.2 Thống kê cho ma trận bcsstk13 .......................................................................... 85
Bảng 3.3 Thống kê cho ma trận lp_cycle ........................................................................... 86
Bảng 3.4 Thống kê cho ma trận onetone2 ......................................................................... 87
Bảng 3.5 Thống kê cho ma trận epb2 ................................................................................ 88
Bảng 3.7 Thống kê cho ma trận random20k ...................................................................... 90
7
DANH MỤC HÌNH VẼ
Trang
Hình 1.1 Phân cấp hệ thống bộ nhớ ................................................................................... 15
Hình 1.2 Mô hình tuyến ..................................................................................................... 20
Hình 1.3 Các giai đoạn của quá trình thiết kế thuật toán ................................................... 23
Hình 1.4 Luật Amdahl........................................................................................................ 27
Hình 1.5 Mô phỏng kiến trúc một cụm tính toán ............................................................... 32
Hình 1.6 Mô hình kiến trúc lập lịch ................................................................................... 33
Hình 2.1 Mô phỏng động lực học bằng ma trận lực thưa .................................................. 40
Hình 2.2 Minh hoạ nhân ma trận thưa với véc tơ song song ............................................. 49
Hình 2.3 Minh hoạ truyền thông nhân ma trận thưa với véc tơ ......................................... 51
Hình 2.4 Phân phối của ma trận impcol_b ......................................................................... 58
Hình 3.1 Hình dạng thưa của ma trận bcsstk13 ................................................................. 84
Hình 3.2 Hình dạng thưa của ma trận lp_cycle .................................................................. 85
Hình 3.3 Hình dạng thưa của ma trận onetone2................................................................. 86
Hình 3.4 Hình dạng thưa của ma trận epb2 ....................................................................... 87
Hình 3.5 Hình dạng thưa của ma trận nasa2910 ................................................................ 88
Hình 3.6 Phân phối LA cho random20k với P = 4 ............................................................ 91
Hình 3.7 Phân phối LA cho lp_cycle với P = 4 ................................................................. 92
8
DANH MỤC CÁC THUẬT TOÁN
Trang
Thuật toán 2.1 Thuật toán nhân ma trận thưa với véc tơ tuần tự ....................................... 39
Thuật toán 2.2 Thuật toán tuần tự nhân ma trận thưa với véc tơ sử dụng CRS ................. 45
Thuật toán 2.3 Thuật toán tuần tự nhân ma trận thưa với véc tơ sử dụng ICRS ............... 46
Thuật toán 2.4 Nhân ma trận thưa với véc tơ song song ................................................... 50
Thuật toán 2.5 Thuật toán Mondrian phân hoạch ma trận thưa ......................................... 59
Thuật toán 2.6 Xây dựng cận dưới địa phương của bộ xử lý s .......................................... 64
Thuật toán 2.7 Chuyển tập C thành C 0,..., C 1...................................................... 66
Thuật toán 2.8 Tạo cận dưới địa phương tổng quát cho bộ xử lý s ................................... 69
Thuật toán 2.9 Thuật toán biên địa phương (LA) .............................................................. 73
Thuật toán 2.10 Thuật toán phân phối véc tơ đồng thời (LAvu)......................................... 80
9
MỞ ĐẦU
Nhân loại ngày nay đang chứng kiến sự phát triển mạnh mẽ của ngành Công nghệ
thông tin, một trong những ngành mũi nhọn của nhiều quốc gia trên thế giới. Sự phát triển
vượt bậc của nó là kết quả tất yếu của sự phát triển các thiết bị phần cứng cũng như phần
mềm tiện ích. Từ những máy tính đơn giản, tốc độ xử lý chậm, và chỉ được sử dụng trong
một số lĩnh vực kỹ thuật nhất định, thì ngày nay chúng đã có khả năng tính toán và tốc độ
xử lý vượt trội trở thành một công cụ không thể thiếu trong mọi lĩnh vực của đời sống.
Những máy tính ra đời đầu tiên, do hạn chế về tốc độ xử lý và cơ chế vào ra dữ liệu
nên việc lập trình rất khó khăn. Điều này làm cho máy tính không có khả năng sử dụng dễ
dàng và phổ cập, nó chỉ được ứng dụng trong một số lĩnh vực khoa học đặc biệt.
Ngày nay, cùng với sự phát triển mạnh mẽ của thiết bị lưu trữ, bộ nhớ, tốc độ xử lý
và các thiết bị ngoại vi,… máy tính đã trở nên thân thiện hơn với người sử dụng, cũng
như tốc độ tính toán nhanh hơn rất nhiều. Nhờ đó mà rất nhiều bài toán lớn đã có khả
năng thực thi và nhiều ứng dụng được đưa ra.
Tuy nhiên, một thực tế là còn rất nhiều vấn đề lớn với số lượng cần tính toán khổng
lồ mà một máy tính thông thường không thể giải quyết được. Vào thập kỷ 70, các nhà
khoa học đã đưa ra ý tưởng về cấu trúc song song nhằm kết hợp sức mạnh của nhiều bộ
xử lý trên một máy tính, hoặc kết hợp nhiều máy tính với nhau thông qua mạng máy tính
tạo thành máy song song ảo. Ngoài việc tính nhanh, các máy tính song song có độ an
toàn cao hơn máy tính đơn, khi một vài bộ xử lý hỏng thì máy tính song song vẫn có thể
hoạt động được trong khi máy tính đơn thì không làm được điều đó.
Hiện nay trên thế giới đã có những máy tính song song chứa đến hàng nghìn bộ xử
lý. Để khai thác tiềm năng và sức mạnh của máy tính song song, cùng với việc thiết kế
kiến trúc song song ta còn phải nghiên cứu những vấn đề quan trọng khác như hệ điều
hành hỗ trợ xử lý song song, các ngôn ngữ lập trình và thuật toán song song.
Việc nghiên cứu thiết kế các máy tính song song, và các thuật toán song song cũng
như các ngôn ngữ lập trình hỗ trợ lập trình song song bắt đầu được quan tâm từ những
10
năm 70, cho đến nay các ứng dụng của chúng đã lan rộng khắp các lĩnh vực của đời sống
như đánh giá khả năng rủi ro về tài chính: dùng để mô hình hoá các xu hướng trên thị
trường… Hỗ trợ quyết định như phân tích thị trường, dự báo thời tiết… Trí tuệ nhân tạo
như thiết kế robot… Xử lý ảnh ứng dụng trong công nghệ nhận dạng… Điều khiển tự
động… Trong đó bài toán có liên quan tới ma trận thưa đóng một vai trò quan trọng, hay
gặp trong các lời giải lặp của hệ phương trình tuyến tính, hệ phương trình giá trị riêng, …
Do vậy việc nghiên cứu các thuật toán ma trận thưa, đặc biệt là các thuật toán song song
trên ma trận thưa là rất cần thiết.
Trong phạm vi luận văn này trình bày ba phần chính, Chƣơng 1 trình bày tổng quan
về xử lý song song, thuật toán song song và giới thiệu lập trình song song với MPI sử
dụng Visual của Microsoft; Chƣơng 2 trình bày về các thuật toán thiết kế cho nhân ma
trận thưa với véc tơ song song; Chƣơng 3 trình bày một số kết quả thực nghiệm trên một
số bộ dữ liệu cho chương trình nhân ma trận thưa với véc tơ song song. Với thời gian tiếp
cận vấn đề và lượng thông tin còn hạn chế, luận văn còn nhiều thiếu sót. Tôi rất mong
nhận được sự góp ý của các thầy, các cô và các anh/chị để có thể tiếp tục phát triển đề tài
đã nghiên cứu và đạt được kết quả.
11
Chƣơng 1 - TỔNG QUAN VỀ XỬ LÝ SONG SONG
1.1 Hệ thống song song
1.1.1 Khái niệm 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 vấn đề, thường được thực hiện trên những hệ thống có
nhiều bộ xử lý [1].
Máy tính song song là tập hợp các bộ xử lý, thường cùng một loại, kết nối với nhau
theo một kiến trúc xác định để cùng hợp tác hoạt động và trao đổi dữ liệu.
1.1.2 Kiến trúc xử lý song song
a) Máy tính song song phân chia theo cách thức thực hiện chương trình
Có nhiều cách để phân loại máy tính song song, người ta thường sử dụng cách phân
loại máy tính song song của M.J. Flynn (1966) [13]. Cách phân loại này dựa vào sự phân
phối dữ liệu và phân phối các lệnh trên mỗi bộ xử lý.
Luồng lệnh (instruction stream) là một dãy các lệnh từ một đơn vị điều khiển hướng
đến một hay nhiều bộ xử lý.
Luồng dữ liệu (data stream) là một dãy dữ liệu từ một vùng nhớ hướng đến một bộ
xử lý hoặc từ một bộ xử lý hướng đến một vùng nhớ.
Bốn cấu trúc máy tính song song được phân loại bởi Flynn đó là:
Mô hình SISD (đơn luồng lệnh, đơn luồng dữ liệu)
Máy tính loại 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 khi xử lý tuần tự 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. Mô hình SISD còn được gọi là SPSD
12
- đơn chương trình và đơn luồng dữ liệu. Đây chính là mô hình máy tính truyền thống
kiểu von Neumann 1.
Mô hình SIMD (đơn luồng lệnh, đa luồng dữ liệu)
Máy tính loại 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 tử
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. Đây là kiểu tính toán lặp lại các đơn vị số
học trong CPU, cho phép những đơn vị khác nhau thực hiện trên những toán hạng khác
nhau, nhưng thực hiện cùng một lệnh. Máy tính SIMD có thể hỗ trợ xử lý kiểu véc tơ,
trong đó có thể gán các phần tử của véc tơ cho các phần tử xử lý để tính toán đồng thời.
Máy tính véc tơ và các bộ xử lý mảng là mô hình chủ yếu thuộc loại này. Mô hình SIMD
còn được gọi là SPMD - đơn chương trình và đa luồng dữ liệu. Đây chính là mô hình máy
tính phổ biến có trên thị trường như: ILLIAC IV, DAP và Connection Machine CM-2.
Mô hình MISD (đa luồng lệnh, đơn luồng dữ liệu)
Máy tính 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, nên còn được gọi là MPSD - đa chương trình, đơn luồng dữ liệu. Kiến trúc kiểu
này có thể chia thành hai nhóm:
-
Lớp các máy tính yêu cầu những đơn vị xử lý khác nhau có thể nhận được những
chỉ lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. Đây là kiến trúc khó
và hiện nay chưa có loại máy tính nào được sản xuất theo loại này.
-
Lớp các máy tính có các luồng dữ liệu được chuyển tuần tự theo dãy các CPU liên
tiếp. Đây là loại kiến trúc hình ống thực hiện xử lý theo vector thông qua một dãy
các bước, trong đó mỗi bước thực hiện một chức năng và sau đó chuyển kết quả
1
Mô hình máy tính do von Neumann (1903-1957) đưa ra, là kiến trúc máy tính phổ biến nhất hiện nay, với đặc
trưng là các lệnh được thực hiện một cách tuần tự, mỗi thời điểm chỉ thực hiện được một lệnh.
13
cho đơn vị xử lý thực hiện bước tiếp theo. Hoạt động của máy tính theo kiến trúc
loại này giống như hệ tuần hoàn nên còn được gọi là hệ tâm thu.
Mô hình MIMD (đa luồng lệnh, đa luồng dữ liệu)
Máy tính loại MIMD còn 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 được
bộ nhớ chung (toàn cục) khi cần, do vậy giảm thiểu được sự trao đổi giữa các bộ xử lý
trong hệ thống.
Đây là 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 sản xuất theo kiến trúc này như: BBN Butterfly, Aliant FX,
iSPC của Intel, …
b) Máy tính song song phân chia theo kiến trúc phần cứng
Kiến trúc máy tính là một phần rất quan trọng quyết định hiệu quả của công việc, đối
với một máy tính song song có một số loại kiến trúc phần cứng cơ bản sau:
Máy tính song song với bộ nhớ chia sẻ
Trong máy tính song song với bộ nhớ chia sẻ, bộ nhớ là chung cho tất cả các bộ xử
lý. Bộ nhớ được phân thành các mô đun nhớ, mỗi mô đun này có kênh vào ra riêng. Các
mô đun nhớ này được nối với bộ xử lý trên mỗi CPU thông qua bus hoặc mạng kết nối
nội bộ.
Trong mô hình này, các CPU được nối đến ngân hàng bộ nhớ trên cùng một bus, với
cùng tốc độ. Các bộ xử lý khi hoạt động cùng chia sẻ dữ liệu ghi trong bộ nhớ chung. Mỗi
bộ xử lý đọc dữ liệu mà nó cần trong bộ nhớ chung, xử lý chúng, rồi lại ghi kết quả vào
bộ nhớ.
Vì các bộ xử lý dùng chung bộ nhớ, có xuất hiện xung đột truy cập, vì vậy loại kết
nối dùng trong mô hình này là: bus hoặc crossbar, với bus thì các bộ xử lý được tổ chức
liên kết với nhau theo dãy, đây là dạng liên kết đơn giản.
14
Máy tính song song với bộ nhớ phân tán
Trong mô hình này mỗi CPU có bộ nhớ riêng, mỗi CPU truy nhập đến bộ nhớ riêng
của mình với tốc độ nhanh, còn truy cập đến bộ nhớ của CPU khác thì chậm hơn.
Trong mô hình này mỗi bộ xử lý ngoài việc sử dụng dữ liệu trong bộ nhớ riêng, nó
còn có thể đọc trên một hoặc nhiều kênh truyền thông từ các bộ xử lý khác mà nó cần,
thực hiện xử lý, rồi lại có thể truyền kết quả cho bộ xử lý khác. Do đó thới gian thực hiện
trong kiến trúc phụ thuộc vào thời gian di chuyển dữ liệu giữa các bộ xử lý.
Nhìn chung mạng liên kết không cho phép kết nối tất cả các CPU với nhau, mỗi
CPU chỉ được kết nối với một số CPU khác.
Mô hình hỗn hợp
Mô hình này là sự kết hợp giữa các mô hình đã trình bày ở trên, nó dung hoà được
các ưu nhược điểm của hai kiến trúc trên, các bộ xử lý được liên kết với nhau thông qua
một mạng giao tiếp tạo thành một hệ thống liên cụm, mỗi cụm có kiến trúc dùng chung
(chia sẻ).
1.2 Các thành phần của máy tính song song
1.2.1 Bộ nhớ
Một trong các thành phần quan trọng nhất của kiến trúc máy tính là bộ nhớ. Bộ nhớ
thường được chia thành n mức như hình 1.1 [1].
BXL
Mức cao nhất
Bộ nhớ mức 1
Nhỏ, nhanh và đắt
Bộ nhớ mức 2
Mức thấp nhất
Bộ nhớ mức n
Lớn, chậm và rẻ
Hình 1.1 Phân cấp hệ thống bộ nhớ
15
Bộ nhớ mức 1 là mức bộ nhớ cao nhất có dung lượng nhỏ nhất, nhanh và đắt nhất,
thường gắn chặt với mỗi bộ xử lý thành bộ nhớ cục bộ. Bộ nhớ mức 2 thường nhỏ hơn,
chậm hơn và rẻ hơn mức 1, …
Về nguyên tắc, dữ liệu được chuyển đổi giữa các mức lân cận của các bộ nhớ và
hoàn toàn được điều khiển bởi bộ nhớ mức 1. Về lý thuyết, trong cấu trúc phân cấp bộ
nhớ, tốc độ truy cập bộ nhớ trung bình gần bằng tốc độ truy cập ở mức cao (mức 1),
nhưng chi phí của các đơn vị nhớ trung bình lại gần với chi phí của bộ nhớ ở mức thấp
nhất (mức n).
Sau đây chúng ta xét một số mô hình bộ nhớ của các máy tính song song:
Bộ nhớ kết hợp
Bộ nhớ kết hợp (AM – Associative Memory) bao gồm các ô nhớ và logic kết hợp.
Mỗi ô nhớ của AM có 4 đầu vào và hai đầu ra.
Tất cả các bộ nhớ AM được tổ chức thành các từ và được xây dựng thành mảng các
ô giống nhau. Mỗi ô trong số m n ô nhớ và nó có một mạch vòng để so sánh đối số với
giá trị được lưu trữ trong các ô nhớ, đồng thời chỉ ra kết quả khi đối sánh thành công. Hệ
thống có thanh ghi lưu trữ đối số, một thanh ghi đánh dấu những trường của mỗi từ mà bộ
nhớ cần so sánh và thanh ghi đối sánh (các bít đối sánh) chỉ ra những từ tìm thấy.
Mô hình bộ nhớ truy cập ngẫu nhiên song song
Mô hình tính toán song song PRAM bao gồm bộ nhớ chung RAM với m vùng nhớ
đủ lớn để chia sẻ cho p bộ xử lý. Bộ nhớ chung được sử dụng để lưu trữ dữ liệu và là
vùng nhớ để trao đổi giữa các bộ xử lý.
Có một số cách khác nhau để các bộ xử lý có thể đọc/ghi dữ liệu, đó là:
-
Concurrent Read (CR): nhiều bộ xử lý có thể đọc đồng thời cùng một ô nhớ.
-
Exlusive Read (ER): p bộ xử lý đọc được p vùng nhớ khác nhau. Mỗi bộ xử lý đọc
được chính xác một vùng nhớ và mỗi vùng nhớ được đọc bởi một bộ xử lý.
16
-
Concurrent Write (CW): cùng một thời điểm cho phép nhiều bộ xử lý ghi vào cùng
một vùng nhớ.
-
Exlusive Write (EW): p bộ xử lý ghi được vào p vùng nhớ khác nhau. Mỗi bộ xử lý
ghi được vào chính xác một vùng nhớ và ngược lại.
Dễ nhận thấy rằng: ER, EW là trường hợp đăc biệt của CR và CW. Trong đó, CW là
cần phải chú ý nhất và được phân nhỏ thành các loại như sau:
-
Ghi đồng thời có ưu tiên (Priority CW): các bộ xử lý được gắn mức ưu tiên và khi
có nhiều bộ xử lý muốn ghi dữ liệu vào một vùng nhớ thì ưu tiên cho bộ xử lý có
mức ưu tiên cao nhất. Các mức ưu tiên có thể gắn tĩnh hoặc động theo những qui
tắc được xác định khi thực hiện.
-
Ghi đồng thời chung (Common CW): tất cả các bộ xử lý được phép ghi vào cùng
một vùng nhớ chỉ khi chúng ghi cùng một giá trị. Trong trường hợp này, một bộ
xử lý được chọn để ghi dữ liệu đó.
-
Ghi đồng thời tự do (Arbitrary CW): một số bộ xử lý muốn ghi dữ liệu đồng thời
vào một vùng nhớ, nhưng chỉ một bộ xử lý được phép thay đổi giá trị của vùng
nhớ đó. Trong trường hợp này, chúng ta phải chỉ ra cách để lựa chọn bộ xử lý thực
hiện.
-
Ghi đồng thời ngẫu nhiên (Random CW): bộ xử lý được lựa chọn để ghi dữ liệu là
ngẫu nhiên.
-
Ghi đồng thời phối hợp (Combining CW): tất cả các dữ liệu mà các bộ xử lý định
ghi đồng thời vào bộ nhớ được tổ hợp lại thành một giá trị. Giá trị này sẽ được ghi
vào bộ nhớ đó.
1.2.2 Chƣơng trình dịch và các hệ điều hành
Chương trình dịch
Chương trình được viết bằng các ngôn ngữ lập trình truyền thống thì phải được dịch
sang dạng mã mà phần cứng hiểu được nó, đó là ngôn ngữ máy. Chương trình dịch và
17
chương trình thông dịch được sử dụng để thực hiện các chuyển đổi đó. Có ba cách tiếp
cận để xây dựng chương trình dịch cho các máy tính song song:
-
Phân hoạch và lập lịch khi chạy: Cách tiếp cận này khá phù hợp với một số ứng
dụng thực tế. Tuy nhiên, nó có hạn chế là việc lập lịch và phân hoạch được thực
hiện lúc chạy chương trình sẽ làm giảm hiệu suất của hệ thống.
-
Phân hoạch khi biên dịch và lập lịch khi chạy: Đây là mô hình chung để xây dựng
chương trình dịch cho đa bộ xử lý. Lập lịch phân việc được thực hiện lúc chương
trình chạy, nhưng việc phân hoạch công việc thành các khối được thực hiện bởi
người lập trình và chương trình dịch. Theo cách tiếp cận này, sự đồng bộ hóa các
tiến trình và truyền thông phải được xác định rõ trong hệ thống.
-
Phân hoạch và lập lịch khi biên dịch: Phân hoạch công việc và lập lịch được thực
hiện ở giai đoạn dịch chương trình. Do vậy, chương trình dịch loại này đòi hỏi phải
rất hoàn hảo. Nhưng điều này khá khó, bởi vì rất khó đánh giá được thời gian thực
hiện chương trình, đặc biệt là vấn đề lập lịch trước sẽ không thể thực hiện tối ưu
được.
Hệ điều hành
Hệ điều hành là một chương trình làm nhiệm vụ phối hợp các hoạt động của máy
tính. Hệ điều hành thực hiện các chức năng chính sau:
-
Khởi động hệ thống.
-
Phân đoạn chương trình và lập lịch cho các tiến trình.
-
Trao đổi và đồng bộ hóa các tiến trình.
-
Quản lý và điều hành hệ thống, v.v.
Nhiệm vụ chính của hệ điều hành đa bộ xử lý là tích hợp các tài nguyên tính toán và
các bộ xử lý trao đổi với nhau thông qua mạng liên kết để tạo thành một hệ thống nhất
làm việc cho hiệu quả.
Nói chung, hệ điều hành đa bộ xử lý cũng giống như hệ điều hành tập trung, phải
chứa các thành phần quản trị hệ thống như: quản trị các tiến trình, quản trị bộ nhớ, quản
18
trị tài nguyên và quản trị các tệp. Người ta phân các hệ điều hành cho các máy tính song
song thành ba loại:
-
Những hệ điều hành mở rộng và phát triển từ những hệ đơn bộ xử lý để chạy được
trên những kiến trúc song song, như VMS, UNIX.
-
Những hệ điều hành được thiết kế riêng cho những kiến trúc song song, như: hệ
Hydra cho C.mmp, Medusa cho Cm*, cả hai đều được phát triển ở CarnegieMellon University.
-
Những hệ điều hành tổng hợp được thiết kế để cài đặt được trên những kiến trúc
song song khác nhau, ví dụ MACH Multiprocessor.
Hầu hết các phiên bản mới của hệ điều hành UNIX đều thực hiện trên các hệ đa bộ
xử lý. Trong số đó có thể kể ra như Solaris của Sun, HP UNIX của HP, Digital UNIX của
Digital, AIX của IBM, … Những hệ điều hành mới nhất như Window NT của Microsoft
cũng được thiết kế để chạy trên những hệ thống đa bộ xử lý.
1.3 Các mô hình lập trình song song
1.3.1 Mô hình chia sẻ bộ nhớ
Trong mô hình này, các bộ xử lý đều được kết nối tới một bộ nhớ chung, thông qua
các phương tiện phần cứng hoặc phần mềm. Có các cơ chế khác nhau như
khóa/semaphores sử dụng để kiểm soát truy cập vào bộ nhớ chung đó.
Điểm bất lợi của mô hình này là khả năng phát triển tới 32 bộ xử lý là rất khó, và mô
hình bộ nhớ chia sẻ là ít linh hoạt hơn mô hình bộ nhớ phân tán.
Dạng đường bus
Các máy MIMD với bộ nhớ chia sẻ có các bộ xử lý cùng chia sẻ một vùng nhớ tập
trung chung. Nói đơn giản nhất, mọi bộ xử lý đều kết nối bằng một đường bus tới bộ nhớ.
Cách kết nối này gọi là dựa trên đường bus, và có quá nhiều xung đột trên đó.
Dạng phân cấp
Các máy MIMD với bộ nhớ chia sẻ phân cấp sử dụng một hệ thống phân chia các
bus cho phép các bộ xử lý truy cập tới các bộ nhớ của những bộ xử lý khác. Các bộ xử lý
19
ở các vùng khác nhau có thể giao tiếp thông qua các nút nối. Các bus hỗ trợ giao tiếp giữa
các máy. Với kiến trúc này, các máy có thể hỗ trợ tới hàng ngàn bộ xử lý.
1.3.2 Mô hình tuyến
Trong mô hình tuyến (hay mô hình luồng) của lập trình song song, một tiến trình
đơn có thể bao gồm nhiều tuyến thực hiện đồng thời, minh họa hình 1.2. Mỗi luồng có dữ
liệu cục bộ, nhưng đồng thời chia sẻ toàn bộ tài nguyên của tiến trình chủ. Điều này tiết
kiệm các chi phí liên quan đến việc sao chép các tài nguyên của chương trình cho mỗi
tuyến.
Có hai chuẩn triển khai luồng đó là: POSIX Threads và OpenMP. Microsoft có triển
khai luồng riêng, không liên quan đến các chuẩn UNIX POSIX hay OpenMP.
Hình 1.2 Mô hình tuyến
Hình 1,2 mô tả chương trình trong tệp a.out, chương trình khởi động chạy như một
tiến trình đơn, sau đó các tiến trình được khởi tạo để chạy đồng thời, các tiến trình có thể
sử dụng tài nguyên của a.out và có thể kết thúc riêng rẽ.
1.3.3 Mô hình song song dữ liệu
Mô hình song song dữ liệu hay gặp khi phần lớn công việc song song tập trung vào
việc thực hiện các tác vụ trên một tập dữ liệu. Tập dữ liệu thường được tổ chức thành một
cấu trúc thông dụng, như mảng hay khối lập phương. Một tập các tác nhiệm làm việc trên
cùng một cấu trúc dữ liệu, tuy nhiên, mỗi tác nhiệm làm việc trên một phân vùng khác
20
nhau của cùng một cấu trúc dữ liệu. Các tác nhiệm thực hiện cùng một tác vụ trên phân
vùng làm việc của chúng.
Trên các kiến trúc bộ nhớ chia sẻ, tất cả các tác nhiệm có thể 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 tán, cấu trúc dữ liệu
được chia ra và được đặt như là các phần trong bộ nhớ cục bộ của mỗi tác nhiệm.
1.3.4 Mô hình truyền thông điệp
Trong mô hình truyền thông điệp, các tiến trình chia sẻ với nhau qua các kênh truyền
thông. Kênh là khái niệm trừu tượng của đường truyền thông vật lý giữa các tiến trình.
Các kênh được truy cập bởi hai phương thức gửi và nhận thông điệp: send() và receive().
Khi một tiến trình gửi đi một thông điệp vào kênh truyền và có một tiến trình khác yêu
cầu nhận thông điệp đó thì diễn ra sự trao đổi dữ liệu và sự trao đổi được hoàn tất khi dữ
liệu đã được chuyển từ nơi gửi tới nơi nhận.
Mô hình truyền thông điệp có các đặc điểm sau:
- Một tập các tác nhiệm sử dụng bộ nhớ cục bộ riêng của chúng trong quá trình tính
toán. Nhiều tác nhiệm có thể nằm trên cùng một máy cũng như nằm trên nhiều
máy.
- Các tác nhiệm vụ trao đổi dữ liệu thông qua truyền thông bằng cách gửi và nhận
các thông điệp.
- Truyền dữ liệu thường đòi hỏi sự hợp tác giữa các tiến trình. Ví dụ, một tác vụ gửi
thông điệp phải có một tác vụ nhận thông điệp tương ứng.
Có hai mô hình truyền thông điệp cơ bản là:
- Truyền thông điệp đồng bộ: Trong mô hình này, tiến trình gửi bị chặn lại cho đến
khi tiến trình nhận sẵn sàng nhận. Ở đây, sự truyền thông và đồng bộ hoá luôn gắn
chặt với nhau.
- Truyền thông điệp dị bộ: Trong mô hình này, tiến trình gửi sẽ không phải chờ đến
khi tiến trình nhận sẵn sàng mà cứ gửi khi có yêu cầu. Như vậy, hai tiến trình gửi
và nhận có thể hoạt động gần như đọc lập với nhau và thông điệp có thể nhận được
sau một khoảng thời gian nào đó (lâu bất kỳ) kể từ khi nó được gửi đi. Tuy nhiên,
21
- Xem thêm -