Song song hóa thuật toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh sử dụng thư viện mpi

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM



TRẦN ĐỨC VIỆT

SONG SONG HÓA THUẬT TOÁN TÌM ĐƯỜNG ĐI

NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH SỬ DỤNG

THƯ VIỆN MPI

Chuyên ngành: Hệ thống thông tin

Mã số: 8480104

TÓM TẮT LUẬN VĂN THẠC SĨ

HỆ THỐNG THÔNG TIN

Đà Nẵng – Năm 2018

Công trình được hoàn thành tại

TRƯỜNG ĐẠI HỌC SƯ PHẠM

Người hướng dẫn khoa học: TS. Nguyễn Đình Lầu

Phản biện 1: PGS.TSKH. Trần Quốc Chiến

Phản biện 2: PGS.TS. Lê Mạnh Thạnh

Luận văn sẽ được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp

thạc sĩ Hệ thống thông tin họp tại Trường Đại học Sư phạm vào ngày

18 tháng 11 năm 2018

Có thể tìm hiểu luận văn tại:

 Trung tâm Học liệu, Đại học Đà Nẵng tại Trường Đại học Bách

khoa

 Thư viện Trường Đại học Sư phạm - ĐHĐN

1

MỞ ĐẦU

1. Đặt vấn đề

Khi xây dựng thuật toán tuần tự cho các bài toán trên mạng đồ

thị, bản thân các thuật toán là rất phức tạp, thời gian của thuật toán

rất lớn. Điều này, đòi hỏi phải song song các thuật toán tuần tự tương

ứng.

Do đó, xây dựng các thuật toán tìm đường đi theo hướng song

song hóa từ các thuật toán tuần tự là đòi hỏi hết sức cần thiết. Xuất

phát từ đó tôi chọn đề tài “Song song hóa thuật toán tìm đường đi

ngắn nhất giữa mọi cặp đỉnh sử dụng thư viện MPI” làm đề tài luận

văn cao học.

2. Mục đích của luận văn

Nghiên cứu và song song hóa thuật toán Floyd_Warshall cho bài

toán tìm đường đi ngắn nhất trên nguồn dữ liệu lớn và phân tán, từ

đó nâng cao hiệu quả của việc xử lý dữ liệu.

3. Nội dung của luận văn

Trong luận văn này gồm có 3 nội dung:

- Nội dung 1: Nghiên cứu về lý thuyết xử lý song song, kiến trúc

song song, các mô hình về xử lý song song, cách đánh giá độ phức

tạp thời gian của thuật toán song song.

- Nội dung 2: Tìm hiều về thư viện lập trình song song MPI

- Nội dung 3: Xây dựng thuật toán Floyd_Warshall song song, tiến

hành thử nghiệm và đánh giá thuật toán.

4. Phƣơng pháp nghiên cứu

- Nghiên cứu các tài liệu về cơ sở lý thuyết: Lý thuyết đồ thị, xử lý

2

song song…

- Sử dụng phương pháp phân tích, so sánh và đánh giá các thuật toán

tìm đường đi ngắn nhất.

- Song song hóa thuật toán FLOYD- WARSHALL tìm đường đi

ngắn nhất giữa mọi cặp đỉnh trong đồ thị.

- Sử dụng đối sánh để đánh giá kết quả thử nghiệm của thuật toán đã

cải tiến.

3

CHƢƠNG 1

XỬ LÝ SONG SONG

1.1. Giới thiệu về xử lý song song

1.2. Kiến trúc máy tính song song

1.3. Các mô hình lập trình song song

1.4. Thuật toán song song

1.5. Kết luận chƣơng

Để giải những bài toán đặt ra một cách hiệu quả trên những

máy tính mà chúng ta có, vấn đề chính là làm thế nào để xây dựng

được những thuật toán song song. Cách làm khá thông dụng là biến

đổi các thuật toán tuần tự về song song, hay chuyển từ một dạng

song song về dạng song song phù hợp hơn nhưng vẫn bảo toàn được

tính tương đương trong tính toán.

Dựa vào bốn công đoạn và những nguyên lý thiết kế chính:

nguyên lý lập lịch, nguyên lý hình ống, nguyên lý chia để trị, nguyên

lý đồ thị phụ thuộc dữ liệu, nguyên lý điều kiện tranh đua để xây

dựng một số thuật toán song song.

Để đánh giá được tính hiệu quả của thuật toán song song

thường phải dựa vào độ phức tạp thời gian của thuật toán. Độ phức

tạp thời gian của thuật toán song song không chỉ phụ thuộc vào kích

cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song

song và số lượng các bộ xử lý được phép sử dụng trong hệ thống.

4

CHƢƠNG 2

LẬP TRÌNH SONG SONG VỚI MPI

2.1. Tổng quan về lập trình song song trong môi trƣờng MPI

2.1.1. Giới thiệu

2.1.2. Một số đặc điểm của lập trình MPI

MPI là một giao thức truyền thông độc lập với ngôn ngữ dùng

để lập trình máy tính song song. MPI hỗ trợ cả giao tiếp điểm - điểm

và giao tiếp tập thể. Mục tiêu của MPI là hiệu suất, khả năng mở

rộng và khả năng di dộng cao.

MPI thường xuyên chạy trên các máy tính chia sẻ bộ nhớ. Mặc

dù MPI thuộc về lớp thứ 5 và lớp cao hơn của mô hình OSI, nhưng

