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

[Andrey_Kireew]

Уважаемые участники, возникла небольшая проблема, прошу помощи.
Несмотря на все ухищрения, программный код получился слишком трудоёмким в вычислительном отношении. Можно конечно дальше оптимизировать, но выигрыш из этого, наверное уже будет небольшой.

В связи с этим, возникла идея, хотя бы распараллелить программу. Но опыт в таких вопросах у меня не большой и возникает много вопросов. Вопрос первый: есть 4-х ядерный процессор, но в описании к нему сказано, что он поддерживает 8 потоков. На сколько потоков ориентироваться мне, чтобы добиться максимальной производительности? В диспетчере задач показывает 8 процессоров, но matlb позволяет запустить только 4 worker. И с этим не совсем понятно.

Вопрос второй, практический: может ли кто-нибудь дать ссылку на простые и доходчивые примеры по созданию параллельной программы на С++?

[SergeCpp]

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

Вопрос второй, практический: может ли кто-нибудь дать ссылку на простые и доходчивые примеры по созданию параллельной программы на С++?

Вот сайт remark (это ник на rsdn): http://www.1024cores.net/home/in-russian -- там в About Me есть информация.

3 базовых вещи относительно параллельных вычислений

[Dmitriy40]

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

Вопрос первый: есть 4-х ядерный процессор, но в описании к нему сказано, что он поддерживает 8 потоков. На сколько потоков ориентироваться мне, чтобы добиться максимальной производительности?

Лучше сразу распараллеливать на N>1 потоков. А по результатам тестового прогона выбрать оптимальное N (достаточно между 4 и 8). В принципе, 8 должно считаться быстрее, но при весьма хитром условии: каждый поток не загружает ни один из портов запуска на 90%-100% на значительное время (десятки процентов времени прогона). Но нарушить его кодом на ЯВУ достаточно сложно, компиляторы не настолько хороши чтобы превратить любой код в плотно загружающий процессор. Тем более если он не оптимизирован специально. Разумеется ориентироваться на загрузку процессора в диспетчере задач нельзя, надо именно запускать тестовые прогоны и засекать время. И чтобы время каждого прогона было не менее десятка секунд чтобы минимизировать случайные флуктуации и погрешности. Но вот ассемблерными вставками я довольно часто загружаю некоторые порты на 100% и тогда от увеличения количества потоков свыше количества физических ядер преимущества не получаю.

Короче делайте на N потоков и прогонами проверяйте при каком N время выполнения меньше. Это самый разумный способ. По идее N=8 должно быть быстрее, но могут быть исключения.
UPD. Ого, в той заметке вообще N=128 рекомендуют ... Честно говоря не согласен, думаю N=8..10 (для 4/8 процессора) для вычислительных задач будет всегда достаточно.

Надеюсь оптимизацию по размерам кэшей уже провели, если это возможно.

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

[Andrey_Kireew]

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

при весьма хитром условии: каждый поток не загружает ни один из портов запуска на 90%-100% на значительное время

можно ли считать, что если программа в однопоточном варианте загружает одно ядро на 100%, то и в многопоточном варианте она загрузит 4 ядра на все 100% и, следовательно, мне нужно ориентироваться на 4 ядра?

[Dmitriy40]

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

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

при весьма хитром условии: каждый поток не загружает ни один из портов запуска на 90%-100% на значительное время

можно ли считать, что если программа в однопоточном варианте загружает одно ядро на 100%, то и в многопоточном варианте она загрузит 4 ядра на все 100% и, следовательно, мне нужно ориентироваться на 4 ядра?

Можно, при одном важном условии: загрузку определяете не по диспетчеру задач! Я ведь говорил не о загрузке всего процессора (что с некоторыми важными оговорками и показывает диспетчер задач), а о загрузке любого из портов запуска в процессоре. Например если абстрактный процессор содержит лишь один порт запуска плавающих инструкций, а вся программа практически только из них и состоит, то следствие будет выполняться, даже если другие 5 портов запуска (для других инструкций) простаивают. А если портов запуска вычислительных инструкций 4, причём не одинаковых, и все они не загружаются на 90%-100%, то нет, распареллеливание на два потока уменьшит время прогона даже на одном ядре (в винде можно заставить программу исполняться лишь на выделенных ядрах).
Во всех этих случаях диспетчер задач покажет 100% загрузку ядра процессора, хотя много внутренних блоков могут вовсе простаивать.
Но вообще всё равно возможны исключения и другие зависимости, тут очень много деталей и тонкостей, которые могут стать важными именно в многопоточной работе. Один из известных примеров, он есть в той заметке по ссылке выше, запись разными ядрами в одну строку кэша в памяти. Не чтение, а именно запись. С записями в память вообще надо очень аккуратно. Или например будет излишняя конкуренция между ядрами за кэш L3, которого хватало на один поток, но станет мало на все ядра. Ну про стоимость синхронизации и взаимные блокировки говорить не буду, это везде освещено.
Короче всё сложно. Если кто даст хорошее руководство (на русском) - и сам почитаю.

