Link tải luận văn miễn phí cho ae
Mục lục
CHƯƠNG 1 : CÁC KIẾN TRÚC SONG SONG.........................................................................5
1.1 Tổng quan về tính toán song song ......................................................................................5
1.1.1 Nhu cầu tính toán............................................................................................................5
1.1.2 Lịch sử phát triển............................................................................................................7
1.1.3 Các thuật ngữ..................................................................................................................9
1.1.4 Các xu thế xây dựng máy tính ........................................................................................9
1.2 Các kiến trúc song song.....................................................................................................10
1.2.1 Máy tính một dòng lệnh, một dòng dữ liệu (SISD)......................................................11
1.2.2 Bộ nhớ chia xẻ (shared memory) và bộ nhớ phân tán (distributed memory). .............13
1.2.3 Máy tính một dòng lệnh, nhiểu dòng dữ liệu (SIMD) ..................................................14
1.2.4 Máy tính nhiều dòng lệnh, một dòng dữ liệu (MISD) ..................................................17
1.2.5 Máy tính nhiều dòng lệnh, nhiểu dòng dữ liệu (MIMD) ..............................................19
1.2.6 Hiệu suất của Máy tính song song................................................................................20
1.3 Tổ chức các bộ vi xử lý ......................................................................................................21
1.3.1 Mạng hình lưới (Mesh).................................................................................................21
1.3.2 Mạng hình cây nhị phân (Binary Tree Networks) ........................................................22
1.3.3 Mạng hình siêu cây (Hypertree networks)....................................................................22
1.3.4 Mạng hình tháp (Pyramid networks) ............................................................................23
1.3.5 Mạng hình bướm (Butterfly networks).........................................................................24
1.3.6 Mạng hình siêu khối (Hypercube networks)................................................................25
1.3.7 Mạng các chu trình hướng kết nối khối (Cube-Connected Cycles networks) .............26
1.3.8 Mạng hoán vị di chuyển (Shuffle-exchange networks)...............................................27
1.3.9 Mạng de Bruijn.............................................................................................................29
1.3.10 Tổng kết về tổ chức các bộ vi xử lý............................................................................29
1.4 Các hệ thống mảng bộ xử lý, đa bộ xử lý, và đa máy tính..............................................30
1.4.1 Hệ thống mảng bộ vi xử lý (processor arrays)..............................................................30
1.4.2 Máy tính đa bộ xử lý (Multiprocessors) .......................................................................35
1.4.3 Hệ thống đa máy tính (Multicomputers) ......................................................................39
1.5 Kết chương..........................................................................................................................41
1.6 Câu hỏi và bài tập ..............................................................................................................42
1.6.1 Câu hỏi..........................................................................................................................42
1.6.2 Bài tập...........................................................................................................................44
CHƯƠNG 2 : CÁC THUẬT TOÁN SONG SONG ..................................................................45
2.1 Mô hình PRAM.................................................................................................................45
2.1.1 Mô hình xử lý tuần tự ...................................................................................................46
2.1.2 Mô hình tính toán song song PRAM ............................................................................46
2.1.3 Một số thuật toán PRAM..............................................................................................48
2.2 Các thuật toán song song nhân hai ma trận ...................................................................56
2.2.1 Thuật toán nhân ma trận tuần tự...................................................................................57
2.2.2 Thuật toán nhân ma trận trên máy SIMD với các bộ xử lý được tổ chức theo mạng
hình lưới hai chiều (2-D Mesh SIMD). .................................................................................57
2.2.3 Thuật toán nhân ma trận trên máy SIMD với các bộ xử lý được tổ chức theo mạng
hình siêu khối (Hypercube SIMD). .......................................................................................61
2.2.4 Thuật toán nhân ma trận trên máy đa bộ xử lý. ............................................................64
2.3 Các thuật toán sắp xếp song song..............................................................................67
2.3.1 Sắp xếp bằng liệt kê (enumeration sort) và cận dưới (lower bounds) của sắp xếp song
song........................................................................................................................................67
2.3.2 Sắp xếp song song đổi chỗ chẵn lẻ (odd-even transposition) ......................................69
2.3.3 Sắp xếp song song trộn bitonic (bitonic merge) ...........................................................71
2.3.4 Sắp xếp song song tựa trên Quicksort ..........................................................................83
2.4 Thuật toán tìm kiếm song song trên danh bạ...........................................................88
2.4.1 Độ phức tạp của tìm kiếm song song. ..................................................................88
2.4.2 Tìm kiếm song song trên máy tính đa bộ xử lý....................................................89
2.5 Thuật toán song song trên đồ thị...............................................................................97
2.5.1 Thuật toán song song tìm đường đi ngắn nhất .....................................................97
2.5.2 Thuật toán song song tìm cây khung bé nhất .....................................................102
2.7 Kết chương ................................................................................................................107
2.8 Câu hỏi và bài tập .....................................................................................................108
2.8.1 Câu hỏi........................................................................................................................108
2.8.2 Bài tập.........................................................................................................................109
Chương 2: Các vấn đề của hệ thống tính toán song song LT8/BT2
2.1 Hiệu suất của hệ thống xử lý song song.
2.2 Tốc độ (speedup) và hiệu quả (efficiency) của xử lý song song
2.2.1 Tốc độ (speedup) của xử lý song song
2.2.2 Hiệu quả (efficiency) của xử lý song song
2.2.3 Định luật Amdhal và Gustafson-Barsis về tốc độ và hiệu quả của xử lý song song.
2.3 Ánh xạ dữ liệu trên máy tính song song
2.3.1 Ánh xạ dữ liệu lên các mảng bộ vi xử lý (processor arrays).
2.3.2 Ánh xạ dữ liệu lên hệ thống nhiều máy tính (multicomputers).
2.4 Vấn đề cân bằng tải động trên hệ thống nhiều máy tính (multicomputers)
2.5 Vấn đề lập lịch biểu trên hệ thống nhiều máy tính (multicomputers)
2.5.1 Giải thuật Graham ‘s List Scheduling
2.5.2 Giải thuật Coffman-Graham Scheduling
2.5.3 Các mô hình đơn định và không đơn định.
2.6 Vấn đề deadlocks
Chương 3: Lập trình song song LT9/TH4/KT1
3.1 Cơ bản về giao tiếp bằng phương pháp trao đổi thông điệp (message passing)
3.1.1 Trao đổi thông điệp như một mô hình lập trình
3.1.2 Cơ chế trao đổi thông điệp
3.1.3 Tiếp cận đến một ngôn ngữ cho lập trình song song
3.2 Thư viện giao diện trao đổi thông điệp (Message Passing Interface – MPI)
3.2.1 Giới thiệu về MPI
3.2.2 Lập trình song song bằng ngôn ngữ C và thư viện MPI
3.2.3 Một số kỹ thuật truyền thông: broadcast, scatter, gather, blocking message passing...
3.3 Máy ảo song song (Parallel Virtual Machine-PVM)
4.4 Thiết kế và xây dựng một chương trình (giải một bài toán (NP-complete) sử dụng MPI và C.
Thực hành: Xây dựng và chạy chương trình sử dụng C và MPI
/file/d/0Bz7Zv9 ... sp=sharing
