Оптимизировать работу программы

@Zoow · Регистрация: 24.03.2022

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

Можно ли сделать программу быстрее не меняя алгоритм вычисления? Я пробовал сделать ее быстрее, но тогда она считает неправильно, но сейчас она считает правильно, но параллельная программа медленнее обычной

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <sys/time.h>
#include <mpi.h>
#include "adi.h"
 
double second();
 
DATA_TYPE X[N][N];
DATA_TYPE A[N][N];
DATA_TYPE B[N][N];
 
static void init_array(int n, DATA_TYPE X[N][N], DATA_TYPE A[N][N], DATA_TYPE B[N][N]) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            X[i][j] = ((DATA_TYPE) i*(j+1) + 1) / n;
            A[i][j] = ((DATA_TYPE) i*(j+2) + 2) / n;
            B[i][j] = ((DATA_TYPE) i*(j+3) + 3) / n;
        }
}
 
static void print_array(int n, DATA_TYPE X[N][N]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%f ", X[i][j]);
        }
        printf("\n");
    }
}
 
static void kernel_adi(int tsteps, int n, DATA_TYPE X[N][N], DATA_TYPE A[N][N], DATA_TYPE B[N][N], int rank, int size) {
    int chunk_size = (n + size - 1) / size;
    int start_row = rank * chunk_size;
    int end_row = (start_row + chunk_size > n) ? n : (start_row + chunk_size);
 
    for (int t = 0; t < _PB_TSTEPS; t++) {
        // Этап 1: Обновление X и B по строкам
        for (int i1 = start_row; i1 < end_row; i1++) {
            for (int i2 = 1; i2 < _PB_N; i2++) {
                X[i1][i2] = X[i1][i2] - X[i1][i2-1] * A[i1][i2] / B[i1][i2-1];
                B[i1][i2] = B[i1][i2] - A[i1][i2] * A[i1][i2] / B[i1][i2-1];
            }
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, B, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
 
        // Этап 2: Нормализация последнего столбца X
        for (int i1 = start_row; i1 < end_row; i1++) {
            X[i1][_PB_N-1] = X[i1][_PB_N-1] / B[i1][_PB_N-1];
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
 
        // Этап 3: Обратное обновление X
        for (int i1 = start_row; i1 < end_row; i1++) {
            for (int i2 = 0; i2 < _PB_N-2; i2++) {
                X[i1][_PB_N-i2-2] = (X[i1][_PB_N-2-i2] - X[i1][_PB_N-2-i2-1] * A[i1][_PB_N-i2-3]) / B[i1][_PB_N-3-i2];
            }
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
 
        // Этап 4: Обновление X и B по столбцам
        for (int i1 = 1; i1 < _PB_N; i1++) {
            for (int i2 = 0; i2 < _PB_N; i2++) {
                X[i1][i2] = X[i1][i2] - X[i1-1][i2] * A[i1][i2] / B[i1-1][i2];
                B[i1][i2] = B[i1][i2] - A[i1][i2] * A[i1][i2] / B[i1-1][i2];
            }
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, B, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
 
        // Этап 5: Нормализация последней строки X
        if (rank == size - 1) { // Только последний процесс обрабатывает последнюю строку
            for (int i2 = 0; i2 < _PB_N; i2++) {
                X[_PB_N-1][i2] = X[_PB_N-1][i2] / B[_PB_N-1][i2];
            }
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
 
        // Этап 6: Обратное обновление X по строкам
        for (int i1 = 0; i1 < _PB_N-2; i1++) {
            for (int i2 = 0; i2 < _PB_N; i2++) {
                X[_PB_N-2-i1][i2] = (X[_PB_N-2-i1][i2] - X[_PB_N-i1-3][i2] * A[_PB_N-3-i1][i2]) / B[_PB_N-2-i1][i2];
            }
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
    }
}
 
int main(int argc, char** argv) {
    int n = N;
    int tsteps = TSTEPS;
    int rank, size;
    double time0, time1;
 
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
 
    if (rank == 0) {
        init_array(n, X, A, B);
    }
    MPI_Bcast(X, N*N, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    MPI_Bcast(A, N*N, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    MPI_Bcast(B, N*N, MPI_DOUBLE, 0, MPI_COMM_WORLD);
 
    MPI_Barrier(MPI_COMM_WORLD);
    time0 = MPI_Wtime();
    
    kernel_adi(tsteps, n, X, A, B, rank, size);
    
    MPI_Barrier(MPI_COMM_WORLD);
    time1 = MPI_Wtime();
 
    if (rank == 0) {
        printf("\nn=%d\n", n);
        printf("\ntime=%f\n", time1 - time0);
        print_array(n, X);
    }
    
    MPI_Finalize();
    return 0;
}

Насколько я понимаю необходимо что-то сделать в этой функции

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
static void kernel_adi(int tsteps, int n, DATA_TYPE X[N][N], DATA_TYPE A[N][N], DATA_TYPE B[N][N], int rank, int size) {
    int chunk_size = (n + size - 1) / size;
    int start_row = rank * chunk_size;
    int end_row = (start_row + chunk_size > n) ? n : (start_row + chunk_size);
 
    for (int t = 0; t < _PB_TSTEPS; t++) {
        // Этап 1: Обновление X и B по строкам
        for (int i1 = start_row; i1 < end_row; i1++) {
            for (int i2 = 1; i2 < _PB_N; i2++) {
                X[i1][i2] = X[i1][i2] - X[i1][i2-1] * A[i1][i2] / B[i1][i2-1];
                B[i1][i2] = B[i1][i2] - A[i1][i2] * A[i1][i2] / B[i1][i2-1];
            }
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, B, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
 
        // Этап 2: Нормализация последнего столбца X
        for (int i1 = start_row; i1 < end_row; i1++) {
            X[i1][_PB_N-1] = X[i1][_PB_N-1] / B[i1][_PB_N-1];
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
 
        // Этап 3: Обратное обновление X
        for (int i1 = start_row; i1 < end_row; i1++) {
            for (int i2 = 0; i2 < _PB_N-2; i2++) {
                X[i1][_PB_N-i2-2] = (X[i1][_PB_N-2-i2] - X[i1][_PB_N-2-i2-1] * A[i1][_PB_N-i2-3]) / B[i1][_PB_N-3-i2];
            }
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
 
        // Этап 4: Обновление X и B по столбцам
        for (int i1 = 1; i1 < _PB_N; i1++) {
            for (int i2 = 0; i2 < _PB_N; i2++) {
                X[i1][i2] = X[i1][i2] - X[i1-1][i2] * A[i1][i2] / B[i1-1][i2];
                B[i1][i2] = B[i1][i2] - A[i1][i2] * A[i1][i2] / B[i1-1][i2];
            }
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, B, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
 
        // Этап 5: Нормализация последней строки X
        if (rank == size - 1) { // Только последний процесс обрабатывает последнюю строку
            for (int i2 = 0; i2 < _PB_N; i2++) {
                X[_PB_N-1][i2] = X[_PB_N-1][i2] / B[_PB_N-1][i2];
            }
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
 
        // Этап 6: Обратное обновление X по строкам
        for (int i1 = 0; i1 < _PB_N-2; i1++) {
            for (int i2 = 0; i2 < _PB_N; i2++) {
                X[_PB_N-2-i1][i2] = (X[_PB_N-2-i1][i2] - X[_PB_N-i1-3][i2] * A[_PB_N-3-i1][i2]) / B[_PB_N-2-i1][i2];
            }
        }
 
        // Синхронизация данных между процессами
        MPI_Allgather(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL, X, chunk_size * N, MPI_DOUBLE, MPI_COMM_WORLD);
    }
}

@Pphantom · 10.03.2025, 11:32

А чему равно N?

@Zoow · 10.03.2025, 11:35 **[ТС]**

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

А чему равно N?

Оно берется в зависимости от датасета
датасеты находятся в adi.h

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
#ifndef ADI_H
# define ADI_H
 
/* Default to STANDARD_DATASET. */
 
# if !defined(USE_SCALAR)//используются ли скалярные значения или массивы в программе
#  define USE_SCALAR
#endif
 
# if !defined(MINI_DATASET) && !defined(SMALL_DATASET) && !defined(LARGE_DATASET) && !defined(EXTRALARGE_DATASET)// размер массивов
#  define SMALL_DATASET
# endif
 
/* Do not define anything if the user manually defines the size. */
# if !defined(TSTEPS) && ! defined(N)
/* Define the possible dataset sizes. */
#  ifdef MINI_DATASET
#   define TSTEPS 2//количество шагов времени, используемых в методе
#   define N 32//размер массивов
#  endif
 
#  ifdef SMALL_DATASET
#   define TSTEPS 10
#   define N 512
#  endif
 
#  ifdef STANDARD_DATASET /* Default if unspecified. */
#   define TSTEPS 50
#   define N 1024
#  endif
 
#  ifdef LARGE_DATASET
#   define TSTEPS 50
#   define N 2048
#  endif
 
#  ifdef EXTRALARGE_DATASET
#   define TSTEPS 100
#   define N 4000
#  endif
# endif /* !N */
 
# ifdef USE_SCALAR
# define _PB_N n//тип, который определяет размер массива n
# define _PB_TSTEPS tsteps//тип, который определяет количество шагов времени
#else
# define _PB_N N
# define _PB_TSTEPS TSTEPS
# endif
 
# ifndef DATA_TYPE
#  define DATA_TYPE double
#  define DATA_PRINTF_MODIFIER "%0.2lf "
# endif
 
 
#endif /* !ADI */

@Pphantom · 10.03.2025, 11:44

Проще говоря, у вас примерно квадратичный по размеру матриц алгоритм, в котором размер матрицы максимум 4000. Ну, в общем, я бы сказал, что в такой ситуации меньшая производительность MPI-версии вполне нормальна. За какое время на максимальном датасете отрабатывают и та, и другая?

@Zoow · 10.03.2025, 12:04 **[ТС]**

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

Проще говоря, у вас примерно квадратичный по размеру матриц алгоритм, в котором размер матрицы максимум 4000. Ну, в общем, я бы сказал, что в такой ситуации меньшая производительность MPI-версии вполне нормальна. За какое время на максимальном датасете отрабатывают и та, и другая?

Если рассматривать обе версии программы, то при самом большом датасете, то есть 4000 матрица, обычная программа выполняется за 28.121191 секунд, а параллельная за 27.902286. То есть различий практически нет. Но разве чем больше процессов используется, тем не должна программа выполняться быстрее? Если да, то можно ли параллельную программу ускорить?

@Pphantom · 10.03.2025, 12:27

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

Но разве чем больше процессов используется, тем не должна программа выполняться быстрее?

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

Я, собственно, веду все это к очередному вредному вопросу: MPI вам реально нужен? В наличии есть кластер, на котором можно все это считать, причем потенциальная экономия времени окажется заведомо больше затрат на дополнительную отладку?

Или это учебно-тренировочная задача?

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

Если да, то можно ли параллельную программу ускорить?

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

@Zoow · 10.03.2025, 12:51 **[ТС]**

Я отправлял эту задачу, но мне пришел более подробный ответ:
Смотрите, немного подробнее объясним задачу. У нас получается, такая задача. Стояла, была последовательная программа одисси, которая реализовывала некий математический алгоритм работы с матрицами. Решала эти матрицы и, соответственно, дела какой-то результат.
Эта программа являлась эталоном этого алгоритма. То есть её решение необходимо считать заведомо правильным. 2 программа, которая, которую следует сделать, это параллельная версия этой программы, её необходима с помощью Реализовать это мы определили в тз, прописали.
Вот как бы это этот момент у нас указан. И самая главная задача, о которой я говорил, необходимо, чтобы параллельная версия
Выдавала тот же результат, что и последовательно, последовательно, менять нельзя. Последовательно.
Это, по сути, я говорю, вот эталон, по которому нужно равняться.
Параллельная версия может изменяться, но она должна представлять одно и то же решение с Последовательная версия, то есть результаты должны сходиться на одних и тех же параметрах. Вот в 1 случае у нас было недопонимание насчёт этого. Вот, ну как бы мы это разрешили с вами. Хорошо. Хорошо.
Сейчас, смотрите, у нас вот этот керна лади метод, который, собственно, производит решение.
Этой матрицы он представлен, да, он хорошо, но в нём как раз-таки есть загвоздка, его необходимо распараллелить. И вот там как раз-таки наблюдается эта зависимость по данных, о которых я описал.
Вот необходимо вот с этим всем, с этой всей проблематикой как бы справиться и представить параллельную версию программы сейчас, просто на данный момент, что последовательно, что параллельная версия программы, ну, они, по сути, работают одинаково по времени.
Никакого ощутимого ускорения не наблюдается при учёте того, что запускали на разном количестве ядер везде время одинаковое должно быть некое ускорение, которое реализована программа именно в этой, в этом методе карма лади, дабы вот эту работу циклов их распараллелить. Вот это вот основная задача.
Что касается других методов, там, ну, возможно необходимо добавить распараллеливание, но тем не менее, они выполняют не столько ключевую роль и как бы не являются основным время затрачивающим методами. Вот поэтому больше нужно сейчас сконцентрироваться именно на 1 Методе термина.
Вот по остальному программа, да, выдаёт одинаковое решение и все хорошо. Просто нужно доправить этот момент.

@Pphantom · 10.03.2025, 13:04

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

Я отправлял эту задачу, но мне пришел более подробный ответ:

Ничего не понял, кроме того, что это чья-то устная речь, записанная в виде текста.

@Zoow · 10.03.2025, 13:07 **[ТС]**

Это голосовое сообщением, распознанное в виде текста. Как я понял, есть такой метод adi, который относится к численным методам, и основная задача распараллелить его и главное условие, чтобы обычная программа была медленнее, чем распараллеленная. Я вроде так и сделал, но время оставляет желать лучшего. Поэтому вопрос, можно ли улучшить его или все и так уже отлично?

@Pphantom · 10.03.2025, 14:03

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

Поэтому вопрос, можно ли улучшить его или все и так уже отлично?

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

По названию можно предположить, что это должен быть неявный метод переменных направлений, но по коду я это не вижу.

@Zoow · 10.03.2025, 14:14 **[ТС]**

Если использовать определения чатика по программе, то он дает это
Этот код представляет собой параллельную реализацию алгоритма ADI (Alternating Direction Implicit method) с использованием MPI (Message Passing Interface) для решения системы уравнений. ADI метод используется для численного решения многомерных дифференциальных уравнений в частных производных, таких как уравнения теплопроводности или диффузии.

### Основные этапы работы кода:

1. **Инициализация и распределение данных:**
- Код распределяет строки матриц `X`, `A`, и `B` между процессами. Каждый процесс обрабатывает свою часть строк (chunk) матриц.
- `rank` — это идентификатор текущего процесса, а `size` — общее количество процессов.
- `start_row` и `end_row` определяют диапазон строк, которые обрабатывает текущий процесс.

2. **Этап 1: Обновление `X` и `B` по строкам:**
- В этом этапе происходит обновление значений матриц `X` и `B` по строкам. Каждый процесс обновляет только свои строки

3. **Синхронизация данных:**
- После обновления строк происходит синхронизация данных между всеми процессами с помощью `MPI_Allgather`. Это необходимо, чтобы все процессы имели актуальные данные для дальнейших вычислений.

4. **Этап 2: Нормализация последнего столбца `X`:**
- В этом этапе происходит нормализация последнего столбца матрицы `X`:

5. **Этап 3: Обратное обновление `X`:**
- В этом этапе происходит обратное обновление значений матрицы `X`:

6. **Этап 4: Обновление `X` и `B` по столбцам:**
- В этом этапе происходит обновление значений матриц `X` и `B` по столбцам:

7. **Этап 5: Нормализация последней строки `X`:**
- В этом этапе только последний процесс (с `rank == size - 1`) нормализует последнюю строку матрицы `X`:

8. **Этап 6: Обратное обновление `X` по строкам:**
- В этом этапе происходит обратное обновление значений матрицы `X` по строкам:

9. **Цикл по времени:**
- Весь процесс повторяется для каждого временного шага `t` в пределах `_PB_TSTEPS`.

### Основные моменты:
- Код использует MPI для параллельного выполнения, что позволяет ускорить вычисления за счет распределения работы между несколькими процессами.
- Синхронизация данных между процессами происходит после каждого этапа, чтобы все процессы имели актуальные данные для дальнейших вычислений.
- Код предполагает, что матрицы `X`, `A`, и `B` имеют размер `N x N`.

### Замечания:
- В коде используются макросы `_PB_TSTEPS` и `_PB_N`, которые должны быть определены где-то в коде или переданы как параметры.
- Тип данных `DATA_TYPE` должен быть определен, например, как `double` или `float`.

Этот код является примером того, как можно параллельно решать сложные системы уравнений с использованием метода ADI и MPI.

@Pphantom · 10.03.2025, 14:16

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

Если использовать определения чатика по программе, то он дает это

Эм... он-то дает, но вы, что, сами не знаете, что пишете?!

@Jin X · 10.03.2025, 16:33

Pphantom, меня терзают смутные сомнения, что ТС написал этот код сам

@Mc X · 10.03.2025, 17:02

Не по теме:

Вы уж извините, но мимо такого пройти невозможно... :pardon:
Это паноптикум какой-то...
Сначала ТС, вместо того чтобы написать текстом нормально, использовал ИИ чтобы сделать транскрибацию, совершенно ужасного разговора и скинул "как есть" сюда.
Потом, он проделал тоже самое с кодом у другого ИИ, опять же вместо того чтобы самостоятельно написать нормально.
Я верно понимаю?

ТС, Вы там сам-то человек? или просто консультируетесь у братьев по разуму? :)

P. S. Надеюсь код у вас пишет не третий ИИ :)))

Добавлено через 7 минут
А это уже по теме...
P.P.S. И если говорить совсем откровенно: Это крайнее неуважение к присутствующим тут, к тем у кого Вы просите помощи.

@VTsaregorodtsev · 11.03.2025, 11:01

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

Можно ли сделать программу быстрее не меняя алгоритм вычисления?

Нельзя. Ни исходную, ни параллельную.
Надо в первую очередь переписать этот говнокод, не обеспечивающий нормального кэширования данных. Ибо сейчас код тормозит не о вычисления - а о постоянный обмен с памятью.
Понятно, что 3 дабл-матрицы 4000*4000 (т.е. суммарно на 384МБ) ни в какой кэш не влезут. Но использование L1- (для мелких матриц) и L2-кэшей (для средних-больших матриц) ядра улучшить у однопоточной проги можно.

Смотрим-анализируем дальше, на примере матриц 4000*4000.
Берём все 4 сдвоенных цикла (на этапы 2 и 5 обработок последнего столбца и последней строки можно не глядеть - они добавляют копейки) - имеем в них суммарно 18 арифметических команд (для плавающей точки) на элемент [i][j] матриц, независимо от числа этих матриц.
Ну и перемножаем: 4000*4000*18*100(внешних итераций)=28 800 000 000 арифметических плавучих операций, предполагая, что вся целочисленка (вычисление индексов/адресов) и чтение-запись данных выполняются другими исполнительными блоками ядра (а это так и есть).
Итоговая цифра оч.удобно ложится на 28сек времени выполнения. При частоте ядра 4ГГц (условно) - имеем по 4 такта ядра на одну плавучую арифм.операцию.
Но, например, интеловское ядро начиная с 6ого поколения - может по паре операций умножения/вычитания за такт делать.
И не просто скалярные операции оно может делать - а векторные, обрабатывая по 2 (SSE) и 4 (AVX) дабла одной командой.
Т.е. имеем сейчас счёт на скорости в 1/16 или 1/32 от потенциальной пиковой производительности ядра для даблов.
Понятно, что пик никогда достигнут не будет. И есть ещё медленные деления. Но в коде же есть "общие множители", которых я из числа 18 отдельных команд не искючал. Т.е. тут лимиты и ещё неучтённые возможности во многом взаимно компенсируются - и всё равно можно итожить, что неиспользование кэширования и, возможно, не сделанная компилятором векторизация (а компилятору её легко будет сделать только для этапов 4-6) тормозят прогу в 1-2-3 ДЕСЯТКА раз.

Так что я бы ещё поглядел и ассемблерный выхлоп компилятора, чтобы понять, сколько проигрывается от отсутствия (или от недостаточно полной) автоматической векторизации. И, м.б., переписал бы переделанный (под улучшение кэширования) сишный код kernel_adi() на ассемблере - именно для максимально эффективного задействования векторизации математики.
Но это я - я и неоптимальности машинного кода вижу/увижу, и переписать смогу.

А MPI тут нафиг не нужен.

@Pphantom · 11.03.2025, 11:33

VTsaregorodtsev, все правильно, но можно, пожалуй, добавить еще пару слов.

Когда (и если) все это будет учтено, следующий шаг - использование более чем одного ядра, коих в нынешних процессорах много. Но это тоже не MPI, а что-нибудь вроде OpenMP. А дальше, если производительности все равно не хватит - графические ускорители, эта задача для них вполне подходит.

@VTsaregorodtsev · 11.03.2025, 15:14

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

следующий шаг - использование более чем одного ядра

Согласен.
Может показаться, что невозможность разделить тут матрицу на совершенно независимые блоки (см на паттерн доступа к элементам матрицы: и по строкам, и по столбцам) как-то помешает многопоточке. На самом деле же - потоки будут/могут синхронизировать обрабатываемые ими данные через общую память, т.е. синхронизировать данные они будут неявно = БЕЗ внешнего управления (управлять тут надо будет синхронизацией потоков - а не gathering'ом данных).
Так что если правильно реализовать многопоточность (это я ТСу опять намекаю, что вижу-знаю, как тут надо действовать) - то эффект должен быть.

Новые блоги и статьи Все статьи Все блоги /
Unity 4D GameUnited 13.06.2025 Четырехмерное пространство. . . Звучит как что-то из научной фантастики, правда? Однако для меня, как разработчика со стажем в игровой индустрии, четвертое измерение давно перестало быть абстракцией из. . .	SSE (Server-Sent Events) в ASP.NET Core и .NET 10 UnmanagedCoder 13.06.2025 Кажется, Microsoft снова подкинула нам интересную фичу в новой версии фреймворка. Работая с превью . NET 10, я наткнулся на нативную поддержку Server-Sent Events (SSE) в ASP. NET Core Minimal APIs. Эта. . .	С днём независимости России! Hrethgir 13.06.2025 Решил побеседовать, с утра праздничного дня, с LM о завоеваниях. То что она написала о народе, представителем которого я являюсь сам сначала возмутило меня, но дальше только смешило. Это чисто. . .	Лето вокруг. kumehtar 13.06.2025 Лето вокруг. Наполненное бурями и ураганами событий. На фоне магии Жизни, священной и вечной, неумелой рукой человека рисуется панорама душевного непокоя. Странные серые краски проникают и. . .	Популярные LM модели ориентированы на увеличение затрат ресурсов пользователями сгенерированного кода (грязь -заслуги чистоплюев). Hrethgir 12.06.2025 Вообще обратил внимание, что они генерируют код (впрочем так-же ориентированы разработчики чипов даже), чтобы пользователь их использующий уходил в тот или иной убыток. Это достаточно опытные модели,. . .
Топ10 библиотек C для квантовых вычислений bytestream 12.06.2025 Квантовые вычисления - это та область, где теория встречается с практикой на границе наших знаний о физике. Пока большая часть шума вокруг квантовых компьютеров крутится вокруг языков высокого уровня. . .	Dispose и Finalize в C# stackOverflow 12.06.2025 Работая с C# больше десяти лет, я снова и снова наблюдаю одну и ту же историю: разработчики наивно полагаются на сборщик мусора, как на волшебную палочку, которая решит все проблемы с памятью. Да,. . .	Повышаем производительность игры на Unity 6 с GPU Resident Drawer GameUnited 11.06.2025 Недавно копался в новых фичах Unity 6 и наткнулся на GPU Resident Drawer - штуку, которая заставила меня присвистнуть от удивления. По сути, это внутренний механизм рендеринга, который автоматически. . .	Множества в Python py-thonny 11.06.2025 В Python существует множество структур данных, но иногда я сталкиваюсь с задачами, где ни списки, ни словари не дают оптимального решения. Часто это происходит, когда мне нужно быстро проверять. . .	Работа с ccache/sccache в рамках C++ Loafer 11.06.2025 Утилиты ccache и sccache занимаются тем, что кешируют промежуточные результаты компиляции, таким образом ускоряя последующие компиляции проекта. Это означает, что если проект будет компилироваться. . .

@Pphantom 2101 / 1347 / 651 Регистрация: 17.03.2022 Сообщений: 4,246
	10.03.2025, 11:32
	А чему равно N? 0

@Pphantom 2101 / 1347 / 651 Регистрация: 17.03.2022 Сообщений: 4,246
	10.03.2025, 11:44
	Проще говоря, у вас примерно квадратичный по размеру матриц алгоритм, в котором размер матрицы максимум 4000. Ну, в общем, я бы сказал, что в такой ситуации меньшая производительность MPI-версии вполне нормальна. За какое время на максимальном датасете отрабатывают и та, и другая? 0

@Zoow 58 / 2 / 0 Регистрация: 24.03.2022 Сообщений: 104
	10.03.2025, 12:51 [ТС]
	Я отправлял эту задачу, но мне пришел более подробный ответ: Смотрите, немного подробнее объясним задачу. У нас получается, такая задача. Стояла, была последовательная программа одисси, которая реализовывала некий математический алгоритм работы с матрицами. Решала эти матрицы и, соответственно, дела какой-то результат. Эта программа являлась эталоном этого алгоритма. То есть её решение необходимо считать заведомо правильным. 2 программа, которая, которую следует сделать, это параллельная версия этой программы, её необходима с помощью Реализовать это мы определили в тз, прописали. Вот как бы это этот момент у нас указан. И самая главная задача, о которой я говорил, необходимо, чтобы параллельная версия Выдавала тот же результат, что и последовательно, последовательно, менять нельзя. Последовательно. Это, по сути, я говорю, вот эталон, по которому нужно равняться. Параллельная версия может изменяться, но она должна представлять одно и то же решение с Последовательная версия, то есть результаты должны сходиться на одних и тех же параметрах. Вот в 1 случае у нас было недопонимание насчёт этого. Вот, ну как бы мы это разрешили с вами. Хорошо. Хорошо. Сейчас, смотрите, у нас вот этот керна лади метод, который, собственно, производит решение. Этой матрицы он представлен, да, он хорошо, но в нём как раз-таки есть загвоздка, его необходимо распараллелить. И вот там как раз-таки наблюдается эта зависимость по данных, о которых я описал. Вот необходимо вот с этим всем, с этой всей проблематикой как бы справиться и представить параллельную версию программы сейчас, просто на данный момент, что последовательно, что параллельная версия программы, ну, они, по сути, работают одинаково по времени. Никакого ощутимого ускорения не наблюдается при учёте того, что запускали на разном количестве ядер везде время одинаковое должно быть некое ускорение, которое реализована программа именно в этой, в этом методе карма лади, дабы вот эту работу циклов их распараллелить. Вот это вот основная задача. Что касается других методов, там, ну, возможно необходимо добавить распараллеливание, но тем не менее, они выполняют не столько ключевую роль и как бы не являются основным время затрачивающим методами. Вот поэтому больше нужно сейчас сконцентрироваться именно на 1 Методе термина. Вот по остальному программа, да, выдаёт одинаковое решение и все хорошо. Просто нужно доправить этот момент. 0

@Zoow 58 / 2 / 0 Регистрация: 24.03.2022 Сообщений: 104
	10.03.2025, 13:07 [ТС]
	Это голосовое сообщением, распознанное в виде текста. Как я понял, есть такой метод adi, который относится к численным методам, и основная задача распараллелить его и главное условие, чтобы обычная программа была медленнее, чем распараллеленная. Я вроде так и сделал, но время оставляет желать лучшего. Поэтому вопрос, можно ли улучшить его или все и так уже отлично? 0

@Zoow 58 / 2 / 0 Регистрация: 24.03.2022 Сообщений: 104
	10.03.2025, 14:14 [ТС]
	Если использовать определения чатика по программе, то он дает это Этот код представляет собой параллельную реализацию алгоритма ADI (Alternating Direction Implicit method) с использованием MPI (Message Passing Interface) для решения системы уравнений. ADI метод используется для численного решения многомерных дифференциальных уравнений в частных производных, таких как уравнения теплопроводности или диффузии. ### Основные этапы работы кода: 1. Инициализация и распределение данных: - Код распределяет строки матриц `X`, `A`, и `B` между процессами. Каждый процесс обрабатывает свою часть строк (chunk) матриц. - `rank` — это идентификатор текущего процесса, а `size` — общее количество процессов. - `start_row` и `end_row` определяют диапазон строк, которые обрабатывает текущий процесс. 2. Этап 1: Обновление `X` и `B` по строкам: - В этом этапе происходит обновление значений матриц `X` и `B` по строкам. Каждый процесс обновляет только свои строки 3. Синхронизация данных: - После обновления строк происходит синхронизация данных между всеми процессами с помощью `MPI_Allgather`. Это необходимо, чтобы все процессы имели актуальные данные для дальнейших вычислений. 4. Этап 2: Нормализация последнего столбца `X`: - В этом этапе происходит нормализация последнего столбца матрицы `X`: 5. Этап 3: Обратное обновление `X`: - В этом этапе происходит обратное обновление значений матрицы `X`: 6. Этап 4: Обновление `X` и `B` по столбцам: - В этом этапе происходит обновление значений матриц `X` и `B` по столбцам: 7. Этап 5: Нормализация последней строки `X`: - В этом этапе только последний процесс (с `rank == size - 1`) нормализует последнюю строку матрицы `X`: 8. Этап 6: Обратное обновление `X` по строкам: - В этом этапе происходит обратное обновление значений матрицы `X` по строкам: 9. Цикл по времени: - Весь процесс повторяется для каждого временного шага `t` в пределах `_PB_TSTEPS`. ### Основные моменты: - Код использует MPI для параллельного выполнения, что позволяет ускорить вычисления за счет распределения работы между несколькими процессами. - Синхронизация данных между процессами происходит после каждого этапа, чтобы все процессы имели актуальные данные для дальнейших вычислений. - Код предполагает, что матрицы `X`, `A`, и `B` имеют размер `N x N`. ### Замечания: - В коде используются макросы `_PB_TSTEPS` и `_PB_N`, которые должны быть определены где-то в коде или переданы как параметры. - Тип данных `DATA_TYPE` должен быть определен, например, как `double` или `float`. Этот код является примером того, как можно параллельно решать сложные системы уравнений с использованием метода ADI и MPI. 0

@Jin X Asm/C++/Delphi/Py/PHP/VBA 6784 / 2027 / 235 Регистрация: 14.12.2014 Сообщений: 4,257 Записей в блоге: 12
	10.03.2025, 16:33
	Pphantom, меня терзают смутные сомнения, что ТС написал этот код сам 1

@Mc X Просто Икс 691 / 233 / 47 Регистрация: 15.12.2009 Сообщений: 696
	10.03.2025, 17:02
	Не по теме: Вы уж извините, но мимо такого пройти невозможно... :pardon: Это паноптикум какой-то... Сначала ТС, вместо того чтобы написать текстом нормально, использовал ИИ чтобы сделать транскрибацию, совершенно ужасного разговора и скинул "как есть" сюда. Потом, он проделал тоже самое с кодом у другого ИИ, опять же вместо того чтобы самостоятельно написать нормально. Я верно понимаю? ТС, Вы там сам-то человек? или просто консультируетесь у братьев по разуму? :) P. S. Надеюсь код у вас пишет не третий ИИ :))) Добавлено через 7 минут А это уже по теме... P.P.S. И если говорить совсем откровенно: Это крайнее неуважение к присутствующим тут, к тем у кого Вы просите помощи. 1

@Pphantom 2101 / 1347 / 651 Регистрация: 17.03.2022 Сообщений: 4,246
	11.03.2025, 11:33
	VTsaregorodtsev, все правильно, но можно, пожалуй, добавить еще пару слов. Когда (и если) все это будет учтено, следующий шаг - использование более чем одного ядра, коих в нынешних процессорах много. Но это тоже не MPI, а что-нибудь вроде OpenMP. А дальше, если производительности все равно не хватит - графические ускорители, эта задача для них вполне подходит. 0