Умножение матриц с разделением на потоки

@compl · Регистрация: 23.10.2012

Студворк — интернет-сервис помощи студентам

Здравствуйте!

Пытаюсь написать программу, которая умножает матрицы, но с разделением на потоки. Вот, что получилось:

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include "stdafx.h"
#include <iostream>
#include <ctime>
#include "windows.h"
#include "process.h"
 
using namespace std;
 
const int NumberOfThreads = 2;
 
const int n = 1000;
const int m = 1000;
const int k = 1000;
 
int **matr_1 = new int *[n];
int **matr_2 = new int *[m];
int **matr_3 = new int *[n];
 
unsigned __stdcall ThreadFunctionMult(void *pData)
{
    for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < k; j++)
                {
                    matr_3[i][j] = 0;
                    for (int z = 0; z < m; z++)
                        matr_3[i][j] += matr_1[i][z] * matr_2[z][j];
                }
            }
    return 0;
}
 
int main()
{
 
    for (int i = 0; i<n; i++)
        matr_1[i] = new int[m];
 
    for (int i = 0; i<m; i++)
        matr_2[i] = new int[k];
 
    for (int i = 0; i<n; i++)
        matr_3[i] = new int[k];
 
    srand(time(0));
 
    for (int i = 0; i<n; i++)
    {
        for (int j = 0; j<m; j++)
        {
            matr_1[i][j] = rand() % 3;
            //cout << matr_1[i][j] << " ";
        }
        //cout << endl;
    }
 
    //cout << endl;
 
    for (int i = 0; i<m; i++)
    {
        for (int j = 0; j<k; j++)
        {
            matr_2[i][j] = rand() % 3;
            //cout << matr_2[i][j] << " ";
        }
        //cout << endl;
    }
 
    //cout << endl;
 
    setlocale(LC_ALL, "rus");
    clock_t start, end;
    start = clock();
 
    HANDLE hThreads[NumberOfThreads];
    unsigned tid;
    for (int i = 0; i < NumberOfThreads; i++)
        hThreads[i] = (HANDLE)_beginthreadex(NULL, 0, ThreadFunctionMult, (void *)i, 0, &tid);
    WaitForMultipleObjects(NumberOfThreads, hThreads, TRUE, INFINITE);
    for (int i = 0; i < NumberOfThreads; i++)
        CloseHandle(hThreads[i]);
 
    end = clock() - start;
    printf("Время выполнения программы с использованием распараллеливания: %f\n", end / (double)CLOCKS_PER_SEC);
 
    //for (int i = 0; i < n; i++)
    //{
    //  for (int j = 0; j < n; j++)
    //      cout << matr_3[i][j] << " ";
    //  cout << endl;
    //}
 
    delete[]matr_1;
    delete[]matr_2;
    delete[]matr_3;
 
    return 0;
}

Умножает всё правильно для различных размерностей матриц. Но время выполнения, например, для одного и двух потоков получается одинаковое, а иногда даже для одного потока меньше. В чем может быть ошибка? Или у меня с компом что-то (2,30 GHz)? Не могли бы Вы написать, сколько у Вас время выполнения для одного и двух потоков.

Tulosba · 07.03.2015, 21:29

clock() считает такты процессора в активном режиме. В режиме ожидания такты, возвращаемые clock(), не увеличиваются. Надо системное время сравнивать.

@zss · 07.03.2015, 21:31

Вот код мультипроцессорного умножения на языке MC#

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
66
67
68
69
70
71
72
73
// MC# Examples
// Parallel matrix multiplication.
//
using System;
public class MatrixMultiplierParallel
{
    public static void Main()
    {
        int         i, j;
 
        int N = 1000;
        int M = 6; 
        double[,]   A = new double[N, N];
        double[,]   B = new double[N, N];
        double[,]   C = new double[N, N];
 
        Random      rnd = new Random();
 
        //  Matrix content generation
 
        for (i = 0; i < N; ++i)
        {
            for (j = 0; j < N; ++j)
            {
                A[i, j] = rnd.NextDouble();
                B[i, j] = rnd.NextDouble();
                C[i, j] = 0.0;
            }
        }
 
        // Divide matrix between asynchronous processes
 
        int q = N / M,            
            r = N % M;            
 
        int from = 0,to;
 
        MatrixMultiplierParallel mmp = new MatrixMultiplierParallel();
 
        DateTime dt1 = DateTime.Now; // Check time
 
        for (i = 0; i < M; ++i)
        {
            to = from + q + (i < r ? 1 : 0);
 
            mmp.Multiply(N, A, B, C, from, to, mmp.sendStop); // Start the async method
            from = to;
        }
 
        for (i = 0; i < M; ++i) mmp.getStop?(); // Wait the process termination
 
        Console.WriteLine("Matrix size: {0}, Number of parts: {1}.", N, M);
        Console.WriteLine("Time was " + (DateTime.Now - dt1).TotalSeconds + " sec."); // Check the time
        Console.ReadLine();
    }
 
