Bài giảng Tính toán song song (Parallel computing): Chương 1 - TS. Ngô Văn Thanh

Chương 1 - Các kiến trúc song song. Nội dung trình bày trong chương 1 gồm có: Tổng quan về tính toán song song, các kiến trúc song song đồng bộ, các kiến trúc song song không đồng bộ, tổ chức các bộ vi xử lý, các mảng bộ vi xử lý (processor arrays), máy tính nhiều bộ vi xử lý (multiprocessor), hệ thống nhiều máy tính (Multicomputers), giới thiệu về máy tính CM-200 (Connection Machine 200 by Thinking Machine Corp).
Nội dung trích xuất từ tài liệu:
Bài giảng Tính toán song song (Parallel computing): Chương 1 - TS. Ngô Văn Thanh TS. Ngô Văn Thanh, Viện Vật lý.Chuyên ngành : Công nghệ thông tin. Michael J. Quinn. Parallel Computing, theory and practice, 2nd edition. Oregon State University, USA. McGraw Hill Inc. Dimitri P. Bertsekas and John N. Tsitsiklis. Parallel and Distributed Computation, Numerical Methods. Massachusets Institute of Technology. Prentice Hall Press. Enrico P. The lecture notes on Parallel Computing (CS 491). Computer Science Dept. New Mexico State University, USA. Spring 2004. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Strein. Introduction to Algorithms, 2nd edition. Massachusets Institute of Technology. The MIT Press. David A. Patterson and John L. Hennessy. Computer Organization & Design, the hardware/software interface, 2nd edition. Stanford University & University of California at Berkeley, 2002. Charles Leiserson. The lecture notes on Theory of Parallel Systems. Massachusets Institute of Technology, Open Course Ware. www.ocw.mit.edu Michel Cosnard & Denis Trystram, Parallel Algorithms and Architectures. International Thomson Computer Press. 1995. @2009, Ngô Văn Thanh - Viện Vật LýChương 1: Các kiến trúc song song 1.1 Tổng quan về tính toán song song 1.2 Các kiến trúc song song đồng bộ 1.2.1 Máy tính một dòng lệnh, một dòng dữ liệu (SISD) 1.2.2 Máy tính một dòng lệnh, nhiều dòng dữ liệu (SIMD) 1.2.3 Máy tính vector. 1.3 Các kiến trúc song song không đồng bộ 1.3.1 Máy tính nhiều dòng lệnh, một dòng dữ liệu (MISD hay Reduction). 1.3.2 Máy tính nhiều dòng lệnh, nhiều dòng dữ liệu (MIMD) 1.4 Tổ chức các bộ vi xử lý 1.5 Các mảng bộ vi xử lý (processor arrays). 1.6 Máy tính nhiều bộ vi xử lý (multiprocessor) 1.6.1 Nhiều bộ vi xử lý truy cập bộ nhớ đồng bộ (Uniform Memory Access Multiprocessors). 1.6.2 Nhiều bộ vi xử lý truy cập bộ nhớ không đồng bộ (Non Uniform Memory Access) 1.7 Hệ thống nhiều máy tính (Multicomputers). 1.8 Giới thiệu về máy tính CM-200 (Connection Machine 200 by Thinking Machine Corp). @2009, Ngô Văn Thanh - Viện Vật LýChương 1: Các kiến trúc song song1.1 Tổng quan về tính toán song song Hạn chế của máy tính Tốc độ của bộ vi xử lý của máy tính (processor). Dung lượng của bộ nhớ RAM. Giải quyết những bài toán lớn mất nhiều thời gian. Tính toán song song Phần cứng:  Siêu máy tính: SIMD, MIMD máy tính có nhiều bộ vi xử lý (multi-processor), có nhiều lõi trong một bộ vi xử lý (multi-core).  Cụm máy tính (cluster): kết nối các máy tính PC với nhau tạo thành cụm máy tính, các máy tính giao tiếp với nhau thông qua mạng.  Máy tính ảo song song (PVM = parallel vitual machine): Chia một CPU thành nhiều CPU ảo mà nó có khả năng hoạt động tương tự như các CPU thực thụ. @2009, Ngô Văn Thanh - Viện Vật Lý Phần mềm lập trình (C/C++ và Fortran):  OpenMP : chỉ hoạt động trên hệ máy tính chia sẻ bộ nhớ (shared memory), có kiến trúc kiểu SIMD.  MPI (message passing interface): thực hiện các câu lệnh song song trên các CPU khác nhau bằng giao thức gửi và nhận các thông điệp.  High performance (HPF/HPC): tính toán song song giữa các phần tử của các mảng dữ liệu. Hay nói cách khác, các mảng dữ liệu được phân bố trên các CPU khác nhau (Data distribution). MPI và HPF/HPC đều có thể sử dụng trên cả máy tính multi-processor (SIMD /MIMD), cụm máy tính và cả trên máy tính ảo song song. Thuật toán song song  Thuật toán song song nhân hai ma trận.  Thuật toán sắp xếp.  Thuật toán song song tìm kiếm tổ hợp. @2009, Ngô Văn Thanh - Viện Vật Lý1.2 Các kiến trúc song song đồng bộ1.2.1 Máy tính một dòng lệnh, một dòng dữ liệu (SISD - Single Instruction - Single Data) Máy tính tuần tự (scalar computer): chỉ thực hiện một chỉ thị (một dòng lệnh) trong mỗi chu trình.  Ví dụ về phép tính cộng hai số a và b: cần phải thực hiện 5 chu trình. Nhận Đọc giá Đọc giá Tính Ghi kết chỉ thị trị a trị b a+b quả  Trong thực tế thì mỗi một chu trình được kết hợp bởi nhiều chu trình con.  Máy tính loại SISD là máy tính PC thông thường, chỉ có duy nhất một bộ vi xử lý. Không có cấu trúc song song và cũng không có dữ liệu song song. @2009, Ngô Văn Thanh - Viện Vật Lý Kênh tuyến (pipeline): chia các bước tính khác nhau thành các đơn vị chức năng để đưa ra kết quả trung g ...