..

ĐẠ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 TỐ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


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

HÀ THỊ TH

MƠ HÌNH TÍNH TỐ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 ĐỒN VĂN BAN

Số hóa bởi Trung tâm Học liệu

Thái Nguyên - 2013

/>

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. Đ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 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 Nguyên, đã 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 đã 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!

Số hóa bởi Trung tâm Học liệu

/>


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 TỐN LƢỚI ................................. 2

1.1 Giới thiệu về mơ hình tính tốn lưới ...................................................................... 2
1.1.1 Q trình phát triển của tính tốn lưới ............................................................ 2
1.1.2 Khái niệm tính tốn lưới .................................................................................. 4
1.1.3 Lợi ích của tính tốn lưới................................................................................. 6
1.1.4 Các dạng tài ngun trên lưới .......................................................................... 9
1.1.5 So sánh tính tố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 tố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 tồn thơng tin và những thách thức đối với tính tốn lưới .................. 18
1.3.1 An tồn thơng tin trong tính tố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 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 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 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 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 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

3.1.2 Đường đi ........................................................................................................ 62
3.2 Thuật toán Dijkstra ............................................................................................... 63
3.2.1 Thuật tốn tuần tự .............................................................................................. 63

Số hóa bởi Trung tâm Học liệu

/>

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 tố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

Số hóa bởi Trung tâm Học liệu

/>

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

GridFTP

Grid File Transfer Protocol

Dịch vụ quản lý và định vị tài
nguyên lưới
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

Số hóa bởi Trung tâm Học liệu

/>

GT

Globus Toolkit

Bộ công cụ được phát triển bởi
Globus Alliance, dùng đê phát
triên các ứng dụng lưới

GTCP

Grid Telecontrol Protocol

Giao thức điều khiển lưới từ xa

GUI

Graphical User Interface

Giao diện người dùng đồ họa

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
tập đồn cơng nghệ máy tính đa
quốc gia có trụ sở tại Armonk,
New York, Mỹ
Giao thức điều khiển truyền tin
trên mạng

IBM

International Business Machines

ICMP

Internetwork Control Message
Protocol


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

Java 2 Enterprise Edittion

Java doanh nghiệp phiên bản 2

JMC

Job Monitor Component

Cấu tạo màn hình cơng việc


LAN

Local Area Network

Mạng cục bộ

MDS

Monitoring and Discovery Service

Giám sát dịch vụ

NCSA

National computer security association

Hiệp hội an ninh máy tính quốc
gia

Số hóa bởi Trung tâm Học liệu

/>

NET

Network

Mạng lưới


NFS

National Science Foundation

Quỹ khoa học quốc gia

NJS

Network Job Supervisors

Mạng lưới giám sát công việc

OGSA

Open Grid Service Architecture

Kiến trúc dịch vụ lưới

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

Remote Method Invocation

Gọi phương thức từ xa

RPC

Remote Procedure Call

Lời gọi hàm xa

SAML

Security Assertion Markup Language

Ngôn ngữ đánh dấu liên kết an
tồn


SDK

Software Development Kit

Tập cơng cụ hỗ trợ phát triển
phần mềm

Số hóa bởi Trung tâm Học liệu

/>

SOAP

Simple Object Acess Protocol

Giao thức truy cập đối tượng
đơn giản

SSL

Secure Socket Layer

Giao thức bảo mật lưới

TCP

Transmission Control Protocol

Giao thức Điều khiển Giao vận


TLS

Transport Layer Security

Giao thức bảo mật tầng giao
vận

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 toàn cầu

Extensible Markup Language

Là một cách thức linh động để
tạo ra các định dạng thông tin
và chia sẻ cả định dạng và dữ
liệu trên web

XML

Số hóa bởi Trung tâm Học liệu

/>

DANH MỤC HÌNH VẼ
Trang
Hình 1.1
Hình 1.2

Mơ hình tính tốn lưới
Tài nguyên lưới dưới quan điểm của người dùng là một khối
thống nhất có được nhờ sự ảo hố.

5
12

Hình 2.1


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

27

Hình 2.2

