Tiểu luận Tìm hiểu các chiến lược song song hóa thuật toán và ứng dụng song song bài toán tính tổng dãy số

TIỂU LUẬN MÔN HỌC CHUY£N §Ò C¸C Kü THUËT HIÖN §¹I TRONG CNTT TÍNH TOÁN SONG SONG Nội dung: Tìm hiểu các chiến lược song song hóa thuật toán và ứng dụng song song bài toán tính tổng dãy số. MỤC LỤC MỞ ĐẦ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. Qua thời gian học tập chuyên đề “Các kỹ thuật hiện đại trong CNTT – Tính toán song song” của thầy giáo TS. Nguyễn Hữu Đức nhóm nghiên cứu chúng em lựa chọn nghiên cứu vấn đề “Tìm hiểu các chiến lược song song hóa thuật toán và ứng dụng song song bài toán tính tổng dãy số”. Với phương thức truyền gói tin bằng cách gọi các hàm trong thư viện của ngôn ngữ thường. Với thời gian và kiến thức còn hạn chế, trong tiểu luận này không tránh khỏi những thiếu sót. Một lần nữa nhóm nghiên cứu xin chân thành cảm ơn thầy giáo TS. Nguyễn Hữu Đức và các bạn trong lớp đã ủng hộ, giúp đỡ trong suốt quá trình thực hiện. Trân trọng cảm ơn! Nhóm nghiên cứu Phần I.Giao thức truyền gói tin(MPI) và các vấn đề song song hóa 1. Kiến trúc máy tính song song Máy tính song song có hai kiến trúc cơ bản: Bộ nhớ phân tán và bộ nhớ dùng chung. Máy tính song song theo kiến trúc bộ nhớ phân tán thực chất là một tập các máy tính tuần tự (gọi là các nut – nodes) cùng làm việc để giải quyết một vấn đề. Mỗi nút có khả năng truy cập nhanh vào bộ nhớ riêng của nó và truy cập vào bộ nhớ của nút khác thông qua mạng giao tiếp, thường là mạng giao tiếp có tốc độ cao. Dữ liệu được trao đổi giữa các nút là các gói tin được truyền trên mạng giao tiếp. Máy tính song song bộ nhớ dùng chung, nhiều bộ xử lý dùng chung một không gian bộ nhớ bằng một bột bus bộ nhớ tốc độ cao. Không gian bộ nhớ dùng chung cho phép các bộ xử lý trao đổi và chia sẻ việc truy cập dữ liệu một cách hiệu quả. Số lượng bộ xử lý dùng trong mô hình bộ nhớ dùng chung là có giới hạn nhỏ. Lý do là số lượng dữ liệu được truyền tải qua bus bộ nhớ đến các bộ xử lý là có giới hạn. Thế hệ tiếp theo của máy tính song song hiện nay sử dụng kết hợp giữa kiến trúc bộ nhớ phân tán và bộ nhớ dùng chung. Mõi nút là một nhóm các bộ xử lý dùng chung bộ nhớ và các nút được kết nối bằng một mạng giao tiếp tốc độ cao. 1.1.Phân tách bài toán Bước đầu tiên để thiết kế một giải thuật song song là phân tích vấn đề cần giải quyết thành các vấn đề nhỏ hơn. Sau đó, các vấn đề nhỏ hơn được gán cho các bộ xử lý làm việc đồng thời. Về cơ bản, có hai kiểu chia nhỏ: 1. Phân tách dữ liệu (Domain decomposition). 2. Phân tách công việc (Function decomposition). 1.2.Phân tách dữ liệu Trong mô hình phân tách dữ liệu hay song song hóa dữ liệu, dữ liệu được chia thành các phần có kích thước xấp xỉ nhau tương ứng với các bộ xử lý khác nhau. Mỗi bộ xử lý sau đó làm việc trên phần dữ liệu tương ứng với nó. Tất nhiên các bộ xử lý có thể cần phải trao đổi dữ liệu với nhau sau những khoảng thời gian nhất định. Mô hình song song hóa dữ liệu chỉ có một luồng điều khiển. Một giải thuật song song dữ liệu bao gồm các phép xử lý tuần tự phù hợp với dữ liệu: Một phép xử lý được bắt đầu chỉ khi phép xử lý trước nó đã kết thúc. Mô hình đơn chương trình đa dữ liệu (Single-Program-Multiple-Data (SPMD)) trong đó chương trình được cài đặt ở tất cả các bộ xử lý thỏa mãn mô hình song song hóa này. Chiến lược này phù hợp với các giải thuật trong đó các bộ xử lý có thể tính toán với một phần dữ liệu có kích thước lớn, sự trao đổi dữ liệu chỉ thực hiện với một số lượng dữ liệu nhỏ ở biên trong các lần lặp. 1.3.Phân tách công việc Chiến lược phân tách dữ liệu không phải là một giải thuật song song hóa tốt nhất cho chương trình song song. Trong trường hợp phân chia dữ liệu, các phần của dữ liệu tương ứng với các tiến trình xử lý khác nhau sẽ cần những khoảng thời gian tương đối khác nhau. Hiệu năng của chương trình bị giới hạn bởi tốc độ của bộ xử lý chậm nhất. Khi đó thời gian rỗi của các bộ xử lý là không được sử dụng. Trong trường hợp này, mô hình phân tách công việc hay song song hóa công việc là hiệu quả hơn mô hình phân tách dữ liệu. Trong song song hóa công việc, bài toán được phân chia thành một số lượng lớn các nhiệm vụ nhỏ hơn và các công việc nhỏ được gán cho các bộ xử lý một cách phù hợp. Các bộ xử lý sẽ kết thúc nhanh chóng một công việc và được gán cho công việc tiếp theo. Song song hóa công việc được thực hiện trên kiến trúc client-server. Các nhiệm vụ được cấp phát cho một nhóm các tiến trình phục vụ bằng một tiến trình chính. Kiến trúc client-server có thể thực hiện hầu như tất cả các kiểu chương trình. 2.Song song hóa dữ liệu và mô hình truyền tin Về mặt lịch sử, có hai cách tiếp cận để viết một chương trình song song: 1.Sử dụng ngôn ngữ song song dữ liệu bằng chỉ dẫn (Directives-based data-parallel language) 2. Truyền gói tin bằng cách gọi các hàm trong thư viện của ngôn ngữ thường. Trong các ngôn ngữ song song dữ liệu bằng chỉ dẫn, như High Performance Fortran (HPF) hay OpenMP, một dòng lệnh tuần tự được thực hiện song song bằng cách thêm vào một chỉ dẫn (nó xuất hiện như là một chú thích trong dòng lệnh tuần tự) báo cho chương trình dịch biết cách phân chia dữ liệu và làm việc đối với các bộ xử lý. Chi tiết cách phân chia dữ liệu, tính toán, và giao tiếp giữa các bộ xử lý được hoàn thành bởi chương trình dịch. Ngôn ngữ song song dữ liệu thường được thực hiện trên kiến trúc bộ nhớ chia sẻ bởi vì không gian bộ nhớ chung làm đơn giản hóa công việc của chương trình dịch. Trong cách tiếp cận truyền gói tin, người lập trình phải tự phân chia dữ liệu và công việc cho các bộ xử lý và tất nhiên là phải quản lý việc trao đổi dữ liệu giữa chúng. Cách tiếp cận này khá phức tạp. Trong ví dụ dưới chúng ta sẽ thực hiện cách tiếp cận này. 3.Tối ưu chương trình song song Mục đích chính khi viết một chương trình song song là thu được hiệu năng thực hiện tốt hơn so với chương trình tuần tự. Với mục đích này, có một số chú ý cần quan tâm khi thiết kế chương trình song song để thu được hiệu năng tốt nhất có thể. Các yêu cầu đó là: Phân chia công việc. Tối thiểu hóa trao đổi dữ liệu. Tránh chồng chập giữa trao đổi dữ liệu và tính toán. 3.1Phân chia công việc Phân chia công việc là nhiệm vụ phân chia công việc giữa các bộ xử lý đang sẵn sàng. Điều này có thể dễ dàng thực hiện khi các phép toán giống nhau được thực hiện bởi tất cả các bộ xử lý (trên các dữ liệu khác nhau). Nhưng nó trở nên không tầm thường khi thời gian thực hiện các tiến trình phụ thuộc vào giá trị dữ liệu làm việc. Khi có sự biến đổi lớn trong thời gian thực hiện, bạn phải thực hiện một vài phương pháp để giải quyết vấn đề này. 3.2Tối thiểu hóa trao đổi dữ liệu Tổng thời gian thực hiện là lợi ích chính của một chương trình song song bởi vì nó là một thành phần cơ bản cần so sánh và cải tiến của tất cả các chương trình. Có 3 thành phần tạo nên thời gian thực hiện: 1.Thời gian tính toán. 2. Thời gian rỗi. 3. Thời gian trao đổi thông tin. “Thời gian tính” là thời gian dùng để thực hiện các tính toán trên dữ liệu. Trường hợp lý tưởng mong đợi là nếu ta có P bộ xử lý làm việc để giải quyết một vấn đề thì công việc sẽ kết thúc trong khoảng thời gian 1/P so với thời gian khi thực hiện tuần tự. Điều này có nghĩa là toàn bộ thời gian bộ xử lý sẽ dùng để tính toán. “Thời gian rỗi” là thời gian bộ xử lý dùng để đợi dữ liệu từ các bộ xử lý khác. Trong thời gian này, các bộ xử lý không làm việc. “Thời gian trao đổi dữ liệu” là thời gian để bộ xử lý gửi và nhận gói tin. Thời gian trao đổi dữ liệu có phụ thuộc vào độ trễ và băng thông. Độ trễ là thời gian cần để thiết lập một giao thức để trao đổi. Băng thông là tốc độ truyền dữ liệu, tính bằng số bit truyền trên một đơn vị thời gian. Chương trình tuần tự không có sự trao đổi dữ liệu giữa các bộ xử lý. Do đó, chúng ta phải tối thiểu hóa thời gian trao đổi để có hiệu năng thực hiện được cải tiến tốt nhất. 3.3Giảm chồng chéo giữa trao đổi dữ liệu và tính toán: Có nhiều cách để giảm thiểu thời gian rỗi của các bộ xử lý, và một ví dụ là sự chồng chéo giữa trao đổi dữ liệu và tính toán. Đó là việc chiếm giữ một tiến trình cho một hay nhiều công việc mới trong khi nó đang chờ trao đổi dữ liệu để kết thúc. 4. MPI MPI được coi như là một chuẩn thực hiện của mô hình “truyền gói tin” trong tính toán song song. Quá trình tính toán song song bao gồm một số lượng tiến trình, mỗi tiến trình làm việc với một bộ dữ liệu cụ bộ. Mỗi tiến trình có các biến cục bộ, và không có cơ chế nào để một tiến trình có thể truy cập trực tiếp vào bộ nhớ của một tiến trình khác. Trao đổi dữ liệu giữa các tiến trình được thực hiện bằng cách truyền gói tin, là phương tiện duy nhất để thực hiện gửi và nhận dữ liệu giữa các tiến trình. Chú ý rằng mô hình bao gồm các tiến trình, trên nguyên tắc nó không cần phải chạy trên các bộ xử lý khác nhau. Lý do chính khiến mô hình này trở nên hữu dụng vì nó thực sự phổ biến. Về bản chất, mọi kiểu tính toán song song đều có thể thực hiện trên mô hình truyền gói tin. Thêm vào đó, mô hình này: - Có thể thực hiện trên nhiều nền tảng khác nhau, từ kiến trúc nhiều bộ xử lý dùng chung bộ nhớ đến trạm làm việc thậm chí là một máy đơn bộ xử lý. - Cho phép quản lý dữ liệu và tiến trình chi tiết hơn so với ứng dụng song song theo mô hình bộ nhớ dùng chung. Hơn nữa chương trình có thể tạo ra một hiệu năng xử dụng cao hơn. 4.1Mục đích của MPI Mục đích chính của MPI là cung cấp thư viện đính kèm chương trình nguồn để một chương trình MPI có thể dịch và chạy như nhau trên bất kỳ nền tảng nào. - Cho phép thực thi một cách có hiệu quả trong nhiều kiến trúc. MPI cũng cung cấp một số lớn chức năng: các kiểu trao đổi dữ liệu khác nhau, các tiến trình đặc biệt để tập hợp các phép xử lý, và cho phép người dùng tự định nghĩa giao thức truyền. - Hỗ trợ các kiến trúc song song không đồng nhất. 4.2Các đặc tính cơ bản của một chương trình MPI Một chương trình MPI bao gồm nhiều chương trình tuần tự có trao đổi dữ liệu với nhau thông qua việc gọi các hàm trong thư viện. Các hàm này thuộc bốn lớp cơ bản: 1. Khởi tạo, quản lý và kết thúc trao đổi. 2. Trao đổi giữa hai tiến trình. 3. Trao đổi giữa một nhóm các tiến trình. 4. Tạo các định dạng dữ liệu bất kỳ. Lớp đầu tiên là các hàm được gọi để khởi đầu quá trình trao đổi, xác định số lượng bộ xử lý được sử dụng, tạo một nhóm con các bộ xử lý, xác định bộ xử lý nào đang chạy chương trình hiện tại. Trong bài toán tính tổng 1 dãy số chúng ta sử dụng các hàm MPI sau: MPI_Init(); khởi tạo quá trình song song. MPI_Finalize(); kết thúc quá trình song song. MPI_Comm_rank(); xác định tên tiến trình. MPI_Comm_size(); xác định tổng số tiến trình chạy song song; Lớp thứ hai là các hàm, được gọi để trao đổi dữ liệu điểm - đến - điểm, với các kiểu gửi và nhận dữ liệu khác nhau giữa hai bộ xử lý. MPI_Send(); gửi dữ liệu đến một tiến trình. MPI_Recv(); nhận dữ liệu từ một tiến trình. Phần 2. Mã nguồn 2.1. Chương trình tuần tự Chương trình tuần tự tính tổng của một dãy số #include#include#include#includeint main (){    clrscr();    int N, i;    int* a = NULL;    long SUM = 0;    printf("\n Nhap vao N:");    scanf("%d", &N);    a = (int*)malloc(N*sizeof(int));    for(i = 0; i < N; i++)    {        printf("\n Nhap phan tu thu %d: ", i);        scanf("%d", &a[i]);        SUM += a[i];    }    for (i = 0; i < N; i++)    {    printf("%d        ", a[i]);    }    printf("\n SUM = %ld", SUM);    free(a);    getch();    return 0;} 2.2. Chương trình song song dùng MPI Chương trình tính tổng của một dãy số #include #include #define max 5 double array[2*max]={1,5,4,7,5,8,19,7,6,6}; void master(); void slave(); int main( argc, argv ) int argc; char **argv; { int myrank; MPI_Init( &argc, &argv ); MPI_Comm_rank(MPI_COMM_WORLD,&myrank); // Master chạy trên process 0, các Slave chạy trên các process còn lại if (myrank==0) master(); else slave(); MPI_Finalize(); return 0; } // Master void master(){ int size,i; double newarray[max]; double firstsum,secondsum,finalsum; MPI_Status status; MPI_Comm_size(MPI_COMM_WORLD,&size); // Gửi nửa mảng đầu cho Slave thứ nhất (process 1) for (i=0;i<max;i++){ newarray[i]=array[i];} MPI_Send(&newarray,max,MPI_DOUBLE,1,0, PI_COMM_WORLD); // Gửi nửa mảng sau cho Slave thứ hai (process 2) for (i=max;i<2*max;i++){ newarray[i-max]=array[i];} MPI_Send(&newarray,max,MPI_DOUBLE,2,0, PI_COMM_WORLD); // Nhận kết quả tính tổng nửa mảng đầu từ Slave thứ nhất (process 1) MPI_Recv(&firstsum,1,MPI_DOUBLE,1, 0,MPI_COMM_WORLD, &status ); // Nhận kết quả tính tổng nửa mảng sau từ Slave thứ hai (process 2) MPI_Recv(&secondsum,1,MPI_DOUBLE,2, 0,MPI_COMM_WORLD,&status); // Tính tổng của mảng  finalsum=firstsum+secondsum; // In kết quả printf("Tong cua mang la: %.4f\n",finalsum); return ; } 2.3. Kết quả Chúng tôi đã tiến hành chạy thử nghiệm trên hệ thống bkluster.hut.edu. Kết quả cụ thể như sau: Với dãy : 1,5,4,7,5,8,19,7,6,6 , số tiến trình chạy np = 3 Kết quả 68 TÀI LIỆU THAM KHẢO Tài liệu [1] Nguyễn Văn Ba, Phát triển hệ thống hướng đối tượng với UML và C++, Nhà xuất bản ĐH Quốc gia Hà nội, 2007. [2] Slide bài giảng của TS. Nguyễn Hữu Đức Trang Web [1] MPI Tutorial [2] Open Source High Performance Computing