GIÁO TRÌNH: TÍNH TOÁN SONG SONG

tổ chức bộ vi xử lý trong các máy tính song song theo 9 cách khác nhau, bao gồm: tổ chức các bộ vi xử lý theo hình mạng lười, theo hình cây. theo hình siêu cây. hình tháp, hình siêu khối, các chu trình hướng khối, hoán vị đổi chổ. Mỗi cách thức tổ chức được đánh giá ưu điểm nhược điểm qua các tiêu chí:đường kích, độ rộng phân đôi...
Nội dung trích xuất từ tài liệu:
GIÁO TRÌNH: TÍNH TOÁN SONG SONG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG TÍNH TOÁN SONG SONG (Dùng cho sinh viên hệ đào tạo đại học từ xa) Lưu hành nội bộ HÀ NỘI - 2007 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG TÍNH TOÁN SONG SONG Biên soạn : THS. PHẠM VĂN CƯỜNG Bài giàng TÍNH TOÁN SONG SONG Biên soạn: Phạm Văn Cường Khoa CNTT1- Học viện Công nghệ BCVT Email: pcuongcntt@yahoo.com 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ế ...