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

[slavav]

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

slavav в сообщении #1433036 писал(а):

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

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

Вместо множества потоков внутри одного процесса, запустите множество процессов (и в каждом единственный поток). Получите тот же результат без возни с параллельным программированием.

[Andrey_Kireew]

Остаётся ещё один очень важный вопрос, который отражен в названии темы.
У процессора i7 6700, как известно 4 ядра, но он может поддерживать 8 потоков - это всем известно.
Но функция GetSystemInfo() выдаёт информацию о 8 процессорах, а не о 4-х, как этого следовало бы ожидать. Понятно, что ив диспетчере задач отображается 8 ядер.

Правильно ли я понимаю, что эти 8 ядер в действительности не являются независимыми и когда загружены только 4 ядра, каждое из них обеспечивает примерно в 2 раза большую производительность, по сравнению с тем, когда загружены все 8 ядер? Верно ли, что при увеличении количества загруженных ядер больше 4 , никакого существенного роста производительности ждать не стоит и заметные преимущества от этого проявляются, только когда задача является многопоточной по своей природе?

[Dmitriy40]

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

Правильно ли я понимаю,

Нет, неправильно. Правильно тут: Hyper-threading (и в английской).

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

Верно ли, что при увеличении количества загруженных ядер больше 4 , никакого существенного роста производительности ждать не стоит и заметные преимущества от этого проявляются, только когда задача является многопоточной по своей природе?

Это неверно само по себе, отдельно, многопоточная программа получает преимущество уже от двух и более потоков/ядер. Однопоточной программе фиолетово сколько у процессора ядер/потоков, она в любом случае будет выполняться не быстрее чем на одном (за исключением тонких эффектов наличия других выполняющихся потоков в системе). Т.е. граница проходит не по цифре 4, а между цифрами 1 и 2.

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

Но функция GetSystemInfo() выдаёт информацию о 8 процессорах, а не о 4-х, как этого следовало бы ожидать.

Посмотрите в сторону GetLogicalProcessorInformation().

[mihaild]

https://en.wikipedia.org/wiki/Hyper-threading
В зависимости от специфики приложения может уменьшить время выполнения на 30% (как я понимаю, теоретически на 50%, но на практике этого достигнуть не получается) или увеличить на 10% (теоретически может и в десятки раз, но это надо делать специально).

[Dmitriy40]

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

[Andrey_Kireew]

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

Для некоторых конкретных 50% вполне достижимы (разумеется минус эффекты межпотоковой синхронизации)

ну вот смотрите, у меня 8 потоков, читают они данные из одной общей памяти (как я понял при чтении никакой синхронизации не требуется), записывают результаты каждый в свою область памяти (постобработка происходит уже после их завершения), друг с другом потоки не взаимодействуют вообще. В этих условиях можно ожидать повышения производительности в 8 раз? или только в 4 раза, т.к. ядер то всё равно 4 а не 8?

[Dmitriy40]

Andrey_Kireew
Этих данных всё равно недостаточно для оценки.
Если программа читает данные предсказуемым образом (например массивы подряд) и обработка прочитанных данных существенно дольше их чтения, то тормозом будет не память или кэш, а вычислительные блоки. Если при этом ещё и вычисления однородны (нет кусков кода в десятки команд где в каждом преобладают разные по типу команды процессора) и не слишком разветвлены (мало плохо предсказуемых условных переходов), то двухкратного ускорения при переходе $4 \to 8$ потоков быть не должно. Но на десятки процентов почему бы и нет. При нарушении любого из этих условий, или некоторых других мною забытых, вполне можно получить и почти двухкратное ускорение. Теоретически оценить это, тем более для ЯВУ, сложно, проще запустить и проверить.

Здесь всё упирается в то, что гипертрединг пытается загрузить простаивающие вычислительные блоки каждого физического ядра командами другого потока. Если простаивающих нет или в буфере предпросмотра процессора нет команд для простаивающих блоков (например все вычисления с плавающей точкой, а накладные расходы на циклы и прочее малы) - не будет и ускорения. Т.е. надо смотреть есть ли причины для простоя вычислительных конвейеров. Как то: случайные чтения памяти, непредсказанные условные переходы, загружающие не все вычислительные блоки куски кода (в терминах команд процессора, не С++), зависимости по данным в коде, может ещё что забыл. Как всё это увидеть на ЯВУ типа С++ объяснить не берусь, это надо детально разбирать исходный код (а часто и машинный).
Плюс в некоторых случаях можно даже и четырёхкратного ускорения не получить. Например если объёма кэша L3 хватало для однопоточного вычисления, но не хватит для 4-х поточного.

Повторю, даже в рафинированных как у Вас условиях, "за глаза" (не разбирая исходный код) трудно сказать что-то определённое. Проще запустить и проверить.

[Andrey_Kireew]

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

двухкратного ускорения при переходе $4 \to 8$ потоков быть не должно

Спасибо, так стало более менее ясно. Видимо, в моём случае, на Hyper-threading надеяться особо не стоит. Лучше рассчитывать на реальное число ядер, т.е. на 4. В любом случае я попробую все варианты. Потом напишу, что получилось. Почти все ошибки в программе уже исправлены. Осталось совсем немного

[Dmitriy40]

Я бы попробовал использовать AVX если это ещё не сделано. Даст выигрыш (до порядка) на каждом ядре. Распараллеливанию почти не мешает (лишь трафик памяти) и может проводиться независимо.

[mihaild]

