Download miễn phí Đề tài Nghiên cứu tính toán lưới và thực nghiệm trên một số thuật toán lý thuyết đồ thị



Mục lục
Chương 1. Giới thiệu . 14
1.1. Các khái niệm . 14
1.2. Những thách thức đối với tính toán lưới . 17
Chương 2. Tính toán song song và phân bố . 18
2.1. Khái niệm . 18
2.2. Nền tảng tính toán song song và phân bố . 19
2.2.1. Kiến trúc xửlý song song và phân bố . 19
2.2.2. Tổchức vật lý của các nền tảng song song và phân bố . 26
2.3. Một sốmô hình lập trình song song thông dụng . 27
2.3.1. Mô hình chia sẽkhông gian bộnhớ. 27
2.3.2. Mô hình truyền thông điệp . 28
2.4. Cách thức xây dựng một chương trình song song và phân bố . 30
2.4.1. Các thuật ngữcăn bản. 31
2.4.2. Thiết kếthuật toán song song . 33
2.4.3. Một sốphương pháp tối ưu. 46
2.4.4. Các mô hình thuật toán song song . 50
Chương 3. Các môi trường hỗtrợtính toán lưới . 55
3.1. Giới thiệu. 55
3.2. Các vấn đềkhi lập trình luới . 56
3.2.1. Tính mang chuyển, tính khảthi và khảnăng thích ứng. 56
3.2.2. Khảnăng phát hiện tài nguyên . 57
3.2.3. Hiệu năng . 57
3.2.4. Dung lỗi . 58
3.2.5. Bảo mật . 58
3.2.6. Các siêu mô hình. 59
3.3. Tồng quát vềcác môi trường hỗtrợ . 59
3.3.1. Một sốmôi trường Grid . 59
3.3.2. Những mô hình lập trình và công cụhỗtrợ. 63
3.3.3. Môi trường cài đặt . 69
3.4. Những kỹthuật nâng cao hỗtrợlập trình . 81
3.4.1. Các kỹthuật truyền thống . 81
3.4.2. Các kỹthuật hướng dữliệu. 82
3.4.3. Các kỹthuật suy đoán và tối ưu. 83
3.4.4. Các kỹthuật phân tán. 83
3.4.5. Nhập xuất hướng Grid . 84
3.4.6. Các dịch vụgiao tiếp cấp cao . 84
3.4.7. Bảo mật . 86
3.4.8. Dung lỗi . 86
3.4.9. Các siêu mô hình và hệthống thời gian thực hướng Grid. 88
3.5. Kết luận . 89
Chương 4. Mô hình lập trình truyền thông điệp - MPI. 91
4.1. Các khái niệm cơbản . 92
4.2. Cấu trúc chương trình MPI . 95
4.3. Trao đổi thông tin điểm-điểm . 96
4.3.1. Các thông tin của thông điệp . 97
4.3.2. Các hình thức truyền thông. 97
4.3.3. Giao tiếp blocking. 99
4.3.4. Giao tiếp non-blocking . 103
4.4. Trao đổi thông tin tập hợp. 109
4.4.1. Đồng bộhóa. 109
4.4.2. Di dời dữliệu trong nhóm . 109
4.4.3. Tính toán gộp . 113
4.5. Các kiểu dữliệu . 118
4.5.1. Những kiểu dữliệu đã được định nghĩa . 118
4.5.2. Các kiểu dữliệu bổsung. 119
4.5.3. Pack và UnPack . 123
4.6. Quản lý nhóm và communicator . 124
4.6.1. Tổng quan . 124
4.6.2. Nguyên tắc sửdụng. 126
Chương 5. Thửnghiệm các thuật toán lý thuyết đồthị . 129
5.1. Các khái niệm cơbản . 129
5.2. Dijkstra . 130
5.2.1. Tuần tự . 130
5.2.2. Song song. 134
5.2.3. Thực nghiệm chương trình . 136
5.3. Prim. 138
5.3.1. Tuần tự . 138
5.3.2. Song song. 141
5.3.3. Thực nghiệm chương trình . 143
5.4. Bellman – Ford. 143
5.4.1. Tuần tự . 143
5.4.2. Song song. 147
Chương 6. Kết luận – Hướng phát triển . 151
6.1. Kết luận . 151
6.2. Hướng phát triển. 151
Tài liệu tham khảo. 153


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-04-09-de_tai_nghien_cuu_tinh_toan_luoi_va_thuc_nghiem_tr.4gabmyS1NA.swf /tai-lieu/de-tai-ung-dung-tren-liketly-5845/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

