Что может замедлить работу программы при использовании большего количества потоков?

https://stackoverflow.com/questions/612860

03-07-2019
|

Вопрос

Этот вопрос касается той же программы, которую я ранее задававшийся вопрос о.Подводя итог, у меня есть программа со структурой цикла, подобной этой:

for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1;

bin_index является полностью детерминированной функцией своих аргументов, которая для целей этого вопроса не использует и не изменяет какое-либо общее состояние - другими словами, она явно реентерабельна.

Сначала я написал эту программу для использования одного потока.Затем я преобразовал его для использования нескольких потоков, так что поток n выполняет все итерации внешнего цикла, где i1 % nthreads == n.Таким образом, функция, которая выполняется в каждом потоке, выглядит следующим образом

for (int i1 = n; i1 < N; i1 += nthreads)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        thread_local_histogram[bin_index(i1, i2, i3, i4)] += 1;

и все эти thread_local_histograms суммируются в основном потоке в конце.

Вот странная вещь:когда я запускаю программу всего с 1 потоком для некоторого определенного размера вычисления, это занимает около 6 секунд.Когда я запускаю его с помощью 2 или 3 потоков, выполняя точно такие же вычисления, это занимает около 9 секунд.Почему это?Я бы ожидал, что использование 2 потоков будет быстрее, чем 1 поток, поскольку у меня двухъядерный процессор.Программа не использует никаких мьютексов или других примитивов синхронизации, поэтому два потока должны иметь возможность выполняться параллельно.

Для справки:типичный результат от time (это в Linux) для одного потока:

real    0m5.968s
user    0m5.856s
sys     0m0.064s

и две нити:

real    0m9.128s
user    0m10.129s
sys     0m6.576s

Код находится по адресу http://static.ellipsix.net/ext-tmp/distintegral.ccs

P.S.Я знаю, что существуют библиотеки, предназначенные именно для такого рода задач, которые, вероятно, могли бы иметь лучшую производительность, но именно об этом был мой последний вопрос, поэтому мне не нужно снова слышать эти предложения.(Кроме того, я хотел использовать pthreads в качестве учебного процесса.)

Решение

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

Видите ли, random хранит глобальную переменную в памяти, которая хранит последнее случайное значение, вычисленное там.Каждый раз, когда вы вызываете random() (а вы вызываете его дважды в рамках одной функции), он считывает значение этой глобальной переменной, выполняет вычисление (которое выполняется не так быстро;random() сама по себе является медленной функцией) и записывает результат обратно туда, прежде чем возвращать его.Эта глобальная переменная предназначена не для каждого потока, она является общей для всех потоков.Итак, то, что я написал относительно отравления кэша, применимо здесь постоянно (даже если вы избежали этого для массива, разделив массивы на поток;это было очень умно с вашей стороны!).Это значение постоянно становится недействительным в кэше любого ядра и должно быть повторно извлечено из памяти.Однако, если у вас есть только один поток, ничего подобного не происходит, эта переменная никогда не покидает кэш после того, как она была первоначально прочитана, поскольку к ней постоянно обращаются снова, и снова, и снова.

Кроме того, что еще хуже, у glibc есть потокобезопасная версия random() - я только что убедился в этом, просмотрев исходный код.Хотя на практике это кажется хорошей идеей, это означает, что каждый вызов random() приведет к блокировке мьютекса, доступу к памяти и разблокировке мьютекса.Таким образом, два потока, вызывающих random в один и тот же момент, приведут к блокировке одного потока на пару циклов процессора.Однако это зависит от конкретной реализации, поскольку AFAIK не требуется, чтобы random() был потокобезопасным.Большинство стандартных функций lib не обязаны быть потокобезопасными, поскольку стандарт C вообще не знает о концепции потоков.Когда они не вызывают его в тот же момент, мьютекс не будет иметь никакого влияния на скорость (поскольку даже однопоточное приложение должно блокировать / разблокировать мьютекс), но тогда снова произойдет отравление кэша.

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

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

Если у вас работает решение только для Linux, вы можете использовать random_r ( случайный ).Это позволяет вам передавать состояние при каждом вызове.Просто используйте уникальный объект состояния для каждого потока.Однако эта функция является расширением glibc и, скорее всего, не поддерживается другими платформами (ни в стандартах C, ни в стандартах POSIX AFAIK - эта функция не существует, например, в Mac OS X, она может отсутствовать ни в Solaris, ни во FreeBSD).

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

