BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC LẠC HỒNG
***
VŨ ĐÌNH TRUNG
SONG SONG HÓA BÀI TOÁN JSP TRÊN MỘT SỐ MÔI
TRƯỜNG TÍNH TOÁN SONG SONG VÀ PHÂN TÁN
Chuyên ngành: Công nghệ thông tin
Mã ngành: 60 48 02 01
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. TRẦN VĂN LĂNG
Đồng Nai – Năm 2012
-i-
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn thạc sĩ công nghệ thông tin “Song song hóa bài toán
JSP trên môi trường tính toán song song và phân tán” là kết quả của quá trình học tập,
nghiên cứu khoa học độc lập, nghiêm túc.
Các số liệu trong luận văn là trung thực, có nguồn gốc rõ ràng, được trích dẫn
và có tính kế thừa, phát triển từ các số liệu, tạp chí, các công trình nghiên cứu đã
được công bố, trên các website.
Các phương pháp nêu trong luận văn được rút từ những cơ sở lý luận và quá
trình nghiên cứu tìm hiểu.
Đồng Nai, tháng 09 năm 2012
Vũ Đình Trung
-ii-
LỜI CẢM ƠN
Lời đầu tiên tôi xin chân thành cảm ơn đến PGS. TS. Trần Văn Lăng đã tận
tình giúp đỡ tôi trong suốt thời gian học tập vừa qua, và hướng dẫn tôi hoàn thành
đề tài này
Tôi chân thành cảm ơn các thầy cô Khoa Công nghệ thông tin, nơi tôi công
tác và nghiên cứu đã tạo điều kiện và hỗ trợ tôi trong suốt thời gian qua.
Tôi cũng xin chân thành cảm ơn người thân, bạn bè đã giúp đỡ và động viên
tôi trong suốt thời gian học tập cũng như trong thời gian thực hiện luận văn.
Chân thành cảm ơn !
Biên Hòa, ngày 31 tháng 8 năm 2012
Vũ Đình Trung
-iii-
TÓM TẮT
Lập lịch công việc là bài toán đã ra đời từ rất lâu, nhưng đến nay vẫn chưa có
một phương pháp nào giải quyết bài toán lập lịch công việc một cách chính xác với
thời gian ngắn. Những nghiên cứu gần đây theo xu hướng nhắm vào mục đích làm
giảm đến mức thấp nhất thời gian hoàn thành bài toán, ưu điểm lớn của những
hướng đi này là kết quả đạt được với thời gian thấp nhưng lịch trình tìm được chỉ
đạt mức gần đúng trong khả năng chấp nhận được.
Từ mục đích và hạn chế đó tác giả tiến hành nghiên cứu một thuật toán có
thể cải thiện được về mặt thời gian mà kết quả lịch trình cho ra vẫn chính xác.
Qua nhiều nghiên cứu của những công trình trước, thì nhánh cận được xác
định là thuật toán tốt nhất trong các phương pháp tìm kiếm chính xác. Nhưng vấn
đề của thuật toán này là thời gian hoàn thành cho ra kết quả chậm. Do đó thuật toán
nhánh cận là thuật toán được chọn để thực hiện yêu cầu công việc trên. Công việc
cần đạt được tại thời điểm này là tìm ra giải pháp để cải tiến làm giảm thời gian
hoàn thành của thuật toán.
Những năm gần đây tính toán song song đang dần trờ thành xu hướng sử
dụng để cải thiện tốc độ các thuật toán. Vì vậy tác giả đã tiến hành nghiên cứu để
tìm ra phướng án cải tiến thuật toán nhánh cận thành thuật toán song song, và có thể
triển khai trên các môi trường tính toán song song là mục đích cuối cùng của luận
văn.
Cấu trúc luận văn như sau, chương thứ nhất giới thiệu tổng quan về bài toán
lập lịch công việc, chương thứ hai trình bày các môi trường tính toán song song và
các mô hình tính toán song song, chương thứ ba trình bày các nội dung nghiên cứu
và đề xuất các thuật toán song song sẽ sử dụng, chương thứ bốn thử nghiệm các
thuật toán trên môi trường tính toán song song và đánh giá kết quả, cuối cùng là kết
luận.
-iv-
MỤC LỤC
LỜI CAM ĐOAN ..................................................................................................... i
LỜI CẢM ƠN .......................................................................................................... ii
TÓM TẮT ............................................................................................................... iii
MỤC LỤC ............................................................................................................... iv
DANH MỤC CÁC TỪ VIẾT TẮT ......................................................................... v
DANH MỤC BẢNG ............................................................................................... vi
DANH MỤC BIỂU ĐỒ ......................................................................................... vii
DANH MỤC HÌNH .............................................................................................. viii
MỞ ĐẦU .................................................................................................................. 1
1. Đặt vấn đề ................................................................................................ 1
2. Lý do chọn đề tài ............................................................................................ 2
3. Mục tiêu.......................................................................................................... 4
4. Đối tượng nghiên cứu ..................................................................................... 4
5. Nội dung nghiên cứu ....................................................................................... 4
6. Phương pháp nghiên cứu ................................................................................. 5
CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH CÔNG VIỆC .............. 6
1.1. Định nghĩa bài toán lập lịch............................................................................... 6
1.1.1. Mô tả bài toán......................................................................................... 6
1.1.2. Dữ liệu bài toán ...................................................................................... 6
1.1.3. Các loại lịch trình ................................................................................... 6
1.2. Tình hình nghiên cứu thuật toán tuần tự để giải quyết bài toán lập lịch công việc
.......................................................................................................................... 9
1.2.1. Tình hình nghiên cứu trên thế giới .......................................................... 9
1.2.1.1. Phương pháp chính xác .......................................................... 11
1.2.1.2. Phương pháp gần đúng........................................................... 12
1.2.2. Tình hình nghiên cứu trong nước .......................................................... 25
1.2.3. Một số công trình biêu biểu .................................................................. 26
-iv-
1.3. Tình hình nghiên cứu thuật toán song song để giải quyết bài toán lập lịch công
việc ................................................................................................................. 43
1.3.1. Tình hình nghiên cứu ngoài nước ......................................................... 43
1.3.2. Tình hình nghiên cứu trong nước .......................................................... 43
1.3.3. Một số công trình tiêu biểu ................................................................... 44
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT............................................................................51
2.1. Tổng quan về tính toán song song ................................................................... 51
2.1.1. Sự cần thiết của tính toán song song và phân tán .................................. 51
2.1.2. Mô hình máy tính song song ................................................................. 52
2.1.2.1.
Phép phân loại Flynn ........................................................... 52
2.1.2.2.
Chia sẻ bộ nhớ cục bộ .......................................................... 55
2.1.3. Mô hình máy tính phân tán ................................................................... 56
2.1.4. Kỹ thuật lập trình song song ................................................................. 56
2.1.4.1.
Những mô hình lập trình song song ..................................... 56
2.1.4.2.
Phương pháp xây dựng thuật toán song song ....................... 57
2.2. Tổng quan về mô hình lập trình truyền thông điệp – MPI ................................ 58
2.2.1. Giới thiệu mô hình truyền thông điệp ................................................... 58
2.2.2. Lập trình truyền thông điệp – MPI ........................................................ 59
2.2.2.1.
Giới thiệu MPI ..................................................................... 59
2.2.2.2.
Đặc điểm của lập trình với MPI ........................................... 61
2.2.2.3.
Các khái niệm cơ bản........................................................... 62
2.2.2.4.
Cấu trúc chương trình MPI .................................................. 63
2.3. Tổng quan về GPU .......................................................................................... 63
2.3.1. Giới thiệu GPU ....................................................................................... 63
2.3.2. Lịch sử phát triển GPU ........................................................................... 64
2.3.3. Kiến trúc GPU ........................................................................................ 67
2.3.3.1.
Đường ống dẫn đồ họa ......................................................... 67
2.3.3.2.
Tiến hóa của kiến trúc GPU ................................................. 69
2.3.3.3.
Kiến trúc GPU hiện đại ........................................................ 70
2.3.3.4.
Mô hình lập trình trên GPU ................................................. 72
-iv-
CHƯƠNG 3: XÂY DỰNG THUẬT TOÁN NHÁNH CẬN SONG SONG ĐỂ
GIẢI QUYẾT BÀI TOÁN LẬP LỊCH ............................................................................ 74
3.1. Lý do chọn thuật toán
3.2. Thuật toán nhánh cận tuần tự giải quyết bài toán lập lịch công việc................. 74
3.2.1. Giới thiệu thuật toán nhánh cận .............................................................. 74
3.2.2. Mô tả thuật toán nhánh cận tuần tự giải quyết bài toán lập lịch công việc…
........................................................................................................................ 77
3.2.3. Thuật toán nhánh cận cải tiến.................................................................. 85
3.3. Thuật toán nhánh cận song song giải quyết bài toán lập lịch công việc ............ 89
3.3.1. Phương án song song thứ nhất ................................................................ 90
3.3.2. Phương án song song thứ hai .................................................................. 92
3.3.3. Triển khai thuật toán trên môi trường tính toán song song ...................... 93
CHƯƠNG 4: ĐÁNH GIÁ KẾT QUẢ THỰC NGHIỆM ..................................... 97
4.1. Kết quả thử nghiệm trên thuật toán nhánh cận song song giải quyết bài toán lập
lịch trên nhiều máy tính ................................................................................... 97
4.2. Kết quả thử nghiệm thuật toán nhánh cận song song giải quyết bài toán lập lịch
công việc trên môi trường CPU – GPU .......................................................... 99.
KẾT LUẬN ...................................................................................................................102
TÀI LIỆU THAM KHẢO
-v-
DANH MỤC TỪ VIẾT TẮT
CA
Clustering agorithm
d
Due date
f
Fitness
GCA
Genetic clustering algorithm
GPU
Graphics processing unit
JSP
Job shop problem
MIMD
Multiple instruction stream, multiple data stream
MPI
Message passing interface
MISD
Multiple instruction stream, single data stream
L
Lateness
LB
Lower bound
LIS
Language independent specifications
O
Operation
PU
Processor Unit
r
Realease date
SISD
Single instruction stream, single data stream
SIMD
Single instruction stream, multiple data stream
SPMD
Single program multiple data
-vi-
DANH MỤC BẢNG
Bảng 1.1: Bảng mô tả công việc và trình tự thực hiện công việc 1 ......................... 21
Bảng 1.2: Bảng mô tả công việc và trình tự thực hiện công việc 2 ......................... 24
Bảng 1.3: Bảng mô tả công việc và trình tự thực hiện công việc 3 ......................... 27
Bảng 1.4: Bảng mô tả công việc và trình tự thực hiện công việc 4 ......................... 30
Bảng 1.5: Bảng mô tả công việc và trình tự thực hiện công việc 5 ......................... 33
Bảng 1.6: Bảng mô tả sự thay đổi E qua từng giai đoạn ......................................... 38
Bảng 4.1: Bảng mô tả kết quả thực hiện công việc 1.............................................. 97
Bảng 4.2: Bảng mô tả kết quả thực hiện công việc 2............................................ 100
-vii-
DANH MỤC BIỂU ĐỒ
Biểu đồ 1.1: Lịch trình không phải là bán chủ động ............................................... 7
Biểu đồ 1.2: Lịch trình bán chủ động ..................................................................... 7
Biểu đồ 1.3: Biểu đồ biểu diễn công việc khi thay đổi vị trí O32 và O31 .................. 8
Biểu đồ 1.4: Lịch trình chủ động sau khi thay đổi trình tự công đoạn ................... 9
Biểu đồ 1.5: Biểu đồ Gantt mô tả trình tự thực hiện công việc 1 .......................... 22
Biểu đồ 1.6: Biểu đồ Gantt mô tả trình tự thực hiện công việc 2 .......................... 31
Biểu đồ 1.7: Biểu đồ Gantt mô tả trình tự thực hiện công việc 3 ......................... 34
Biểu đồ 1.8: Biểu đồ Gantt mô tả trình tự thực hiện công việc 4 ......................... 35
Biều đồ 1.9:
Biểu đồ Gantt mô tả trình tự thực hiện công việc 5 ......................... 36
Biều đồ 1.10: Biểu đồ Gantt mô tả trình tự thực hiện công việc 6 ......................... 37
Biều đồ 1.11: Biểu đồ Gantt mô tả trình tự thực hiện công việc 7 ......................... 38
-viii-
DANH MỤC HÌNH
Hình 2.1: Mô hình máy tính SISD ........................................................................ 52
Hình 2.2: Mô hình máy tính SIMD ........................................................................ 53
Hình 2.3: Mô hình máy MIMD .............................................................................. 54
Hình 2.4: Máy tính chia sẻ bộ nhớ ......................................................................... 55
Hình 2.5: Máy tính bộ nhớ phân tán ...................................................................... 56
Hình 2.6: Mô hình máy tính phân tán .................................................................... 56
Hình 2.7: Mô hình phân chia chức năng ................................................................ 58
Hình 3.1: Nhánh mở rộng từ nút (2, 2)................................................................... 87
Hình 3.2: Mở rộng nhánh từ (3, 1), LB>minLB ..................................................... 88
Hình 3.3: Mở rộng nhánh từ (3,1), LB
- Xem thêm -