ĐẠ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 Ngun - 2013 Số hóa bởi Trung tâm Học liệu
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 q 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 hồn
chỉnh trong bất cứ tài liệu nào.
Số hóa bởi Trung tâm Học liệu
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. Đồ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 q 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 Ngun, đã tạo
điều kiện thuận lợi giúp đỡ tơi trong q 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 đã ln bên cạnh tơi những lúc khó khăn nhất, động viên và
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 TỐN LƢỚI 22
2.1 Cơ sở hạ tầng lưới 22
Số hóa bởi Trung tâm Học liệu
2.1.1 Portal/Giao diện người dùng 22
2.1.2 An tồn và bảo mật (Security) 23
2.1.3 Bộ mơi giới tài ngun (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 ngun (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 qt 27
2.2.3 Các chuẩn đối với tính tốn lưới 32
2.3 Một số mơi trường và cơng cụ hỗ trợ tính tố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 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 TỐ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
Architecture
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 tồn cầu
GRAM
Globus Resource Allocation
Management
Dịch vụ quản lý và định vị tài
ngun lưới
GridFTP
HPC
High Performance Computing
Tính tốn hiệu năng cao
HTML
Hyper Text Markup Language
Ngơn ngữ hiển thị siêu văn bản
HTTP
Hyper Text Transfer Protocol
Giao thức truyền siêu văn bản
IBM
International Business Machines
tập đồn cơng nghệ máy tính đa
quốc gia có trụ sở tại Armonk,
New York, Mỹ
ICMP
Internetwork Control Message
Protocol
Giao thức điều khiển truyền tin
trên mạng
IDB
Installation Database
Thơng số cần khai báo về cơ sở
dữ liệu
IP
Internet Protocal
Giao thức Internet
IT
Information Technology
Cơng nghệ thơng tin
J2EE
OGSI
Open Grid Service Infrastructure
Hạ tầng dịch vụ lưới mở
OSPF
Open Shortest Path First
Giao thức tìm đường ngắn nhất
đầu tiên
PC
Personal Computer
Máy tính cá nhân
PU
Processing Unit
Đơn vị xử lý
PVM
Parallel Virtual Machine
Song song máy ảo
QoS
Quality of Service
Chất lượng dịch vụ
RFT
Reliable File TransferService
Dịch vụ truyền file tin cậy
RLS
Replica Location Service
Dịch vụ định vị bản sao trong
kiến trúc lưới dữ liệu Globus,
cho phép xác định vị trí của các
bản sao của thực thể dữ liệu
trong lưới.
RMI
UDP
User Datagram Protocol
Giao thức sử dụng gói
VO
Virtual Organizations
Các tổ chức ảo
VPN
Virtual Private Networks
Mạng riêng ảo
WAN
Wide Area Network
Mạng diện rộng
WS
Web Service
Dịch vụ web
WSDL
Web Service Deployment Descriptor
Language
Ngơn ngữ đặc tả dịch vụ web
WSIL
WS- Inspection Language
Dịch vụ web kiểm tra ngơn ngữ
WSRF
Web Services Resource Framework
Framework đưa ra bởi GT4 hỗ
trợ kiến trúc lập
trình mới
WWW
World Wide Web
Mạng lưới tồn cầu
Mô hình kiến trúc hoạt động của UNICORE
49
Hình 3.1
Cung (u, v)
61
Hình 3.2
Cạnh (u, v)
61
Hình 3.3
Biểu diễn khuyên
61
Hình 3.4
Đồ thị G cho trước
62
Hình 3.5
Giao diện chương trình trên máy server - thuật toán Dijkstra
65
Hình 3.6
Hướng dẫn sử dụng các chức năng chính
65
Hình 3.7
Giao diện chương trình trên client - thuật toán Dijkstra
66
Hình 3.8
Giao diện chương trình trên máy server - thuật toán tô màu
đồ thị
69
Hình 3.9
Giao diện chương trình trên client - thuật toán tô màu đồ thị
69
2 CHƢƠNG 1. GIỚI THIỆU VỀ CÔNG NGHỆ TÍNH TOÁN LƢỚI
1.1 Giới thiệu về mô hình tính toán lƣới
1.1.1 Quá trình phát triển của tính toán lưới
Cũng như các công nghệ tính toán khác, tính toán lưới (Grid Computing) ra đời
xuất phát từ nhu cầu tính toán của con người. Thực tế, ngày càng có nhiều bài toán
phức tạp hơn được đặt ra và do đó các tổ chức cũng cần phải có những năng lực tính
toán mạnh mẽ hơn. Có thể giải quyết vấn đề này bằng hai cách [1]:
Một là: Đầu tư thêm trang thiết bị, cơ sở hạ tầng tính toán (mua thêm máy chủ,
máy trạm, siêu máy tính, cụm máy tính (cluster), ).
Hai là: Phân bố lại hợp lý các nguồn tài nguyên trong tổ chức hoặc thuê thêm
các nguồn tài nguyên từ bên ngoài (dĩ nhiên là với chi phí rẻ hơn nhiều so với việc đầu
tư cho cơ sở hạ tầng tính toán).
Cách giải quyết thứ hai này chính là mục tiêu và nguồn gốc yêu cầu cho sự hình
thành của tính toán lưới. Các nhà khoa học tại Argone National Laboratory thuộc đại
học Chicago (Mỹ) là những người đầu tiên đề xuất ý tưởng về tính toán lưới.
Tính toán lưới hướng đến việc chia sẻ và sử dụng hiệu quả các nguồn tài nguyên
thuộc về nhiều tổ chức trên một quy mô rộng lớn (thậm chí là quy mô toàn cầu). Chính
công nghệ mạng và truyền thông phát triển mạnh mẽ trong những năm qua đã biến
những khả năng này dần trở thành hiện thực. Các nghiên cứu về tính toán lưới đã và
đang được tiến hành nhằm tạo ra một cơ sở hạ tầng lưới cho phép dễ dàng chia sẻ và
quản lý các tài nguyên đa dạng và phân tán trong môi trường lưới.
Giống như Internet, khái niệm lưới (Grid) đã phát triển từ những nhu cầu về tính
toán khoa học lớn. Internet được phát triển để thoả mãn nhu cầu về một phương tiện
liên lạc giữa các trung tâm tính toán lớn do liên bang đầu tư. Những sự liên kết này dẫn
tới việc chia sẻ tài nguyên và thông tin giữa các trung tâm này và sau đó là cung cấp sự
3
quả thì nằm trên các nút tính toán. Mã cần để thực hiện các tác vụ phân tán được gửi
riêng rẽ tới các nút. Theo cách này, các nút của lưới có thể dễ dàng lập trình lại [13].
Có thể nói, việc phát triển và xây dựng mô hình tính toán lưới là sự kế thừa và phát
triển các ý tưởng, các công nghệ hiện hành ở mức cao hơn. Sự phát triển không ngừng của
cơ sở hạ tầng, phần cứng máy tính, mạng đã giúp cho các mô hình tính toán lưới ngày
càng được ứng dụng để thực hiện được nhiều điều hơn những ý tưởng trước đây.
1.1.2 Khái niệm tính toán lưới
Trong mỗi giai đoạn phát triển, mỗi tổ chức, cá nhân tùy theo quan điểm và thực
tế xây dựng hệ thống của mình mà đưa ra các định nghĩa khác nhau về tính toán lưới.
Dưới đây, luận văn xin trình bày một số định nghĩa về tính toán lưới như sau:
Dưới quan điểm cá nhân của tiến sỹ I.Foster và các đồng nghiệp thì [9] "Một
lưới là một hệ thống có các đặc trưng như phối hợp các tài nguyên phân tán từ nhiều
miền tự trị khác nhau; sử dụng các chuẩn mở và giao thức mở; cung cấp chất lượng
dịch vụ không tầm thường" - I. Foster„s Three-Point Checklist (HPCWIRE -
20.07.2002).
Còn dưới quan điểm của một số công ty và liên minh phát triển lưới uy tín trên
thế giới thì tính toán lưới được định nghĩa như sau [6]:
Định nghĩa của Oracle: tính toán lưới là việc liên kết nhiều máy chủ và thiết
bị lưu trữ thành một siêu máy tính nhằm tối ưu hóa được tính ưu việt của các hệ thống
máy chủ cũng như hệ thống ứng dụng, nhờ đó giảm thiểu đến mức thấp nhất chi phí.
Định nghĩa của IBM: tính toán lưới là một môi trường tính toán ảo. Môi
trường này cho phép bố trí song song, linh hoạt, chia sẻ, tuyển lựa, tập hợp các nguồn
tài nguyên hỗn hợp về mặt địa lý, tùy theo mức độ sẵn sàng, hiệu suất, chi phí của các
tài nguyên tính toán và yêu cầu về chất lượng dịch vụ của người sử dụng.
Định nghĩa của liên minh điện toán lưới: môi trường tính toán lưới được hiểu
như một hạ tầng kết nối hệ thống máy tính, hệ thống mạng, hệ thống cơ sở dữ liệu
5
Vượt qua phạm vi một tổ chức: có nhiều trạm và các chính sách truy nhập có thể
khác nhau trên các trạm, tổng thể lưới sẽ tạo ra một tổ chức ảo thống nhất.
Cơ chế và chính sách an toàn bảo mật phức tạp. Cơ chế quản lý tài nguyên đa
dạng, phức tạp.
Có thể hình dung đơn giản một lưới bao gồm một tập các tài nguyên đa dạng
(còn gọi là các nút lưới - có thể là PC, cluster, hệ thống lưu trữ, ) thuộc về nhiều tổ
chức nhằm giải quyết một bài toán nào đó.
1.1.3 Lợi ích của tính toán lưới
Tính toán lưới có thể đem lại những ích lợi rất lớn [10].
1/. Khai thác, tận dụng các tài nguyên nhàn rỗi
7 Hầu hết các tổ chức đều có một lượng lớn các tài nguyên tính toán nhàn rỗi, các
máy tính cá nhân thường chỉ sử dụng hết 5% thời gian xử lý CPU, ngay cả các server
cũng thường “rảnh rỗi”. Lưới có thể tối ưu sử dụng các tài nguyên nhàn rỗi này theo
nhiều cách khác nhau, ví dụ, gửi một công việc trên một máy tính đang bận rộn đến
một máy khác rảnh rỗi hơn để xử lý, hoặc phân nhỏ một công việc rồi gửi các công
việc con đến các máy tính nhàn rỗi khác cho xử lý song song,
Lưới cho phép kết hợp nhiều không gian lưu trữ nhàn rỗi để tạo thành một
không gian lưu trữ lớn hơn, được cấu hình để tăng hiệu suất, độ tin cậy hơn so với các
máy đơn lẻ thông qua các cơ chế quản lý dữ liệu.
Một chức năng của lưới nữa là cân bằng sử dụng tài nguyên tốt hơn. Một tổ
chức thường gặp các vấn đề khó khăn khi các hoạt động đòi hỏi thêm nhiều tài nguyên
hơn. Với lưới, có thể chuyển hoạt động đến các tài nguyên nhàn rỗi khác, hoặc có thể
thêm các tài nguyên mới một cách dễ dàng, từ đó làm tăng khả năng chịu đựng của hệ
thống. Lưới có thể quản lý nhiều loại tài nguyên, do đó có thể cho phép theo dõi tổng
quan về các hoạt động sử dụng tài nguyên trong các tổ chức lớn, hỗ trợ hoạch định các
chiến lược sử dụng tài nguyên.
tiếp cận mới để giải quyết vấn đề độ tin cậy dựa nhiều hơn vào các công nghệ phần
mềm hơn là các phần cứng đắt tiền. Lưới là sự khởi đầu cho các công nghệ đó. Các hệ
thống trong lưới thường rẻ và phân tán theo địa lý, do đó, nếu có sự cố về nguồn điện
hay các lỗi hệ thống khác tại một vị trí, toàn bộ phần còn lại không bị ảnh hưởng. Các
phần mềm quản trị lưới có khả năng thực thi lại công việc trên một nút khác khi phát
hiện có lỗi hệ thống. Nếu quan trọng hơn nữa, trong các hệ thống theo thời gian thực,
nhiều bản dự phòng của các các công việc quan trọng có thể được chạy trên nhiều máy
tính khác nhau trong lưới để đảm bảo độ tin cậy tối đa.
6/. Tăng khả năng quản trị các hệ thống
Mục tiêu ảo hoá tất cả các tài nguyên và cung cấp giao diện quản lý đơn nhất
các hệ thống hỗn tạp đem lại những cơ hội mới để quản trị tốt hơn trong các cơ sở hạ
tầng công nghệ thông tin lớn, phân tán. Bên cạnh đó, đối với tầm quản lý vĩ mô, có
9 nhiều dự án sử dụng cơ sở hạ tầng công thông tin, lưới cho phép quản lý độ ưu tiên sử
dụng tài nguyên của các dự án này. Trước đây, mỗi dự án thường chịu trách nhiệm
quản lý một số tài nguyên, thường xảy ra tình trạng các tài nguyên của dự án này đang
nhàn rỗi trong khi dự án khác đang gặp vấn đề, thiếu tài nguyên do gặp các sự kiện
không lường trước. Với tầm nhìn rộng hơn do lưới cung cấp, các tình huống trên có thể
được giải quyết dễ dàng.
Trên đây giới thiệu một số ích lợi khi sử dụng công nghệ tính toán lưới, lưới
còn mang lại rất nhiều lợi ích khác mà không thể kể hết ở đây, tuỳ vào tình huống cụ
thể mà đem lại các lợi ích khác nhau. Vấn đề là phải hiểu rõ bản chất lưới, sử dụng tốt
các công cụ nhằm khai khác tốt nhất trong các tình huống cụ thể.
Từ đó, công nghệ tính toán lưới có thể được ứng dụng trong các bài toán trong
khoa học lẫn thương mại:
Đòi hỏi năng lực xử lý lớn (High-performance computing), yêu cầu rút ngắn
thời gian hoàn thành kết quả càng nhanh càng tốt.
thường không nằm trên máy đang thực thi công việc. Khả năng về băng thông trong
những trường hợp như vậy là một tài nguyên then chốt, ảnh hưởng đến khả năng của
lưới.
Việc giao tiếp với bên ngoài được thực hiện thông qua mạng Internet. Lưới có
thể sử dụng các kết nối Internet để liên lạc giữa các nút. Vì các kết nối này không chia
sẻ một đường truyền nên làm tăng băng thông truy cập Internet.
Các đường truyền dự phòng đôi khi cần thiết để giải quyết tốt hơn các vấn đề về
hư hỏng mạng và truyền dữ liệu lớn.
4/. Tài nguyên phần mềm
Lưới có thể được cài đặt các phần mềm mà có thể quá mắc để cài trên tất cả mọi
máy tính trong lưới. Các phần mềm này chỉ cần được cài trên một số nút. Thông qua
lưới, khi một công việc cần đến chúng, nó sẽ gửi dữ liệu đến nút đã được cài đặt phần
11 mềm và cho thực thi. Đây có thể là một giải pháp tốt để tiết kiệm chi phí về bản quyền
phần mềm.
5/. Các tài nguyên đặc dụng
Là các thiết bị dùng trong khoa học, kỹ thuật như kính viễn vọng, các bộ cảm
biến (sensor),… Các thiết bị này chủ yếu thu thập các dữ liệu khoa học, phục vụ cho
các bước phân tích, xử lý sau này.
Các tài nguyên trên đây đến từ nhiều nguồn khác nhau, có thể không thuộc
quyền quản lý của một tổ chức, của một đơn vị mà có thể thuộc nhiều tổ chức, ở nhiều
nơi khác nhau. Một số tài nguyên có thể được sử dụng tự do, trong khi một số khác
được sử dụng dưới những chính sách nhất định. Các tài nguyên được “ảo hóa”
(virtualize) để che dấu sự phức tạp, đa dạng nhằm đưa ra một cái nhìn thống nhất, đơn
giản về toàn bộ tài nguyên trên lưới sao cho dưới mắt của người dùng, các tài nguyên
lưới là một khối thống nhất.
Các tài nguyên ảo được tổ chức lại thành các “tổ chức ảo”, đến lượt nó, các tổ
dùng một số ứng dụng cụ thể nào đó cũng như không gian lưu trữ. Người dùng tương
tác với nhà cung cấp dịch vụ thường là thông qua mạng riêng ảo (VPN) hoặc các
đường truyền dành riêng nên loại bỏ được rất nhiều nguy cơ về an toàn bảo mật. Do
vậy khi nói về các loại dịch vụ này thì ngữ cảnh của chúng cũng hẹp hơn tính toán lưới
rất nhiều.
3/. Các hệ thống tính toán ngang hàng (Peer - to - peer Computing Systems)
Tính toán ngang hàng cũng là một lĩnh vực của tính toán phân tán. Một số hệ
thống tính toán ngang hàng phổ biến hiện nay là Seti@home hay các mạng ngang hàng
chia sẻ tập tin như Napster, Kazaa, Morpheus và Gnutella. Những điểm khác biệt chính
giữa tính toán ngang hàng và tính toán phân tán là:
Tính toán lưới có cộng đồng người sử dụng có thể nhỏ hơn tuy nhiên tập
trung nhiều vào các ứng dụng và có yêu cầu cao hơn về an ninh cũng như tính toàn vẹn
của ứng dụng. Trong khi đó các hệ thống mạng ngang hàng có thể có số người sử dụng
rất lớn bao gồm cả các người dùng đơn lẻ và các tổ chức tuy nhiên không đòi hỏi cao
về an ninh và mô hình chia sẻ tài nguyên cũng đơn giản hơn.
Môi trường lưới liên kết các nguồn tài nguyên mạnh hơn, đa dạng hơn và chặt
chẽ hơn.
4/. Công nghệ tính toán hiệu năng cao truyền thống (High performance computing)
Như đã nói ở trên, để giải quyết những bài toán lớn người ta có thể đầu tư cho
cơ sở hạ tầng tính toán. Để giải quyết những bài toán rất lớn và phức tạp người ta phải
nghiên cứu xây dựng những hệ thống siêu tính toán. Các hướng nghiên cứu trong tính
toán hiệu năng cao chủ yếu bao gồm:
Copyright: Tài liệu đại học ©