    public handler getStop int() & channel sendStop(int x)
    {
        return x;
    }
 
    public async Multiply (int N, double[,] A, double[,] B, double[,] C, int from, int to, channel (int) sendStop) // Async!
    {
        for (int i = from; i < to; i++)
        {
            for (int j = 0; j < N; j++)
            {
                for (int k = 0; k < N; k++) C [i, j] += A [i, k] * B [k, j];
            }
        }
        sendStop ! (0);
    }
}

Отсюда возьмите главную идею.
Матрицу надо разбить по строкам на блоки по N / M строк (M - количество процессов) и распределить их по потокам.

@compl · 08.03.2015, 20:40 **[ТС]**

Да, про распределение я забыл. Но теперь почему-то вообще неправильно считает. Я правильно сделал? Вот код:

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include "stdafx.h"
#include <iostream>
#include <ctime>
#include "windows.h"
#include "process.h"
 
using namespace std;
 
const int NumberOfThreads = 1;
 
const int n = 3;
const int m = 3;
const int k = 3;
 
int **matr_1 = new int *[n];
int **matr_2 = new int *[m];
int **matr_3 = new int *[n];
 
int q = n / NumberOfThreads,
r = n % NumberOfThreads;
 
int from = 0, to;
 
unsigned __stdcall ThreadFunctionMult(void *param)
{
    for (int i = from; i < to; i++)
            {
                for (int j = 0; j < k; j++)
                {
                    matr_3[i][j] = 0;
                    for (int z = 0; z < m; z++)
                        matr_3[i][j] += matr_1[i][z] * matr_2[z][j];
                }
            }
    return 0;
}
 
int main()
{
    for (int i = 0; i<n; i++)
        matr_1[i] = new int[m];
 
    for (int i = 0; i<m; i++)
        matr_2[i] = new int[k];
 
    for (int i = 0; i<n; i++)
        matr_3[i] = new int[k];
 
    srand(time(0));
 
    for (int i = 0; i<n; i++)
    {
        for (int j = 0; j<m; j++)
        {
            matr_1[i][j] = rand() % 3;
            cout << matr_1[i][j] << " ";
        }
        cout << endl;
    }
 
    cout << endl;
 
    for (int i = 0; i<m; i++)
    {
        for (int j = 0; j<k; j++)
        {
            matr_2[i][j] = rand() % 3;
            cout << matr_2[i][j] << " ";
        }
        cout << endl;
    }
 
    cout << endl;
 
    setlocale(LC_ALL, "rus");
    clock_t start, end;
    start = clock();
 
    HANDLE hThreads[NumberOfThreads];
    unsigned id;
    for (int i = 0; i < NumberOfThreads; i++){
        to = from + q + (i < r ? 1 : 0);
        hThreads[i] = (HANDLE)_beginthreadex(NULL, 0, ThreadFunctionMult, (void *)i, 0, &id);
        from = to;
    }
    WaitForMultipleObjects(NumberOfThreads, hThreads, TRUE, INFINITE);
    for (int i = 0; i < NumberOfThreads; i++)
        CloseHandle(hThreads[i]);
 
    end = clock() - start;
    printf("Время выполнения программы: %f\n", end / (double)CLOCKS_PER_SEC);
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << matr_3[i][j] << " ";
        cout << endl;
    }
 
    delete[]matr_1;
    delete[]matr_2;
    delete[]matr_3;
 
    return 0;
}

@zss · 08.03.2015, 20:58

Сообщение от compl

int from = 0, to;

Не могут быть общими для всех процессов,
они у них разные.

@compl · 08.03.2015, 21:05 **[ТС]**

Сообщение от zss

Не могут быть общими для всех процессов,
они у них разные.

Точно. Но как тогда можно сделать, если эти переменные используются и в функции, и в main?

@zss · 08.03.2015, 21:28

Надо как-то передать номер процесса через param.
Я не очень разобрался в параметрах _beginthreadex.
Поробовал вот так

C++
1
2
3
4
5
6
7
8
int from[NumberOfThreads] = {0}, to[NumberOfThreads] = {0};
 