static uint32_t getRandom(uint32_t * m_z, uint32_t * m_w)
{
    *m_z = 36969 * (*m_z & 65535) + (*m_z >> 16);
    *m_w = 18000 * (*m_w & 65535) + (*m_w >> 16);
    return (*m_z << 16) + *m_w;
}

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

uint32_t m_z = random();
uint32_t m_w = random();
uint32_t nextRandom;

for (...) {
    nextRandom = getRandom(&m_z, &m_w);
    // ...
}

Таким образом, каждому потоку нужно всего лишь дважды вызвать random(), а затем использовать ваш собственный генератор.Кстати, если вам нужны двойные рандомы (которые находятся между 0 и 1), приведенную выше функцию можно легко обернуть для этого:

static double getRandomDouble(uint32_t * m_z, uint32_t * m_w)
{
    // The magic number below is 1/(2^32 + 2).
    // The result is strictly between 0 and 1.
    return (getRandom(m_z, m_w) + 1) * 2.328306435454494e-10;
}

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

Другие советы

Чтобы избежать дальнейших комментариев по этому поводу:Когда я писал свой ответ, спрашивающий еще не разместил ссылку на свой источник, поэтому я не смог адаптировать свой ответ к его конкретным вопросам.Я только отвечал на общий вопрос, что "может" вызвать такую проблему, я никогда не говорил, что это обязательно будет применимо к его случаю.Когда он опубликовал ссылку на свой источник, я написал другой ответ, который в точности посвящен только его проблеме (которая вызвана использованием функции random (), как я объяснил в моем другом ответе).Однако, поскольку вопрос этого поста по-прежнему звучит так: "Что может замедлить работу программы при использовании большего количества потоков?", а не "Что замедляет работу моего очень специфического приложения?", я также не вижу необходимости менять свой довольно общий ответ (общий вопрос -> общий ответ, конкретный вопрос -> конкретный ответ).

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

2) Предотвращение разрывов памяти
Память считывается быстрее всего, если читать последовательно пакетами, точно так же, как при чтении файлов с HD.Обращение к определенной точке памяти на самом деле происходит ужасно медленно (точно так же, как "время поиска" на HD), даже если на вашем КОМПЬЮТЕРЕ лучшая память на рынке.Однако, как только этот момент был устранен, последовательное чтение происходит быстро.Первая адресация выполняется путем отправки индекса строки и индекса столбца и всегда имеет время ожидания между ними, прежде чем можно будет получить доступ к первым данным.Как только эти данные появятся, процессор начнет работать с перебоями.Пока данные все еще находятся в пути, они уже отправляют запрос на следующий пакет.До тех пор, пока он поддерживает пакет (всегда отправляя запросы "Пожалуйста, следующую строку"), оперативная память будет продолжать перекачивать данные так быстро, как только может (и это на самом деле довольно быстро!).Пакетирование работает только в том случае, если данные считываются последовательно и только в том случае, если адреса памяти растут вверх (AFAIK, вы не можете выполнять пакетирование с высоких адресов на низкие).Если теперь два потока выполняются одновременно и оба продолжают чтение / запись в память, однако оба с совершенно разных адресов памяти, каждый раз, когда потоку 2 требуется прочитать / записать данные, он должен прерывать возможный пакет потока 1 и наоборот.Эта проблема усугубляется, если у вас еще больше потоков, и эта проблема также является проблемой в системе, которая имеет только один одноядерный процессор.

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

Вы видите подпрыгивание строки кэша.Я действительно удивлен, что вы не получаете неверных результатов из-за условий гонки на сегментах гистограммы.

Одна из возможностей заключается в том, что время, затраченное на создание потоков, превышает экономию, полученную при использовании потоков.Я бы подумал, что N не очень велико, если затраченное время составляет всего 6 секунд для операции O (n ^ 4).

Также нет гарантии, что несколько потоков будут выполняться на разных ядрах или процессорах.Я не уверен, какова привязка потока по умолчанию к Linux - it мочь быть, что оба потока выполняются на одном ядре, что свело бы на нет преимущества такого ресурсоемкого фрагмента кода, как этот.

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

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

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

Навскидку с моей головы:

Контекстные переключатели
Конкуренция за ресурсы
Конфликт между процессорами (если они не разделяются на несколько процессоров).
Перетряска кэша

Дэвид,

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow