Подтвердить что ты не робот

Обработка многопоточных изображений в С++

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

Подобные преобразования изображений очень напряжены в CPU. Я хотел бы использовать многопоточность, чтобы ускорить работу. Как мне это сделать? Я думал создать один поток на строку пикселей.

У меня есть несколько требований:

  • Исполняемый размер должен быть сведен к минимуму. Другими словами, я не могу использовать массивные библиотеки. Какая самая легкая портативная библиотека для потоковой передачи для C/С++?
  • Исполняемый размер должен быть сведен к минимуму. Я думал о функции forEachRow (fp *), которая запускает поток для каждой строки или даже forEachPixel (fp *), где fp работает на одном пикселе в своем потоке. Что лучше?
    • Должен ли я использовать обычные функции или функторы или функциональные функции или некоторые лямбда-функции или... что-то еще?
    • В некоторых операциях используются оптимизации, требующие обработки информации из предыдущего обработанного пикселя. Это делает EachRow благоприятным. Будет ли использовать forEachPixel лучше даже с учетом этого?
  • Нужно ли мне блокировать мои только для чтения и только для записи массивы?
    • Вход только считывается, но для многих операций требуется ввод из более чем одного пикселя в массиве.
    • Вывод написан только один раз для каждого пикселя.
  • Скорость также важна (конечно), но оптимизация размера исполняемого файла имеет приоритет.

Спасибо.

Дополнительная информация по этой теме для любопытных: Библиотеки параллелизма С++: OpenMP vs. Thread Building Blocks

4b9b3361

ОТВЕТЫ

Ответ 1

Если ваш компилятор поддерживает OpenMP (я знаю VС++ 8.0 и 9.0, как и gcc), это может сделать такие вещи намного проще.

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

OpenMP позволяет легко адаптировать количество потоков, созданных для количества доступных ЦП. Использование его (особенно в случаях обработки данных) часто включает простое добавление нескольких #pragma omp в существующий код и позволяющий компилятору обрабатывать потоки и синхронизацию.

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

Для OpenMP нет необходимости делать что-либо особенное для объектов-функторов/функций. Напишите его в зависимости от того, что вам больше всего подходит. Здесь пример обработки изображений из Intel (преобразует rgb в оттенки серого):

#pragma omp parallel for
for (i=0; i < numPixels; i++)
{
   pGrayScaleBitmap[i] = (unsigned BYTE)
       (pRGBBitmap[i].red * 0.299 +
        pRGBBitmap[i].green * 0.587 +
        pRGBBitmap[i].blue * 0.114);
}

Это автоматически разбивается на столько потоков, сколько у вас есть, и назначает раздел массива каждому потоку.

Ответ 2

Не приступайте к потоку легко! Условия гонки могут стать основной болью в заднице, чтобы понять. Особенно, если у вас нет большого опыта в потоках! (Вы были предупреждены: вот драконы! Большие волосатые не детерминированные невозможные-надежно-размножаемые драконы!)

Знаете ли вы, что такое тупик? Как насчет Livelock?

Это сказало...

Как уже предлагали ckarmann и другие: Использовать модель рабочей очереди. Один поток на ядро ​​процессора. Разбейте работу на N кусков. Сделайте куски достаточно большими, как и многие ряды. По мере того, как каждый поток становится свободным, он выгружает следующий рабочий фрагмент из очереди.

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

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

Сама модель рабочей очереди достаточно мощная. Он позволяет вам распараллеливать такие вещи, как quick-sort, которые обычно не распараллеливаются по N нити/ядрам.

Больше потоков, чем ядер? Ты просто теряешь голову. У каждого потока есть накладные расходы. Даже при # threads = # ядрах вы никогда не достигнете идеального коэффициента ускорения Nx.

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

Библиотеки? Какая ваша платформа? В Unix/Linux/g++ я предлагаю pthreads и семафоры. (Pthreads также доступен под окнами с уровнем совместимости с Microsoft. Но, на самом деле, я действительно не верю в это. Cygwin может быть лучшим выбором там.)

В Unix/Linux man:

* pthread_create, pthread_detach.
* pthread_mutexattr_init, pthread_mutexattr_settype, pthread_mutex_init,
* pthread_mutexattr_destroy, pthread_mutex_destroy, pthread_mutex_lock,
* pthread_mutex_trylock, pthread_mutex_unlock, pthread_mutex_timedlock.
* sem_init, sem_destroy, sem_post, sem_wait, sem_trywait, sem_timedwait.

Некоторые люди, такие как переменные условия pthreads. Но я всегда предпочитал семафоры POSIX 1003.1b. Они справляются с ситуацией, когда вы хотите сигнализировать другой поток, прежде чем он начнет ждать несколько лучше. Или где несколько потоков сигнализируются несколько раз.

О, и сделай себе одолжение: обменивай свои нити/мьютекс/семафор pthread на пару классов С++. Это упростит многое!

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

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

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

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

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

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

Если вы хотите поделиться одной общей областью данных между потоками с помощью мьютексов, неэффективность столкновения/ожидания мьютекса будет накапливаться и разрушить вашу эффективность!

Посмотрите, чистые границы данных - суть хорошего многопоточного кода. Когда ваши границы не ясны, когда вы попадаете в неприятности.

Точно так же важно держать все на границе мьютексированным! И чтобы сохранить мьютексные области короткими!

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

По возможности используйте мьютексы ERROR-CHECKING или RECURSIVE. FAST-мьютексы просто задают проблемы с очень небольшим фактическим (измеренным) коэффициентом усиления скорости.

Если вы попадаете в тупик, запустите его в gdb, нажмите ctrl-c, посетите каждый поток и обратную трассировку. Вы можете найти проблему довольно быстро таким образом. (Livelock намного сложнее!)

