Сколько потоков нужно, чтобы сделать их плохим выбором?

Question

Я должен написать небольшую программу на C ++, используя boost :: thread.

Проблема в том, чтобы обработать большое (возможно, тысячи или десятки тысяч. Возможны также сотни и миллионы) большое количество (возможно) больших файлов. Каждый файл независим от другого, и все они находятся в одном каталоге. Я думаю об использовании многопоточного подхода, но вопрос в том, сколько потоков я должен использовать? Я имею в виду, какой порядок? 10, 500, 12400?

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

Я думал о

for(each file f in directory){

    if (N < max_threads)//N is a static variable controlling amount of threads
         thread_process(f)
    else
       sleep()
}

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

Answer 1

Согласно закону Амдала, который обсуждал Херб Саттер в его статье :

Некоторая часть обработки программы полностью "O (N)" распараллеливается (назовите эту часть p), и только эта часть может масштабироваться непосредственно на машинах, имеющих все больше и больше процессорных ядер. Остальная часть работы программы является последовательной (ыми) «O (1)». [1,2] Предполагая идеальное использование всех доступных ядер и отсутствие затрат на распараллеливание, Закон Амдала гласит, что наилучшее возможное ускорение этой программной нагрузки на машине с N ядрами дает

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

---

Полный список статей, связанных с параллелизмом, Хербом Саттером можно найти здесь .

Answer 2

Я не слишком уверен насчет HP / UX, но в мире Windows мы используем пулы потоков для решения такого рода проблем. Раймонд Чен писал об этом некоторое время назад, на самом деле ...

Сложнее всего то, что я не ожидал бы, что что-либо будет хорошо масштабироваться при нагрузке на процессор, если число потоков более чем в 2 раза превышает количество ядер процессора в системе. Для нагрузок, связанных с вводом / выводом, вы можете получить больше, в зависимости от скорости вашей дисковой подсистемы, но как только вы достигнете примерно 100 или около того, я серьезно подумаю об изменении модели ...

Answer 3

Вы сказали, что все файлы находятся в одном каталоге. Значит ли это, что все они находятся на одном физическом диске?

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

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

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

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

Answer 4

Чтобы уточнить это действительно зависит от

IO boundedness of the problem
    how big are the files
    how contiguous are the files
    in what order must they be processed
    can you determine the disk placement
how much concurrency you can get in the "global structure insert"
    can you "silo" the data structure with a consolidation wrapper
the actual CPU cost of the "global structure insert" 

Например, если ваши файлы находятся на 3-терабайтном массиве флеш-памяти, тогда решение будет другим, чем если бы они находились на одном диске (где, если «вставка глобальной структуры» занимает меньше времени, чем проблема чтения, I / O ограничен, и вы также можете иметь двухступенчатую трубу с 2-мя потоками - стадия чтения, питающая стадию вставки.)

Но в обоих случаях архитектура, вероятно, будет представлять собой вертикальный конвейер из 2 этапов. n читает потоки и m пишет потоки, причем n и m определяются «естественным параллелизмом» для этапа.

Создание потока для файла, вероятно, приведет к перегрузке диска. Так же, как вы приспосабливаете количество потоков процесса, связанного с процессором, к естественно достижимому параллелизму процессора (и выходу за пределы, создающему переключение контекста при перегрузке AKA), то же самое относится и к стороне ввода / вывода - в некотором смысле вы можете думать о перебивание диска как «переключение контекста на диске».

Answer 5

Если рабочая нагрузка приближается к I / O , ограниченному как это звучит, то вы, вероятно, получите максимальную пропускную способность с таким количеством потоков, сколько у вас есть шпинделей. Если у вас более одного диска и все данные находятся на одном RAID 0, вы, вероятно, не хотите больше одного потока. Если более чем один поток пытается получить доступ к непоследовательным частям диска, ОС должна прекратить чтение одного файла, даже если он может находиться прямо под заголовком, и перейти к другой части диска для обслуживания другого потока, чтобы это не голодает. При наличии только одного потока, диск не должен останавливать чтение, чтобы двигать головой.

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

Как подсказывают другие постеры, сначала профиль!

Answer 6

Ответ зависит в некоторой степени от того, насколько интенсивна загрузка процессора для каждого файла.

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

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

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

Answer 7

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

Answer 8

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

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

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

Второе случается. Я видел один фрагмент кода, который в итоге создал более 30000 потоков. Он оказался быстрее, ограничив его до 1000.

Другой способ взглянуть на это: насколько быстро достаточно быстро? Точка, в которой ввод / вывод становится узким местом, - это одно, но вы можете достичь точки до того момента, когда она будет «достаточно быстрой».

Answer 9

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

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

Answer 10

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