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

[Andrey_Kireew]

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

это просто подать в потоки N одинаковых указателей на одно и то же место массива

да, именно так

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

Пока какие-то чудеса, не может память стека и кучи работать с разной скоростью

Вернее сказать, с динамическими массивами иногда бывают какие то "глюки" и время выполнения сильно увеличивается, порой в 2 раза, а порой и больше. Иногда же - всё и сними работает нормально. С простыми массивами - всё надёжно и стабильно.
Да, какая то мистика. Я весь инет облазил - ничего не нашел. Но, тем не менее - как только поменял массивы - ни одного глюка до сих пор не было.

Пробовал на 1, 2, 3 и 4 ядрах. На 1-м ядре получается 320 секунд, т.е. 4 ядра не дают строго 4-х кратного ускорения, но очень близко к этому.

[Mihaylo]

for (ii=0; ii<L; ii++) M[ii]=new double[(ii+2)*(ii+1)/2];

Звездочка перед M должна быть?

[mihaild]

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

да, именно так

В смысле читают все потоки одни и те же данные из одного и того же места, пишут в разные (но соответственно тоже одно и то же значение), а вспомогательные переменные выделяют по месту?
Andrey_Kireew, какого порядка $L$?
Попробуйте вместо двумерных массивов использовать одномерные - эффект сохраняется?

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

Пока какие-то чудеса, не может память стека и кучи работать с разной скоростью

Но они по-разному расположены могут быть, что может быть важно.

[Andrey_Kireew]

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

В смысле читают все потоки одни и те же данные из одного и того же места, пишут в разные (но соответственно тоже одно и то же значение)

да, но запись я вообще убирал - это ни на что не влияет абсолютно

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

какого порядка $L$?

маленькое, не больше 10, в этом примере L=4

Опять вернул динамические массивы: 2 потока отработали нормально, за 95 сек, но третий за 140 сек, а четвёртый вообще за 160. Никаких других изменений больше не было, только тип массива.
Думал - может с адресацией проблема, проверил

 sizeoff(double*)=8;

и в потоках и в основной программе. Так, что с этим всё в порядке.

-- 16.01.2020, 17:06 --

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

Попробуйте вместо двумерных массивов использовать одномерные - эффект сохраняется?

что Вы имеете в виду?
Сейчас у меня действительно, в одном месте, выделяется массив указателей, а потом, под каждый из них выделяется массив double. Если это понимается под двухмерным массивом (как создать двухмерный динамический массив по другому - я не знаю), то пробовал и так:
выделяю один большой кусок памяти, а потом определяю положения всех указателей. Так получается почти то же самое, но все данные следуют друг за другом.
Запустил первый раз - всё отлично. Запустил второй - в одном потоке время выполнения 120 сек, т.е. на 30 сек больше чем нужно. Запустил третий раз - уже в 2-х потоках аномально большое время выполнение. И пошло - поехало.
В общем от этого толку нету. С динамическими массивами, хоть двухмерными, хоть одномерными, почему то, в некоторых потоках наблюдается аномально большое время выполнения. Причём от случая к случаю, никакой системы нет.

[Dmitriy40]

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

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

это просто подать в потоки N одинаковых указателей на одно и то же место массива

да, именно так

И это неправильно! Надо было в 4 разных места продублировать одинаковую информацию и уже тогда запускать 4 потока, чтобы они читали из 4-х разных мест каждый своё, но это вот "своё" у них было бы одинаковым.
В принципе в этом и может быть затык, в трафике памяти или кэша L3. А чтение из одного физического места производится одинарно, а не N раз.

mihaild
Правда я тогда не понимаю опыта с 180КБ данных, это же в L2 должно было помещаться и глюк исчезать ...
Andrey_Kireew
Впрочем я уже давно вообще не понимаю что в каких условиях тестируется, тестов много, каждый раз что-то меняется, но нет уверенности что описываются все изменения, а не лишь их часть.

-- 16.01.2020, 18:24 --

mihaild
Я правильно помню что new выделяет выравненную память и проверять кратность адреса начала массива четырём/восьми нет смысла?
Я бы предположил что не хватает ассоциативности кэшей и идут запросы в память (или L3), как это проверить без кода не представляю, да и опыт с 180КБ данных этому наверняка противоречит. Не представляю почему ещё может отличаться скорость работы памяти по разным адресам.

[Andrey_Kireew]

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

И это неправильно! Надо было в 4 разных места

да какая разница, данных во внутренних буферных массивах мало, намного меньше 180 кБ,
чтение из внешнего массива, который большой, занимает не более 10% от общего времени, да оно плавает, но главная причина совсем не в этом а в маленьких буферных массивах, которые выделяются с помощью new - до этого я дошел путём последовательного исключения участков кода.

К стати, недавно состоялся ещё один эксперимент, в котором я от отчаяния попытался выделить память на стёке с помощью _malloca(). Работать всё стало нормально и стабильно

[mihaild]

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

Я правильно помню что new выделяет выравненную память и проверять кратность адреса начала массива четырём/восьми нет смысла?

По стандарту - должен. Что он реально делает в древней студии - никому не ведомо.

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

маленькое, не больше 10, в этом примере L=4

Значит данные из разных потоков вполне могут попадать в одну кеш линию. Вы получается создаваемые массивы никак не используете (раз запись убрали; а читать из них нельзя, пока что-то не запишете).
Попробуйте заранее выделить память каждому потоку (и передать соответствующие указатели). Причем двумя способами: 1) выделить сначала всё что нужно одному потоку, потом другому, и т.д.; 2) выделять вперемешку - сначала M[0] для всех потоков, потом M[1] и т.д.

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

что Вы имеете в виду?