Одно последнее предложение: Постройте его однопоточным, а затем начните оптимизацию. В одноядерной системе вы можете получить больше скорости от таких вещей, как foo [i ++] = bar == > * (foo ++) = bar, чем от потоковой передачи.

Добавление: Что я сказал о сохранении мьютексных областей короче вверху? Рассмотрим два потока: (учитывая глобальный общий объект mutex класса Mutex.)

/*ThreadA:*/ while(1){  mutex.lock();  printf("a\n");  usleep(100000); mutex.unlock(); }
/*ThreadB:*/ while(1){  mutex.lock();  printf("b\n");  usleep(100000); mutex.unlock(); }

Что произойдет?

В моей версии Linux один поток будет работать непрерывно, а другой будет голодать. Очень редко они меняются местами, когда происходит обмен контекстом между mutex.unlock() и mutex.lock().

Добавление: В вашем случае это вряд ли будет проблемой. Но с другими проблемами можно заранее не знать, как долго будет выполняться конкретный рабочий блок. Разрушение проблемы на 100 частей (вместо 4 частей) и использование рабочей очереди для разделения ее на 4 ядра сглаживает такие расхождения.

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

Ответ 3

Я бы порекомендовал boost::thread и boost::gil (generic image libray). Потому что есть довольно много шаблонов, я не уверен, будет ли размер кода по-прежнему приемлемым для вас. Но это часть повышения, так что, вероятно, стоит посмотреть.

Ответ 4

Как немного идеи левого поля...

Какие системы вы используете? Вы думали использовать GPU на своих ПК?

Nvidia имеют CUDA API для такого рода вещей

Ответ 5

Я не думаю, что вы хотите иметь один поток в строке. Там может быть много строк, и вы будете тратить много ресурсов памяти/ЦП, просто запуская/уничтожая потоки, и чтобы CPU переключался с одного на другой. Более того, если у вас есть P-процессоры с ядром C, у вас, вероятно, не будет много выигрыша с более чем потоками C * P.

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

Что касается библиотек, вы можете использовать boost:: thread, который довольно переносимый и не слишком тяжелый.

Ответ 6

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

Ответ 7

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

Ответ 8

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

Я также предлагаю Boost.GIL, который генерирует высокоэффективный код. Для простого многопоточного примера проверьте gil_threaded автор Victor Bogado. Сеть обработки изображений с использованием Dataflow.Signals и Boost.GIL также объясняет интересную модель потока данных.

Ответ 9

Одна строка нити на пиксель безумна, лучше всего вокруг n-1 до 2n потоков (для n cpu), и каждый цикл выбирает один узел работы (может быть одна строка или другой вид раздела)

на unix-подобном, используйте pthreads это простой и легкий.

Ответ 10

Может быть, написать свою собственную крошечную библиотеку, которая реализует несколько стандартных функций потоковой передачи, используя #ifdef для каждой платформы? Там действительно мало, и это уменьшит размер исполняемого файла больше, чем любая библиотека, которую вы могли бы использовать.

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

Ответ 11

Я думаю, что независимо от выбранной вами модели потоковой передачи (boost, pthread, native threads и т.д.). Я думаю, вы должны рассмотреть пул потоков, а не поток за строку. Нити в пуле потоков очень дешевы для "запуска", поскольку они уже созданы в отношении ОС, это просто вопрос, чтобы дать ему что-то делать.

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

Это самый простой способ IMHO для добавления потоков в задачу SIMD.

Ответ 12

Очень возможно, что узким местом является не ЦП, а пропускная способность памяти, поэтому многопоточность НЕ МОЖЕТ помочь. Постарайтесь минимизировать доступ к памяти и работать с ограниченными блоками памяти, чтобы можно было кэшировать больше данных. Некоторое время назад у меня была аналогичная проблема, и я решил оптимизировать свой код для использования инструкций SSE. Увеличение скорости было почти 4 раза за одну нить!

Ответ 13

Ваш компилятор не поддерживает OpenMP. Другой вариант заключается в использовании библиотечного подхода, доступны как Intel Threading Building Blocks, так и Microsoft Concurrency Runtime (VS 2010).

Существует также набор интерфейсов, называемых библиотекой параллельных шаблонов, которые поддерживаются обеими библиотеками, и в них есть шаблонный вызов parallel_for library. поэтому вместо:

#pragma omp parallel for 
for (i=0; i < numPixels; i++) 
{ ...}

вы пишете:

parallel_for(0,numPixels,1,ToGrayScale());

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

parallel_for(0,numPixels,1,[&](int i)
{  
   pGrayScaleBitmap[i] = (unsigned BYTE)  
       (pRGBBitmap[i].red * 0.299 +  
        pRGBBitmap[i].green * 0.587 +  
        pRGBBitmap[i].blue * 0.114);  
});

-Rick

Ответ 14

Я думаю, что карта/сокращение рамки будет идеальной возможностью для использования в этой ситуации. Вы можете использовать потоки Hadoop для использования вашего существующего приложения на С++.

Просто выполните карту и уменьшите задания.

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

Надеюсь, это полезно.

Ответ 15

Вы также можете использовать библиотеки, такие как IPP или Cassandra Vision API С++, который в основном намного оптимизирован, чем собственный код.

Ответ 16

Существует еще один вариант использования сборки для оптимизации. Теперь один интересный проект для генерации динамического кода - softwire (который датируется некоторое время - здесь - это оригинальный сайт проекта). Он был разработан Ником Капенсом и превратился в коммерчески доступный swiftshader. Но выделение исходного программного обеспечения по-прежнему доступно на gna.org.

Это может послужить введением к его решению.

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