c - 在C中使用多线程做矩阵乘法

Question

因此，我尝试编写一个程序来使用多个线程进行矩阵乘法，然后绘制所用时间与所用线程数之间的图表。 我使用了以下方法:

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
pthread_mutex_t lock;

#define M 200
#define N 300
#define P 400
#define X 2 // Number of Threads
#define RED "\x1b[31m"
#define GREEN "\x1b[32m"

int A[M][N], B[N][P], C[M][P], D[M][P];

int row = 0;

void *matrixMulti(void *arg)
{
    pthread_mutex_lock(&lock);
    int i = row++;

    for (int j = 0; j < P; j++)
    {
        C[i][j] = 0;
        for (int k = 0; k < N; k++)
        {
            C[i][j] += A[i][k] * B[k][j];
        }
    }

    
    pthread_exit(NULL);
    pthread_mutex_unlock(&lock);
}

void matrixMultiplicationWithoutThreading();
void matrixMultiplicationWithThreading();
void verifyIfBothMatrixAreSame();
int main()
{
    int m, n, p;
    // A: m*n Matrix, B: n*p Matrix
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            A[i][j] = rand() % 10;
    // scanf("%d", &A[i][j]);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < P; j++)
            B[i][j] = rand() % 10;
    // scanf("%d", &B[i][j]);
    
    struct timeval start, end;
    gettimeofday(&start, NULL);
    matrixMultiplicationWithoutThreading();
    gettimeofday(&end, NULL);
    double time = (end.tv_sec - start.tv_sec) * 1e6;
    time = (time + end.tv_usec - start.tv_usec) * 1e-6;
    printf("The time taken by simple matrix calculation without threding is %0.6f\n", time);

    struct timeval start_th, end_th;
    gettimeofday(&start_th, NULL);
    matrixMultiplicationWithThreading();
    gettimeofday(&end_th, NULL);
    time = (end_th.tv_sec - start_th.tv_sec) * 1e6;
    time = (time + end_th.tv_usec - start_th.tv_usec) * 1e-6;
    printf("The time taken by using the Threading Method with %d threads is %0.6f\n", X, time);

    verifyIfBothMatrixAreSame();
}

void matrixMultiplicationWithThreading()
{
    pthread_t threads[X];
    for (int i = 0; i < X; i++)
    {
        threads[i] = (pthread_t)-1;
    }

    // Computation Started:
    for (int i = 0; i < M; i++)
    {

        // At any moment only X threads at max are working
        if (threads[i] == (pthread_t)-1)
            pthread_create(&threads[i % X], NULL, matrixMulti, NULL);
        else
        {
            pthread_join(threads[i % X], NULL);
            pthread_create(&threads[i % X], NULL, matrixMulti, NULL);
        }
    }
    for (int i = 0; i < X; i++)
        pthread_join(threads[i], NULL);
    // Computation Done:
}

void matrixMultiplicationWithoutThreading()
{
    // Computation Started:
    for (int i = 0; i < M; i++)
        for (int j = 0; j < P; j++)
        {
            D[i][j] = 0;
            for (int k = 0; k < N; k++)
                D[i][j] += A[i][k] * B[k][j];
        }
    // Computation Done:
}
void verifyIfBothMatrixAreSame()
{
    for (int i = 0; i < M; i++)
        for (int j = 0; j < P; j++)
        {
            if (C[i][j] != D[i][j])
            {
                printf(RED "\nMatrix's are not equal something wrong with the computation\n");
                return;
            }
        }
    printf(GREEN "\nBoth Matrixes are equal thus verifying the computation\n");
}

现在，此代码有时有效，有时无效，例如结果与实际结果不匹配。同样，此代码在其中一个 Linux 虚拟机中给出了段错误。此外，即使它工作正常，它也不会给出渐近递减的图形。相反，时间几乎是恒定的，随着线程数的任意变化。

有人可以帮忙解决这个问题吗，比如为什么会这样？我在互联网上找到了解决这个问题的多种方法；其中一些不起作用(很少但会发生)，但我还没有看到我的方法；我认为这可能是一个问题。那么，任何人都可以对使用 pthread_create(&threads[i % X], NULL, matrixMulti, NULL) 发表评论，比如为什么这不是一个好主意？

编辑: 我尝试采纳建议并优化代码，我没有完成矩阵乘法高效方法，因为我们被要求执行 O(n^3) 方法，但我尝试正确执行线程。这是正确的吗？

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <math.h>

#define M 2
#define N 2
#define P 2
#define X 40 // Number of Threads
#define RED "\x1b[31m"
#define GREEN "\x1b[32m"

int t = 0; // Computation done by the first usedXFullthreads
int usedXFull = 0;

int A[M][N], B[N][P], C[M][P], D[M][P];

int row = 0;