những triển khai có thể bao gồm hầu hết các lớp, với socket và TCP

(Transmission Control Protocol) được dùng trong tần vận chuyển.

Hầu hết các triển khai MPI bao gồm một thiết lập định tuyến

riêng có thể được gọi trực tiếp từ C, C++, Fortran hay bất kỳ ngôn

ngữ nào có giao diện với các thư viện, bao gồm C#, Java hoặc

Python. Những ưu điểm ucar MPI vượt qua những thư viện truyền

thông điệp cũ là tính di động (MPI có thể được triển khai cho hầu hết

các kiến trúc bộ nhớ phân tán) và tốc độ (MPI thực hiện nguyên tắc

tối ưu hoá cho phần cứ mà nó chạy).

MPI sử dụng LIS (Language Independent Specifications) để

gọi và ràng buộc ngôn ngữ. Phiên bản đầu tiên được phát hành chỉ

định ràng buộc ANSI C và Fortran 77 cùng với LIS. Năm 2008,

chuẩn MPI-1.3 chứa khoảng 128 chức năng, đây cũng là phát hành

5

cuối cùng của seri MPI-1 trong năm 2008.

Phiên bản MPI-2.2 bao gồm những tính năng nới như là I/O

song song, quản lý tiến trình động và điều hành bộ nhớ từ xa. LIS

của MPI-2 thiết lập hơn 500 hàm và cung cấp ràng buộc ngôn ngữ

cho ANSI C, ANSI C++ và ANSI Fortran (Fortran 90). Khả năng

tương tác đối tượng cũng được thêm vào để cho phép lập trình

truyền thông điệp bằng ngôn ngữ hỗn hợp dễ dàng hơn.

MPI cung cấp mô hình liên kết ảo, đồng bộ hoá và chức năng

liên lạc giữa một tập hợp các tiến trình (đã được ánh xạ tới các

nút/máy chủ/máy tính cụ thể) trong một ngôn ngữ độc lập, với cú

pháp ngôn ngữ đặc trưng (ràng buộc), cùng với một vài tính năng

ngôn ngữ đặc trưng. Những chương trình MPI luôn luôn làm việc

với các tiến trình, nhưng những lập trình viên thường xem các tiến

trình như là những bộ vi xử lý. Thông thường, để đạt hiệu suất tối

đa, mỗi CPU (hoặc 1 nhân trong một máy tính đa nhân) sẽ được giao

chỉ một tiến trình duy nhất.

Những chức năng thư viện MPI bao gồm (không giới hạn)

những hoạt động nhận/gửi loại điểm - điểm, lựa chọn giữa mô hình

xử lý logic Cartesian hoặc mô hình xử lý logic đồ thị tương đồng,

trao đổi dữ liệu giữa những cặp tiến trình, kết hợp các kết quả từng

phần của tính toán (thu thập và giảm các hoạt động), đồng bộ hoá

các nút cũng như thu thập thông tin liên quan đế mạng như số lượng

của tiến trình trong phiên tính toán, nhận dang bộ vi xử lý hiện tại

mà bộ vi xử lý được ánh xạ, những tiến trình lân cận truy cập trong

một mô hình liên kết logic.

6

2.2. Lập trình song song trong môi trƣờng MPI

2.2.1. Giới thiệu

2.2.2. Một số vấn đề về hiệu năng

2.3. Tìm hiểu tập lệnh của thƣ viện MPI

2.3.1. Các lệnh quản lý môi trƣờng MPI

2.3.2. Các kiểu dữ liệu

2.3.3. Các cơ chế truyền thông điệp

2.3.4. Các lệnh truyền thông điệp blocking

2.3.5. Các lệnh truyền thông điệp non-blocking

2.3.6. Các lệnh truyền thông tập thể

7

CHƢƠNG 3

ỨNG DỤNG XÂY DỰNG THUẬT TOÁN SONG SONG TÌM

ĐƢỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH

3.1. Các bài toán tìm đƣờng đi

3.1.1. Thuật toán Dijkstra

3.1.2. Thuật toán Ford_Bellman

3.1.3. Thuật toán Floyd – Warshall

Phát biểu bài toán: Cho đồ thị có hướng liên thông có trọng

số G=(V,E). Ký hiệu w(i,j) là trọng số của canh (i,j). Độ dài đường đi

∞ = v0 → v1 → v2 → … →vn-1 → vn có tổng các trọng số L(d) =

∑

(vi-1, vi).

Bài toán đặt ra là tìm đường đi ngắn nhất giữa mọi cặp đỉnh

trong đồ thị.

Thuật toán Floyd – Warshall:

Thuật giải tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong

đồ thị liên thông có trọng số.[2]

+ Đầu vào: Đồ thị liên thông G=(V,E), V = {1,2,…n} có trọng số

với mọi cung (i,j).

+ Đầu ra: Ma trận D = [d(i, j)], trong đó d(i, j) là chiều dài đường đi

ngắn nhất từ i đến j với mọi cặp (i, j).

Ma trận P = [p(i, j)] dùng để xác định đường đi ngắn nhất.

+ Phương pháp:

(1) Bước khởi tạo: Ký hiệu D0 = [d0(i,j)] và P0 = [p0(i,j)] là các ma

trận xuất phát, trong đó d0(i,j)=w(i,j) nếu tồn tại cung (i,j) và