2014-05-18

作業系統 Thread 程式作業

1. C++ Thread 練習
2. 代碼
3. 其他

C++ Thread 練習

作業要求

作業一:應用 Thread 撰寫任意程式(語言不限)，繳交方式 FTP:140.115.155.192(選擇自己學號的資料夾上傳) 帳:os2014 密碼不知道者請再問助教，檔案名稱: “作業一學號姓名_第幾版” ex:”作業一10252200x林大乖_v1” 繳交內容:壓縮檔(報告word 以及程式碼,執行檔)，截止日期:2014/05/25(日)23:59

程式功能

兩個 n*n 矩陣相乘，在最基礎的 O(n^3) 效能上，使用 Thread 等相關技巧使其加速。

運行

Mac OSX
```
$ clang -pthread x.cpp -o x
```
Linux
```
$ gcc -lpthread x.cpp -o x
```

測試效率

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

#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) {
    //clock_t start, finish;
    //start = clock(); // start time clock
    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);
    //finish = clock(); // finish time clock
    //printf("Time: %lf\n", (double)(finish - start)/1000);
    return 0;
}

matrix[v2].cpp

#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) {
    //clock_t start, finish;
    //start = clock(); // start time clock
    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);
    //finish = clock(); // finish time clock
    //printf("Time: %lf\n", (double)(finish - start)/1000);
    return 0;
}

matrix[v3].c

#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");
    //clock_t start, finish;
    //start = clock(); // start time clock
    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);
    }
    //finish = clock(); // finish time clock
    //printf("Time: %lf\n", (double)(finish - start)/1000);
    return 0;
}

其他

雖然作業可以有其他語言的相關 Thread，在 Java 作品方面可以查看 Github。

Morris' Blog