namha_11a1

New Member
Luận vă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 ThS. Toán học: 60 46 35
Nhà xuất bản: ĐHKHTN
Ngày: 2011
Chủ đề: Nhân ma trận
Véctơ
Tính toán song song
Toán tin
Miêu tả: 94 tr. + CD-ROM + Tóm tắt
Luận văn ThS. Bảo đảm toán học cho máy tính và hệ thống tính toán -- Trường Đại học Khoa học Tự nhiên. Đại học Quốc gia Hà Nội, 2011
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. 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. 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
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...............................................225
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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi6
BẢNG THUẬT NGỮ VIẾT TẮT
Thuật ngữ Tiếng Anh Nghĩa tiếng Việt
CCS Compressed Column Storage 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
MIMD
Multi Instruction Stream, Multi
Data Stream Đa luồng lệnh, đa luồng dữ liệu
MISD Multi Instruction Stream, Single
Data Stream Đa luồng lệnh, đơn 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
SIMD Single Instruction Stream, Multi
Data Stream Đơn luồng lệnh, đa luồng dữ liệu
SISD Single Instruction Stream, Single
Data Stream Đơn luồng lệnh, đơn luồng dữ liệu
TCP Transmission Control Protocol Giao thức điều khiển truyền thông
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ạm7
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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi8
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.................................................................929
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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi10
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, hay 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ững11
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. tui 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ả.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi12
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ý hay 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à SPSD13
- đơ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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi14
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 hay 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 hay 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.15
 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 hay 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].
Hình 1.1 Phân cấp hệ thống bộ nhớ
BXL
Bộ nhớ mức 1
Bộ nhớ mức n
Bộ nhớ mức 2
Mức thấp nhất
Mức cao nhất Nhỏ, nhanh và đắt
Lớn, chậm và rẻ
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi16
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ý.17
- 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 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 hay độ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à
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi18
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
Bước 2 các cột mà không có bộ xử lý trên nó thì được phân cho bộ xử lý mà có số
cột được phân là ít nhất.
b) Cài đặt
Phần này sẽ đưa ra một vài chi tiết cài đặt của thuật toán biên địa phương, thuật toán
này có độ phức tạp thời gian là O(nz+P2).
Trong mỗi lần lặp của bước 2 trong pha 1, thời gian cho tìm kiếm bộ xử lý có L(s)
lớn nhất mất O(P) thời gian, với n vòng lặp mất O(n.P) thời gian nếu cài đặt trực tiếp.
Tuy nhiên có thể thực hiện chỉ với O(nz + P2) thời gian. Trong khi ở vòng lặp đầu tiên,
việc tìm kiếm cho bộ xử lý có L(s) lớn nhất mất O(P) thời gian. Trong khi lặp có nhiều
nhất k(c) – 1 giá trị L(s) được tăng trong bước 4. Các giá trị L(s) khác còn lại là như nhau.
Chúng ta chỉ so sánh k(c) – 1 giá trị được tăng này xem có lớn hơn L(p). Sau khi so sánh
bộ xử lý mà L(s) là lớn nhất sẽ là bộ xử lý p có một cột trong vòng lặp tiếp theo. Tuy
nhiên, nếu Ls(p) = Ns(p) thì p đã bị loại từ pha 1 và chúng ta lại phải tìm từ các bộ xử lý
còn lại mà có L(s) lớn nhất, ở đây mất O(P) thời gian. Vì vậy, với n vòng lặp chúng ta
phải thực hiện    
1 0
1 ( )
n c
k c nz n nz
 
      phép so sánh và tìm kiếm P lần mất O(P2) thời
gian.
Trong bước 4 của pha 1, việc khởi tạo C s L  hoàn toàn từ đầu sẽ mất O(n) thời gian.
Thay vì vậy, chúng ta có thể gỡ bỏ cột c khỏi C s L  và thêm một cột chưa được sở hữu c0
từ C s ( ) vào C s L  mà vẫn thoả mãn (i) và (ii). Điều này có nghĩa rằng C s L   chỉ điều
chỉnh lại mà không phải là khởi tạo hoàn toàn, và vì vậy sẽ mất ít thời gian hơn.
Nếu trong bước 3 của pha 1, các cột của C p L  được sắp xếp lại theo tăng dần số bộ
xử lý, việc chọn cột c sẽ mất O(1) thời gian nhưng việc sắp xếp này phải duy trì tới khi
các cột mới được thêm vào C p L  trong bước 4 cái này mất nhiều hơn O(1) thời gian.
Thay vì chọn một cột chưa được sở hữu từ C p L  được sắp, chúng ta chọn một cột chưa
được sở hữu từ tập B(p) được sắp, bởi vì B(p) là không thay đổi. Việc sử dụng B(p) thay75
vì C p L  trong bước 3, tuy nhiên sẽ gây cho thuật toán một số trường hợp khi thêm một
cột vào C(s) nhưng cột này lại không thuộc C s L  . Đó là bởi vì cận dưới địa phương tổng
quát không quan tâm xem cột có k(c) bộ xử lý nào mà chỉ cần biết là có k(c) bộ xử lý trên
nó. Vì vậy thay vì lưu giữ một danh sách C s L   các cột mà bộ xử lý cần để đạt đến cận
dưới địa phương tổng quát của nó, chúng ta lưu giữ các giá trị needed(s,a), và để điều
chỉnh các giá trị một cách thích đáng, các giá trị avail(s,a) được lưu. Ta có các định nghĩa
như sau:
C(s,a): là tập các cột c C s   với k(c) = a.
C s a ( , ) : là số các cột chưa sở hữu c C s  ( ) với k(c) = a.
n ded s a ee ( , ) : lá số các cột c C s  L( ) mà k(c) = a.
avail s a C s a C s a ( , ) : ( , ) ( , ). 
Với lưu ý rằng, C s a n ded s a avail s a ( , ) ee ( , ) ( , ),  
2
( ) ( 1) ee ( , )
P
a
Ls s a n ded s a

   và
