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

[SergeCpp]

Ненулевой Sleep, даже 1ms, это совершенно огромное время даже для медленных процессоров, что были лет 20 назад, тем более для чисто вычислительной, неинтерфейсной задачи. Там верно говорится: "the best thing to do is to wait on a proper synchronization object so that your thread goes to sleep until there is work to do". А "if you can’t do that for some reason" говорит о том, что в программе что-то не так, раз используются методы "слона в посудной лавке" ("at least sleep for a nonzero amount of time").

[Dmitriy40]

SergeCpp
Простите, но 1мс sleep раз в секунду это жалкие 0.1%. Уж о такой точности тут речи и близко не идёт.
И да, я отдаю себе отчёт что 1мс может превратиться и в 18мс (как в древних ОС был тик переключения задач), но и это тоже жалкие 2%.
Но прелесть в том что при отсутствии других готовых к выполнению потоков не превратится. А если они таки есть - то им будет дано процессорное время, даже если они ниже приоритетом, это важно.
Просто я часто и помногу считаю и натурально вижу огрехи в распределении ресурсов у винды (Win7Pro). Когда два одинаковых многопоточных процесса могут считать с очень (в разы!) разной скоростью, только лишь потому что винда вот так им выделяет процессорное время. По хорошему надо вообще регулярно возвращать управление в ОС, и один из простых способов это сделать как раз Sleep(). А уж с 0 или 1 её вызывать — зависит от конкретной ситуации. Я и с 50 её вызываю когда жду завершения потоков и ничего, работает как мне надо.
А с объектами синхронизации гемороя бывает больше чем удобства. Тем более в таких несложных программах.

И вообще, это уже слабо к теме относится.

[Andrey_Kireew]

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

А это Вы своими словами повторили мой совет
(даже с готовым исходником!)

проверил этот способ, код правда написал свой

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

HANDLE *Th=new HANDLE[numCPU];
for (int j=0;j<numCPU;j++)
 do
   Th[j]=(HANDLE)_beginthreadex(NULL, 0, &select, (void *) &a[j], 0, NULL); 
 while (Th[j]==0);
Sleep(1);
for (int j=numCPU;j<numWork;j++)
{
di=WaitForMultipleObjects(numCPU, Th, FALSE, INFINITE); 
di-=WAIT_OBJECT_0;
    
 do
  Th[di]=(HANDLE)_beginthreadex(NULL, 0, &select, (void *) &a[j], 0, NULL);
 while (Th[di]==0); Sleep(1);
}
WaitForMultipleObjects(numCPU, Th, TRUE, INFINITE); 
 

толку никакого нет, наоборот, даже медленнее работает.

-- 07.01.2020, 15:37 --

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

Если мерять посредством GetThreadTimes, то будут две важные полезности

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

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

Можно ли как нибудь выровнять динамические массивы в VС2010, и на сколько их выравнивать на 32 или на 64?

[mihaild]

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

толку никакого нет, наоборот, даже медленнее работает

Что логично - ваше разбиение делает ситуацию хуже, а не лучше. Вы сначала ждете первые несколько блоков, потом следующие несколько блоков и т.д. - если скажем у вас 2 потока, то, пока не досчитаются первый и второй блоки, следующие считаться не начнут. В частности если скажем первый блок посчитался быстро - то поток будет простаивать, пока не досчитается второй - а мог бы уже считать третий блок.
Ну и тут вы создаете кучу процессов, это тоже не бесплатно.

В коде Dmitriy40 потоки создаются сразу, но работа между ними разбивается динамически - как только очередной поток досчитал свой блок, он берется за первый еще не посчитанный. В результате потоки могут простаивать только если все блоки либо уже посчитались, либо считаются.
Например если разбивать на блоки, время подсчета которых распределено равномерно от 1 до 2 секунд, то в вашем подходе на каждую группу мы получаем в среднем $\frac{1}{3}$ секунд, когда выполняется только один поток. А в правильном это происходит в течении максимум двух секунд за всё время (если последний блок оказался тяжелым и его взяли как раз когда другой поток уже почти досчитал свой блок).

[Andrey_Kireew]

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

Вы сначала ждете первые несколько блоков, потом следующие несколько блоков

это не так, с аргументом FALSE

di=WaitForMultipleObjects(numCPU, Th, FALSE, INFINITE);

срабатывает сразу по завершении любого из потоков, и выдаёт номер завершившегося потока. Потом я ставлю в него следующий блок и запуская по новой.

[mihaild]

А, ну так лучше. Но всё равно создание новых потоков - это довольно дорого.

-- 07.01.2020, 15:31 --

А, ну так лучше. Но всё равно создание новых потоков - это довольно дорого.

[Andrey_Kireew]

Наверное дорого, поэтому подольше и получается. Но не на много, примерно 10%.

Главная причина остаётся не выясненной. Я пытался выровнять структуру таким образом

__declspec(align(8)) struct DATA

по началу всё было отлично, время выполнения потоков стало почти одинаковым (и это ещё раз подтверждает, что сами по себе задачи одинаковые по трудоёмкости, но для выполнения, почему то требуют разного времени), но это была иллюзия, через несколько повторных запусков потоки опять стали выполняться по разному

