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

[Andrey_Kireew]

Есть ли у Вас Dmitriy40
какие нибудь идеи по поводу сложившейся ситуации?

[SergeCpp]

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

общее количество задач должно быть не меньше чем, ну скажем, 16*количество_ядер

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

не нужно 16N потоков

Из "абсолютный размер задачи должен быть в разумных пределах, скажем, не больше 100 мс" видно, что задача здесь (в статье) -- не поток.

[Dmitriy40]

Andrey_Kireew
Есть:

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

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

[Andrey_Kireew]

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

Потом подумать где в функции может циклиться не заходя в метку NEXT

этого нет, вернее есть, но там циклы с заданным числом повторений, число мат. операций выполняется всегда одно и то же

 for()

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

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

взаимодействие потоков только через read-only данные, запись я вообще временно закомментировал, но это ничего не дало

[Dmitriy40]

Andrey_Kireew
Запускайте программу в трёхпоточном режиме, чтобы одно ядро всегда было свободным (на нужды ОС или других фоновых процессов).
Проверьте что все эти непоказанные циклы for не зависят от входных данных в массивах, кроме как от переменной L (кажется она задаёт длину массивов). Можно даже инициализировать входные массивы откровенным бредом (но неизменным от запуска к запуску!) и проверить что будет со временем выполнения.
Насыпьте больше разнообразных счётчиков в код, хоть прямо в каждый цикл и if (во все ветки). Сравните что показания счётчиков постоянны при значительном изменении времени (десяток процентов времени игнорировать). Сравните что показания счётчиков (видимо в сумме) не зависят от коэффициента разбития задачи. Найдёте скачущий счётчик — выдумывайте и проверяйте причины.
Раз записи не влияют - комментируйте куски вычислений с конца и ищите в какой момент время перестанет скакать. Надеюсь "пустой" код, без ваших вычислений, работает правильно (стабильно по суммарному времени от запуска к запуску и вне зависимости от количества потоков и разбиения задачи).
Оцените общий объём читаемых данных из памяти всеми потоками (например в однопоточном режиме), сравните со скоростью памяти (если не знаете точно можно принять 10ГБайт/с). Если память окажется медленнее, то проверьте что чтения выполняются предсказуемо (например последовательно, или с постоянным шагом) хотя бы для большинства обращений. И что шаг при этом не кратен 32768 (длина одной страницы кэша L2, чтобы хватало его ассоциативности). Для произвольных чтений считайте каждое из них за 64 байта независимо от фактической длины переменной. Это всё чтобы убедиться что тормоза не из-за памяти и кэша.
Кажется уже предлагал запускать потоки строго последовательно, дожидаясь завершения предыдущего, перенеся WaitForSingleObject внутрь цикла for запуска потоков, не помню результата (есть ли скачки времени).
А, да, обязательно проверьте что нет неинициализированных переменных или массивов! Что все они обязательно чем-то пишутся перед первым чтением. Это должен сообщать компилятор, вам говорили исправить все (хотя бы такие) ошибки и предупреждения. И не надейтесь на обнуление при объявлении. Это легко даст самое удивительное поведение программы.

Это же всё "общие" слова, но что ещё можно советовать "за глаза" то ...
И сразу у всех прошу прощения что предлагаемые методы отладки столь низкоуровневые, не привык к хорошему.

[mihaild]

(Оффтоп)

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

Что все они обязательно чем-то пишутся перед первым чтением. Это должен сообщать компилятор

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

[venco]

А не может проблема быть в понижении частоты процессора из-за перегрева? Не знаю, правда, как это попроще проверить.

[Dmitriy40]

venco
О, а это похоже и ответ на мой вопрос чем QueryThreadCycleTime лучше GetThreadTimes — привяжется к тактам процессора независимо от скачков его частоты. Правда что будет при троттлинге (если он реально реализован в Core i7) непонятно.
Проверить же можно либо по снижению тактовой частоты в диспетчере задач (для Win8 и новее) или отдельными утилитами (например HWmonitor), многие из которых и троттлинг покажут.
Ну или просто по температуре ядер.

[Andrey_Kireew]

Для проверки поставил счётчики времени GetTickCount() на все участки чтения-записи данных.
Вот что получилось для 2-х запусков:

T_User=111883 ms
N_iter= 2723888 тыс.
T_rc= 14 sec.
T_rr= 7 sec.

