contents
作業要求
作業一:應用 Thread 撰寫任意程式(語言不限),繳交方式 FTP:140.115.155.192(選擇自己學號的資料夾上傳) 帳:os2014 密碼不知道者請再問助教,檔案名稱: “作業一學號姓名第幾版” ex:”作業一_10252200x林大乖_v1” 繳交內容:壓縮檔(報告word 以及 程式碼,執行檔),截止日期:2014/05/25(日)23:59
程式功能
兩個 n*n
矩陣相乘,在最基礎的 O(n^3)
效能上,使用 Thread 等相關技巧使其加速。
運行
測試效率
- Mac OSX and Linux
$ time ./a.out
測試結果
測試環境為 2013 Mac Air 1.3 GHz Intel Core i5 上對 1024 x 1024
的矩陣進行相乘的統計結果。
matrix.cpp
最原始的一般寫法,直接使用 O(n^3)
。運行時間約在 20 秒左右完成。
matrix[v2].cpp
使用轉置矩陣後,在進行運算,這種方式是加快作業系統中的快取層,速度提升至約在 4 秒左右完成。
matrix[v3].cpp
建立在 matrix[v2].cpp
的基礎上,使用 4 條 thread,分別對處理的 column 進行分割操作,速度約在 2 秒內完成。
- matrix[v4].cpp
與 matrix[v3].cpp
類似,調整 thread 的數量,查看效率變化,但是速度沒有更快的趨勢。
結論
Thread 多不代表會比較快,而是該程式佔有 CPU 的機會比較高,使用的資源就會比較多。在整個作業系統中,Thread 多上下文切換的次數就會上升,對於作業系統整體效率是下降的,但是又不能沒有 Thread,看起來像是所有程式同時在運行,也要防止落入死機無法動彈的情況。
而在 thread 上面會發現,當數量達到一定程度後,速度就不會上升,有一部分是因為 CPU 超頻運作。
超頻(英語:Overclocking)是把一個電子配件的時脈速度提升至高於廠方所定的速度運作,從而提升性能的方法,但此舉有可能導致該配件穩定性下降。
可能是長時間閒置的 CPU 發現有大規模的工作運行,把時脈速度升起。
代碼
matrix.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
#define MAX_N 1024 double A[MAX_N][MAX_N]; double B[MAX_N][MAX_N]; double C[MAX_N][MAX_N]; void multiply(double A[][MAX_N], double B[][MAX_N], double C[][MAX_N]) { for (int i = 0; i < MAX_N; i++) { for (int j = 0; j < MAX_N; j++) { double sum = 0; for (int k = 0; k < MAX_N; k++) { sum += A[i][k] * B[k][j]; } C[i][j] = sum; } } } int main(void) { for (int i = 0; i < MAX_N; i++) { for (int j = 0; j < MAX_N; j++) { A[i][j] = i; B[i][j] = j; } } multiply(A, B, C); return 0; }
|
matrix[v2].cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
#include <stdio.h> #include <stdlib.h> #include <algorithm> #include <time.h> using namespace std; #define MAX_N 1024 double A[MAX_N][MAX_N]; double B[MAX_N][MAX_N]; double C[MAX_N][MAX_N]; void trans(double A[][MAX_N]) { for (int i = 0; i < MAX_N; i++) { for (int j = i+1; j < MAX_N; j++) { swap(A[i][j], A[j][i]); } } } void multiply(double A[][MAX_N], double B[][MAX_N], double C[][MAX_N]) { trans(B); for (int i = 0; i < MAX_N; i++) { for (int j = 0; j < MAX_N; j++) { double sum = 0; for (int k = 0; k < MAX_N; k++) { sum += A[i][k] * B[j][k]; } C[i][j] = sum; } } } int main(void) { for (int i = 0; i < MAX_N; i++) { for (int j = 0; j < MAX_N; j++) { A[i][j] = i; B[i][j] = j; } } multiply(A, B, C); return 0; }
|
matrix[v3].c
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
|
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <pthread.h> #define MAX_N 1024 double A[MAX_N][MAX_N]; double B[MAX_N][MAX_N]; double C[MAX_N][MAX_N]; void trans(double A[][MAX_N]) { double x; int i, j; for (i = 0; i < MAX_N; i++) { for (j = i+1; j < MAX_N; j++) { x = A[i][j]; A[i][j] = A[j][i]; A[j][i] = x; } } } #define MAX_THREAD 4 void *multiply(void *arg) { int id = *((int *)arg); int st = id * MAX_N / MAX_THREAD; int ed = (id + 1) * MAX_N / MAX_THREAD - 1; int i, j, k; for (i = st; i <= ed; i++) { for (j = 0; j < MAX_N; j++) { double sum = 0; for (k = 0; k < MAX_N; k++) { sum += A[i][k] * B[j][k]; } C[i][j] = sum; } } return NULL; } int main(void) { puts("Thread version"); int i, j; for (i = 0; i < MAX_N; i++) { for (j = 0; j < MAX_N; j++) { A[i][j] = i; B[i][j] = j; } } trans(B); pthread_t *threads; threads = (pthread_t *) malloc(MAX_THREAD * sizeof(pthread_t)); for (int i = 0; i < MAX_THREAD; i++) { int *p = (int *) malloc(sizeof(int)); *p = i; pthread_create(&threads[i], NULL, multiply, (void *)(p)); } for (i = 0; i < MAX_THREAD; i++) { pthread_join(threads[i], NULL); } return 0; }
|
其他
雖然作業可以有其他語言的相關 Thread,在 Java 作品方面可以查看 Github。
近期评论