Распараллеливание с помщью потоков. Время работы

@prime2019 · Регистрация: 19.02.2019

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

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

Написал программу, которая должна распараллеливать умножение матриц

$https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> A=\{a_{ik}\} \in M(m\times n), B= \{b_{kj}\} \in M(n \times l)<br />$

(код программы ниже).

Распараллеливал по i формулу:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> c_{ij} = \sum_{k=1}^n a_{ik}b_{kj}, \quad i = 1,2, \ldots m, \quad j = 1,2,\ldots,l.<br />$

Тестировал на матрицах размера 2000 x 2000, 2000 x 2000 на машине с 4-мя процессорами.
Запускал с 2, 3, 4 потоками.

Вопрос: Почему программа работает медленнее, чем последовательный вариант?
Причем чем больше потоков, тем медленнее.

Использовать одну память для чтения несколькими потоками нельзя?

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
#include<stdio.h>
#include<pthread.h>
#include<stdlib.h>
#include<time.h>
 
 
 
typedef struct Thread_Data {
    pthread_t id; 
    double ** a;
    double ** b;
    double ** c;
    int from; 
    int to;
    int col2; 
    int row2;
} Thread_Data;
void * Thread_Function(void * arg) {
    int i, j, k;
    Thread_Data * data = (Thread_Data *) arg;
    for(i = data -> from; i < data -> to; i++) {
        for(j = 0; j < data -> col2; j++) {
            data -> c[i][j] = 0.0;
            for(k = 0; k < data -> row2; k++)
                data -> c[i][j] += data -> a[i][k] * data -> b[k][j];
        }
    }
    return NULL;
}
void mult_mat (int thread_count, double ** mat1, double ** mat2, double ** res, int r1, int r2, int c2) {
    int s  = r1 / thread_count;
    int i;
    Thread_Data * data;
    data = (Thread_Data *) malloc(thread_count * sizeof(Thread_Data));
    for(i = 0; i < thread_count - 1; i++) {
        data[i].a = mat1;
        data[i].b = mat2;
        data[i].c = res;
        data[i].from = i * s;
        data[i].to = (i + 1) * s;
        data[i].col2 = c2;
        data[i].row2 = r2;
        pthread_create(&(data[i].id), NULL, Thread_Function, &(data[i]));
    }
    data[thread_count - 1].a = mat1;
    data[thread_count - 1].b = mat2;
    data[thread_count - 1].c = res;
    data[thread_count - 1].from = (thread_count - 1) * s;
    data[thread_count - 1].to = r1;
    data[thread_count - 1].col2 =c2;
    data[thread_count - 1].row2 = r2;
 
    pthread_create(&(data[thread_count - 1].id), NULL, Thread_Function, &(data[thread_count - 1]));
 
    for( i = 0; i < thread_count; i++)
        pthread_join(data[i].id, NULL);
}
int main(int argc, char* argv[]) {
    double **a, **b, **c;
    int m, n, k, i, j, nproc;
    unsigned start_time, end_time, time;
    FILE *fin, *fout;
    fin = fopen("input.txt", "r");
    fscanf(fin, "%d %d%d", &m, &n, &k);
    a  = (double **)malloc(m * sizeof(double *));
    for(i = 0; i < m; i++)
        a[i] = (double *) malloc(n * sizeof(double));
    b  = (double **)malloc(n * sizeof(double *));
    for(i = 0; i < n; i++)
        b[i] = (double *) malloc(k * sizeof(double));
    c  = (double **)malloc(m * sizeof(double *));
    for(i = 0; i < m; i++)
        c[i] = (double *) malloc(k * sizeof(double));
    printf("Ok \n");
    for(i= 0; i< m; i++) {
        for(j = 0; j < n; j++)
            fscanf(fin, "%lf", &a[i][j]);
    }
    for(i= 0; i< n; i++) {
        for(j = 0; j < k; j++)
            fscanf(fin, "%lf", &b[i][j]);
    }
    start_time = clock();
    nproc = atoi(argv[1]);
    mult_mat(nproc, a, b, c, m, n, k);
    fout = fopen("output.txt", "w");
    for(i = 0; i < m; i++) {
        for(j = 0; j < k; j++)
            fprintf(fout, "%lf ", c[i][j]);
        fprintf(fout, "\n");
    }
    end_time = clock();
    printf("time = %lf \n", (end_time - start_time) * 1.0 / CLOCKS_PER_SEC);
    return 0;
}

@prik · 21.02.2019, 21:15

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

Оверхед от операционки(еа переключение процессов) в данном случае минимален:

Думаю, он появится на тысячах (десятках тысяч???) нитей.

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

Откуда он взялся?

Сорри.

C
1
2
3
4
5
6
7
8
9
#define timespecsub(tsp, usp, vsp)                                      \
        do {                                                            \
                (vsp)->tv_sec = (tsp)->tv_sec - (usp)->tv_sec;          \
                (vsp)->tv_nsec = (tsp)->tv_nsec - (usp)->tv_nsec;       \
                if ((vsp)->tv_nsec < 0) {                               \
                        (vsp)->tv_sec--;                                \
                        (vsp)->tv_nsec += 1000000000L;                  \
                }                                                       \
        } while (0)

