Mô hình tính toán lưới và ứng dụng giải một số bài toán trên đồ thị

ĐẠI HỌC THÁI NGUYÊN

ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Hà Thị Thúy

MÔ HÌNH TÍNH TOÁN LƢỚI VÀ ỨNG DỤNG GIẢI

MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2013

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

ĐẠI HỌC THÁI NGUYÊN

ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

HÀ THỊ THUÝ

MÔ HÌNH TÍNH TOÁN LƢỚI VÀ ỨNG DỤNG GIẢI

MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ

Chuyên ngành : Khoa học máy tính

Mã số : 60 48 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS ĐOÀN VĂN BAN

Thái Nguyên - 2013

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

LỜI CAM ĐOAN

Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm

hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận văn

tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo đó.

Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày hoàn

chỉnh trong bất cứ tài liệu nào.

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

LỜI CẢM ƠN

Lời đầu tiên, tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc nhất tới

PGS.TS. Đoàn Văn Ban, người thầy đã chỉ bảo và hướng dẫn tận tình cho tôi trong

suốt quá trình nghiên cứu khoa học và thực hiện luận văn này.

Tôi xin chân thành cảm ơn các thầy cô giáo, cán bộ thuộc phòng Khoa học và

Đào tạo, Trường Đại học Công nghệ thông tin & Truyền thông Thái Nguyên, đã tạo

điều kiện thuận lợi giúp đỡ tôi trong quá trình học tập và nghiên cứu.

Và cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, người thân và bạn bè - đồng

nghiệp - những người đã luôn bên cạnh tôi những lúc khó khăn nhất, động viên và

khích lệ tôi trong cuộc sống và trong công việc.

Tôi xin chân thành cảm ơn!

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

MỤC LỤC

LỜI CAM ĐOAN........................................................................................................................

LỜI CẢM ƠN............................................................................................................................ ..

MỤC LỤC ...................................................................................................................................

DANH MỤC TỪ VIẾT TẮT .....................................................................................................

DANH MỤC HÌNH VẼ..............................................................................................................

LỜI MỞ ĐẦU............................................................................................................................ 1

CHƢƠNG 1. GIỚI THIỆU VỀ CÔNG NGHỆ TÍNH TOÁN LƢỚI................................. 2

1.1 Giới thiệu về mô hình tính toán lưới ......................................................................2

1.1.1 Quá trình phát triển của tính toán lưới............................................................2

1.1.2 Khái niệm tính toán lưới..................................................................................4

1.1.3 Lợi ích của tính toán lưới.................................................................................6

1.1.4 Các dạng tài nguyên trên lưới..........................................................................9

1.1.5 So sánh tính toán lưới với các công nghệ khác .............................................12

1.2 Phân loại lưới........................................................................................................15

1.2.1 Lưới phòng ban (Departmental Grids) ..........................................................15

1.2.2 Lưới doanh nghiệp (Enterprise Grids)...........................................................16

1.2.3 Lưới toàn cầu (Global Grids).........................................................................16

1.2.4 Lưới tính toán (Compute Grids)....................................................................17

1.2.5 Lưới dữ liệu (Data Grids) ..............................................................................17

1.2.6 Lưới tiện ích (Utility Grids)...........................................................................18

1.3 Vấn đề an toàn thông tin và những thách thức đối với tính toán lưới..................18

1.3.1 An toàn thông tin trong tính toán lưới...........................................................18

1.3.2 Những thách thức với một lưới......................................................................20

1.4 Kết luận ................................................................................................................20

CHƢƠNG 2. PHÁT TRIỂN ỨNG DỤNG TRÊN MÔI TRƢỜNG TÍNH TOÁN LƢỚI 22

2.1 Cơ sở hạ tầng lưới ................................................................................................22

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

2.1.1 Portal/Giao diện người dùng..........................................................................22

2.1.2 An toàn và bảo mật (Security).......................................................................23

2.1.3 Bộ môi giới tài nguyên (Broker)....................................................................23

2.1.4 Bộ lập lịch (scheduler)...................................................................................23

2.1.5 Thành phần quản lý dữ liệu (Data management)...........................................24

2.1.6 Thành phần quản lý công việc và tài nguyên (Job and resource management)

................................................................................................................................24

2.1.7 Các thành phần khác......................................................................................24

2.2 Kiến trúc của một lưới..........................................................................................25

2.2.1 Bản chất kiến trúc ..........................................................................................25

2.2.2 Kiến trúc lưới tổng quát.................................................................................27

2.2.3 Các chuẩn đối với tính toán lưới....................................................................32

2.3 Một số môi trường và công cụ hỗ trợ tính toán lưới ............................................38

2.3.1 Alchemi..........................................................................................................39

2.3.2 Globus............................................................................................................40

2.3.3 Legion ............................................................................................................47

2.3.4 UNICORE......................................................................................................48

2.4 Các vấn đề khi lập trình trên lưới.........................................................................51

2.4.1 Các yêu cầu đối với lập trình trên lưới ..........................................................51

2.4.2 Các vấn đề cần quan tâm khi lập trình trên lưới............................................53

2.5 Kết luận ................................................................................................................60

CHƢƠNG 3. GIẢI MỘT SỐ BÀI TOÁN ĐỒ THỊ TRÊN MÔI TRƢỜNG LƢỚI......... 61

3.1 Các khái niệm cơ bản ...........................................................................................61

3.1.1 Đồ thị .............................................................................................................61

3.1.2 Đường đi ........................................................................................................62

3.2 Thuật toán Dijkstra ...............................................................................................63

3.2.1 Thuật toán tuần tự..............................................................................................63

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

3.2.2 Song song thuật toán Dijkstra trên lưới.........................................................63

3.2.3 Thực nghiệm chương trình ............................................................................64

3.3 Thuật toán tô mầu đồ thị.......................................................................................66

3.3.1 Thuật toán tuần tự..........................................................................................67

3.3.2 Song song trên lưới........................................................................................67

3.3.3 Thực nghiệm chương trình ............................................................................68

3. 4 Kết luận ...............................................................................................................70

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN............................................................................. 71

TÀI LIỆU THAM KHẢO...................................................................................................... 73

Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/

DANH MỤC TỪ VIẾT TẮT

Viết tắt Tên đầy đủ Chú giải

API Application Programming Interface Giao diện lập trình ứng dụng

CMM Common Management Model Quản lý chung mẫu

CORBA Common Object Request Broker

Architecture

Yêu cầu chung kiến trúc đối

tượng môi giới

CPU Center Processing Unit Bộ xử lý trung tâm

DAP Directory Access Protocol

Giao thức đặc tả các kỹ thuật

định danh đối tượng, tìm kiếm

và ghi các khoản mục dữ liệu

DCOM Digital Computer Thiết bị không dây

DNS Domain Name System Hệ thống phân giải tên miền

FTP File Transfer Protocol Giao thức truyền tệp qua mạng

TCP

GGF Global Grid Forum Diễn đàn lưới toàn cầu

GRAM Globus Resource Allocation

Management

Dịch vụ quản lý và định vị tài

nguyên lưới

GridFTP Grid File Transfer Protocol

GridFTP là mở rộng của giao

thức FTP, tích hợp khả năng

bảo mật lưới, truyền dữ liệu tốt

hơn so với FTP

GSH Grid Service Handle Lưới dịch vụ xử lý

GSR Grid Service Reference Lưới dịch vụ tham khảo

GSS-API Generic Security Service Application

Program Interface

Giao diện lập trình ứng dụng

dịch vụ bảo mật chung