2
( ) ( ) ee ( , ).
P
a
Lr s B s n ded s a

  Và C s a ( , ) xác định theo nghĩa „chưa được sở hữu‟. Có
nghĩa là một cột c mà k(c) = a được sở hữu bởi một bộ xử lý khác s mà được xử lý trên
tập C s ( ) nhưng không thuộc tập C s a ( , ) (bởi vì nó không phải là chưa được sở hữu).
Chúng ta sử dụng các biến needed và avail trong các bước 3 và 4. Trong bước 3,
một cột chưa được sở hữu c sẽ được chọn từ B(p). Cột c cũng xử lý trong C s k c ( , ( )) cho
mọi bộ xử lý s mà xử lý trên c. Bởi vì bộ xử lý p sẽ sở hữu cột c, cột c sẽ bị gỡ bỏ khỏi
C p k c ( , ( )) và thêm vào C(p,k(c)), bởi vậy avail(p,k(c)) là không thay đổi. Trong bước 4,
với tất cả các bộ xử lý khác mà xử lý c và sẽ không xử lý c, c cũng sẽ gỡ bỏ khỏi
C s k c ( , ( )) nhưng không thêm vào C(s,k(c)), bởi vậy các bộ xử lý này avail(s,k(c)) là nhỏ
hơn 1 giá trị. Tức là gây nên needed(s,k(c)) > avail(s,k(c)). Điều này có nghĩa là CL(s) của
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi76
các bộ xử lý mà không nhận được cột c là dựa trên sự mong đợi có đủ các cột có k(c) bộ
xử lý trong khi thực sự là không đủ. Để giải quyết sự không thống nhất này chúng ta phải
trừ needed(s,k(c)) đi 1, cái này tương ứng với việc di chuyển cột c khỏi CL(s). Khi các cột
di chuyển khỏi CL(s), các cột khác có thể phải thêm lại vào CL(s) để thoả mãn (ii). Chỉ các
cột mà ở trong C s a ( , ) có thể thêm vào CL(s), với 2 .   a P Bởi vì tính chất (i) sẽ phải
được thoả mãn, chúng ta phải tìm giá trị nhỏ nhất a mà needed(s,a) < avail(s,k(c)). Như
vậy cũng có nghĩa rằng không phải tất cả các cột từ C s a ( , ) có thể thêm vào CL(s). Nếu
chúng ta tìm thấy một C s a ( , ) chúng ta tăng needed(s,a) thêm một, tương ứng với thêm
một cột vào CL(s) mà có bộ xử lý trên nó. Bây giờ CL(s) thoả mãn (i) và (ii) và cũng là
cận dưới địa phương tổng quát.
Giá trị nhỏ nhất mà thoả mãn needed(s,a) < avail(s,a) có thể chỉ tăng trong quá trình
chạy thuật toán, bởi vì khi needed(s,a) bị giảm thì avail(s,a) cũng bị giảm, và avail(s,a)
không tăng trong khi chạy thuật toán, với mọi s và a. Bởi vậy khi chúng ta tìm được một
giá trị thấp nhất thoả needed(s,a) < avail(s,a) cho bộ xử lý s, chúng ta sử dụng giá trị
trước của a, gọi là aprev, mà thoả mãn needed(s,aprev) < avail(s,aprev), và tăng aprev
thêm 1 nếu needed(s,aprev) = avail(s,aprev) cho tới khi needed(s,aprev) < avail(s,aprev)
hay aprev = P. Bởi vậy aprev tăng nhiều nhất P lần. Bởi vì chúng ta tìm kiếm trong các
tập C s aprev ( , ) với 0 ,   aprev P C s ( ,0) 0  và C s ( ,1) 0  , aprev được thiết lặp bằng 2
trong quá trình khởi tạo. Lưu ý rằng, khi needed(q, k(c)) tăng hay giảm, thì Ls(q), Lr(q)
và L(q) sẽ được điều chỉnh dựa theo định nghĩa của chúng.
Trong bước 2 của pha 2, nhiều nhất là n lần, mỗi lần |C(s)| là nhỏ nhất, nên sẽ mất
O(n.P) thời gian. Thay vì, chúng ta sắp xếp các bộ xử lý tăng dần theo |C(s)|:
C p C p C p  0 1 1       ... .  p  Thì, chúng ta sẽ phân các cột c mà k(c) = 0 cho bộ xử lý
p0 cho tới khi C p C p  0 1     . Rồi, chúng ta lại phân các cột cho p0 và p1 cho tới khi
C p C p C p  0 1 2        ,... cho tới khi tất cả các cột c với k(c) = 0 được phân. Bởi vì có
nhiều nhất n lần phân, bước 3 của pha 2 mất O(n + P.log P) thời gian.77
Cấu trúc dữ liệu cho thuật toán biên địa phương như sau:
Cấu trúc của cột c:
owner(c)
procindex(c)[]
k(c)
Cấu trúc bộ xử lý s:
Ns(s), Nr(s), Nvecto(s)
B(s)[], nB(s), Bcount(s)
Ls(s), Lr(s), L(s)
needed(s), avail(s)[], aprev(s)
Ở đây, owner(c) là chỉ số của bộ xử lý mà sở hữu cột c, procindex(c)[] là mảng lưu
tất cả các chỉ số của bộ xử lý mà xử lý cột c, và k(c) là số bộ xử lý trên cột c, bởi vậy
procindex(c)[] độ dài k(c). Nvecto(s) lưu số thành phần véc tơ sở hữu bởi bộ xử lý s
(Nvecto(s) = |C(s)|). Mảng B(s)[] độ dài nB(s) và lưu tất cả các chỉ số của cột c với
k(c)  2 mà bộ xử lý s xử lý trên đó, nB(s) = |B(s)| và Bcount(s) = i có nghĩa B(s) là cột
sau khi phân cho bộ xử lý s. Các mảng avail(s)[] và needed(s)[] có độ dài P + 1.
c) Đánh giá thuật toán
Thời gian
Pha 1:
Bước 1, chúng ta phải khởi tạo procindex(c)[], B(s)[], avail(s)[] và needed(s)[] cho
mọi bộ xử lý s, ở đây sẽ mất O(nz) thời gian.
Bước 2, như trình bày ở phần trước, mất O(nz+P2) thời gian.
Bước 3, chúng ta phải kiểm tra mỗi phần tử B(s)[] của mỗi bộ xử lý một lần, ở đây
mất O(nz) thời gian bởi vì chúng ta chỉ phải tìm kiếm theo một chiều trong mảng B(s)[]
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi78
đã sắp thứ tự. Việc phân cột và tăng số gửi và số nhận cũng chỉ mất O(nz) thời gian cho n
vòng lặp.
Bước 4, vòng lặp for chạy nhiều nhất là nz lần trong n lần lặp. Vì vậy, vòng lặp
while mất nhiều nhất O(nz + P2) khi các giá trị aprev(q) chỉ tăng. Tóm lại bước 4 mất
O(nz+P2).
Pha 2:
Bước 1 mất O(nz) thời gian bởi vì nhiều nhất n cột có thể được phân, tức là tất cả nz
phần tử khác không sẽ phải được kiểm tra.
Bước 2, như trình bày ở phần trên, sẽ mất O(n+P.log P) thời gian.
Như vậy toàn bộ thuật toán mất O(nz+P2) thời gian nếu n < nz.
Bộ nhớ
Tất cả n mảng procindex(c)[] sử dụng O(nz) bộ nhớ, P mảng B(s)[] cũng vậy. Các
mảng needed(s)[] và avail(s)[] mất O(P2) bộ nhớ. Như vậy bộ nhớ cho thuật này
cũng là O(nz + P2).
2.2.3.3 Phân phối các véc tơ đồng thời
Ở đây xét cho trường hợp ma trận vuông, các thành phần của hai véc tơ ui và vi được
phân cho cùng bộ xử lý. Ta nói phân phối của hai véc tơ u và v là đồng thời.
a) Thuật toán biên địa phƣơng
Mục tiêu ở đây là cực tiểu hoá max(Nsendr,Nreceiver)+max(Nsendc,Nreceivec), ở
đây „r‟ và „c‟ có nghĩa chỉ hàng và cột tương ứng. Và trong thuật toán này cũng có một số
thay đổi. Thay vì phân một cột cho một bộ xử lý thì chúng ta sẽ phân một cặp gồm hàng i
và cột i cho một bộ xử lý và ta gọi là cặp rowcol. Thay vì giá trị L(s) thì sẽ cần các giá trị
L
r(s) và Lc(s) cho mỗi bộ xử lý. Từ đây sẽ đặt ra một số vấn đề như sau.
Link Download bản DOC
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:

 
Last edited by a moderator:

Các chủ đề có liên quan khác

Top