unsigned __stdcall ThreadFunctionMult(void *param)
{
    int iNum=*(reinterpret_cast<int*>(param));
    for (int i = from[iNum]; i < to[iNum]; i++)
...
        hThreads[i] = (HANDLE)_beginthreadex(NULL, 0, ThreadFunctionMult, (void *)&i, 0, &id); // (void *)&i

Но считывается сразу макс значение i
как-то передать надо ЗНАЧЕНИЕ i

Добавлено через 11 минут
Вот так получилось (может можно и покрасивее)

C++
1
2
3
4
5
6
7
8
    int noms[NumberOfThreads];
    for (int i = 0; i < NumberOfThreads; i++){
        to[i] = from[i] + q + (i < r ? 1 : 0);
        noms[i]=i;
        hThreads[i] = (HANDLE)_beginthreadex(NULL, 0, ThreadFunctionMult, (void *)(noms+i), 0, &id);
        if(i<NumberOfThreads-1)
             from[i+1] = to[i];
    }

@compl · 08.03.2015, 21:42 **[ТС]**

Спасибо. Но разбираться придется долго.

Я пытался вот так сделать, но работает правильно только тогда, когда размерность массива и кол-во процессов четное или нечетное одновременно. Т.к. int целые только, а, например, 3 (размерность матрицы) делится на 2 и получается 1.5 и int округляет до 1. И всегда получается, что недосчитывается последний столбец или строка.

C++
1
2
3
4
5
6
7
8
9
10
11
unsigned __stdcall ThreadFunctionMult(void *param)
{
    int id = (int)param;
    int start = n / NumberOfThreads * id;
    int end = n / NumberOfThreads * (id + 1); 
    cout << "id=" << id;
    cout << "start=" << start;
    cout << "end=" << end;
 
    for (int i = start; i < end; i++)
...

@zss · 08.03.2015, 22:41

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <ctime>
#include <windows.h>
#include <process.h>
 
using namespace std;
 
const int NumberOfThreads = 6;
 
const int n = 1000;
const int m = 1000;
const int k = 1000;
 
int **matr_1 = new int *[n];
int **matr_2 = new int *[m];
int **matr_3 = new int *[n];
 
int q = n / NumberOfThreads,
r = n % NumberOfThreads;
 
int from[NumberOfThreads] = {0}, to[NumberOfThreads] = {0};
 
unsigned __stdcall ThreadFunctionMult(void *param)
{
    int iNum=*(reinterpret_cast<int*>(param));
    for (int i = from[iNum]; i < to[iNum]; i++)
            {
                for (int j = 0; j < k; j++)
                {
                    matr_3[i][j] = 0;
                    for (int z = 0; z < m; z++)
                        matr_3[i][j] += matr_1[i][z] * matr_2[z][j];
                }
            }
    return 0;
}
 
int main()
{
    for (int i = 0; i<n; i++)
        matr_1[i] = new int[m];
 
    for (int i = 0; i<m; i++)
        matr_2[i] = new int[k];
 
    for (int i = 0; i<n; i++)
        matr_3[i] = new int[k];
 
    srand(time(0));
 
    for (int i = 0; i<n; i++)
    {
        for (int j = 0; j<m; j++)
        {
            matr_1[i][j] = rand() % 3;
            //cout << matr_1[i][j] << " ";
        }
        //cout << endl;
    }
 
    //cout << endl;
 
    for (int i = 0; i<m; i++)
    {
        for (int j = 0; j<k; j++)
        {
            matr_2[i][j] = rand() % 3;
            //cout << matr_2[i][j] << " ";
        }
        //cout << endl;
    }
 
    //cout << endl;
 
    setlocale(LC_ALL, "rus");
    clock_t start, end;
    start = clock();
 
    HANDLE hThreads[NumberOfThreads];
    unsigned id;
    int noms[NumberOfThreads];
    for (int i = 0; i < NumberOfThreads; i++){
        to[i] = from[i] + q + (i < r ? 1 : 0);
        noms[i]=i;
        hThreads[i] = (HANDLE)_beginthreadex(NULL, 0, ThreadFunctionMult, (void *)(noms+i), 0, &id);
        if(i<NumberOfThreads-1)
             from[i+1] = to[i];
    }
    WaitForMultipleObjects(NumberOfThreads, hThreads, TRUE, INFINITE);
    for (int i = 0; i < NumberOfThreads; i++)
        CloseHandle(hThreads[i]);
 
    end = clock() - start;
    printf("Время выполнения программы: %f\n", end / (double)CLOCKS_PER_SEC);
 
    //for (int i = 0; i < n; i++)
    //{
        //for (int j = 0; j < n; j++)
            //cout << matr_3[i][j] << " ";
        //cout << endl;
    //}
 
    delete[]matr_1;
    delete[]matr_2;
    delete[]matr_3;
    system("pause");
    return 0;
}

На моем компе с 6 ядрами посчиталось за 2.6 секунд.
с 1 ядром за 10.3 сек

Кстати, сразу не заметил, массивы надо удалять так

C++
1
2
3
4
5
6
7
8
9
10
11
 for (int i = 0; i<n; i++)
      delete[] matr_1[i];
 
    for (int i = 0; i<m; i++)
       delete[] matr_2[i];
 
    for (int i = 0; i<n; i++)
       delete[] matr_3[i];
    delete[] matr_1;
    delete[] matr_2;
    delete[] matr_3;

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	07.03.2015, 21:29
	clock() считает такты процессора в активном режиме. В режиме ожидания такты, возвращаемые clock(), не увеличиваются. Надо системное время сравнивать. 0

Умножение матриц с разделением на потоки

Решение