Link tải luận văn miễn phí cho ae Kết nối
Luận văn ThS. Bảo đảm toán học cho máy tính và hệ thống tính toán -- Trường Đại học Khoa học Tự nhiên. Đại học Quốc gia Hà Nội, 2011
Tổng quan về tính toán song song: các mô hình tính toán song song; một số kỹ thuật phân rã trong tính toán song song; kỹ thuật song song hóa tính toán dựa trên phân đoạn dãy các nghiệm của bài toán. Nghiên cứu bài toán dãy bị chặn: bài toán dãy bị chặn; thuật toán tìm các dạy bị chặn; song song hóa thuật toán tìm các dạy bị chặn. Nghiên cứu, áp dụng cho một bài toán tổ hợp: bài toán hoán vị; bài toán tập con; bài toán phân hoạch
CHƯƠNG 1. TỔNG QUAN VỀ TÍNH TOÁN SONG SONG................. 8
1.1 CÁC MÔ HÌNH TÍNH TOÁN SONG SONG ....................................... 8
1.1.1 Mô hình SISD (Single Instruction, Single Data) ........................ 8
1.1.2 Mô hình SIMD (Single Instruction, Multiple Data).................... 9
1.1.3 Mô hình MISD (Multiple Instruction, Single Data)...................... 9
1.1.4 Mô hình MIMD (Multiple Instruction, Multiple Data)............... 10
1.2 MỘT SỐ KỸ THUẬT PHÂN RÃ TRONG TÍNH TOÁN SONG
SONG ........................................................................................................ 11
1.2.1 Phân rã đệ quy (recursive decomposition) ................................. 12
1.2.2 Phân rã dữ liệu (data-decomposition)........................................ 13
2.2.3 Phân rã thăm dò (exploratory decomposition) ........................... 17
1.3 KỸ THUẬT SONG SONG HÓA TÍNH TOÁN DỰA TRÊN PHÂN
ĐOẠN DÃY CÁC NGHIỆM CỦA BÀI TOÁN ........................................ 20
CHƯƠNG 2. BÀI TOÁN DÃY BỊ CHẶN .............................................. 22
2.1 BÀI TOÁN DÃY BỊ CHẶN................................................................ 22
2.2 THUẬT TOÁN TÌM CÁC DÃY BỊ CHẶN ........................................ 23
2.3 SONG SONG HÓA THUẬT TOÁN TÌM CÁC DÃY BỊ CHẶN........ 25
CHƯƠNG 3. ÁP DỤNG CHO MỘT SỐ BÀI TOÁN TỔ HỢP ............ 28
3.1 BÀI TOÁN HOÁN VỊ......................................................................... 28
3.1.1 Bài toán hoán vị....................................................................... 28
3.1.2 Thuật toán sinh các hoán vị .................................................... 29
3.1.3 Song song hóa thuật toán sinh các hoán vị............................. 36
3.1.4 Ứng dụng của bài toán hoán vị ............................................... 37
3.2 BÀI TOÁN TẬP CON ........................................................................ 39
3.2.1 Bài toán tập con....................................................................... 40
3.2.2 Thuật toán sinh các tập con..................................................... 41
3.2.3 Song song hóa thuật toán sinh các tập con ............................. 42
3.2.4 Ứng dụng của bài toán tập con................................................ 42
3.3 BÀI TOÁN PHÂN HOẠCH................................................................ 43
3.3.1 Bài toán phân hoạch................................................................ 43
3.3.2 Thuật toán tìm các phân hoạch............................................... 47
3.3.3 Song song hóa thuật toán tìm các phân hoạch........................ 49
3.3.4 Ứng dụng của bài toán phân hoạch ........................................ 49
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................... 51
TÀI LIỆU THAM KHẢO........................................................................ 53
PHỤ LỤC.................................................................................................. 54
PHỤ LỤC 1. BÀI TOÁN DÃY BỊ CHẶN................................................. 54
1. Chương trình cho thuật toán tuần tự ........................................... 54
2. Chương trình cho thuật toán khi phân đoạn nghiệm .................. 55
PHỤ LỤC 2. BÀI TOÁN HOÁN VỊ.......................................................... 58
1. Chương trình cho thuật toán tuần tự ........................................... 58
2. Chương trình cho thuật toán khi phân đoạn nghiệm .................. 59
PHỤ LỤC 3. BÀI TOÁN TẬP CON.......................................................... 62
1. Chương trình cho thuật toán tuần tự ........................................... 62
2. Chương trình cho thuật toán khi phân đoạn nghiệm .................. 63
PHỤ LỤC 4. BÀI TOÁN PHÂN HOẠCH................................................. 65
1. Chương trình cho thuật toán tuần tự ........................................... 65
2. Chương trình cho thuật toán khi phân đoạn nghiệm .................. 66
MỞ ĐẦU
1. LÝ DO CHỌN ĐỀ TÀI
Trong tính toán truyền thống, phần mềm máy tính được viết cho tính
toán tuần tự. Để giải quyết một bài toán, một thuật toán được xây dựng và
thực hiện như một chuỗi tuần tự các lệnh. Các lệnh này được thực hiện trong
bộ xử lý trung tâm (CPU) của máy tính. Tại một thời điểm, chỉ có một lệnh
được thực hiện. Sau khi lệnh trước kết thúc thì lệnh tiếp theo mới được thực
hiện. Quá trình thực hiện các lệnh được thể hiện như hình dưới đây.
Hình 1. Mô hình tính toán tuần tự
Tính toán song song là một hình thức tính toán, trong đó nhiều tính toán
được thực hiện đồng thời. Tính toán song song hoạt động trên nguyên tắc một
bài toán lớn được chia thành các bài toán nhỏ hơn, sau đó các bài toán này
được giải quyết đồng thời. Song song đã được sử dụng nhiều năm và trong
những năm gần đây tính toán song song đã trở thành mô hình thống trị trong
kiến trúc máy tính, chủ yếu dưới hình thức các bộ đa xử lý (multi-processors).
Vậy, tại sao phải tính toán song song? Mặc dù tốc độ xử lý của các bộ
xử lý tăng lên nhiều, nhưng do giới hạn về vật lý nên khả năng tính toán của
chúng không thể tăng mãi được. Điều này dẫn tới là muốn tăng được khả năng
tính toán của các hệ thống máy tính thì phải khai thác được khả năng xử lý
song song của chúng.
Nhiều bài toán với số lượng tính toán rất lớn như bài toán mô phỏng
thời tiết, bài toán tạo hình trong y học hay phân tích mật mã… không thể giải
được trong một khoảng thời gian hợp lý nếu sử dụng tính toán tuần tự - ngay
cả khi ta thực hiện trên các siêu máy tính, do đó đòi hỏi phải sử dụng những
hệ thống đa bộ xử lý và xử lý song song.
Để song song hóa tính toán, chúng ta có thể chia bài toán thành các bài
toán nhỏ hơn rồi giải quyết song song các bài toán đó như chiến lược chia để
trị. hay có thể chia nhỏ dữ liệu của bài toán rồi giải quyết song song theo
từng phần. Tuy nhiên, với các bài toán tổ hợp thì hai phương pháp trên là
không khả thi. Với một hướng tiếp cận mới, song song hóa tính toán dựa trên
phân đoạn dãy các nghiệm của bài toán, chúng tui sẽ giải quyết được vấn đề
song song hóa các thuật toán tổ hợp.
2. PHẠM VI NGHIÊN CỨU
Trong phạm vi một luận văn thạc sĩ, đề tài tập trung nghiên cứu cơ sở
lý thuyết và ứng dụng. Trên cơ sở đó, tiến hành phân đoạn dãy nghiệm cho
một số bài toán tổ hợp tiêu biểu.
3. PHƯƠNG PHÁP NGHIÊN CỨU
- Phương pháp nghiên cứu tài liệu
- Phương pháp phân tích
- Phương pháp tổng hợp
- Phương pháp thực nghiệm
- Phương pháp lập trình
Ab8u2KIAmldKW0w