T_User=114426 ms
N_iter= 2642387 тыс.
T_rc= 15 sec.
T_rr= 8 sec.

T_User=111727 ms
N_iter= 2660488 тыс.
T_rc= 10 тыс.
T_rr= 7 тыс.

T_User=118747 ms
N_iter= 2635530 тыс.
T_rc= 14 sec.
T_rr= 7 sec.

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

T_User=110963 ms
N_iter= 2723888 тыс.
T_rc= 13 тыс.
T_rr= 8 тыс.

T_User=208526 ms
N_iter= 2642387 тыс.
T_rc= 23 тыс.
T_rr= 9 тыс.

T_User=198183 ms
N_iter= 2660488 тыс.
T_rc= 19 тыс.
T_rr= 12 тыс.

T_User=173426 ms
N_iter= 2635530 тыс.
T_rc= 18 тыс.
T_rr= 13 тыс.

Время чтения в разных потоках может отличиться очень сильно. Когда такое происходит - сильно различается и время выполнения потоков. Если время чтения примерно одинаковое - то и время выполнение потоков тоже почти одинаковое.
Что касается времени записи, то оно, видимо, крайне мало и GetTickCount() всегда выдаёт 0.

Как Вы думаете Dmitriy40 это ли причина моих злоключений? И как можно с этим бороться?

[Dmitriy40]

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

Разумеется причина именно в этом, в плавающем времени чтений, если вы его правильно измерили. Но вообще то сравнивать надо скорее не время чтений в потоках, а их сумму.
И мне плохо понятен Ваш вывод если я вижу в первом запуске при одинаковом времени 111с заметно разное время чтений 14+7 и 10+7 в разных потоках.
Что делать я уже писал выше.
Плюс можно уменьшить размер всех массивов данных до 6МБайт (размер L3) суммарно — а лучше даже до 250КБ (размер L2) на поток включая и глобальные — и проверить что время чтений стало стабильным.

PS. GetTickCount() слишком грубая/неточная (погрешность 10-16 мс), измерять ею что-то менее сотен мс непрактично. Пользуйтесь командой процессора RDTSC (если в вашем С++ её нету, добавьте сами руками из скачанного .h файла).

[Andrey_Kireew]

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

Что делать я уже писал выше

Вы имеете в виду увеличить количество потоков и включить HyperTraid?

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

-- 08.01.2020, 15:21 --

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

И мне плохо понятен Ваш вывод если я вижу в первом запуске при одинаковом времени 111с заметно разное время чтений 14+7 и 10+7 в разных потоках

просто наверное, время 10 уже не является лимитирующим. Оно может быть уменьшено до 8 и 4, но время выполнения программы от этого уже не уменьшается. Я заметил, время выполнение потока сильно увеличивается, когда время чтения больше 10. И влияет на всё, по большей части T_rc, так как время чтения у него всегда больше.

[Dmitriy40]

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

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

Что делать я уже писал выше

Вы имеете в виду увеличить количество потоков и включить HyperTraid?

Нет, я имею в виду попробовать все те идеи что я перечислил выше: post1433946.html#p1433946 , post1433906.html#p1433906 , post1433891.html#p1433891

[Andrey_Kireew]

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

Нет, я имею в виду попробовать все те идеи что я перечислил выше

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

Размер входного массива я уменьшил до 180 КБ. Это не помогает, время чтения всё равно различается очень сильно.
Правильно ли я понимаю, что никаких ошибок в коде нет, и так как сейчас - это нормальное явление и толком сделать ничего нельзя?

[Dmitriy40]

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

Правильно ли я понимаю, что никаких ошибок в коде нет,

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

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

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

Я говорил о чтении разных данных в разных потоках.
К тому же в процессорах есть команды упреждающего чтения, которые запускают пересылку данных в кэш заранее, до того как они понадобятся программе. Как ими воспользоваться в С++ (кроме как фиктивного чтения) не знаю.
И в любом случае это не должно влиять при 180К данных. Значит причина не в этом.

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

Какой смысл их развивать, если причина найдена я не совсем понимаю.

Ну так исправьте её и всё. Я тут ничего посоветовать не могу так как не вижу найденной Вами причины.

[Andrey_Kireew]

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

И даже посмотреть на него может оказаться недостаточно

что на него смотреть, данные там читаются в 2-х местах (в буфер) просто в цикле, типа такого

for (i=0; i<R; i++) buf[i]=M[ind[i]]; 

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