Report Parallel

nguyễn khắc anh. mssv: 50400048

chương trình nhân 2 ma trận sử dụng giải thuật song song và thư viện mpi I.Ý tưởng của chương trình: nhân 2 ma trận số nguyên a và b, ma trận kết quả số thực dấu chấm động c. các ma trận là hai chiều nhưng được biểu diễn là các dãy một chiều. trong đó a[mxn], b[nxp], c[mxp]. các thông số m, n, p là do người sử dụng nhập vào. tài nguyên của a, b, c sẽ được cung cấp động dùng hàm malloc. cách giải quyết: • chia việc tính toán ra nhiều phần, mỗi phần do một cpu(một process) đảm nhận. cách chia: • cố gắng chia đều số phần tử cần tính trong ma trận c cho các cpu. ma trận c có mxp phần tử, số cpu là nproc thì mỗi cpu sẽ tính toán cho xấp xỉ mxp/nproc phần tử trong ma trận c, sau đó thu gom ma trận c. • nproc – 1 cpu đầu tiên sẽ đảm nhận việc tính toán cho roundup(mxp/nproc) phần tử trong ma trận c. cpu thứ nproc sẽ đản nhận việc tính toán cho số phần tử còn lại. Ưu điểm: • cách chia này “mịn” hơn cách chia số hàng của ma trận kết quả cho các cpu, trong đó mỗi cpu đảm nhận tính toán cho một số hàng nào đó trong ma trận tích c. • khi số lượng phần tử trong ma trận tích c nhiều thì cách chia này cho kết quả hợp lý, số lượng tính toán ở mỗi cpu là xấp xĩ nhau. ta cần nhớ rằng mpi chỉ cho phép tối đa 40 process do đó cách chia này thường cho kết quả tốt. nhược điểm: • khi số phần tử cần tính toán rất ít (và có lẽ không cần dùng giải thuật song song để tính) và với một vài giá trị của số lượng process thì cách chia trên là sai. vd trường hợp mxp = 16 và nproc = 6. II.các hàm sử dụng trong chương trình: void init_matrix(int *m, int r, int c); mục đích: là khởi tạo giá trị cho các ma trận a và b các thông số truyền cho hàm:

int *m: con trỏ chỉ đến địa chỉ đầu của ma trận nguyên int r cột, int c hàng. các phần tử của ma trận được gán các giá trị random sinh bởi hàm int rand(void);. void print_usage(char *s); hàm dùng để in ra cách sử dụng. chuỗi s là tên chương trình (tên file object). void print(float *mt, int row, int col); hàm dùng để in ma trận kết quả ra màn hình console. các thông số truyền vào có ý nghĩa như sau: float *mt: con trỏ đến địa chỉ đầu của ma trận. int row, int col: số hàng, cột của ma trận. void print_file(float *mt, int row, int col, char *name); hàm dùng để in ma trận kết quả ra file. các thông số truyền vào tương tự như của hàm print. tuy nhiên hàm print_file có thêm biến char *name chỉ tên của file. void calculate(int start, int end, int n, int p); hàm dùng để tính toán một phần của ma trận. do các ma trận dùng trong chương trình là các mảng 1 chiều nên các biến start và end được dùng để chỉ vị trí bắt đầu và vị trí kết thúc cần tính toán. n chỉ số cột của ma trận thứ nhất và p chỉ số cột của ma trận thứ hai, cũng là số cột của ma trận kết quả. int main(int argc, char *argv[]); là hàm chính trong chương trình. trong hàm main process cha (rank = 0) có nhiệm vụ gởi dữ liệu, phân chia việc tính toán, thu gom kết quả và tính thời gian nhân hai ma trận. Ý nghĩa của các hàm và lệnh được giải thích trong phần comment trong source code. III.hàm main: trình tự thực thi trong hàm main xảy ra như sau: 1. nhận các thông số người dùng nhập vào. cung cấp vùng nhớ cho các ma trận. 2. thực hiện các hàm khởi tạo để tạo không gian cho các process 3. nếu là process cha thì khởi tạo giá trị cho các ma trận a, b. 4. broadcast ma trận a, b, c. 5. nếu là process cha a. tính các giá trị khởi đầu và kết thúc trong ma trận c mà các process khác đảm nhận việc tính toán. b. truyền các giá trị khởi đầu và kết thúc vừa tính.

c. tính toán phần việc mà process cha đảm nhận. d. thu gom ma trận c. e. in ra thời gian tính toán. 6. nếu là process con: a. nhận các giá trị khởi đầu và kết thúc do process cha gởi. b. tính toán phần việc của nó. c. gởi kết quả tính toán (là một phần ma trận c) cho process cha. 7. kết thúc chương trình. IV.hàm calculate: chuyển đổi các giá trị khởi đầu và kết thúc thành các giá trị hàng cột. các giá trị hàng, cột gần gũi với ma trận hai chiều. V.kết quả kiểm nghiệm: trường hợp nhân 2 ma trận a[1000x1000] và b[1000x1000] bảng 1: thời gian chạy của trường hợp ma trận kích thước 1000x1000 số cpu 1 2 3 4 5 6 7 8 9 10 11

lần 1(s)

lần 2

lần 3

28.038186 15.206342 11.632732 10.429459 9.147007 8.093839 7.595076 7.205485 7.64108 8.35324 9.18139

28.21939 15.43065 11.75972 10.76177 9.053092 8.145811 7.508397 7.023469 7.720308 9.061447 10.06477

29.73623 15.20551 11.75576 10.38361 9.12834 8.11779 7.593398 7.023635 7.651218 8.372963 9.619515

trung bình 28.6646 15.28083 11.71607 10.52495 9.10948 8.119147 7.565624 7.084196 7.670869 8.595883 9.621892

hình 1: biểu đồ speedup của trường hợp ma trận kích thước 1000x1000

12 10

Speedup

8 Series1

6

Series2

4 2 0 1 2 3 4 5

6 7 8 9 10 11

CPUs

trường hợp nhân 2 ma trận a[100x100] và b[100x100] bảng 2: thời gian chạy của trường hợp ma trận kích thước 100x100 số cpu 1 2 3 4 5 6 7 8 9 10 11

lần 1(s)

lần 2

lần 3

trung bình

0.022519 0.025086 0.031297 0.040219 0.044437 0.042828 0.046051 0.048086 0.05733 0.100594 0.075461

0.022789 0.032102 0.032752 0.040195 0.043389 0.042617 0.045241 0.048331 0.056813 0.060714 0.344643

0.024396 0.032615 0.031275 0.041711 0.043807 0.044842 0.048292 0.049467 0.056791 0.060704 0.074929

0.023235 0.029934 0.031775 0.040708 0.043878 0.043429 0.046528 0.048628 0.056978 0.074004 0.165011

hình 2: biểu đồ speedup của trường hợp ma trận 100x100 1.2 1

Speedup

0.8 0.6

Series1

0.4 0.2 0 1

2

3

4

5

6 CPUs

7

8

9

10

11