Распараллеливание программы (ядра/потоки)

[Dmitriy40]

Лично мне непонятны минимум две вещи: почему время так сильно скачет и почему нет ускорения для 3 и 4 потоков. Может они и не связаны ...
Вообще по хорошему надо сначала разобраться почему время так сильно прыгает.
4Мб вообще слёзы, они практически в L3 будут и значит обращение к данным сильно тормозить не должно.
Тем более говорите завершаются почти одновременно.
Даже не знаю что и подумать.
Запустите в один поток вчетверо меньшее задание? Т.е. как бы в 4 потока, но лишь один из них. Будет ли время ~вчетверо меньше? А если повторить это раз 5 будет ли время прыгать?

-- 02.01.2020, 21:57 --

У меня время выполнения столь сильно прыгает только если в фоне запущены вычисления, даже с idle приоритетом. Для точных измерений времени/скорости приостанавливаю все вычисления, чтобы загрузка процессора была пара процентов (фоновая активность ОС), не более. И при этом уже разброс времени доли секунды (просто лень точнее учитывать).

[Andrey_Kireew]

Dmitriy40 в сообщении #1433153 писал(а):

как бы в 4 потока, но лишь один из них. Будет ли время ~вчетверо меньше?

сейчас попробую

-- 03.01.2020, 01:53 --

Вот такой результат:

111,36 sec
111,70 sec
111,58 sec
111,71 sec
111,53 sec

-- 03.01.2020, 02:11 --

А вот на тех же данных в 4-х потоках:

63
55
34
70
65

в общем время при использовании нескольких потоков скачет - это факт.

[SergeCpp]

Dmitriy40 в сообщении #1433153 писал(а):

Для точных измерений времени/скорости приостанавливаю все вычисления, чтобы загрузка процессора была пара процентов (фоновая активность ОС), не более. И при этом уже разброс времени доли секунды (просто лень точнее учитывать).

Это GetThreadTimes такие результаты выдаёт?

[Dmitriy40]

SergeCpp в сообщении #1433183 писал(а):

Dmitriy40 в сообщении #1433153 писал(а):

Для точных измерений времени/скорости приостанавливаю все вычисления, чтобы загрузка процессора была пара процентов (фоновая активность ОС), не более. И при этом уже разброс времени доли секунды (просто лень точнее учитывать).

Это GetThreadTimes такие результаты выдаёт?

Нет, это внешней утилитой измеряется полное время выполнения .exe файла:

Цитата:

Calculate programs work time Version 1.01 Copyright (c) 1998 Vladimir Tarasov
Usage: wt.exe <prog_name.exe> [<parameters>]

Тем более что обычно интересует как раз полное время выполнения .exe, а не разбивка его по потокам. Добавлять в каждую программу измерение времени и его вывод - лень. А когда и делаю, то использую GetTickCount в основном потоке, её достаточно.

Andrey_Kireew
В один поток всё красиво и правильно (если проигнорировать что $111 \cdot 4 \not \approx 380$), в 4 - тот же бред. Что-то у Вас с делением задачи не то ... Но что - не пойму. Не могу придумать ситуацию когда 4 независимых потока будут так тормозить на 4Мб данных (при отсутствии фоновых) ...
Что я попробовал бы сделать: запустить потоки остановленными (предпоследний параметр = CREATE_SUSPENDED), потом в цикле вызывать ResumeThread с ожиданием завершения каждого (WaitForSingleObject). Т.е. запустить 4 потока, но не одновременно, а строго последовательно. И убедиться что время снова станет 111с без скачков. Правда что это даст не очень понятно. Хотя если станет не 111с или будут большие скачки - ищите ошибку при делении задачи.

[Andrey_Kireew]

Dmitriy40 в сообщении #1433189 писал(а):

будут большие скачки - ищите ошибку при делении задачи

не совсем понимаю, при чём тут деление, ведь деление всегда выполняется по одному и тому же алгоритму, и данные используются всегда одни и те же - а время выполнения скачет от случая к случаю, чуть ли не в 2 раза

У меня возникло такое подозрение: Например, при n=2 потоки могут попасть на разные ядра, а могут - стать гиперпотоками одного ядра. Понятно, что производительность будет сильно различаться. А если поток всего один - этого произойти попросту не может. Как Вы думаете, может в этом всё и дело?

Если так, то нужно как то привязывать потоки к разным физическим ядрам.

-- 03.01.2020, 09:49 --

Чтобы сразу снять многие вопросы - отключил режим Hyper Thread. В диспетчере задач теперь только 4 процессора. Вот результаты работы на той же маленькой подзадаче:

110
59
51
55

время скачет как и раньше.

Что характерно - на одном потоке стабильно получаются всё те же 111 sec, различия только в десятых долях.

[Dmitriy40]

Andrey_Kireew в сообщении #1433196 писал(а):

отключил режим Hyper Thread.
...
время скачет как и раньше.

Спасибо, полезно, это и ответ на Ваш предыдущий вопрос, могут ли два процесса попасть на один физический - теперь то уж точно не могут.
Оно мало того что скачет, так ещё и не уменьшается для 3-4 потоков. И думаю Вы посмотрели что дял 4-х потоков загрузка процессора 100% практически до конца. А значит что? А значит потоки или делают чужую работу, или не столь независимы как Вы декларируете (readonly общих данных, отсутствие синхронизаций, запись в разные области памяти).
Что могу сказать, замените свои вычисления в потоках на пустые заглушки (только не средствами ОС! просто цикл суммирования индекса с его записью в выходной массив чтобы оптимизатор не убил цикл) с тем же временем выполнения в 111с и проверьте что в многопоточном режиме время уменьшается правильно. Тогда можно будет предположить что делите задачу всё же правильно и искать придётся взаимосвязь потоков. Например заменив цикл задержки времени на чтение входных массивов.
Короче упростите программу до правильно работающего состояния (111с/Nпотоков), а потом по шагам возвращайте функциональность.