ЗЫ: спасибо за тесты.

Добавлено через 4 минуты

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

В каком стандарте/версии gcc собираешь? Откуда этот макрос взялся?

По работе, 2ю неделю портирую демона с бсд kqueue на линукс epoll - в голове уже каша где что есть, а где нет или есть, но не так

@drfaust · 21.02.2019, 21:30

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

ю неделю портирую демона с бсд kqueue на линукс epol

Хорошее дело...

Bash
1
2
3
4
5
6
7
8
9
10
11
12
[faust@archlinux par]$ ./1 10
2000x2000 * 2000x2000, 10 threads: 26.821805596 
2000x2000 * 2000x2000, 9 threads: 26.426754516 
2000x2000 * 2000x2000, 8 threads: 26.221151541 
2000x2000 * 2000x2000, 7 threads: 26.704989468 
2000x2000 * 2000x2000, 6 threads: 28.804998238 
2000x2000 * 2000x2000, 5 threads: 27.448898460 
2000x2000 * 2000x2000, 4 threads: 26.696667084 
2000x2000 * 2000x2000, 3 threads: 35.486375616 
2000x2000 * 2000x2000, 2 threads: 52.773950965 
2000x2000 * 2000x2000, 1 threads: 104.978787706 
[faust@archlinux par]$

Ошибочка есть, судя по монитору в трее на "4 threads" у меня было загружено 3 ядра. Сейчас перегружусь в чистую консоль и в бивисе отключу энергосберегайки проца(хотя должны быть отключены, т.к. немного пытаюсь разогнать старичка)...

@prik · 21.02.2019, 21:35

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

Хорошее дело...

Не уверен. Чем больше я узнаю kqueue тем меньше мне нравиться epoll Ж)

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

т.к. немного пытаюсь разогнать старичка)...

Спасибо, не мучайте его

и так ясно - каждое железное ядро делает свое дело +- 1% можно списать на другую нагрузку и погрешности измерений.

@drfaust · 21.02.2019, 23:43

В обоих тестах отключены C1E и Cool&Quiet, дабы не менять частоту на уровне BIOS.

На первом тесте, что бы не менять другие параметры системы в BIOSe занизил множитель ядер проца до минимума - FSB_220*4 = 880

Bash
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
[faust@archlinux ~]$ lscpu
Архитектура:         x86_64
CPU op-mode(s):      32-bit, 64-bit
Порядок байт:        Little Endian
Address sizes:       48 bits physical, 48 bits virtual
CPU(s):              4
On-line CPU(s) list: 0-3
Thread(s) per core:  1
Ядер на сокет:       4
Сокетов:             1
NUMA node(s):        1
ID прроизводителя:   AuthenticAMD
Семейство ЦПУ:       16
Модель:              4
Имя модели:          AMD Phenom(tm) II X4 945 Processor
Степпинг:            2
CPU MHz:             880.064
BogoMIPS:            1760.46
Виртуализация:       AMD-V
L1d cache:           64K
L1i cache:           64K
L2 cache:            512K
L3 cache:            6144K
NUMA node0 CPU(s):   0-3
Флаги:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm 3dnowext 3dnow constant_tsc rep_good nopl nonstop_tsc cpuid extd_apicid pni monitor cx16 popcnt lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt hw_pstate vmmcall npt lbrv svm_lock nrip_save
[faust@archlinux ~]$ cd Проекты/C/Чужое/par
[faust@archlinux par]$ ./1 20
2000x2000 * 2000x2000, 20 threads: 95.586214438 
2000x2000 * 2000x2000, 19 threads: 95.640646845
2000x2000 * 2000x2000, 18 threads: 96.201631761 
2000x2000 * 2000x2000, 17 threads: 97.137435124 
2000x2000 * 2000x2000, 16 threads: 95.534677231 
2000x2000 * 2000x2000, 15 threads: 95.950472885 
2000x2000 * 2000x2000, 14 threads: 95.972183953 
2000x2000 * 2000x2000, 13 threads: 97.370742220 
2000x2000 * 2000x2000, 12 threads: 96.500770688 
2000x2000 * 2000x2000, 11 threads: 97.529222418 
2000x2000 * 2000x2000, 10 threads: 97.676820437 
2000x2000 * 2000x2000, 9 threads: 96.1009824 
2000x2000 * 2000x2000, 8 threads: 95.596991995 
2000x2000 * 2000x2000, 7 threads: 96.976429326 
2000x2000 * 2000x2000, 6 threads: 105.403793417 
2000x2000 * 2000x2000, 5 threads: 97.352634751 
2000x2000 * 2000x2000, 4 threads: 95.557950790 
2000x2000 * 2000x2000, 3 threads: 127.603116234 
2000x2000 * 2000x2000, 2 threads: 190.502411947 
2000x2000 * 2000x2000, 1 threads: 380.21703902 
[faust@archlinux par]$

На этом тесте, при всех прочих равных вернул множитель ядер проца до максимума - FSB_220*15 = 3300

Bash
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
[faust@archlinux par]$ lscpu
Архитектура:         x86_64
CPU op-mode(s):      32-bit, 64-bit
Порядок байт:        Little Endian
Address sizes:       48 bits physical, 48 bits virtual
CPU(s):              4
On-line CPU(s) list: 0-3
Thread(s) per core:  1
Ядер на сокет:       4
Сокетов:             1
NUMA node(s):        1
ID прроизводителя:   AuthenticAMD
Семейство ЦПУ:       16
Модель:              4
Имя модели:          AMD Phenom(tm) II X4 945 Processor
Степпинг:            2
CPU MHz:             3300.171
BogoMIPS:            6602.35
Виртуализация:       AMD-V
L1d cache:           64K
L1i cache:           64K
L2 cache:            512K
L3 cache:            6144K
NUMA node0 CPU(s):   0-3
Флаги:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm 3dnowext 3dnow constant_tsc rep_good nopl nonstop_tsc cpuid extd_apicid pni monitor cx16 popcnt lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt hw_pstate vmmcall npt lbrv svm_lock nrip_save
[faust@archlinux par]$ ./1 20
2000x2000 * 2000x2000, 20 threads: 26.201631852 
2000x2000 * 2000x2000, 19 threads: 26.419142470 
2000x2000 * 2000x2000, 18 threads: 26.346822520 
2000x2000 * 2000x2000, 17 threads: 26.597330252 
2000x2000 * 2000x2000, 16 threads: 26.198918727 
2000x2000 * 2000x2000, 15 threads: 26.314265419 
2000x2000 * 2000x2000, 14 threads: 26.331527646 
2000x2000 * 2000x2000, 13 threads: 26.639730347 
2000x2000 * 2000x2000, 12 threads: 26.518676882 
2000x2000 * 2000x2000, 11 threads: 26.739260158 
2000x2000 * 2000x2000, 10 threads: 26.850347619 
2000x2000 * 2000x2000, 9 threads: 26.296397622 
2000x2000 * 2000x2000, 8 threads: 26.159613363 
2000x2000 * 2000x2000, 7 threads: 26.487268110 
2000x2000 * 2000x2000, 6 threads: 29.63262863 
2000x2000 * 2000x2000, 5 threads: 27.166253646 
2000x2000 * 2000x2000, 4 threads: 26.691675021 
2000x2000 * 2000x2000, 3 threads: 35.403382048 
2000x2000 * 2000x2000, 2 threads: 52.537255531 
2000x2000 * 2000x2000, 1 threads: 105.61475235 
[faust@archlinux par]$

Не думаю, что в больших выч. нагрузках можно вычислить роль ядра операционки. Тут нужна синтетика из syscall`ов, желательно без тормозов внешних устройств(веник, видюха, звук и пр.)

З.Ы. Разгон - это хобби. Недавно был потоп "сверху", погибла хорошая мать, и пострадал контроллёр DDR-3 памяти в Athlon-X3 450(Rana), они в паре держали 4ГГц стабильно. Сейчас вполне хороший проц(Deneb), но с "тоскливой" материнкой, пока уткнуться в разгон времени не хватает, но проц обещает около 4ГГц. Пока стабильно, тупо, не напрягаясь вместо штатных 3ГГц пашет на 3,3ГГц(+10%)...

Новые блоги и статьи Все статьи Все блоги /
Администрация Хабра удаляет новые алгоритмы, которые не западно ориентированной философии кода, без уведомлений и объяснений. Hrethgir 20.06.2026 Делается это, как замечено, при правках - при объявлении концептуальных отличий в алгоримах. Делается это, по линейке событий - после дополнения публикации основными отличиями от основных западных. . .	Процесс ориентированная диалектика (не новость - просто системное обновление, философия). Hrethgir 20.06.2026 Однажды один участник в своём блоге, на этом форуме, сделал запись "О языках замолвите слово". Понимая, что язык - важная вещь, я решил хорошо подумать, прежде чем сказать, и сказал то, что вы видите. . .	Контроль уникальности строк в табличной части документа Maks 18.06.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ПланированиеСпецтехники" с табличной частью "НаличиеОборудования", разработанного в КА2. Задача: контроль уникальности строк в. . .	Клиент Uhbif79 18.06.2026 Здесь простой клиент для работы с сервером.
Сервер Uhbif79 18.06.2026 Выкладываю простейший сервер.	Дефенестрация kumehtar 18.06.2026 Узнал интересное слово. Дефенестрация. Это когда ты выбрасываешь кого-либо или что-либо из окна. Возьму на вооружение)))	Дихотомия добра и зла kumehtar 18.06.2026 Как Дзен-буддисты говорят о добре и зле: не нужно воевать против зла, нужно воевать против невежества. Тогда добро станет ествественным, и поэтому вечным. Но дело в том, что невежество всё время. . .	Своя Интернет-Компания iceja 18.06.2026 Я программист с экономическим образованием, пишу свой проект, это SaaS для бизнесов. Мне нужен co-founder с высшим экономическим образованием, и/ или инвестор. Сейчас проект в интенсивной разработке,. . .