Mối quan hệ giữa OGSA và OGSI

33

Hình 2.3

Kiến trúc của Alchemi

40

Hình 2.4

Mơ hình hệ thống hướng dịch vụ web

41

Hình 2.5

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 tố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 tốn Dijkstra

66

Hình 3.8
Hình 3.9

Giao diện chương trình trên máy server - thuật tốn tơ màu
đồ thị
Giao diện chương trình trên client - thuật tốn tơ màu đồ thị

69
69


1

LỜI 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 đó là kết quả tất yếu của sự phát triển kèm theo các thiết bị phần
cứng cũng như phần mềm tiện ích.
Sự phát triển đó đã kéo theo rất nhiều các ngành khác phát triển theo, trong đó

có lĩnh vực nghiên cứu khoa học. Tuy công nghệ ngày càng phát triển, tốc độ xử lý các
thiết bị cũng không ngừng tăng cao, nhưng nhu cầu tính tốn của con người là khơng
giới hạn, vì thế tính tốn lưới đã ra đời nhằm đáp ứng nhu cầu này.
Cơng nghệ tính tốn lưới ra đời đánh dấu một bước phát triển mới .Trong lĩnh
vực điện toán hiệu năng cao. Nó cho phép tận dụng năng lực xử lý, lưu trữ cùng các
tài nguyên nhàn rỗi khác để cung cấp một mơi trường tính tốn có năng lực xử lý lớn,
khả năng lưu trữ dồi dào để giải quyết các bài tốn phức tạp - khó có thể giải quyết
được với các công nghệ hiện hành hoặc giải quyết được nhưng với chi phí rất cao trong khoa học, thương mại. Tính tốn lưới giúp tận dụng tối đa tài nguyên, tăng cường
hợp tác, giảm chi phí đầu tư trong khi vẫn cung cấp năng lực tính toán như mong
muốn. Hiện nay, đất nước ta đang thực hiện cơng cuộc cơng nghiệp hố, hiện đại hóa,
trong đó việc rút ngắn sự tụt hậu, phát triển về khoa học công nghệ là yếu tố then chốt
quyết định đến thành công của công cuộc đổi mới. Cấu trúc của luận văn bao gồm các
mục sau:
Chƣơng 1: Giới thiệu về cơng nghệ tính tốn lưới
Chƣơng 2: Phát triển ứng dụng trên mơi trường tính tốn lưới
Chƣơng 3: Giải một số bài tốn đồ thị trên mơi trường lưới
Kết luận, hƣớng phát triển và tài liệu tham khảo được trình bày ở phần cuối
của luận văn.


2

CHƢƠNG 1. GIỚI THIỆU VỀ CƠNG NGHỆ TÍNH TỐN LƢỚI
1.1 Giới thiệu về mơ hình tính tốn lƣới
1.1.1 Q trình phát triển của tính tốn lưới
Cũng như các cơng nghệ tính tốn khác, tính tốn lưới (Grid Computing) ra đời
xuất phát từ nhu cầu tính tốn của con người. Thực tế, ngày càng có nhiều bài tố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
tố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 tố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 tốn).
Cách giải quyết thứ hai này chính là mục tiêu và nguồn gốc u cầu cho sự hình
thành của tính tố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 tốn lưới.
Tính tố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ơ tồ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 tố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
tố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 tố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