[SergeCpp]

Andrey_Kireew, вот Рихтер онлайн, 4-е издание (есть также вид для печати, может быть удобнее), про потоки там очень хорошо и доступно. Обратите внимание на главу 11 (Пулы потоков). Для чтения в режиме не для печати нужен JavaScript (при отключённом у меня не показывает ничего); режим для печати работает и без JavaScript.

[Andrey_Kireew]

Спасибо SergeCpp! хорошо написано, почитаю

[Dmitriy40]

Andrey_Kireew
Как бы Вы не выравнивали структуру DATA, в вычислительных потоках она читается (и пишется) лишь однажды — т.е. на скорость влиять ну никак не может.
А правильное выравнивание массивов обеспечит насколько я понимаю сама new. И она же автоматом обеспечит разделение массивов в разных потоках по разным кэшлиниям.
Насколько дорого создание и завершение потока Вы можете увидеть по той же GetThreadTimes, наверняка оно даже в сумме для всех блоков на порядки меньше 1% общего времени.
Sleep(1) Вы добавили напрасно, ничего полезного это не даёт и даже чуточку вредит (два лишних перехода между режимами пользователя и ядра, каждое по несколько мкс).
Завершение и запуск потоков вместо диспетчеризации блоков в самих потоках (как было у меня) так же дважды переключает контекст, снова по несколько мкс, плюс неопределённое время ожидание переключения задач в процессоре/ОС.
Если вычисления каждого блока занимают хотя бы десятки-сотни мс это всё в сумме конечно мало и на скорость ощутимо влиять не должно. 10% это слишком много.
Почему время выполнения потока может скакать вдвое остаётся непонятным.
Заведите счётчики в самом внутреннем цикле (сразу за меткой NEXT) и в конце выводите их на печать и проверьте что при разных запусках они идентичны во всех потоках даже когда времена сильно отличаются.

[Andrey_Kireew]

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

Заведите счётчики в самом внутреннем цикле

Разумно. Я так и сделал. Вот что получается:

N_iter= 2642387 тыс.
N_iter= 2723888 тыс.
N_iter= 2635530 тыс.
N_iter= 2660488 тыс.
0 :, T_Kern=0 ms, T_User=96330 ms
1 :, T_Kern=0 ms, T_User=94645 ms
2 :, T_Kern=0 ms, T_User=184876 ms
3 :, T_Kern=0 ms, T_User=124488 ms
T=186890 ms
Elapsed time is 186.877153 seconds.

Повторял несколько раз, N_iter всегда одинаковые, только меняется их порядок, видимо потому, что порядок завершения потоков всегда разный. Ну а временна выполнения каждый раз совершенно разные, и как Вы видите, могут отличаться почти в 2 раза

[Dmitriy40]

Ну вот теперь вопрос упрощается до "почему одна итерация может занимать сильно разное время?". В показанном куске кода такое вроде невозможно (снова повторю, при отсутствии работающих (занимающих процессорное время) фоновых потоков), значит искать надо в непоказанной части. И самый простой способ — расставить assert перед каждой строкой, в которой есть обращения к массивам, с проверкой всех указателей и индексов. Потом подумать где в функции может циклиться не заходя в метку NEXT. Потом подумать где могут читаться или тем более писаться объекты из чужого потока, при наличии ошибок или каких-то неправильных условиях в if (и тоже поставить ловушки в эти точки). И т.д.

[SergeCpp]

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

1. T_User = 94645 ms
2. T_User = 184876 ms

1) Интересно, как соотносятся у так отличающихся потоков цифры QueryThreadCycleTime. Но это в сущности неважно для работы (только для "разобраться, почему").

2) Я же в самом начале приводил ссылку на статью remark, где написано: "общее количество задач должно быть не меньше чем, ну скажем, 16*количество_ядер (для обеспечения балансировки нагрузки), и так же абсолютный размер задачи должен быть в разумных пределах, скажем, не больше 100 мс". Ключевое я выделил.

Можно задать параметрами: число_потоков и число_задач. И смотреть-выбирать минимальное по времени работы. Задачи в очередь. Потоки в очередь. Свободен поток -- берёт из очереди. У Рихтера, сколь помню, всё это тоже описано (не перечитывал сейчас).

[Andrey_Kireew]

что такое

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

QueryThreadCycleTime .

, я затрудняюсь перевести

[Dmitriy40]

Andrey_Kireew
Да просто количество тактов процессора, а не мс.

SergeCpp
А чем QueryThreadCycleTime поможет в разбирательстве? Или она не учитывает и время (в тактах) кэшпромахов? И прочих прелестей ожидания конвейеров? Ведь по идее количество тактов будет хорошо скоррелировано с временем. Тут бы больше помогли счётчики производительности, но с ними надо разбираться как их настроить, да и можно ли вообще использовать для массивов (но хотя бы количество кэшпромахов они должны выдавать), да ещё и пустят ли к ним с уровня пользователя ...

-- 07.01.2020, 22:49 --

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

Свободен поток -- берёт из очереди.

Именно эту модель я уже и привёл выше, с готовым исходником. И не нужно 16N потоков, достаточно лишь N.