void *matrixMulti(void *arg)
{
    int* l = (int *)arg;
    int n = *l;
    int i = 0, j = 0, k = 0, comp = 0;
    if (n <= usedXFull)
    {
        i = n * t / (N * P);
        j = (n * t - N * P * i) / N;
        k = n * t - N * P * i - N * j;
        if (n == usedXFull)
            comp = M * N * P - usedXFull * t;
        else
            comp = t;
    }
    while (comp)
    {
        if (i == M)
            printf(RED "Some fault in the code\n\n");
        C[i][j] += A[i][k] * B[k][j];
        comp--;
        k++;
        if (k == N)
        {
            j++;
            if (j == P)
            {
                i++;
                j = 0;
            }
            k = 0;
        }
    }

    return NULL;
}

void matrixMultiplicationWithoutThreading();
void matrixMultiplicationWithThreading();
void verifyIfBothMatrixAreSame();
int main()
{
    int m, n, p;
    // A: m*n Matrix, B: n*p Matrix
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            A[i][j] = rand() % 10;
    // scanf("%d", &A[i][j]);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < P; j++)
            B[i][j] = rand() % 10;
    // scanf("%d", &B[i][j]);
    for (int i = 0; i < M; i++)
        for (int j = 0; j < P; j++)
            C[i][j] = 0;

    struct timeval start, end;
    gettimeofday(&start, NULL);
    matrixMultiplicationWithoutThreading();
    gettimeofday(&end, NULL);
    double time = (end.tv_sec - start.tv_sec) * 1e6;
    time = (time + end.tv_usec - start.tv_usec) * 1e-6;
    printf("The time taken by simple matrix calculation without threding is %0.6f\n", time);

    struct timeval start_th, end_th;
    gettimeofday(&start_th, NULL);
    matrixMultiplicationWithThreading();
    gettimeofday(&end_th, NULL);
    time = (end_th.tv_sec - start_th.tv_sec) * 1e6;
    time = (time + end_th.tv_usec - start_th.tv_usec) * 1e-6;
    printf("The time taken by using the Threading Method with %d threads is %0.6f\n", X, time);

    verifyIfBothMatrixAreSame();
}

void matrixMultiplicationWithThreading()
{
    int totalComp = M * N * P; // Total Computation
    t = ceil((double)totalComp / (double)X);
    usedXFull = totalComp / t;
    int computationByLastUsedThread = totalComp - t * usedXFull;
    int computationIndex[X];

    pthread_t threads[X];

    // Computation Started:
    for (int i = 0; i < X; i++)
    {
            computationIndex[i] = i;
        int rc = pthread_create(&threads[i], NULL, matrixMulti, (void *)&computationIndex[i]);
        if (rc)
        {
            printf(RED "ERROR; return code from pthread_create() is %d\n", rc);
            exit(-1);
        }
    }
    for (int i = 0; i < X; i++)
        pthread_join(threads[i], NULL);
    // Computation Done:
}

void matrixMultiplicationWithoutThreading()
{
    // Computation Started:
    for (int i = 0; i < M; i++)
        for (int j = 0; j < P; j++)
        {
            D[i][j] = 0;
            for (int k = 0; k < N; k++)
                D[i][j] += A[i][k] * B[k][j];
        }
    // Computation Done:
}
void verifyIfBothMatrixAreSame()
{
    for (int i = 0; i < M; i++)
        for (int j = 0; j < P; j++)
        {
            if (C[i][j] != D[i][j])
            {
                printf(RED "\nMatrix's are not equal something wrong with the computation\n");
                return;
            }
        }
    printf(GREEN "\nBoth Matrixes are equal thus verifying the computation\n");
}

Answer 1

代码中有很多问题。以下是一些要点:

• lock 未使用必需的(也未释放)pthread_mutex_init 进行初始化。
• 在矩阵乘法中不需要锁:应该首选工作共享(特别是因为当前锁使您的代码完全串行运行)。
• 使用pthread_exit 通常不是一个好主意，至少在这里是这样。考虑只返回 NULL。此外，在 matrixMulti 中返回某些内容是强制性的。请启用编译器警告以检测此类事件。
• 在基于 0..M 的循环中存在 threads[i] 的越界。
• 无需创建 M 个线程。您可以创建 2 个线程并将工作沿着基于 M 的维度平均分成 2 个部分。在只允许 2 个线程同时运行的情况下创建 M 个线程只会无缘无故地增加更多开销(操作系统创建和调度线程需要时间)。
• 动态分配大型数组通常比使用静态全局 C 数组更好。
• 最好避免使用全局变量并使用arg 参数来获取特定于线程的数据。

要设计快速矩阵乘法，请考虑阅读 this article .例如，ijk 循环嵌套是非常低效的，真的不应该为了性能而使用(在缓存中效率不高)。此外，请注意，您可以为此使用 BLAS 库(它们经过高度优化且易于使用)，但我想这是一项家庭作业。此外，请注意，您可以使用 OpenMP 而不是 pthread，这样可以使代码更短且易于阅读。