truy nhập tới các tài nguyên cho các nhiều người sử dụng. Các thủ tục chia sẻ tài
nguyên đặc biệt giữa các nhóm này đã hình thành phương thức để chuẩn hố những
giao thức cần để trao đổi thơng tin giữa các khu vực hành chính. Cơng nghệ lưới có thể
xem như một mở rộng hoặc một ứng dụng của nền tảng này để tạo nên phương thức
chia sẻ tài nguyên tổng quát [13].
Dự án phi lợi nhuận Seti@home là một trong những nhân tố khoa học nổi tiếng
thúc đẩy việc tạo ra một dự án tính tốn lưới đơn giản bằng cách thu thập tất cả các tài
nguyên CPU chưa được sử dụng (những người theo chủ nghĩa lưới thuần túy cho rằng
CPUi@home thực chất là một ứng dụng tính tốn phân tán bởi nó hầu như khơng thúc

đẩy việc sử dụng bất kỳ một khái niệm lưới nào). Seti@home không phải là dự án đầu
tiên mở đường cho kỹ thuật này. Việc tận dụng tài nguyên CPU trên các máy trong
mạng cục bộ đã bắt đầu từ thập niên 1970 với những dự án phi lợi nhuận như
distributed.net nhưng Seti@home nổi tiếng bởi dự án này được ứng dụng vào rất nhiều
dự án khác như dự đoán cấu trúc protein, nghiên cứu thuốc cho bệnh ung thư, giải các
bài toán phức tạp và dự báo thời tiết. Hầu hết những dự án này đều thực hiện dưới dạng
các tiến trình chạy trên các máy tính cá nhân, xử lý những phần dữ liệu nhỏ khi máy
tính ở trạng thái chờ hoặc sử dụng ít tài nguyên. Nhiều dự án như vậy đã bị kéo dài
hoặc tốn quá nhiều tiền [13].
Vào năm 1997, một trong những dịch vụ tính toán lưới thương mại đầu tiên đã
được Entropia cung cấp, và tới nay có rất nhiều dịch vụ như vậy do các cơng ty và các
phịng thí nghiệm thực hiện. Một điểm khác biệt quan trong giữa các lưới và các dự án
gần giống lưới là trong tính tốn lưới cho phép di trú các nhiệm vụ tính tốn tới tất cả
các nút tính tốn trên lưới để thực thi. Chẳng hạn chương trình xử lý ảnh viễn vọng
Seti@home chứa cả mã xử lý dữ liệu từ kính viễn vọng vô tuyến và mã để lấy dữ liệu
từ cơ sở dữ liệu và trả lại kết quả. Hai đoạn mã này được trộn lẫn vào một chương
trình. Trong lưới, chỉ có các đoạn mã địi hỏi phải truy vấn cơ sở dữ liệu và trả về kết


4

quả thì nằm trên các nút tính tố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 tố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 tố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 tố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 tốn lưới được định nghĩa như sau [6]:
Định nghĩa của Oracle: tính tố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 tốn lưới là một mơi trường tính tố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 ngun tính tốn và 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 tốn lưới: mơi trường tính tố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

được sở hữu và quản lý bởi nhiều tổ chức, cá nhân nhằm cung cấp mơi trường tính
tốn ảo duy nhất với hiệu năng cao cho người sử dụng.

Hình 1.1: Mơ hình tính tốn lưới
Định nghĩa chính thức về một lưới được Ian Foster đưa ra trong bài báo “
What is a Grid?” và trong định nghĩa một lưới có ba đặc điểm chính là:
 Tài ngun tính tốn khơng được quản lý tập trung
 Sử dụng các chuẩn mở
 Có chất lượng dịch vụ tốt.



6

