Đề tài Tìm hiểu về tính toán song song, áp dụng giải quyết một số bài toán

MỤC LỤC MỞ ĐẦU Bốn thập kỷ qua chứng kiến sự phát triển bùng nổ về sức mạnh máy tính, tạo tiền đề cho những bước tiến chưa từng thấy về phát minh, năng suất lao động và phúc lợi cho con người. Nhưng quá trình đó giờ đây đứng trước một trở ngại mà ít ai nghĩ đến: sự kết thúc của quá trình mở rộng sức mạnh điện toán. Ngành tin học đã đạt đến giới hạn của những gì từng khả thi với một hay hai vi xử lý trung tâm hoạt động theo chuỗi truyền thống (serial processing). Ngành nào vẫn dựa vào mô hình đó để tiếp tục phát triển năng suất, tăng trưởng kinh tế và phát triển xã hội thì cần phải bắt đầu một bước nhảy mới vào điện toán xử lý song song (parallel processing). Năm 1965, nhà đồng sáng lập hãng Intel là Gordon Moore đăng một bài viết trong đó dự báo số bóng bán dẫn transistor trên mạch tích hợp sẽ tăng gấp đôi mỗi năm (về sau điều chỉnh lại là "tăng gấp đôi theo chu kỳ 18 tháng"), sau này được biết đến là “định luật MORE”. Tuy nhiên với sự phát triển như vũ bão của công nghệ, và sự hạn chế của kỹ thuật, lượng transistor không còn tăng được nữa, tính quy mô của định luật MORE không còn. Đã đến lúc cần 1 giải pháp khác cho sự phát triển của công nghệ điện toán. Và điện toán song song sẽ có thể đem đến một nền tảng phát triển mới. Định luật MORE đã chết, bây giờ là thời kỳ của tính toán song song. Minh họa một cách đơn giản, tính toán truyền thống giống như việc một người đọc bài văn theo kiểu tuần tự từ đầu đến cuối, còn tính toán song song thì giống như tách bài văn đó thành các phần và cho nhiều người khác nhau cùng đọc một lúc để có kết quả nhanh hơn. Tính toán song song mang lại một nền tảng mới cho sự phát triển của công nghệ xử lý. Đây là một hướng đi mới, đúng đắn và hiệu quả cho công nghệ điện toán trong tương lai. Bài viết sau đây về đề tài “Tìm hiểu về tính toán song song , áp dụng giải quyết một số bài toán” phần nào thể hiện được những kiến thức cơ bản đầu tiên về tính toán song song, tính đúng đắn và ứng dụng của nó. NỘI DUNG Những khái niệm cơ bản về tính toán song song Nhu cầu tính toán hiệu năng cao và tính khả dụng của tính toán song song. Nhu cầu tính toán song song Ví dụ 1: Oregon State University: – Mô phỏng các dòng chảy lưu thông của đại dương -> xác định nguyên nhân gây trái đất đang nóng dần lên. – Phân chia đại dương thành: • 4096 vùng từ đông sang tây. • 1024 vùng từ bắc sang nam. • 12 tầng biển. • Xấp sỉ 50 triệu khối trong không gian 3 chiều. – Mô phỏng lưu thông thực hiện ~ 30 tỷ phép tính trong 10 phút. Công việc này thực hiện liên tục trong năm. Ví dụ 2: Dự báo thời tiết (weather forecasting): – Chia bầu khí quyển theo không gian 3 chiều, mỗi khối kích thước 1mile x 1mile x 1mile. – Ước tính khoảng 5x10^8 khối (cells). – Trên mỗi khối cần thực hiện ~ 200 phép toán -> cần thực hiện ~ 10^11 phép toán. – Nếu cần dự báo cho 1 tuần, chu kỳ 1 phút -> cần thực hiện 10^4 lần, mỗi lần 10^11phép toán. – Siêu máy tính có thể thực hiện: 10^9 phép toán trên 1 giây -> cần 10^6 giây ~ 10 ngày để thực hiện. Ví dụ 3: Mô phỏng tương tác của các protein với phân tử nước (Levin 1990): – Thực hiện trên máy Cray X/MP (~800 triệu phép toán / 1 giây): để mô phỏng 10^-12 giây phản ứng protein cần 1 giờ thực hiện. – Nếu mô phỏng một phản ứng thực sự trên cùng máy Cray X/MP cần 31,688 năm. TÓM LẠI: Yêu cầu về thực nghiệm nghiên cứu, mô phỏng -> giải quyết những bài toán có khối lượng tính toán lớn trong một khoảng thời gian chấp nhận được. Phương hướng giải quyết vấn đề: – Thực hiện trên các siêu máy tính mạnh. – Thực hiện phân chia công việc thực hiện song song trên hệ thống các máy tính Tính khả dụng của tính toán song song SIÊU MÁY TÍNH: Khả năng tính toán phụ thuộc nhiều vào tốc độ xử lý của CPU -> phụ thuộc vào cấu trúc và số lượng transistors chứa trong CPU –> Có những giới hạn nhất định về kích thước, nhiệt độ -> không thể tăng số transistors lên mãi được THỰC HIỆN SONG SONG: Nguyên tắc: thực hiện phân chia công việc chính thành các công việc con, có thể thực hiện song song với nhau. Xây dựng hệ thống song song từ nhiều bộ xử lý riêng biệt. Thực hiện các công việc song song trên các bộ xử lý đó. Vấn đề: – Phương pháp phân chia công việc. – Môi trường hỗ trợ thực hiện song song. Ví dụ: Xếp sách trong thư viện • Sách trong thư viện được phân loại theo chữ cái đầu tiên và sắp xếp theo thứ tự. • Sách cùng nhóm được xếp trên cùng một giá. Các giá đặt trong các tủ sách. • Thư viện nhập một số lượng sách lớn -> yêu cầu thủ thư phải sắp xếp sách theo đúng nguyên tắc. • Cách giải quyết hiệu quả nhất? Nếu chỉ có 1 thủ thư • Cách thứ nhất: Lấy từng cuốn sách rồi sắp xếp vào vị trí thích hợp ->không hiệu quả. • Cách thứ hai: Sắp xếp các cuốn sách theo thứ tự trước rồi mang từng chồng sách cùng vị trí đi sắp xếp. • Rõ ràng cách thứ 2 hiệu quả hơn. • Muốn hiệu quả hơn nữa thì cần có nhiều người làm hơn. Nhiều thủ thư hơn • Cách thứ nhất: Mỗi người lấy 1 cuốn rồi đi sắp đặt vị trí -> không hiệu quả. • Cách thứ hai: Phân chia mỗi người một nhóm ký tự, khi đó mỗi người chỉ mang sách thuộc nhóm mình đi sắp xếp. • Cách thứ ba: Sắp xếp sách trước khi mang đi đặt vị trí. Mỗi người đảm nhận một số ký tự: – Nếu cuốn sách đang cầm của mình thì đặt vào chồng sách của mình. – Nếu của người khác thì chuyển cho người đấy. – Sau đó mang sách đi sắp xếp. ->cách thứ ba hiệu quả nhất. Ý nghĩa của tính toán song song • Thực hiện công việc trong khoảng thời gian ngắn hơn -> tiết kiệm thời gian. • Thực hiện được với số lượng phép toán lớn hơn -> giải quyết được bài toán lớn. • Hỗ trợ giải quyết nhiều công việc đồng thời. Những khái niệm cơ bản: • Task: là một công việc cần thực hiện. • Parallel Task: công việc cần thực hiện song song. • Serial Execution: thực hiện tuần tự. • Parallel Execution: thực hiện song song. • Shared Memory: bộ nhớ dùng chung. • Distributed Memory: bộ nhớ phân tán. • Communication: sự liên lạc, trao đổi thông tin giữa các chương trình chạy song song. • Synchronization: sự đồng bộ hóa trong thựchiện song song • Flops (floating point operation per second) là số phép toán thực hiện trên một giây. • Rpeak: là khả năng tính toán tối đa của siêu máy tính do nhà sản xuất công bố. • Rmax: là khả năng thực tế của siêu máy tính được xác định thông qua các phần mềm kiểm định. • Ví dụ: 1 máy tính có CPU 1GHz, DRAM có thời gian truy nhập dữ liệu là 100ns, giả sử CPU thực hiện 1 lệnh/1ns khi đó: – Theo lý thuyết: Rpeak = 10^9flops. (1ns = 10^-9s) – Nhưng khi chạy phần mềm kiểm định giá trị Rmax có thể thấp hơn nhiều ví dụ: Vì truy cập dữ liệu trên RAM mất 100ns -> CPU phải đợi 100ns cho mỗi lệnh -> Rmax = 10^7flops. • Speedup (tăng tốc): S = Ttuần tự/ Tsong song. • Efficiency (hiệu quả): E = S / NCPU. • Cost (chi phí): C = Tkết thúc x NCPU. • Ví dụ: Có 10 CPU thực hiện song song: – P1thực hiện công việc của mình hết 10s, – P2 hết 11s,… P9 thực hiện hết 19s – -> thời gian kết thúc công việc là 19s -> chi phí thực hiện = 19 x 10 = 190. Các dạng song song • Bit-level parallelism. • Instruction-level parallelism. – VLIW. – Pipeline. • Data parallelism. • Task parallelism Các mô hình máy tính song song: • Siêu máy tính đa nhân: multi-core processor. • Đa xử lý đối xứng: Symmetric multiprocessing. • Hệ phân tán: Distributed computing. Mô hình song song OpenMP • OpenMP cung cấp mô hình lập trình đa luồng cấp cao, xây dựng trên thư viện lập trình đa luồng của hệ thống, vd. POSIX Threads • Thực hiện theo mô hình Fork-Join – Chương trình OpenMP bắt đầu việc thực hiện như một luồng chủ duy nhất, master thread – Luồng chủ thực hiện tuần tự cho đến vùng song song đầu tiên – Luồng chủ tạo nhóm các luồng để chia sẻ thực hiện các công việc song song Lập trình song song với OPENMP OpenMP: Open specifications for Multi Processing • OpenMP là – Application Programming Interface (API), – đem lại mô hình lập trình linh động cho những nhà phát triển ứng dụng song song chia sẻ bộ nhớ • OpenMP được hợp thành bởi – Chỉ thị chương trình dịch (compiler directives) – Thư viện hàm thời gian chạy (library runtime routines) – Các biến môi trường (environment variables) • Có thể dùng được trên hầu hết các máy với kiến trúc một không gian nhớ (single memory space) • OpenMP không phải một ngôn ngữ lập trình mới – Thực ra OpenMP hoạt động trên sự liên kết chặt chẽ với ngôn ngữ lập trình làm cơ sở, vd. Fortran, C/C++ • Tự động song song hóa chương trình – Người lập trình phải tự ý thức về tính song song của công việc – OpenMP cung cấp cơ chế để chỉ định việc thực hiện song song • Phương tiện lập trình cho hệ thống có bộ nhớ phân tán Ưu điểm của OpenMP • Một chuẩn hoàn chỉnh và được công nhận trên thực tế • Hiệu suất và khả năng mở rộng tốt – Nếu chương trình được thiết kế đúng! • Tính khả chuyển cao – Chương trình viết ra có thể dịch bởi nhiều chương trình dịch khác nhau • Dễ sử dụng nhờ sự đơn giản và số lượng ít các chỉ thị • Cho phép song song hóa tăng dần chương trình tuần tự Mô hình song song OpenMP: • OpenMP cung cấp mô hình lập trình đa luồng cấp cao, xây dựng trên thư viện lập trình đa luồng của hệ thống, vd. POSIX Threads • Thực hiện theo mô hình Fork-Join – Chương trình OpenMP bắt đầu việc thực hiện như một luồng chủ duy nhất, master thread – Luồng chủ thực hiện tuần tự cho đến vùng song song đầu tiên – Luồng chủ tạo nhóm các luồng để chia sẻ thực hiện các công việc song song • Song song đa luồng • Song song có khai báo • Song song động Mô hình bộ nhớ OpenMP • Mọi luồng có quyền truy cập đến vùng nhớ chung toàn cục • Dữ liệu hoặc là chia sẻ hoặc là riêng tư • Việc truyền dữ liệu là trong suốt với người lập trình • Cần thiết phải đồng bộ hóa nhưng hầu như được thực hiện ngầm Tính năng chính của OpenMP • Tạo nhóm các luồng cho thực hiện song song • Chỉ rõ cách các chia sẻ công việc giữa các luồng thành viên của nhóm • Khai báo dữ liệu chia sẻ và riêng tư • Đồng bộ các luồng và cho phép các luồng thực hiện thực hiện công việc một các độc quyền • Cung cấp hàm thời gian chạy • Quản lý số lượng luồng Viết chương trình song song với OpenMp • Chia tách bài toán thành các công việc – Lý tưởng nhất khi các cộng việc là hoàn toàn độc lập • Gán công việc cho các luồng thực thi • Viết mã trên môi trường lập trình song song • Thiết kế chương trình phụ thuộc vào – Nền tảng phần cứng – Cấp độ song song – Bản chất của bài toán • Song song theo dữ liệu – Khuyến kích lập trình song song có cấu trúc dựa trên phân chia công việc trong vòng lặp – #pragma omp parallel for • Song song theo công việc – Hỗ trợ việc gán các công việc cụ thể cho các luồng thông qua chỉ số của luồng – #pragma omp parallel sections Dịch chương trình OpenMP • GNU GCC – Version GCC 4.3.2, OpenMP 3.0 – #include – gcc –fopenmp • Microsoft Visual C++ – Version VC++ 2005, 2008, OpenMP 2.0 – Win 32 Console Project → Empty Project – project properties → configuration properties → C.C++/language – Activate OpenMP option – Build project – Run “without debug” Các hàm OpenMP • OpenMP cung cấp các hàm giúp người dùng – Điều khiển và truy vấn môi trường song song – Thủ tục semaphore/lock đa mục đích... • Hàm có độ ưu tiên cao hơn các biến môi trường tương ứng • Chương trình C/C++ cần thêm khai báo #include • Nên sử dụng kèm macro #ifdef _OPENMP Cấu trúc song song: #pragma omp parallel [clause[ [, ]clause] ...] new-line structured-block clause: if(scalar-expression) num_threads(integer-expression) default(shared | none) private(list) firstprivate(list) shared(list) copyin(list) reduction(operator: list) #pragma omp for [clause[[,] clause] ... ] new-line for-loops clause: private(list) firstprivate(list) lastprivate(list) reduction(operator: list) schedule(kind[, chunk_size]) collapse(n) ordered nowait #pragma omp sections [clause[[,] clause] ...] new-line // Thực hiện mỗi luồng một section { [#pragma omp section new-line] structured-block [#pragma omp section new-line structured-block ] ... } clause: private(list) firstprivate(list) lastprivate(list) reduction(operator: list) nowait #pragma omp single [clause[[,] clause] ...] new-line structured-block clause: private(list) firstprivate(list) copyprivate(list) nowait #pragma omp task [clause[ [, ]clause] ...] new-line structured-block clause: if(scalar-expression) untied default(shared | none) private(list) firstprivate(list) shared(list) Các hàm song song: Ứng dụng vào bài toán “Connected component” Phân tích bài toán Bài toán “Connected component” – tìm thành phần liên thông trong đồ thị vô hướng biểu diễn bằng ma trận kề. Đồ thị và thành phần liên thông Đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh và E là tập các cặp không có thứ tự gồm 2 phần tử khác nhau của V gọi là các cạnh Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G Đồ thị vô hướng G được gọi là liên thông nếu luôn tìm được đường đi giãu 2 đỉnh bất kỳ của nó. Đối với các đồ thị không liên thông, các đồ thị con liên thông của nó được gọi là các thành phần liên thông cảu đồ thị. Xét đồ thị G=(V,E) có n đỉnh. Ma trận A[n][n] với A[i][j]=1 nếu (i,j) là cạch của đồ thị, ngược lại A[i][j]=0, được gọi là ma trận kề của đồ thị. Tìm kiếm theo chiều sâu(DFS) và ứng dụng tìm thành phần liên thông của đồ thị: Tư tưởng của tìm kiếm theo chiều sâu: “Đi sâu nhất có thể, nếu không được thì quay lại” Thủ tục tìm kiếm theo chiều sâu là một thủ tục đệ quy. Ta sẽ tìm kiếm từ một đỉnh s nào đó của đồ thi. Sau đó chọn u trong số các đỉnh kề của s và lặp lại quá trình đó. Nếu trong các đỉnh kề của đỉnh s tìm được đỉnh chưa thăm thì thực hiện thủ tục DFS với đỉnh đó. Nếu không tìm được thì s được duyệt xong, quay trở lại tìm kiếm tiếp tục với đỉnh xét trước s. Do thủ tục DFS(s) cho phép thăm tất cả các đỉnh thuộc thành phần liên thông với s nên số thành phần liên thông của đồ thị chính bằng số lần gọi đến thủ tục DFS. Mô tả thuật toán Như đã trình bày ở trên, ta ứng dụng thủ tục DFS kết hợp với các chỉ thị song song để tìm thành phần liên thông trong đồ thị. Ý tưởng là chia nhỏ đồ thị thành từng phần nhỏ tiến hành DFS mỗi phần trên một luồng rồi tổng hợp dữ liệu đưa ra kết quả. Cụ thể ta chia ma trận kề của đồ thị thành p phần tương ứng với p luồng dữ liệu (p bộ xử lý).Tiến hành thủ tục DFS ở mỗi phần. Dùng hàm Union(x,y) để tổng hợp dữ liệu. Ví dụ: Ta có đồ thị như hình vẽ và 2 bộ xử lý. Chia dữ liệu như hình vẽ cho 2 bộ xử lý thực hiện DFS. Sau khi chia dữ liệu, ta được 2 đồ thị con như hình c và e. Thực hiện DFS với 2 đồ thị con được 2 rừng như hình d và f. Ta sử dụng hàm unions(x,y) để kết hợp 2 rừng thu được ở 2 bộ xử lý riêng biệt. Khi gọi hàm unions(x,y), chương trình sẽ kiểm tra xem nếu (x,y) là cạnh của 1 cây trong rừng 1 và cũng là 1 cạnh của 1 cây trong rừng 2 thì ta kết hợp 2 rừng lại, nếu không thì không có sự kết hợp nào cả. Kết quả cuối cùng ta sẽ được rừng là kết quả của thủ tục DFS trên toàn đồ thị. Từ đó ta có thể đưa ra các thành phần liên thông trên đồ thị đã cho. Code Chương trình “Connected component” viết bằng ngôn ngữ C++ sử dụng thư viện omp.h, trên visual C++ 2010: // Connected_component.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include #include #ifdef _OPENMP #include #endif using namespace std; int N,i,j, divi=0; int Solt1=0,Solt2=0,Solt=0; int Tnu,NuT; int **Data, **chuaxet,*chuaxet_tt; bool test=false; volatile DWORD dwStart; volatile int global = 0; //Ham vao du lieu tu ban phim void IN_data(); //Ham doc du lieu void READ_data(); //Ham thiet lap ban dau void Thiet_Lap(); //Ham tim kiem theo chieu sau xuat phat tu dinh i tren mot doan DL void DFS1(int); void DFS2(int); //Ham tim kiem theo chieu sau tuan tu void DFS(int); //Ham tim thanh phan lien thong void LienThong(); //Ham dua ra ket qua lien thong tuan tu void LienThong_TT(); //Ham ket hop void unions(int, int); //Ham main int main(int argc, char* argv[]) { int k; char c; do{ cout<<"\n ------ CONNECTED COMPONENT PROGRAM ------"; cout<<"\n MENU "; cout<<"\n Nhap 1 de nhap du lieu bang ban phim"; cout<<"\n Nhap 2 de nhap du lieu tu file"; cout<<"\n Nhap 3 de tim thanh phan lien thong theo mo hinh song song"; cout<<"\n Nhap 4 de tim thanh phan lien thong theo mo hinh tuan tu"; cout<<"\n Nhap 5 de ket thuc chuong trinh"; cout>k; switch(k){ case 1: IN_data(); printf("\n NHAP DU LIEU THANH CONG \n"); cout<<"\n Do thi co "<<N<<" dinh \n"; for(i=1;i<=N;i++){ for(j=0;j<=N;j++){ cout<<Data[i][j]<<"\t"; } cout<<"\n"; } break; case 2: READ_data(); printf("\n NHAP DU LIEU THANH CONG\n "); cout<<"\n Do thi co "<<N<<" dinh \n"; for(i=1;i<=N;i++){ for(j=0;j<=N;j++){ cout<<Data[i][j]<<"\t"; } cout<<"\n"; } break; case 3: cout<<"\n Mo hinh song song\n\n"; dwStart = GetTickCount(); LienThong(); cout<<"\n Thoi gian thuc hien song song: "<<GetTickCount() - dwStart<<" ms"; break; case 4: cout<<"\n Mo hinh tuan tu\n\n"; dwStart = GetTickCount(); LienThong_TT(); cout<<"\n Thoi gian thuc hien tuan tu: "<<GetTickCount() - dwStart<<" ms"; break; case 5: cout<<"\n Ban da thoat khoi chuong trinh...!!!"; cout<<"\n BYE BYE..............!!!!!!!!! \n "; exit(0); break; default: cout<<"\n Error...!!!"; break; } cout<<"\n Ban co muon thuc hien tiep chuong trinh khong (c/k)? "; cin>>c; }while(c=='c'); cout<<"\n BYE BYE..............!!!!!!!!! \n \n\n\n"; system("pause"); } //Ham thiet lap ban dau void Thiet_Lap(){ Data=new int *[N+1]; for(i=0;i<=N;i++) { Data[i]=new int [N+1] ; } #ifdef _OPENMP #pragma omp parallel for default(none) shared(Data,j,N) private(i) for(i=0;i<=N;i++) for(j=0;j<=N;j++) Data[i][j]=0; #endif } //Ham vao du lieu tu ban phim void IN_data(){ cout>N; Thiet_Lap(); for(i=1;i<=N;i++) { j=1; while(j!=0){ cout>j; Data[i][j]=1; } } } //Ham doc du lieu tu tep void READ_data() { char s[60]; FILE *f; int temp; do{ cout<<"\n Nhap vao ten file du lieu: ";fflush(stdin);cin.getline(s,100); f=fopen(s,"rt"); if(f==NULL) { cout<<"\n khong mo duoc file...!!!"; cout<<"\n Nhap lai ten file"; } }while(f==NULL); fscanf(f,"%d",&N); Thiet_Lap(); for(i=1;i<=N;i++) for(j=1;j<=N;j++) { fscanf(f,"%d",&temp); Data[i][j]=temp; if(feof(f)) { if((i<N)||(j<N)) {cout<<"\n error...!!!"; cout<<"\n An phim bat ki de thoat"; fclose(f); exit(1);} else fclose(f); cout<<"\n Finish...!!!"; } } fclose(f); } //Ham tim kiem theo chieu sau xuat phat tu dinh i void DFS1(int v){ int u; chuaxet[0][v]=Solt1; for(u=1;u<=N;u++){ if(Data[v][u]==1 && chuaxet[0][u]==0){ if(u<=divi) DFS1(u); else chuaxet[0][u]=Solt1; } } } void DFS2(int v){ int u; chuaxet[1][v]=Solt2; for(u=1;u<=N;u++){ if(Data[v][u]==1 && chuaxet[1][u]==0){ if(u<=divi) chuaxet[1][u]=Solt2; else DFS2(u); } } } //Ham tim kiem theo chieu sau tuan tu void DFS(int v){ int u; chuaxet_tt[v]=Solt; for(u=1;u<=N;u++){ if(Data[v][u]==1 && chuaxet_tt[u]==0) DFS(u); } } //Ham Lien thong void LienThong(){ int x,y; Solt=Solt1=Solt2=0; chuaxet=new int *[2]; chuaxet[0]=new int [N+1]; chuaxet[1]=new int [N+1]; #ifdef _OPENMP #pragma omp parallel for default(none) shared(chuaxet,N) private(i) for(i=0;i<=N;i++){ chuaxet[0][i]=0; chuaxet[1][i]=0; } #endif divi = N/2; #ifdef _OPENMP #pragma omp parallel sections { #pragma omp section { for(i=1;i<=N;i++){ if(chuaxet[0][i]==0){ Solt1+=1; if(i<=divi) DFS1(i); else chuaxet[0][i]=Solt1; } } } #pragma omp section { for(j=N;j>0;j