Ну собственно то что вы написали.

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

Правда я тогда не понимаю опыта с 180КБ данных, это же в L2 должно было помещаться и глюк исчезать

Если я правильно помню, L2 может быть разным для разных ядер. Что, с учетом того что шедулер в windows (вроде) любит перекидывать потоки между ядрами сильно затрудняет рассуждения о нем.

[realeugene]

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

и уже тогда запускать 4 потока, чтобы они читали из 4-х разных мест каждый своё

Не нужно. Главное, чтобы процессоры не писали в разделяемые линии кэша.

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

Я правильно помню что new выделяет выравненную память и проверять кратность адреса начала массива четырём/восьми нет смысла?

Выравненная, но не по границе кэш-линии. В начале блока присутствует заголовок для кучи. Начиная с С++17 в new можно передавать требуемое выравнивание.

[Dmitriy40]

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

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

Правда я тогда не понимаю опыта с 180КБ данных, это же в L2 должно было помещаться и глюк исчезать

Если я правильно помню, L2 может быть разным для разных ядер. Что, с учетом того что шедулер в windows (вроде) любит перекидывать потоки между ядрами сильно затрудняет рассуждения о нем.

Простите, здесь с Вами не соглашусь: шедулер не должен перекидывать потоки чаще тика ОС, примем его с запасом в 1мс, перекидывание потока на другое ядро в почти самом худшем случае (перезагрузку всяких TLB проигнорирую) приводит лишь к сбросу всего L2 в L3 (в память оно уйти скорее всего не успеет) и загрузку их же обратно в L2 другого ядра. Это происходит хоть и не потоком, а лишь по запросам, но не более одного раза для каждой кэшлинии. Латентность L3 составляет 16 тактов, даже если и запись и чтение кэшлинии будет по 16 тактов это в сумме 32 такта на 64 байта, или полтакта на байт, или 130 тысяч тактов на весь L2. Вариант что в L3 нет места и оно будет освобождаться записями в память тоже проигнорирую (там должны быть буфера записи, освобождающие кэшлинию за такт). 130 тысяч тактов на частоте 3ГГц это всего лишь 43мкс или менее 5% от тика переключения задач. Т.е. даже в почти самом худшем случае перекидывание потока между ядрами не замедлит более чем на 5%. Реально, при тике 18мс и отсутствии латентности L3 по чтению запрошенной кэшлинии из другого ядра, это жалкие доли процента. Замедления вдвое это не объясняет никак.

ALL:
Не всматривался, но если там товарищ выделяет память через new для единичных указателей или переменных — это Я как бы предполагал что память всегда выделяется под целиком массив. Но даже если под переменные, но readonly — это снова влиять не должно, без записей обращения по чтению не тормозят (пока не превышается ассоциативность кэшей и/или TLB).

mihaild, realeugene, спасибо про выравнивание, уверен оно всё же правильное (как минимум на размер элемента).

-- 16.01.2020, 19:13 --

realeugene в сообщении #1435482 писал(а):

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

и уже тогда запускать 4 потока, чтобы они читали из 4-х разных мест каждый своё

Не нужно. Главное, чтобы процессоры не писали в разделяемые линии кэша.

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

[realeugene]

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

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

Код, видимо, утонул где-то в глубинах обсуждения, и я понятия не имею, что за задача решается, но нет, если из памяти производится только чтение, то лучше, когда в общем кэше сидит одна разделяемая копия на несколько ядер. Одна копия занимает меньше места, чем N копий.

[Andrey_Kireew]

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

Вы получается создаваемые массивы никак не используете (раз запись убрали; а читать из них нельзя, пока что-то не запишете).

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

Не использую запись - имелось в виду запись результатов во внешнюю структуру.

-- 16.01.2020, 21:06 --

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

Попробуйте заранее выделить память каждому потоку (и передать соответствующие указатели)

Я это раньше уже пробовал, где то об этом написано, но теперь наверное не найти. В общем, получилось - что так ещё хуже, чем выделять внутри функции. Всё работает ещё нестабильнее и медленнее. Хотя, как бы и память таже, и массивы те же, но увы - факт есть факт.

Единственное, что пока удалось выяснить - это при выделении памяти на стёке, всё пока работает нормально. Хотя не факт, что эти глюки не появятся и в этом случае. В принципе _malloca() позволяет решить эту проблему, но всё равно, очень интересно было бы узнать причину такого необычного поведения.

-- 16.01.2020, 21:08 --

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

Если я правильно помню, L2 может быть разным для разных ядер. Что, с учетом того что шедулер в windows (вроде) любит перекидывать потоки

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

[Dmitriy40]

realeugene в сообщении #1435486 писал(а):

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

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

Код, видимо, утонул где-то в глубинах обсуждения, и я понятия не имею, что за задача решается, но нет, если из памяти производится только чтение, то лучше, когда в общем кэше сидит одна разделяемая копия на несколько ядер. Одна копия занимает меньше места, чем N копий.

Это лучше с точки зрения быстродействия, но с точки зрения поиска причины глюков в "боевой" программе (где копии разные) лучше наоборот, во всяком случае проверить так ли это.
А полного кода и не было, были огрызки, в основном внешние обёртки запуска и ожидания потоков и выделения памяти в потоках. Остальное на словах, часто малопонятных.

[Andrey_Kireew]

Вот, что мне удалось найти в сети

Цитата:

У каждого потока свой стек, размер которого задается при запуске и причем размер с запасом

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

-- 16.01.2020, 22:01 --

Вот ещё, что пишут

Цитата:

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

уж не знаю, правда это, или нет

[Mihaylo]

Обе эти штуки работают быстро.

[Dmitriy40]

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