Trên thực tế, tính tốn lưới hấp dẫn đối với các nỗ lực cộng tác nghiên cứu phân
tán theo địa lý phi lợi nhuận như các lưới nghiên sinh tin học của trung tâm ứng dụng
siêu máy tính NCSA chẳng hạn lưới BIRN (lưới ngồi).
Tính tốn lưới cũng hấp dẫn đối với các doanh nghiệp thương mại lớn với các
bài tốn phức tạp, đây là các tổ chức ln cố gắng tận dụng các tài ngun tính tốn
bên trong một cách hiệu quả nhất (lưới nội bộ).
Mỗi tác giả khi đưa ra định nghĩa đều đứng trên một số quan niệm nhất định. Để
có cái nhìn tồn diện về tính tốn lưới, ta khơng đưa ra một định nghĩa cụ thể nào, thay
vào đó chúng ta sẽ xem xét khái niệm tính tốn lưới các đặc trưng sau:
Kích thước lớn: theo số lượng tài nguyên và khoảng cách địa lý giữa chúng
Phân tán: có độ trễ đáng kể trong truyền dữ liệu, tài nguyên trải dài trên các
vùng địa lý khác nhau
Động: các tài nguyên có thể thay đổi khi ứng dụng đang được thực hiện
Hỗn tạp: kiến trúc và tính chất của các nút lưới có thể là hồn tồn khác nhau.
Tài ngun lưới có thể là các máy đơn hoặc mạng con khác nhau
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 tồn bảo mật phức tạp. Cơ chế quản lý tài ngun đ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 tốn lưới
Tính tố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 ngun tính tố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.
2/. Sử dụng CPU song song
Khả năng sử dụng các CPU song song là một đặc tính tuyệt vời của lưới, ngồi
việc hỗ trợ các nhu cầu tính tốn của các nhà khoa học, sức mạnh tính tốn do lưới
cung cấp có thể giúp giải quyết các bài tốn địi hỏi năng lực xử lý lớn trong các ngành
khác như y dược, tính tốn tài chính, kinh tế, khai thác dầu hoả, dự báo thời tiết, công
nghiệp vũ trụ, thiết kế sản phẩm, ... và rất nhiều lĩnh vực khác.
3/. Cho phép hợp tác trên tồn thế giới
Một trong những đóng góp quan trọng của cơng nghệ tính tốn lưới là cho phép
và đơn giản hoá hợp tác chia sẻ, làm việc giữa một cộng đồng rộng lớn trên tồn thế
giới. Các cơng nghệ tính toán phân tán trước đây cũng cho phép hợp tác nhưng chỉ trong
một phạm vi nhỏ, còn lưới cho phép mở rộng trên phạm vi toàn cầu khi đưa ra những



8

chuẩn quan trọng cho phép các hệ thống không đồng dạng làm việc chung với nhau để
tạo nên một hệ thống tính tốn ảo cung cấp rất nhiều dạng tài nguyên khác nhau.
4/. Cho phép chia sẻ, sử dụng tất cả các loại tài nguyên
Không chỉ cho phép chia sẻ các chu kỳ tính tốn, dữ liệu, lưới có thể cho phép
chia sẻ tất cả các loại tài nguyên mà trước đây chưa được chia sẻ, như băng thông mạng,
các thiết bị đặc biệt, phần mềm, bản quyền, các dịch vụ. Ví dụ, nếu một người dùng
muốn tăng băng thơng kết nối Internet của mình lên để thực hiện một ứng dụng khai thác
dữ liệu, ứng dụng đó có thể được gửi đến nhiều máy tính trong lưới có các kết nối
Internet riêng, từ đó băng thơng truy cập Internet của anh ta tăng lên rất nhiều lần.
5/. Tăng tính tin cậy cho các hệ thống máy tính
Hiện nay, các hệ thống tính tốn sử dụng các phần cứng chun dụng, đắt đỏ để
tăng độ tin cậy. Ví dụ, một máy tính có thể sử dụng các bộ vi xử lý đơi, cho phép “cắm
nóng”, để khi có một vi xử lý bị hỏng, có thể thay thế cái khác mà không làm ngưng
hoạt động của hệ thống. Các giải pháp này làm tăng độ tin cậy của hệ thống, tuy nhiên
với chi quá đắt khi phụ kiện đi kèm cũng phải nhân lên. Trong tương lai, các hướng
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í, tồ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 tố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 tố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.
Hướng dữ liệu, đòi hỏi phải thu thập, lưu trữ, phân tích một lượng lớn dữ liệu,
mang tính phân tán.
Cần sự hợp tác, chia sẻ giữa các cộng đồng.
1.1.4 Các dạng tài nguyên trên lưới
1/. Tài nguyên tính toán
Đây là tài nguyên phổ biến nhất, là các chu kỳ tính tốn (computing cycles)
được cung cấp bởi bộ vi xử lý của các thiết bị trong lưới. Các bộ vi xử lý khơng cần
phải cùng loại mà có thể có tốc độ, kiến trúc, chạy phần mềm khác nhau.
Có 3 cách để khai thác tài ngun tính tốn của lưới:
Cách đơn giản nhất là chạy các ứng dụng hiện có trên một nút của lưới thay vì
chạy trên máy tính cục bộ.