thi,
và bên cạnh đó cũng phải cung cấp khả năng phục hồi và phản ứng khi có lỗi xảy
ra ở cấp độ chương trình. Tại thời điểm đó các công cụ cũng phải bảo đảm cho các
phép tính cũng được thực thi ở cấp độ tối thiểu khi có lỗi xảy ra.
3.2.5. Bảo mật
Chúng ta sẽ còn tiếp tục chứng kiến sự phát triển của tính toán lưới trên
nhiều domain chia sẽ, như là các mạng. Trong khi việc cung cấp một chức năng
chứng thực mạnh giữa hai site là cực kỳ quan trọng, thì bên cạnh đó việc quản lý
chương trình trên nhiều site cũng là điều không đơn giản. Vì thế, một phương
pháp bảo mật có cấp khả năng xác thực người dùng phải được tích hợp vào trong
các mô hình lập trình lưới.
ht
t
p
:
/
/
e
t
r
i
t
h
u
c
.
v
n
Trang 59
3.2.6. Các siêu mô hình
Phương pháp lập trình truyền thống với các ngôn ngữ lập trình cổ điển dựa
vào trình biên dịch để thực hiện việc chuyển đổi giữa 2 mô hình lập trình, như là
giữa ngôn ngữ cấp cao C hay Fortran, với tập các chỉ thị phần cứng thể hiện bởi
việc thực thi tuần tự các hàm trên dữ liệu trong bộ nhớ. Quá trình chuyển đổi này
có thể là sự xây dựng của một số các mô hình liên quan đến ngữ nghĩa của mã
nguồn và sự áp dụng một số chức năng cải tiến như tối ưu, dọn dẹp bộ nhớ, và
kiểm tra phạm vi. Sự kết hợp các siêu mô hình tương tự sẽ góp phần xây dựng
chương trình Grid.
3.3. Tồng quát về các môi trường hỗ trợ
3.3.1. Một số môi trường Grid
Autonomic IBM Computing Toolkit :Là một tập hợp những kỹ thuật,
những công cụ, tài liệu được thiết kế cho người dùng học, thích hợp, và phát triển
JXTA Peer to Peer do những nhà nghiên cứu Sun Microsystems dựa trên giao
những truyền thông API JXTA Peer to Peer
3.3.1.1. NetSolve
NetSole là một ứng dụng client/server đuợc thiết kế để giải quyết những
vấn đề tính toán khoa học trong môi trường phân phối.
ht
t
p
:
/
/
e
t
r
i
t
h
u
c
.
v
n
Trang 60
Agent
Agent
Network of servers Client
Client
MPP servers
Scalar
serverrequest
choice
reply
Hình 3-1 : mô hình NetSolve
Hệ thống Netsolve dựa trên những hệ thống phân phối, được kết nối thông
qua mạng LAN hay WAN. Những chương trình từ máy khách Netsolve có thể
được viết bằng C hay FORTRAN, và sử dụng Web để giao tiếp với Server. Một
server Netsolve có thể sử dụng một số gói phần mềm liên quan đến khoa học để
cung cấp cho những phần mềm tính toán. Những giao tiếp truyền thông bên trong
Netsolve thông qua những socket. Netsolve đáp ứng những khả năng cho việc tìm
kiếm những tài nguyên máy tính trên một mạng máy tính, chọn những tài nguyên
sẵn dùng tốt nhất ,giải quyết một vấn đề ,và trả kết quả cho người sử dụng.
3.3.1.2. Legion
Là một hệ thống trên cơ sở đối tượng được phát triển ở đại học Virginia.
Legion cung cấp kiến trúc phần mềm để hệ thống những máy tính phân phối khắp
nơi, số lượng lớn có thể giao tiếp với nhau một cách dễ dàng. Trong hệ thống
Legion, những áp dụng sau đây.
Mọi thứ là một đối tượng. Những đối tượng đặc trưng cho tất cả các phần
cứng và phần mềm. Mỗi đối tượng là một xử lý hoạt động, đáp ứng những yêu cầu
giải pháp cho những đối tượng khác bên trong hệ thống. Legion định nghĩa một
ht
t
p
:
/
/
e
t
r
i
t
h
u
c
.
v
n
Trang 61
tập API cho việc giao tiếp đối tượng. Nhưng không phải là ngôn ngữ lập trình hay
giao thức truyền thông.
Những lớp quản lý những trường hợp. Mọi đối tượng Legion được định
nghĩa và quản lý bởi chính đối tượng hoạt động .Những lớp đối tượng có những
khả năng như sau : tự tạo một trường hợp thể hiện(instance), lập biểu cho việc
thực thi,làm cho một đối tượng khác hoạt động, hay không hoạt động, và cung cấp
thông tin về trạng thái cho những đối tượng thuộc về các máy tính khác.
Những người dùng có thể định nghĩa thêm các lớp mới. Giống ngôn ngữ
lập trình hướng đối tượng ,người dùng có thể định nghĩa lại hay viết lại những
chức năng của một lớp. Đặc điểm này cho phép những chức năng này có thể thêm,
hay xoá tùy theo nhu cầu của người dùng.
Hệ thống Legion hỗ trợ một tập các dạng đối tượng cốt lõi :
• Những lớp và lớp tự định nghĩa
• Những đối tượng chủ : Những đối tượng chủ là sự trừu tượng hóa của
việc xử lý những tài nguyên, chúng có thể thể hiện một bộ xử lý đơn
hay nhiều máy tính hay mhiều bộ xử lý.
3.3.1.3. Globus
Globus cung cấp một cơ sở hạ tầng phần mềm, làm cho những ứng dụng có thể
quản lý phân phối những tài nguyên tính toán lớn như một máy tính đơn ảo.
Một Grid, là một cở sở hạ tầng phần cứng và phần mềm, cung cấp truy xuất các tài
nguyên khắp nơi dùng cho tính toán cấp cao, dù cho sự phân phối thuộc về địa lý
của tài nguyên và người sử dụng có sự cản trở. Globus cung cấp những dịch vụ cơ
bản và những khả năng được yêu cầu để cấu trúc một mạng tính toán lưới. Bộ
công cụ bao gồm một tập hợp các thành phần bổ sung cho những dịch vụ cơ bản,
chẳng hạn như bảo mật, định vị tài nguyên, quản lý tài nguyên, và dịch vụ truyền
thông.
Mạng tính toán lưới được hỗ trợ một số lượng lớn những ứng dụng và mô
hình lập trình, đó là điều thiết yếu.Vì thế, việc cung cấp hơn một mô hình lập trình
ht
t
p
:
/
/
e
t
r
i
t
h
u
c
.
v
n
Trang 62
chuẩn, chẳng hạn như mô hình lập trình hướng đối tượng là điều cần thiết yếu.
Globus cung cấp một số dịch vụ cho phép những nhà phát triển công cụ đặc biệt
hay những ứng dụng có thể sử dụng để tạo ra những yêu cầu cụ thể cho chính họ.
Phương pháp này chỉ khả thi khi những dịch vụ có sự khác biệt và được định
nghĩa tốt thông qua những tập APIcủa nó, Globus được kiến tạo như một tầng kiến
trúc với những dịch vụ cấp cao được xây dựng trên những dịch vụ cốt lõi ở tầng
thấp hơn. Bộ công cụ Globus được phân thành những mô đun ,và một ứng dụng có
thể khai thác những đặc điểm này của từng mô đun của Globus, chẳng hạn như sự
quản lý tài nguyên hay hạ tầng thông tin,mà không sử dụng những thư viện truyền
thông của Globus. Bộ công cụ Globus hỗ trợ những dịch vụ sau :
• GSI(Grid Security Infrastructure) :kiến trúc bảo mật
• GridFTP :giao thức truyền tập tin
• GRAM (Globus Resource Allocation Manager) :quản lý các tài nguyên trên
môi trường Grid.
• Metacomputing Directory Service
• Globus Access to Secondary Storage
• data catalogue and replica management
• Advanced Resource Reservation and Allocatoin(GARA)
ht
t
p
:
/
/
e
t
r
i
t
h
u
c
.
v
n
Trang 63
Hình 3-2 : Các thành phần của Globus
Globus có thể được nhìn nhận như một hệ thống cở bản cho tính toán lưới,
ngoài việc cung cấp cho nhà phát triển ứng dụng một tập thư viện API đặc trưng
cho các dịch vụ Globus cung cấp. Globus còn cung cấp cho những nhà phát triển
ứng dụng một phương tiện hiện thực cho việc bổ sung các dịch vụ để cung ứng
cho một môi trường thực thi ứng dụng trên môt vùng rộng lớn.
Globus được chúng tui nghiên cứu kỹ và đã cài đặt phiên bản Globus 3.2
trên máy đơn, nhưng không...

---