[Andrey_Kireew]

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

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

#include<stdio.h>
#include<windows.h>
#include<process.h>

static unsigned int __stdcall myFun(void* a)
{

.............

*a=1;
return 0;
}
main
{
int s;
int numCPU = sysconf(_SC_NPROCESSORS_ONLN);

for (int j=0;j<numCPU;j++)
_beginthreadex(NULL, 0, &myFun, (void*)a[j], 0, NULL);


do
{   s=0;
for (int j=0;j<numCPU;j++) s=+*a[j];
}
while (s<numCPU);

        ......
printf("%e", value);
return 0;
        
}
 

[SergeCpp]

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

[mihaild]

Andrey_Kireew, очень советую пользоваться средствами многопоточности из стандартной библиотеки (есть начиная с C++11).
(а еще поправить отступы, не писать тело цикла в одной строке с объявлением цикла, и не писать ничего после открывающей фигурной скобки, и, наверное, лучше приводить код целиком)

Я не вижу где в вашем коде ожидание завершения созданных потоков - т.е. (если _beginthreadex с указанными вами параметрами действительно создает поток), ничем не гарантируется, что цикл do..while начнется после того, как эти потоки отработают. В частности, у вас тут гонка - вы в одном (созданном) потоке пишете в a[j], в другом (основном) читаете, и между этими операциями нет никаких синхронизаций. Это UB.

[Andrey_Kireew]

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

очень советую пользоваться средствами многопоточности из стандартной библиотеки (есть начиная с C++11)

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

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

не вижу где в вашем коде ожидание завершения созданных потоков

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

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

#include<stdio.h>
#include<windows.h>
#include<process.h>

static unsigned int __stdcall myFun(void* a)
{

.............

return 0;
}

main()
{

int numCPU = sysconf(_SC_NPROCESSORS_ONLN);

HANDLE *Th=new HANDLE*[numCPU];

for (int j=0;j<numCPU;j++)
{
Th[j]=CreateEvent(NULL, FALSE, FALSE, NULL);
_beginthreadex(NULL, 0, &myFun, (void*)a[j], 0, NULL);
}

WaitForMultipleObjects(numCPU, Th, TRUE, INFINITE);

        ......

printf("done!!! /n");
printf("%e", value);

delete [] Th;

return 0;
       
}
 

[Aritaborian]

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

Сообщите пожалуйста, теперь программа работоспособна?

Тупее вопроса я не слышал. Ну скомпилируйте, ну запустите. Работает? Вот и ответ.

[Andrey_Kireew]

Aritaborian в сообщении #1432984 писал(а):

Тупее вопроса я не слышал

большое спасибо за содержательный ответ, и вам не хворать

[mihaild]

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

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

на данный момент у меня VC2010

Это древность, неужели нет возможности найти что-то посвежее? clang есть под windows, и у MS вроде есть бесплатные варианты.

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

HANDLE *Th=new HANDLE*[numCPU];

А это вообще компилируется? Слева HANDLE*, справа HANDLE**.

Aritaborian в сообщении #1432984 писал(а):

Ну скомпилируйте, ну запустите

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

[Aritaborian]

Aritaborian в сообщении #1432984 писал(а):

Работает?

Так оно работает или нет? И работает ли именно многопоточно? И как вы определяете функционирование многопоточности.

[Andrey_Kireew]

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

то древность, неужели нет возможности найти что-то посвежее?

наверное можно, но для моих приложений и этого вполне достаточно, к тому же - уже привык ...

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

Andrey_Kireew в сообщении #1432976

писал(а):
HANDLE *Th=new HANDLE*[numCPU];
А это вообще компилируется? Слева HANDLE*, справа HANDLE**.

это ошибка, разумеется, правильно так

HANDLE *Th=new HANDLE[numCPU]; 

[Dmitriy40]

Aritaborian в сообщении #1432987 писал(а):

Aritaborian в сообщении #1432984 писал(а):

Работает?

Так оно работает или нет? И работает ли именно многопоточно? И как вы определяете функционирование многопоточности.

В диспетчере задач винды есть колонка (на странице процессов) "Счётчик потоков" - в ней и будет видно запустились ли вторичные потоки. Например. Или по времени прогона.

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

Ещё мелкий совет: в поток неплохо бы добавить опрос требования завершения потока со стороны ОС (и соответственно при его получении и корректно завершиться). Запускать потоки без общения с ОС - плохой стиль. Как сделать - есть практически в любом описании многопоточных программ.