1 GHz * 1 IPC = 1 GFLOPS 1 GHz * 4 IPC = 4 GFLOPS 1 GHz * 4 IPC * 4 cores = 16 GFLOPS Show Single Core SIMD SMPProcessor Trendspclock frequency won't increase, we will get more cores,larger SIMD instructionspnormal programs use a single core(and SIMD instructions)p"Free Lunch is over" 3 GHz * 16 SIMD * 16 cores = 768 GFLOPS Multi-coreWhy Parallel Programming?3 GHz * 16 SIMD * 1 cores = 48 GFLOPS 3 GHz * 1 SIMD * 1 cores = 3 GFLOPS 4 GHz * 4 SIMD * 1 cores = 16 GFLOPS Single core2 GHz * 1 SIMD * 1 cores = 2 GFLOPS 0 GHz * 1 SIMD * 1 cores = 0 GFLOPS Parallel Programming Models
OpenMP API
pragma omp parallel { foo(); /* .... */ } ... C ....pragma omp parallel { ... D ... } ... E ... Call foo() Call foo() Call foo() Call foo() A B C D E fork joinOpenMP Execution ModelCPU CPU CPU CPUBUSuMultiple cores share main memoryuThreads executed in each core(CPU) communicate with each other by accessing shared data inmain memory. Shared-memory Multicore Processorparallel Directivep starts parallel executionp creates a thread teamp by default, all variables are shared among threads int x = 100; pragma omp parallel { int my_thread_id = omp_get_thread_num(); printf("[%d] x is %d¥n", my_thread_id, x); if (my_thread_id == 0) x = 0; } printf("x is %d¥n", x); Master Thread 0 Thread 1 Thread N Master Parallel Region Thread Team Parallel RegionRunning OpenMP Code[ jinpil]$ gcc -O3 -fopenmp test -o test [ jinpil]$ OMP_NUM_THREADS= [ jinpil]$ ./test [0] x is 100 x is 0 [ jinpil]$ OMP_NUM_THREADS= [ jinpil]$ ./test [0] x is 100 [2] x is 0 [3] x is 0 [1] x is 0 x is 0 [ jinpil]$ ./test [0] x is 100 [2] x is 0 [3] x is 100 [1] x is 100 x is 0 int x = 100; pragma omp parallel { int my_thread_id = omp_get_thread_num(); printf("[%d] x is %d¥n", my_thread_id, x); if (my_thread_id == 0) x = 0; } printf("x is %d¥n", x);Data Race in Parallel Executionp all threads do their workloads concurrentlyp it can cause some unexpectable results int x = 100; pragma omp parallel { int my_thread_id = omp_get_thread_num(); printf("[%d] x is %d¥n", my_thread_id, x); if (my_thread_id == 0) x = 0; } printf("x is %d¥n", x); Master Thread 0 Thread 1 Thread 2 Master 1 2 1 1 2 1 100 100 0 0 [ jinpil]$ ./test [0] x is 100 [1] x is 100 [2] x is 0 x is 0Another Data Race Problemp be careful when writing shares variablesp because mostly statements are not atomic ####### p each statement is divided into several instructions int sum = 0; pragma omp parallel {pragma omp critical { sum++; } } printf("sum is %d¥n", sum); Master Thread 0 Thread 1 Thread 2 Master [ jinpil]$ OMP_NUM_THREADS= [ jinpil]$ ./test sum is 128 [ jinpil]$ ./test sum is 128 R 0 W 1 R 1 W 2 R 2 W 3Bài tập lớn Lập trình song song Đề tài : Áp dụng tính toán song song vào giải quyết bài toán tìm đi ngắn nhất xuất phát từ một đỉnh sử dụng giải thuật Dijkstra. Giảng viên hướng dẫn : Ths. Nguyễn Tiến Dũng Sinh viên thực hiện : 1- Nguyễn Thị Thúy SHSV:20082599 2- Nguyễn Đình Hưởng SHSV:20081338 Lớp : Hệ Thống Thông Tin K53 Hà Nội tháng 11/2011 Mục lục I- II- III- IV- Tổng quan về mô hình lập trình song song OpenMP 1- Giới thiệu về mô hình OpenMP 2- Mô hình lập trình song song OpenMP 3- Một số chỉ thị trong OpenMP 4- Một số mệnh đề thường gặp trong OpenMP 5- Thư viện và các biến môi trường Bài toán tìm đường đi ngắn nhất 1- Các khái niệm mở đầu 2- Bài toán đường đi ngắn nhất xuất phát từ một đỉnh Giải thuật Dijkstra 1- Thuật toán Dijkstra 2- Tính đúng đắn của thuật toán Dijkstra 3- Độ phức tạp của thuật toán Dijkstra Kết quả thực nghiệm 1- Cài đặt bằng lập trình tuần tự 2- Cài đặt bằng lập trình song song 3- Kết luận. I- Tổng quan về mô hình lập trình song song OpenMP 1- Giới thiệu về mô hình OpenMP a- OpenMP là gì? Theo Wikipedia: OpenMP- Open Multi-Processing là một giao diện lập trình ứng dụng API (Application programming interface) hỗ trợ đa nền tảng dựa trên cấu trúc chia sẻ bộ nhớ chung, đa ngôn ngữ lập trình C, C++, Fortran và hầu hết các bộ kiến trúc vi xử lý và hệ điều hành Linux, Unix, Mac OS X, nền tảng Microsoft Windows. Nó bao gồm : Các chỉ thị biên dịch (Compiler directives) Các thư viện Runtime (Library rountines) Các biến môi trường (Environment variables) b- Lịch sử OpenMP OpenMP Architecture Review Board(ARB) được công bố như một giao diện lập trình ứng dụng đầu tiên, phiên bản 1.0 ra đời vào tháng 10 năm 1997 cho Fortran. Tháng 10 năm sau đó là phiên bản cho C/C++. Năm 2000 phiên bản 2.0 cho Fortran và năm 2002 là phiên bản 2.0 cho C/C++. Năm 2005 phiên bản 2.5 cho C/C++/Fortran ra đời. Tháng 5-2008 phiên bản 3.0 ra đời bao gồm thêm nhiều tính năng mới các khái niệm về task và nhiện vụ của task. 2- Mô hình lập trình song song OpenMP OpenMP sử dụng mô hình Fork-Join để thực thi song song Trong mô hình này tất cả các chương trình song song đều bắt đầu với việc xử lý đơn bởi một luồng chủ (master thread). Luồng chủ này sẽ thực thi một cách tuần tự cho tới khi bắt gặp vùng song song (parallel region) đầu tiên . FORK: Có nghĩa là luồng chủ sau đó sẽ tạo ra một tập các luồng song song. Và sau đó đoạn mã trong vùng song song được thực thi song song bởi tập luồng song song vừa tạo ra JOIN: Khi mà tập luồng song song đã hoàn thành đoạn mã trong vùng song song chúng sẽ được đồng bộ và kết thúc rồi sau đó công việc lại được thực hiện bởi luồngchủ. 3- Một số chỉ thị trong OpenMP 3.1 Khuôn dạng chỉ thị Chỉ thị trong OpenMP được cho dưới dạng sau # pragma omp directive-name [clause...] newline • # pragma omp: Yêu cầu bắt buộc đối với mọi chỉ thị OpenMP C/C++ • directive-name: Là tên của chỉ thị phải xuất hiện sau pragma omp và đứng trước bất kì mệnh đề nào• [clause...]: Các mệnh đề này không bắt buộc trong chỉ thị • newline : Yêu cầu bắt buộc với mỗi chỉ thị nó là tập mã lệnh nằm trong khối cấu trúc được bao bọc bởi chỉ thị Ví dụ: pragma omp parallel default ( shared ) private (beta,pi) 3.2 Phạm vi của chỉ thị: Phạm vi tĩnh ( Static Extent ) Đó là những đoạn mã nguyên bản trong phạm vi từ đầu đến cuối khối cấu trúc cho sau mỗi chỉ thị. Phạm vi tĩnh của chỉ thị không mở rộng đến các thủ tục và các tệp chứa mã. Chỉ thị đơn độc (Orphaned Directive) Chỉ thị đơn độc là chỉ thị xuất hiện độc lập với chỉ thị khác. Nó tồn tại ở ngoài phạm vi tĩnh của chỉ thị khác. Chỉ thị đơn độc mở rộng với các thử tục và các tệp mã nguồn Phạm vi động (Dynamic Extent) Phạm vi động của chỉ thị bao gồm phạm vi tĩnh của của chỉ thị và phạm vi của các chỉ thị mồ côi OpenMP có rất nhiều chỉ thị như: atomic, barrier, critical, flush, for, master, ordered, parallel, section, single, threadprivate. Các cấu trúc thường gặp : Cấu trúc chia sẻ Cấu trúc đồng bộ Trong phạm vi bài tập lớn này em xin trình bày các chỉ thị đã dùng: 3.3 Cấu trúc chia sẻ 3.3.1 Chỉ thị do/for • Mệnh đề schedulepragma omp for schedule(static,t) T= so dinh cua do thi / so luong. For(i=1;i=0 u,v thuộc V Đầu ra : Khoảng cách từ s đến các đỉnh còn lại d[v], v thuộc V Truoc[v] ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v *) Begin (* khởi tạo *) For v Begin D[v]= c[s,v]; Truoc[v]=s; End D[s]=0 ; T= V\{s} (* T là tập các đỉnh có nhãn tạm thời *) (* bước lặp *) While (T do Begin Tìm đỉnh u T thỏa mãn d[u]= min{ d[z]: z T}; T= T\{u}; (* cố định nhãn u *)For v do (* Gán lại nhãn cho các đỉnh trong T*) If( d[v]>d[u]+a[u,v] ) Begin d[v]=d[u]+a[u,v]; truoc[v]=u; end; end; end; Ví dụ : Ma trận trọng số 1 2 3 4 5 6 A= 1 0 ∞ ∞ 2 ∞ ∞ 2 1 0 ∞ ∞ ∞ ∞ 3 ∞ 5 0 1 ∞ ∞ 4 ∞ 2 ∞ 0 3 ∞ 5 ∞ ∞ ∞ 4 0 1 6 ∞ 7 1 ∞ ∞ ∞ Bảng kết quả tính toán theo thuật toán Dijkstra : Quy ước viết hai thành phần của nhãn theo thứ tự là d[v] và truoc[v] Bước lặp Khởi tạo 1 2 3 4 5 2- Đỉnh 1 0.1 - Đỉnh 2 1,1* - Đỉnh 3 ∞,1 6,2 4,4* - Đỉnh 4 ∞,1 3.2* - Đỉnh 5 ∞,1 ∞,1 7,4 7,4 6,6* - Đỉnh 6 ∞,1 8,2 8.2 5,3* - Tính đúng đắn của giải thuật Dijkstra Trước hết ta đi chứng minh là thuật toán tìm được đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ thị. Giả sử rằng ở một bước lặp nào đó các nhãn cố định cho ta độ dài các đường đi ngắn nhất từ s đến các đỉnh có nhãn cố định, ta sẽ chứng minh ở lần lặp tiếp theo nếu đỉnh u* thu được nhãn cố định là d[u*] chính là độ dài đường đi ngắn nhất từ s đến u*. Thật vậy ta có Kí hiệu S1 là tập các đỉnh có nhãn cố đinh còn S2 là tập các đỉnh có nhãn tạm thời ở bước lặp đang xét. Kết thúc mỗi bước lặp nhãn tạm thời d[v] cho ta độ dài đường đi từ s đến v chỉ qua những tập nằm hoàn toàn trong S1. Giả sử rằng đường đi ngắn nhất từ s đến u* không nằm ngọn trong S1, tức là nó đi qua ít nhất một đỉnh của tập S2. Gọi z thuộc S2 là đỉnh đầu tiên như vậy trên đường đi này. Do trọng số trên các cung là không âm, nên đoạn đường từ z đến u* có độ dài là L>0 và d[z]< d[u*] –L |
