Đề tài: ỨNG DỤNG LẬP TRÌNH SONG SONG GIẢI QUYẾT BÀI TOÁN SẮP XẾP BẰNG PHƯƠNG PHÁP TRỘN (MERGE SORT)

Chia sẻ: Bùi Quốc Khánh | Ngày: | Loại File: DOC | Số trang:18

Thêm vào BST

Báo xấu

132
lượt xem 19
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong những năm gần đây, mặc dù nền Công nghệ thông tin của thế giới ngày một phát triển. Tốc độ xử lí máy tính ngày càng tăng lên. Tuy nhiên, chúng ta cũng gặp phải khó khăn trong một số bài toán có dữ liệu đầu vào lớn (bài toán dự báo thời tiết, dự báo động đất, …). Với dữ liệu đầu vào là một con số rất lớn, dù máy tính có tốc độ lớn, bộ nhớ nhiều vẫn vấp phải yêu cầu phải giải quyết bài toán trong thời gian chấp nhận được. Trong nhiều năm qua, các nhà khoa học đã nghĩ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề tài: ỨNG DỤNG LẬP TRÌNH SONG SONG GIẢI QUYẾT BÀI TOÁN SẮP XẾP BẰNG PHƯƠNG PHÁP TRỘN (MERGE SORT)