10

Thiết kế ứng dụng, tách các công việc thành các phần riêng rẽ để có thể thực
thi song song trên nhiều bộ xử lý khác nhau trên nhiều nút khác nhau của lưới.
Chạy ứng dụng thực thi nhiều lần trên nhiều nút khác nhau trong lưới.
2/. Tài nguyên lƣu trữ
Tài nguyên phổ biến thứ nhì trong lưới là tài nguyên lưu trữ. Mỗi thiết bị trong
lưới thường cung cấp một số dung lượng lưu trữ phục vụ cho việc thực thi ứng dụng
trên lưới. Tài nguyên lưu trữ có thể là bộ nhớ trong, ổ đĩa cứng hoặc các thiết bị lưu trữ
khác. Bộ nhớ trong thường dùng để lưu trữ dữ liệu tạm thời cho ứng dụng, trong khi
các thiết bị lưu trữ ngồi có thể được sử dụng để tăng không gian lưu trữ, tăng hiệu
suất, khả năng chia sẻ và đảm bảo tính tin cậy của dữ liệu.
3/. Tài nguyên đƣờng truyền mạng
Khả năng liên lạc giữa các máy tính phát triển nhanh chóng đã giúp cho cơng
nghệ lưới trở nên hiện thực, do đó đây cũng là một tài nguyên quan trọng. Ở đây bao
gồm việc liên lạc, trao đổi dữ liệu giữa các thành phần trong lưới và giao tiếp giữa lưới
với bên ngoài. Một số cơng việc địi hỏi một lượng dữ liệu lớn nhưng các dữ liệu này
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 ngồ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ổ
chức ảo lại thực hiện chia sẻ tài nguyên của mình để hình thành lưới lớn hơn, tạo thành
một kho tài nguyên khổng lồ.


12

Hình 1.2 Tài nguyên lưới dưới quan điểm của người dùng là một khối thống nhất có
được nhờ sự ảo hố.
1.1.5 So sánh tính tốn lưới với các cơng nghệ khác
1/. World Wide Web (WWW):
WWW hiện nay đang phát triển mạnh mẽ và được sử dụng rộng khắp. Sử dụng
các chuẩn mở và các giao thức mở (TCP, HTTP, XML, SOAP), WWW có thể được sử

dụng để xây dựng các tổ chức ảo tuy nhiên nó thiếu một số đặc tính quan trọng như các
cơ chế chứng thực một lần, ủy nhiệm, các cơ chế phối hợp sự kiện, ....
2/. Các hệ thống tính tốn phân tán (Distributed computing systems)
 Các cơng nghệ tính tốn phân tán hiện tại bao gồm CORBA, J2EE, và
DCOM rất thích hợp cho các ứng dụng phân tán tuy nhiên chúng không cung cấp một
nền tảng phù hợp cho việc chia sẻ tài nguyên giữa các thành viên của tổ chức ảo. Một
số khó khăn có thể kể ra trong việc khai phá tài nguyên, đảm bảo an ninh và xây dựng
động các tổ chức ảo. Thêm nữa việc tương tác giữa các công nghệ này cũng gặp phải


13

khó khăn. Tuy nhiên cũng đã có một số nghiên cứu nhằm mở rộng những công nghệ
này cho môi trường lưới, ví dụ như Java JINI.
 Các nhà cung cấp dịch vụ ứng dụng và dịch vụ lưu trữ (Application and
Storage Service Provider).
 Các nhà cung cấp ứng dụng và dịch vụ lưu trữ thường cung cấp cho người
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 tốn lưới
rất nhiều.
3/. Các hệ thống tính tốn ngang hàng (Peer - to - peer Computing Systems)
Tính tốn ngang hàng cũng là một lĩnh vực của tính tố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 tốn ngang hàng và tính tốn phân tán là:
 Tính tố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 tồ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 ngun 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 tố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 tốn lớn người ta có thể đầu tư cho
cơ sở hạ tầng tính tố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 tốn. Các hướng nghiên cứu trong tính
tốn hiệu năng cao chủ yếu bao gồm: