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

@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'ом данных).
Так что если правильно реализовать многопоточность (это я ТСу опять намекаю, что вижу-знаю, как тут надо действовать) - то эффект должен быть.

Новые блоги и статьи Все статьи Все блоги /
AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .

@Pphantom 2326 / 1568 / 722 Регистрация: 17.03.2022 Сообщений: 5,064
	10.03.2025, 11:32
	А чему равно N? 0

@Pphantom 2326 / 1568 / 722 Регистрация: 17.03.2022 Сообщений: 5,064
	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 6812 / 2052 / 238 Регистрация: 14.12.2014 Сообщений: 4,308 Записей в блоге: 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 2326 / 1568 / 722 Регистрация: 17.03.2022 Сообщений: 5,064
	11.03.2025, 11:33
	VTsaregorodtsev, все правильно, но можно, пожалуй, добавить еще пару слов. Когда (и если) все это будет учтено, следующий шаг - использование более чем одного ядра, коих в нынешних процессорах много. Но это тоже не MPI, а что-нибудь вроде OpenMP. А дальше, если производительности все равно не хватит - графические ускорители, эта задача для них вполне подходит. 0