Download miễn phí Bài giàng Tính toán song song



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ằngliệ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


/file/d/0Bz7Zv9 ... sp=sharing

---