[Dmitriy40]

Вот вам минимальный работающий пример:

Используется синтаксис C

#include <windows.h>

int nTh, buf[10];

int MyFun(void* p) {
int i, s, n;
        s = 0; n = 2000000000 / nTh;//Деление работы
        for (i = 0; i < n; i++) s += ((i / nTh) / nTh) / nTh;//Основная работа
        *((int*)p) = s;//Не позволим оптимизатору убить предыдущий цикл!
        return 0;
}

HANDLE hh[10];
int i, t;

int main(void) {
        printf("Times:");
        for (nTh = 1; nTh <= 10; nTh++) {
                t = GetTickCount();
                for (i = 0; i < nTh; i++) hh[i] = CreateThread(NULL, 0, &MyFun, &buf[i], 0, NULL);
                WaitForMultipleObjects(nTh, hh, TRUE, INFINITE);
                printf(" %0.1fs", (GetTickCount() - t) / 1e3);
                for (i = 0; i < nTh; i++) CloseHandle(hh[i]);
        }
        printf("\n");
        return 0;
}

Его вывод для трёх запусков на 4-х ядерном процессоре без гипертрединга:

Используется синтаксис Text

Times: 13.3s 7.8s 5.1s 3.7s 4.4s 3.7s 3.7s 3.6s 3.7s 3.7s
Times: 13.3s 7.9s 5.1s 3.7s 4.3s 3.6s 3.6s 3.7s 3.7s 3.6s
Times: 13.3s 7.9s 5.0s 3.6s 4.3s 3.7s 3.6s 3.7s 3.6s 3.6s

Как видите многопоточность работает.

[Andrey_Kireew]

С этим всё понятно, значит дело в коде.
Тут у меня возникло ещё одно подозрение. В коде поточной есть динамическое выделение памяти, небольшой объём - но всё же. Это может как то влиять на работу?

[mihaild]

Andrey_Kireew в сообщении #1433309 писал(а):

Это может как то влиять на работу?

Зависит от деталей - аллокатор вполне может быть блокирующим, или выделять память для разных потоков рядом. Первое существенно только если память выделяется в цикле, и существенное время уходит на работу аллокатора.

[Dmitriy40]

Andrey_Kireew в сообщении #1433309 писал(а):

Это может как то влиять на работу?

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

[Andrey_Kireew]

Dmitriy40 в сообщении #1433317 писал(а):

На крайний случай выделить всю память заранее в основном потоке ещё до запуска вычислительных потоков, передавая им лишь ссылки

Да, наверное попробую так и сделать. По результатам потом отпишусь

[Andrey_Kireew]

В общем создал я все массивы в основном потоке и прицепил к структуре с данными, передаваемой в функции.
Результат оказался противоположным ожидаемому. Работать всё стало намного хуже. Самое главное - потоки стали выполнятся сильно неравномерно - один в 2 раза быстрее другого, хотя алгоритм деления задачи остался прежним. Один раз - вообще всё зависло. Похоже, всё дело в этой структуре с данными. Чтобы она не пропала по ходу выполнения программы, я её сделал static, но это не помогло ...

-- 04.01.2020, 01:19 --

Что характерно - в одном потоке всё работает отлично.

[mihaild]

Dmitriy40 в сообщении #1433317 писал(а):

Но что мешает выделить всю нужную память в стеке (локальных переменных)?

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

Andrey_Kireew в сообщении #1433347 писал(а):

Один раз - вообще всё зависло

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

Кстати, код Dmitriy40 у вас работает с ожидаемым ускорением?
Если да - то попробуйте понемногу переносить в него вычисления из вашего кода, и смотреть, в какой момент ускорение от 3+ потоков исчезнет.

[Andrey_Kireew]

mihaild в сообщении #1433349 писал(а):

вы кстати не забываете при экспериментах следить не только за временем, но и за правильностью ответа?

что за ним следить, если он всегда один и тот же

mihaild в сообщении #1433349 писал(а):

Кстати, код Dmitriy40 у вас работает с ожидаемым ускорением?
Если да - то попробуйте понемногу переносить в него вычисления из вашего кода

Я не пробовал, но видимо работает, он такой же как у меня, только переменные объявлены глобально, а у меня локально
вычисления я по частям перенести не могу, без динамических массивов работать ничего даже не начнёт, а сними вообще непонятно как быть, думаю вернуть обратно внутрь функции, там хоть ничего не зависало, и работало быстрее.

Больше всего меня удивляет, почему так сильно изменилась трудоёмкость задач в потоках

[mihaild]

Andrey_Kireew в сообщении #1433351 писал(а):

что за ним следить, если он всегда один и тот же

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

Andrey_Kireew в сообщении #1433351 писал(а):

Больше всего меня удивляет, почему так сильно изменилась трудоёмкость задач в потоках

Судя по зависанию - просто где-то ошибка, и в итоге считается непонятно что (и скорее всего вообще UB). Но вообще могут быть спецэфеекты из-за false sharing.

Andrey_Kireew в сообщении #1433351 писал(а):

Я не пробовал

Попробуйте. Когда происходит что-то непонятное - всегда стоит сделать простые sanity check.

Andrey_Kireew в сообщении #1433351 писал(а):

вычисления я по частям перенести не могу

Тогда наоборот: возьмите ваш код, удалите из него как можно больше, и посмотрите, сохранится ли эффект. Потом понемногу возвращайте.