Dmitriy40, 30% и 10% это то что я видел в реальных бенчмарках для конкретных нетривиальных приложений.

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

И получить в разы тоже не так уж сложно, достаточно писать всеми потоками в одну строку кэша (пусть и в формально разные переменные).

Здесь есть что-то специфическое для гипертрединга?
Я думал про ситуации когда потокам на одном ядре не хватает L1 или L2 кеша.

[Andrey_Kireew]

В общем, вот что получилось:

1 Corn ... Elapsed time is 383.29 seconds ... Elapsed time is 369.87 seconds.
2 Corn ... Elapsed time is 192.22 seconds ... Elapsed time is 190.06 seconds.
3 Corn ... Elapsed time is 218.10 seconds ... Elapsed time is 271.16 seconds.
4 Corn ... Elapsed time is 151.93 seconds ... Elapsed time is 220.19 seconds.
5 Corn ... Elapsed time is 165.95 seconds ... Elapsed time is 227.75 seconds.
6 Corn ... Elapsed time is 164.80 seconds ... Elapsed time is 161.17 seconds.
7 Corn ... Elapsed time is 171.64 seconds ... Elapsed time is 139.13 seconds.
8 Corn ... Elapsed time is 157.88 seconds ... Elapsed time is 164.03 seconds.

на 2-х ядрах прирост в 2 раза, а потом почти никакого толку.

-- 02.01.2020, 20:57 --

Ну а вот и исправленный код:

1. #include<stdio.h> 
2. #include<windows.h> 
3. #include<process.h> 
4.  
5. static unsigned int __stdcall myFun(void* a) 
6. { 
7.  
8. ............. 
9.  
10. return 0; 
11. } 
12.  
13. main() 
14. { 
15.  
16. .............. 
17.  
18. SYSTEM_INFO sysinfo; 
19. GetSystemInfo(&sysinfo); 
20. int numCPU = sysinfo.dwNumberOfProcessors; 
21. printf("numCPU= %d \n",numCPU); 
22.  
23. HANDLE *Th=new HANDLE[numCPU]; 
24. for (int j=0;j<numCPU;j++) 
25.   Th[j]=(HANDLE)_beginthreadex(NULL, 0, &select, (void *) &a[j], 0, NULL); 
26.  
27. WaitForMultipleObjects(numCPU, Th, TRUE, INFINITE); 
28.  
29.         ...... 
30.  
31. printf("done!!! /n"); 
32. printf("%e", value); 
33.  
34. delete [] Th; ... 
35.  
36. return 0; 
37.         
38. } 

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

-- 02.01.2020, 21:00 --

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

Я бы попробовал использовать AVX если это ещё не сделано

это нужно ассемлер использовать?

[Dmitriy40]

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

Здесь есть что-то специфическое для гипертрединга?
Я думал про ситуации когда потокам на одном ядре не хватает L1 или L2 кеша.

Пожалуй нет, разве что при дроблении на большее количество потоков уменьшится грануляция записи. Тем более что запись двумя потоками в одну строку кэша на одном физическом ядре не приводит к штрафу (кэши не привязаны к потокам, они работают в физическом пространстве адресов). Но обычно распределение потоков по ядрам отдано ОС, а уж как она там их распихает - никому не ведомо (там же вмешается и балансировка нагрузки, и прыганье частот каждого ядра, и остальные потоки в ОС тоже не все остановлены).
Канал между кэшами довольно быстр (32-64 байта за такт), объём L3 превышает суммарный объём всех L2, так что просто нехватка L2 (про L1 вообще молчу) слабо скажется на скорости. Ну, чаще всего, исключения всегда возможны. А вот пропасть между скоростью и латентностью памяти и кэшем L3 - в разы больше, потому и её влияние сильнее.

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

на 2-х ядрах прирост в 2 раза, а потом почти никакого толку.

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

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

это нужно ассемлер использовать?

Если компилятор не умеет сам векторизировать циклы, то скорее всего почти да: есть технология Intrinsics, но разбираться с командами SSE/AVX таки придётся.

-- 02.01.2020, 21:02 --

Поделить на мелкие блоки можно примерно так (вызов и ожидание завершения те же):

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

int curBlock = 0;
#define incBlock        1000;
#define numBlocks       1000000;

static unsigned int __stdcall MyFun() {
int base, stop;
        while (true) do {
                CS.Lock;//Критическая секция
                base = curBlock; curBlock += incBlock; stop = numBlock;
                CS.Leave;//Критическая секция
                if (base >= stop) return 0;//Больше работы нет
                if (base + incBlock < stop) stop = base + incBlock;//Последний блок может быть меньше, а остальные одинакового размера
                for (int i = base; i < stop; i++) {
                        ... //Основная работа
                }
        }
}

[Andrey_Kireew]

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

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

Есть подозрение, что это не так. Работа распределена более - менее равномерно. Все потоки завершаются в течение последних 5-10 сек., это видно по диспетчеру задач. На фоне 150 - 300 сек. - это почти одновременно. Дело наверное в чём то другом.

-- 02.01.2020, 22:24 --

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

Поделить на мелкие блоки можно примерно так

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

[Dmitriy40]

Да, readonly данные дублировать не надо, это даже вредно: копии займут больше места в L3 и трафика памяти. А так все потоки могут пользоваться одной общей копией.

[Andrey_Kireew]

Этот массив, в той задаче, на которой я всё испытываю, всего 4 Мб - не такой он и большой. В чём тогда может быть дело?