TIỂU LUẬN MÔN HỌC CÁC KỸ THUẬT HIỆN ĐẠI TRONG CNTT Nội dung: ỨNG DỤNG LẬP TRÌNH SONG SONG GIẢI QUYẾT BÀI TOÁN SẮP XẾP BẰNG PHƯƠNG PHÁP TRỘN (MERGE SORT) Phú Thọ, tháng 05-2011
MỤC LỤC TIỂU LUẬN MÔN HỌC..................................................................................1 CÁC KỸ THUẬT HIỆN ĐẠI TRONG CNTT............................................. 1 2
LỜI M Ở Đ Ầ U Trong nh ữ ng năm g ầ n đây, m ặ c dù n ề n Công ngh ệ thông tin c ủ a th ế gi ớ i ngày m ộ t phát tri ể n. T ố c đ ộ x ử lí máy tính ngày càng tăng lên. Tuy nhiên, chúng ta cũng g ặ p ph ả i khó khăn trong m ột s ố bài toán có d ữ li ệ u đ ầ u vào l ớ n (bài toán d ự báo th ời ti ết, d ự báo đ ộ ng đ ấ t, …). V ớ i d ữ li ệ u đ ầ u vào là m ộ t con s ố r ấ t l ớ n, dù máy tính có t ố c đ ộ l ớ n, b ộ nh ớ nhi ề u v ẫ n v ấ p ph ả i yêu c ầ u ph ả i gi ả i quy ế t bài toán trong th ờ i gian ch ấ p nh ậ n đ ượ c. Trong nhi ề u năm qua, các nhà khoa h ọ c đã nghĩ ra bi ện pháp gi ả n quy ế t hi ệ u qu ả đó là chia nh ỏ bài toán ra thành nhi ều bài toán. Vi ệ c gi ả i quy ế t các bài toán nh ỏ đ ượ c ti ế n hành đ ồ ng th ời v ớ i nhi ề u máy tính. K ế t qu ả c ủ a bài toán l ớ n s ẽ đ ượ c gi ả i quy ết khi t ấ t c ả các bài toán nh ỏ đã đ ượ c làm. Các máy tính ti ế n hành x ử lí song song đ ượ c k ế t n ố i v ớ i nhau thành các c ụ m tính toán t ố c đ ộ cao. 3
N Ộ I DUNG I.MÔ T Ả GI Ả I THU Ậ T SONG SONG 1. Giới thiệu Hiện nay, để giải quyết các bài toán lớn người ta thường nghĩ đến việc sử dụng các siêu máy tính hoặc việc kết hợp nhiều máy tính với nhau để tính toán. Tuy nhiên, với phương pháp lập trình cổ điển thì không thể nào phát triển được chương trình có thể tận dụng được sức mạnh của các hệ thống đó. Đó chính là lý do lập trình song song ra đời. Lập trình song song là một công việc rất phức tạp so với lập trình tuần tự thông thường, người phát triển phải thực hiện một quá trình “song song hóa”, biến đổi các chương trình tuần tự thành chương trình song song có khả nănG tận dụng tối đa sức mạnh của hệ thống. 2. Nguyên lý thiết kế thuật toán song song 2.1. Cách thức xây dựng một chương trình song song và phân bố Phát triển thuật toán là một phần quan trọng trong việc giải quy ết v ấn đề khi sử dụng máy tính . Một thuật toán song song là một ph ương pháp gi ải quyết vấn đề dựa trên việc sử dụng nhiều bộ xử lý . Tuy nhiên đ ể ch ỉ ra được một thuật toán song song không đơn giản chỉ ra từng bước cụ thể, mà là ở một mức độ nào đó thuật toán song song phải được them vào tính đồng th ời và người thiết kế ra thuật toán cũng phải chỉ ra tập hợp những bước xử lý đồng thời , điều này sẽ tận dụng được khả năng tính toán của các máy tính song song. Trên thực tế việc thiết kế ra một thuật toán song song là khá phức tạp,gồm các công việc: Chỉ ra phần của công việc có thể thực thi đồng thời Ánh xạ các phần của công việc vào nhiều bộ xử lý chạy song song Phân tán dữ liệu nhập, xuất và trung gian cùng với chương trình Quản lý truy cập vào dữ liệu chung giữa các bộ xử lý Đồng bộ hóa các bộ xử lý khi thực thi các chương trình song song 2.2. Thiết kế thuật toán song song 4
Thuật toán song song là một tập các tiến trình (process) hoặc các tác vụ (task) có thể thực hiện đồng thời và có thể trao đổi dữ liệu với nhau để kết hợp cùng giải một bài toán đặt ra. Thiết kế giải thuật song song là chia bài toán thành các bài toán nhỏ hơn và gán bài toán nhỏ cho các bộ vi xử lý khác nhau để thực hiện song song.Quá trình thiết kế giải thuật song song là quá trình song song hóa bài toán tuần tự. Nguyên lý cơ bản trong thiết kế giải thuật song song bao gồm: 2.2.1. Nguyên lý lập lịch: Giảm tối thiểu các bộ xử lý sử dụng trong thuật toán sao cho thời gian tính toán là không tăng (xét theo khía cạnh độ phức tạp). Nghĩa là, nếu độ phức tạp tính toán của thuật toán là O(f(n)) thì thời gian thực hiện của chương trình có thể tăng khi số bộ xử lý giảm, và thời gian tính toán tổng thể tăng lên một hằng số nào đó - nhưng vẫn là O(f(n)). 2.2.2. Nguyên lý hình ống: Nguyên lý này được áp dụng khi bài toán xuất hiện một dãy các thao tác {T1, T2, . . ., Tn },trong đó Ti+1 thực hiện sau khi Ti kết thúc. 2.2.3. Nguyên lý chia để trị: Tức là chia bài toán thành những phần nhỏ hơn tương đối độc lập với nhau và giải quyết chúng một cách song song. Tạo ra một mô hình cây phân cấp để phân cấp quá trình truyền thông và tính toán. - Tăng tính song song so với mô hình trước - Thời gian chạy giảm từ O(n) xuống O(logn) 2.2.4. Nguyên lý đồ thị phụ thuộc dữ liệu: Phân tích mối quan hệ dữ liệu trong tính toán để xây dựng đồ thị phụ thuộc dữ liệu và dựa vào đó để xây dựng thuật toán song song. 2.2.5. Nguyên lý điều kiện tương tranh: Nếu hai tiến trình cùng muốn truy cập vào cùng một mục dữ liệu chia sẻ thì chúng phải tương tranh với nhau, nghĩa là chúng có thể cản trở lẫn nhau. II. MÔ HÌNH LẬP TRÌNH TRUYỀN THÔNG ĐIỆP- CHUẨN MPI 1. Giới thiệu 5
Có rất nhiều ngôn ngữ lập trình và các thư viện được xây dựng nên để dành cho lập trình song song. Mô hình lập trình truyền thông điệp là một trong những mô hình cổ nhất và được sử dụng rộng rãi nhất trong các mô hình dùng cho lập trình trên các máy tính song song. Mô hình này có hai tính chất quan trọng đó là: nó giả sử không gian địa chỉ được phân chia và nó chỉ hỗ trọ song song hóa tường minh. Môi trường truyền thông điệp LAM/MPI là phiên bản nguồn m ở, cung cấp miễn phí với chuẩn MPI. Chuẩn MPI (Message Passing Interface) là kết quả sau hơn 2 năm thảo luận của MPI Forum, 1 nhóm g ồm khoảng 60 ng ười từ 40 tổ chức khác nhau đại diện cho những nhà phân ph ối các h ệ th ống song song, những phòng thí nghiệm quốc gia và những trường đại học danh ti ếng. MPI là một thư viện các hàm có thể chèn vào mã ngu ồn đ ể truyền dữ liệu giữa các tiến trình. 2. Các khái niệm cơ bản Communicator: Một nhóm các tiến trình có thể truyền thống với nhau. Một tiến trình có thể thuộc nhiều Communicator. Rank: Mỗi tiến trình trong 1 communicator có 1 định danh, gọi là Rank, đánh số bắt đầu từ 0.Một tiến trình có thể các rank khác nhau khi thu ộc về các communicator khác nhau. Group: là các nhóm xử lý Process(tiến trình hay xử lý): với kiểu lập trình trên một máy có một bộ xử lý thì process được coi như là một tiến trình trong một chương trình có không gian địa chỉ riêng do hệ điều hành cung cấp. Send/receive: Vì các chương trình sử dụng phương pháp lạp trình Message passing không chia sẻ vùng nhớ chung, hay biến cục bộ mà t ất cả dữ liệu đều phải giao tiếp thông qua truyền thông. Do đó MPI định nghĩa Send/receive là 2 cơ chế gửi nhận thông điệp giữa các xử lý trên máy khác nhau. 3. Cấu trúc chương trình MPI Các tập tin tư viện: liên quan đến các hàm và thủ tục , các kiểu dưa liệu.Bao gồm tập tin.h như mpi.h, mpio.h,…Cấu trúc chương trình MPI: 6
Các tập tin thư viện Khởi tạo môi trường MPI Thực hiện các thủ tục hàm MPI Thoát khỏi môi trường III.BÀI TOÁN S Ắ P X Ế P Trong toán học, cũng như khoa học máy tính thì bài toán sắp xếp m ột dãy số cho trước thành 1 dãy số tăng hoặc giảm được gi ọi là các bài toán s ắp xếp. Việc sắp xếp giúp ích rất nhiều trong công việc tìm ki ếm thông tin cũng như trong cuộc sống. Một số thuật toán sắp xếp tương đối đơn giản như: 1. Sắp xếp nổi bọt Sắp xếp nổi bọt (bubble sort) là phương pháp sắp xếp đơn giản, dễ hiểu thường được dạy trong khoa học máy tính. Giải thuật bắt đầu từ đầu của tập dữ liệu. Nó so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử tiếp theo cho đến cuối tập hợp dữ liệu. Sau đó nó quay lại với hai phần tử đầu cho đến khi không còn cần phải đổi chỗ nữa. 2. Sắp xếp chèn Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp rất hiệu quả với các danh sách nhỏ. Nó lần lượt lấy các phần tử của danh sách chèn vào vị trí thích hợp trong một danh sách mới đã được sắp. 3. Sắp xếp chọn Sắp xếp chọn (select sort) là phương pháp sắp xếp bằng cách chọn phần tử bé nhất xếp vào vị trí thứ nhất, tương tự với các phần tử nhỏ thứ hai, thứ ba,... 4. Sắp xếp trộn Sắp xếp trộn (merge sort) cùng với sắp xếp nhanh là hai thuật toán sắp xếp dựa vào tư tưởng "chia để trị" (divide and conquer). Thủ tục cơ bản là việc trộn hai danh sách đã được sắp xếp vào một danh sách mới theo thứ tự. 7
Nó có thể bắt đầu trộn bằng cách so sánh hai phần tử một (chẳng hạn phần tử thứ nhất với phần tử thứ hai, sau đó thứ ba với thứ tư...) và sau khi kết thúc bước 1 nó chuyển sang bước 2. Ở bước 2 nó trộn các danh sách hai phần tử thành các danh sách bốn phần tử. Cứ như vậy cho đến khi hai danh sách cuối cùng được trộn thành một. 5. Sắp xếp vun đống Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n2). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(nlogn). 6. Sắp xếp nhanh Sắp xếp nhanh (quicksort) là một thuật toán theo tư tưởng chia để trị, nó dựa trên thủ tục phân chia như sau: để chia một dãy ta chọn một phần tử được gọi là "chốt" (pivot), chuyển tất cả các phần tử nhỏ hơn chốt về trước chốt, chuyển tất cả các phần tử lớn hơn chốt về sau nó. Thủ tục này có thể thực hiện trong thời gian tuyến tính. Tiếp tục phân chia các dãy con đó như trên cho đến khi các dãy con chỉ còn một phần tử. Điểm khác biệt giữa sắp xếp nhanh và sắp xếp trộn là trong sắp xếp trộn việc xác định thứ tự được xác định khi "trộn", tức là trong khâu tổng hợp lời giải sau khi các bài toán con đã được giải, còn sắp xếp nhanh đã quan tâm đến thứ tự các phần tử khi phân chia một danh sách thành hai danh sách con. Ngoài ra còn nhiều giải thuật sắp xếp khác, trong đó nhiều giải thuật sắp xếp được cải tiến từ các giải thuật trên. Trong sau giải thuật liệt kê trên, ta thường coi các giải thuật chèn, chọn, nổi bọt là các giải thuật cơ bản, độ phức tạp trong trường hợp trung bình của chúng là O(n2). Ba giải thuật còn lại thường được coi là giải thuật cao cấp, độ phức tạp tính toán trung bình của chúng là n.ln(n). 8
IV. ỨNG DỤNG LẬP TRÌNH SONG SONG VÀO BÀI TOÁN SẮP XẾP BẰNG PHƯƠNG PHÁP TRỘN(MERGESORT) 1. Phát biểu bài toán Giả sử có hai danh sách đã được sắp xếp a[1..m] và b[1..n.] (trong đó m và n là các số rất lớn) Ta có thể trộn chúng lại thành một danh sách mới c[1..m + n] được sắp xếp theo cách sau: So sánh hai phần tử đứng đầu của hai danh sách, lấy phần tử nhỏ hơn cho vào danh sách mới. Tiếp tục như vậy cho tới khi một trong hai danh sách là rỗng. Khi một trong hai danh sách là rỗng ta lấy phần còn lại của danh sách kia cho vào cuối danh sách mới. Ví dụ: Cho hai danh sách a = (1,3,7,9),b = (2,6), quá trình hòa nhập diễn ra như sau: Danh sách a Danh sách b So sánh Danh sách c 1,3,7,9 2,6 1
Dưới đây là mã nguồn C dùng MPI của chương trình trên, mã nguồn này được trình bày trong cuốn "Parallel Programming in C with MPI and OpenMP" của tác giả Quinn. 10
#include #include #include #include #define N 10000000 #define MASTER 0 int * merge(int *A, int asize, int *B, int bsize); void m_sort(int *A, int min, int max); double startT, stopT; double startTime; int * merge(int *A, int asize, int *B, int bsize) { int ai, bi, ci, i; int * C; int csize = asize+bsize; ai = 0; bi = 0; ci = 0; C = (int *)malloc(csize*sizeof(int)); while((ai
int left = mid - min + 1; int right = max - mid; if(max != min) { m_sort(A, min, mid); m_sort(A, mid+1, max); C = merge(A + min, left, A + mid + 1, right); } } int main(int argc, char* argv[]) { int * data; int * blk; int * temp; int m, n = N; int id, p; int s = 0; int i; int step; MPI_Status status; MPI_Init(&argc,&argv); MPI_Comm_rank(MPI_COMM_WORLD,&id); MPI_Comm_size(MPI_COMM_WORLD,&p); startT = MPI_Wtime(); if(id == MASTER) { int r; srandom(MPI_Wtime()); s = n/p; r = n%p; data = (int *)malloc((n+s-r)*sizeof(int)); for(i=0;i
m_sort(blk, 0, s-1); } step = 1; while(step < p) { if(id%(2*step)==0) { if(id + step < p) { MPI_Recv(&m,1,MPI_INT,id+step,0,MPI_COMM_WORLD, &status); temp = (int *)malloc(m*sizeof(int)); MPI_Recv(temp,m,MPI_INT,id+step,0,MPI_COMM_WORL D,&status); blk = merge(blk,s,temp,m); s += m; } } else { int near = id-step; MPI_Send(&s,1,MPI_INT,near,0,MPI_COMM_WORLD); MPI_Send(blk,s,MPI_INT,near,0,MPI_COMM_WORLD); break; } step *= 2; } stopT = MPI_Wtime(); printf(" %d; %d processors; %f secs\n", s, p, (stopT- startT)); MPI_Finalize(); return 0; } 3. Đánh giá thời gian chạy với số CPU khác nhau K ế t qu ả m ộ t s ố test th ự c hi ệ n trên bkluster@hut.edu.vn S ắ p x ế p 1 m ả ng có 400.000 th ự c hi ệ n trên 4 processors [guest@bkluster ~]$ mpirun -np 4 MergeSort 100000; 4 processors; 0.081254 secs 100000; 4 processors; 0.083078 secs 200000; 4 processors; 0.096949 secs 400000; 4 processors; 0.105866 secs S ắ p x ế p 1 m ả ng có 400.000 th ự c hi ệ n trên 40 processors [guest@bkluster ~]$ mpirun -np 40 MergeSort 10000; 40 processors; 0.013951 secs 10000; 40 processors; 0.019274 secs 10000; 40 processors; 0.022400 secs 10000; 40 processors; 0.022348 secs 20000; 40 processors; 0.026182 secs 20000; 40 processors; 0.026826 secs 13
20000; 40 processors; 0.031455 secs 10000; 40 processors; 0.019963 secs 10000; 40 processors; 0.019862 secs 10000; 40 processors; 0.020511 secs 10000; 40 processors; 0.024505 secs 10000; 40 processors; 0.022193 secs 20000; 40 processors; 0.032605 secs 10000; 40 processors; 0.024016 secs 20000; 40 processors; 0.034100 secs 10000; 40 processors; 0.029445 secs 20000; 40 processors; 0.034308 secs 10000; 40 processors; 0.030610 secs 10000; 40 processors; 0.030799 secs 10000; 40 processors; 0.031756 secs 10000; 40 processors; 0.033447 secs 10000; 40 processors; 0.027346 secs 10000; 40 processors; 0.028244 secs 20000; 40 processors; 0.035594 secs 20000; 40 processors; 0.035773 secs 10000; 40 processors; 0.030917 secs 10000; 40 processors; 0.037861 secs 20000; 40 processors; 0.039877 secs 10000; 40 processors; 0.033726 secs 40000; 40 processors; 0.042259 secs 20000; 40 processors; 0.044526 secs 40000; 40 processors; 0.044677 secs 40000; 40 processors; 0.044937 secs 40000; 40 processors; 0.040305 secs 80000; 40 processors; 0.051000 secs 40000; 40 processors; 0.054588 secs 80000; 40 processors; 0.056556 secs 160000; 40 processors; 0.060220 secs 80000; 40 processors; 0.066859 secs 400000; 40 processors; 0.074034 secs S ắ p x ế p 1 m ả ng có 1.000.000 th ự c hi ệ n trên 20 processors [guest@bkluster ~]$ mpirun -np 20 MergeSort 50000; 20 processors; 0.057896 secs 50000; 20 processors; 0.063329 secs 50000; 20 processors; 0.062425 secs 50000; 20 processors; 0.075495 secs 100000; 20 processors; 0.084388 secs 50000; 20 processors; 0.096323 secs 50000; 20 processors; 0.099152 secs 100000; 20 processors; 0.106208 secs 50000; 20 processors; 0.106753 secs 50000; 20 processors; 0.112207 secs 50000; 20 processors; 0.114848 secs 100000; 20 processors; 0.117695 secs 50000; 20 processors; 0.119958 secs 200000; 20 processors; 0.101777 secs 100000; 20 processors; 0.126893 secs 100000; 20 processors; 0.324322 secs 14
200000; 20 processors; 0.329881 secs 400000; 20 processors; 0.341076 secs 200000; 20 processors; 0.358863 secs 1000000; 20 processors; 0.378503 secs S ắ p x ế p 1 m ả ng có 10.000.000 th ự c hi ệ n trên 20 processors [guest@bkluster ~]$ mpirun -np 20 MergeSort 500000; 20 processors; 0.651765 secs 500000; 20 processors; 0.652185 secs 500000; 20 processors; 0.659507 secs 500000; 20 processors; 0.767964 secs 1000000; 20 processors; 0.793689 secs 500000; 20 processors; 0.899705 secs 500000; 20 processors; 0.937705 secs 1000000; 20 processors; 1.002965 secs 500000; 20 processors; 1.039666 secs 500000; 20 processors; 1.092781 secs 1000000; 20 processors; 1.110230 secs 1000000; 20 processors; 1.206062 secs 2000000; 20 processors; 1.170763 secs 1000000; 20 processors; 1.635967 secs 2000000; 20 processors; 1.686629 secs 4000000; 20 processors; 1.735968 secs 2000000; 20 processors; 1.968635 secs 500000; 20 processors; 1.050071 secs 500000; 20 processors; 1.143645 secs 10000000; 20 processors; 2.155330 secs Dựa vào kết quả trên, ta có thể thấy sự tối ưu của giải thuật song song để giải quyết các bài toán lớn. Với sự tham gia của nhiều bộ vi xử lí, kết h ợp với giải thuật tính toán xong xong tối ưu xẽ mang lại hiệu quả tính toán cao nhất. 15
KẾT LUẬN Bộ môn giải thuật và tính toán song song trong CNTT là một chuyên ngành đang phát triển mạnh mẽ trong nhiều năm gần đây. Bằng sự hiệu quả của tính toán song song đã giúp cho chúng ta giải quyết một cách thành công các bài toán khó (với số lượng tính toán rất lớn) trong nhiều ngành khoa học. Trong những năm gần đây, bằng việc các nhà sản xuất bộ vi xử lí cố gắng tăng tốc độ tính toán cho bộ vi xử lí của mình. Trong vòng 30 năm qua, các nhà thiết kế CPU đã thực hiện gia tăng tốc độ trong 3 lĩnh v ực chính, hai trong số đó tập trung vào tiến trình thực thi lệnh: Tốc độ xung nhịp, Tối ưu việc thực thi, Bộ nhớ đệm (cache). Việc gia tăng tốc độ xung nhịp cho nhiều chu kỳ xung h ơn. Ch ạy CPU nhanh hơn gần như đồng nghĩa với việc thực hiện công việc nhanh hơn. Việc tối ưu khả năng thực thi cho phép làm được nhiều việc hơn trong mỗi chu kỳ. Các CPU hiện nay có tập lệnh mạnh hơn và thực hiện đủ loại tối ưu từ cơ bản đến phức tạp như tạo tuyến ưu tiên, tiên đoán rẽ nhánh, thực thi nhiều lệnh trong cùng xung nhịp; thậm chí còn sắp xếp lại chuỗi lệnh để cho phép thực thi không theo trình tự. Các kỹ thuật này đều được thiết kế nh ằm làm cho tiến trình thực thi tốt hơn và nhanh hơn, tận dụng tối đa từng chu kỳ xung nhịp. Và câu hỏi đặt ra khi nào thì việc gia tăng tốc đ ộ s ẽ d ừng l ại? Đ ịnh lu ật Moore tiên đoán sự gia tăng theo số mũ rõ ràng không th ể ti ếp t ục mãi khi chúng ta đạt đến giới hạn vật lý. Việc tăng t ốc đ ộ r ồi s ẽ ch ậm l ại và có th ể dừng lại. (Chú thích: định luật Moore chủ yếu áp dụng cho m ật đ ộ transistor, tuy nhiên việc tăng theo cấp số mũ tương tự cũng xảy ra trong các lĩnh vực liên quan như tốc độ xung nhịp. Thậm chí trong những lĩnh vực khác còn gia tăng nhanh hơn, chẳng hạn như lưu trữ dữ liệu). Khi việc tăng tốc độ cho CPU càng ngày càng khó khăn, thì việc xử lí song song có nhiều lợi thế: Tận dụng được tốc độ của CPU, tận dụng th ời gian để thực hiện bài toán (giải quyết cùng một lúc các bài toán). Từ đó làm ra tăng tốc độ tính toán thực tế (bằng cách rút ngắn thời gian thực hiện bài toán). Xử lí song song có các lợi thế: Thứ nhất, bản chất các luồng đi ều khi ển đ ộc lập tách biệt nhau về mặt lí luận. Thứ hai, song hành đem đến sự cải thi ện 16
hiệu suất, hoặc nhờ tận dụng nhiều CPU hoặc thời gian “ch ết” của các ti ến trình trong ứng dụng. Bên cạnh những thuận lợi trên, thì xử lí song song còn có nh ững nh ược điểm sau: Trước hết, không phải tất cả ứng dụng đều có th ể th ực hiện song song. Và trở ngại lớn nhất là việc lập trình song song khó h ơn nhiều so với lập trình theo trình tự quen thuộc trước đây. Thách th ức mà l ập trình viên c ấu trúc khi chuyển sang OO (đối tượng là gì? làm thế nào sử dụng kế th ừa?...) từng gặp cũng là thách thức tương tự cho lập trình viên tuần tự khi chuy ển sang song hành (luồng thực thi là gì? tắc nghẽn là gì? làm th ế nào giải quy ết hoặc tránh nó? những tiến trình nào có thể thực hiện song song...). Đa s ố l ập trình viên hiện nay không am hiểu kỹ thuật song song, cũng như cách đây 15 năm đa số lập trình viên không am hiểu kỹ thuật hướng đối t ượng (OO). Tuy nhiên, mọi thứ đều có thể học được. 17
TÀI LI Ệ U THAM KH Ả O 1. Ananth Gramma, Anshul Gupta, George Karypis, Vipin Kumar: Introduction to Parallel Computing 2 n d , Add Wesley, USA, 2003 2. Parallel Programming in C with MPI and OpenMP" của tác giả Quinn. 3. http://www.lam-mpi.org/ 4. http://www.mpi.org/ 5.http://www.cs.uncc.edu/~abw/parallel/par_prog/resources.htm 6. Slide bài gi ả ng môn “Các k ỹ thu ậ t hi ệ n đ ạ i trong công ngh ệ thông tin và tính toán song song ” c ủa T.S Nguy ễ n H ữ u Đ ứ c 18