Bài giảng Tính toán song song (Parallel computing) - Phần 1: Tổng quan tính toán song song - Phan Trọng Tiến

Nội dung text: Bài giảng Tính toán song song (Parallel computing) - Phần 1: Tổng quan tính toán song song - Phan Trọng Tiến

1. 5/11/16 TÍNH TOÁN SONG SONG PARALLEL COMPUTING Phan Trọng Tiến Bộ môn CNPM – Khoa CNTT Học Viện Nông nghiệp Việt Nam Email: phantien84@gmail.com Website: 1/1/15 Tổng quan tính toán song song 1 Nội dung q Xử lý song song q Xu hướng phát triển của CPU q Các mô hình lập trình song song qTruy ền thống qD ựa trên dữ liệu 1/1/15 Tổng quan tính toán song song 2 1
2. 5/11/16 Quầy tính tiền ở siêu thị Source: data/news/2009/1/21476/thitruong.jpg Source: Checkouts 1/1/15 Tổng quan tính toán song song 5 Mua vé vào công viên Source: vtc_216925_suoitien.jpg Source: The Old Entrance 1/1/15 Tổng quan tính toán song song 6 3
3. 5/11/16 Ứng dụng xử lý song song q Những bài toán phức tạp ở nhiều lĩnh vực thực tế đòi hỏi cao về tốc độ q Đưa ra quyết định nhanh dựa trên lượng lớn dữ liệu như: qD ự báo thời tiết (dự báo bão, lũ, ) qChu ẩn đoán y khoa qKinh tế - tài chính (mua bán chứng khoán) qQuân sự q q Xây dựng mô hình để tính toán và phân tích trên máy tính 1/1/15 Tổng quan tính toán song song 9 Ứng dụng xử lý song song q Mô phỏng thực tế xem xét đến nhiều yếu tố (tham số) khác nhau è nhiều khả năng/thể hiện của một bài toán è có thể được xử lý song song 1/1/15 Tổng quan tính toán song song 10 5
4. 5/11/16 Sự phát triển của CPU 60 YEARS OF THE TRANSISTOR: 1947 – 2007 1/1/15 Tổng quan tính toán song song 13 Sự phát triển của CPU 60 YEARS OF THE TRANSISTOR: 1947 – 2007 1/1/15 Tổng quan tính toán song song 14 7
5. 5/11/16 Power Wall q Công suất (W) của CPU tỉ lệ với NCV2f qN : số lượng transistor qC : điện dung qV : số vol qf : tần số q Xu hướng ↑N ↓C ↓V (Công nghệ transistor mới) è Sẽ như thế nào nếu ↑f 1/1/15 Tổng quan tính toán song song 17 Power Wall — Mỗi thế hệ mạch in mới (90, 60, 45, 32, 22, 16, 11 nm) — Số lượng transistor/die tăng gấp đôi (↑N) — Kích thước transistors thu nhỏ hơn (↓C) — Sử dụng số vol thấp hơn (↓V). 1/1/15 Tổng quan tính toán song song 18 9
6. 5/11/16 Memory Wall — Độ trễ của DRAM cải thiện không đáng kể è dùng cache của CPU — CPU cache tốn kém do miss (có thể mất 300 xung đồng hồ) — Để giảm miss ½ è tăng gấp 4 lần dung lượng cache (kích thước thực sự tăng!) èNhiều transitor trong CPU được dùng cho việc xử lý truy xuất bộ nhớ này — Cách dễ dàng hơn để tăng băng thông bộ nhớ è Truy xuất bộ nhớ song song è Nhìn chung hiệu năng được nâng cao 1/1/15 Tổng quan tính toán song song 21 Memory Wall q Tỉ lệ miss khi tăng dung lượng cache 1/1/15 Tổng quan tính toán song song 22 11
7. 5/11/16 Máy tính và hiệu năng phần mềm Source [3] 1/1/15 Tổng quan tính toán song song 25 LẬP TRÌNH SONG SONG 1/1/15 Tổng quan tính toán song song 26 13
8. 5/11/16 Tính toán song song là gì? (2) q Ý nghĩa đơn giản nhất, tính toán song song là việc sử dụng đồng thời nhiều tài nguyên máy tính để giải quyết bài toán về tính toán. q Để chạy trên nhiều CPU q Một bài toán được chia thành các phần riêng biệt mà có thể được giải quyết đồng thời. q Mỗi phần được chia nhỏ hơn dưới một dãy các câu lệnh q Các câu lệnh của mỗi phần thực thi đồng thời trên các CPU khác nhau 1/1/15 Tổng quan tính toán song song 29 Tính toán song song: Các tài nguyên q Các nguồn tài nguyên tính toán có thể bao gồm: qM ột máy tính đơn với nhiều bộ vi xử lý (CPU); qM ột máy tính đơn với một hoặc nhiều CPUvà một số tài nguyên chuyên dụng như GPU, FPGA ; qM ột số lượng tuỳ ý các máy tính được kết nối bởi một mạng máy tính; qHo ặc kết hợp của cả hai loại trên. 1/1/15 Tổng quan tính toán song song 30 15
9. 5/11/16 Tính toán song song: để làm gì? (2) q Tính toán song song có thể được coi là “tính toán hiệu năng cao” và là động lực để mô phỏng cho cấc hệ thống phức tạp và giải quyết “các bài lớn” như: qD ự báo thời tiết và khí hậu qCác phản ứng hoá học và hạt nhân qCác bài toán sinh học và gen người qCác hoạt động địa chất qCác thiết bị cơ khí – như chân tay giả cho tàu vũ trụ qCác mạch điện tử qCác quy trình sản xuất 1/1/15 Tổng quan tính toán song song 33 Tính toán song song: để làm gì? (3) q Ngày nay các ứng dụng thương mại đang là động lực thúc đẩy các nhà phát triển máy tính và phần mềm tạo ra các máy tính có tốc độ nhanh hơn. Vì các ứng dụng này yêu cầu xử lý một số lượng lớn dữ liệu và tinh vi phức tạp. Ví dụ như các ứng dụng: q Các cơ sở dữ liệu song song, data mining q Thăm dò dầu khí q Các máy chủ tìm kiếm, các dịch vụ thương mại q Máy tính trợ giúp chuẩn đoán trong y học q Quản lý các tập đoàn quốc gia và đa quốc gia q Đồ hoạ cải tiến và ảo hoá q Video mạng và các công nghệ đa phương tiện q Môi trường làm việc cộng tác q Cuối cùng, tính toán song song là một cố gắng để tối đa hoá những yêuvô hạn nhưng dường như chúng ta vẫn cần thêm thời gian 1/1/15 Tổng quan tính toán song song 34 17
10. 5/11/16 Lập trình song song truyền thống q Lập trình song song không đơn giản q 3 khó khăn chủ đạo qCách suy nghĩ tuần tự qChuy ển đổi từ tuần tự sang song song qKh ả năng mở rộng theo phần cứng q Còn nhiều vấn đề khác như debug, kiểm thử, hiệu năng 1/1/15 Tổng quan tính toán song song 37 Cách suy nghĩ tuần tự q Kiến trúc Von Neumann Source [2] è kết quả có tính tất định (chắc chắn) q Không còn phù hợp khi chuyển sang song song è trạng thái không xác định 1/1/15 Tổng quan tính toán song song 38 19
11. 5/11/16 Chuyển đổi tuần tự sang song song q Hàm tính Fibonacci đệ qui int fib(int n) 1 { song song 1 if (n < 2) 2 return n; else { 3 4 3 int x = fib(n-1); 4 int y = fib(n-2); 5 return x + y; 2 5 } } 1/1/15 Tổng quan tính toán song song 41 Chuyển đổi tuần tự sang song song q Định luật Amdahl 1 Tỉ lệ code chạy song song speedup = càng nhiều è tốc độ tăng 1− p lên càng nhiều lần Source [2] 1/1/15 Tổng quan tính toán song song 42 21
12. 5/11/16 int main(int argc, char *argv[]) typedef struct { { pthread_tKhả nthread;ăng m ở rộng theo int ph input;ần cứng int output; thread_args args; } thread_args; int status; int result; void *thread_func ( void *ptr ) int thread_result; { if (argc input; int n = atoi(argv[1]); ((thread_args *) ptr)->output = if (n < 30) result = fib(n); fib(i); return NULL; else { } args.input = n-1; status = pthread_create(&thread, NULL, thread_func, (void*) &args ); q Tăng tốc 1.5 lần // main can continue executing while the thread executes. q Code cho CPU 2 nhân result = fib(n-2); // Wait for the thread to terminate.q CPU 4 nhân pthread_join(thread, NULL); è Sửa code result += args.output; } printf("Fibonacci of %d is %d.\n", n, result); return 0; } 1/1/15 Tổng quan tính toán song song 45 Lập trình song song kiểu truyền thống q Đặc điểm qTheo mô hình song song về tác vụ qKhông phù hợp với các kiến trúc máy tính đa nhân/đa lõi mới. qCó nhiều vấn đề về lý thuyết chưa khắc phục được trong mô hình lập trình song song theo tác vụ. 1/1/15 Tổng quan tính toán song song 46 23
13. 5/11/16 Lập trình song song dựa trên dữ liệu q Môi trường lập trình: qNgôn ngữ truyền thống (Fortran) qTh ư viện đồ họa (OpenGL, Direct3D) qNgôn ngữ mở rộng (CUDA) qNgôn ngữ xử lý theo kiểu mảng 1/1/15 Tổng quan tính toán song song 49 Ngôn ngữ truyền thống q Bắt nguồn từ lĩnh vực tính toán hiệu năng cao (High Performance Computing) q Sử dụng rộng rãi trong các siêu máy tính q Ngôn ngữ Fortran (Fortran 90, HPF) qVí dụ: Cộng hai ma trận A và B Fortran 90 Fortran 77 C = A + B DO I = 1, N DO J = 1, N C(I, J) = A(I, J) + B(I, J) END DO END DO 1/1/15 Tổng quan tính toán song song 50 25
14. 5/11/16 Thư viện đồ họa – ví dụ float main(float2 texcoord : TEXCOORD0, uniform samplerRECT img) : COLOR { float a, b, c, d; a = f1texRECT(img, texcoord); b = f1texRECT(img, texcoord + float2(0, 1)); c = f1texRECT(img, texcoord + float2(1, 0)); d = f1texRECT(img, texcoord + float2(1, 1)); return max(max(a, b), max(c, d)); } Source [8] 1/1/15 Tổng quan tính toán song song 53 Ngôn ngữ mở rộng q Được phát triển và hỗ trợ bởi nhà sản xuất phần cứng q Mở rộng dựa trên ngôn ngữ quen thuộc q Gồm qXMT-C (PRAM trên Chip) qCUDA - NVIDIA năm 2007 qCAL(Compute Abstraction Layer) – AMD - Radeon 1/1/15 Tổng quan tính toán song song 54 27
15. 5/11/16 Ngôn ngữ xử lý theo kiểu mảng C++ RapidMind Thực hiện tính toán float results[10000]; Array output; //Stream Program chạy trên dữ liệu for(int i = 0; i a; // input 1 result[i] = input1[i] + In b; // input 2 input2[i]; Out c; // output } c = a + b; //thao tác } RM_END; output = prg(input1, input2); 1/1/15 Tổng quan tính toán song song 57 Ngôn ngữ xử lý theo kiểu mảng C++ RapidMind Xuất kết quả const float* results = output.read_data(); for (int i = 0; i < 10000; ++i) for (int i = 0; i < 10000; ++i) { { std::cout << "output[" std::cout << "output[" << i << "] = (" << i << "] = (" << results[i] << ")" << results[i] << ")" << std::endl; << std::endl; } } 1/1/15 Tổng quan tính toán song song 58 29