Не приступайте к заправке слегка! Условия гонки могут быть основной болью в заднице, чтобы разобраться. Особенно, если у вас нет большого опыта работы с потоками! (Вас предупредили: вот драконы! Большие волосатые недетерминированные, невозможно надежно воспроизводить драконов!)
Вы знаете, что такое тупик? Как насчет Livelock?
Это говорит ...
Как ckarmann и другие уже предложили: Используйте модель рабочей очереди. Один поток на ядро процессора. Разбейте работу на N кусков. Сделайте куски достаточно большими, как много рядов. Когда каждый поток становится свободным, он забирает следующий рабочий блок из очереди.
В самой простой версии IDEAL у вас есть N ядер, N потоков и N частей проблемы, причем каждый поток с самого начала точно знал, что он собирается делать.
Но на практике это обычно не происходит из-за накладных расходов на запуск / остановку потоков. Вы действительно хотите, чтобы потоки уже были созданы и ожидали действий. (Например, через семафор.)
Сама модель рабочей очереди довольно мощная. Это позволяет вам распараллеливать такие вещи, как быстрая сортировка, которая обычно не распределяется между N нитями / ядрами корректно.
Больше потоков, чем ядер? Вы просто тратите впустую. Каждый поток имеет накладные расходы. Даже при # threads = # ядрах вы никогда не достигнете идеального коэффициента ускорения Nx.
Один поток на строку будет очень неэффективным! Одна нить на пиксель? Я даже не хочу думать об этом. (Этот попиксельный подход имеет гораздо больше смысла при игре с векторизованными процессорами, как это было на старых Crays. Но не с потоками!)
Библиотеки? Какая у тебя платформа? Под Unix / Linux / g ++ я бы предложил pthreads и семафоры. (Pthreads также доступен в Windows со слоем совместимости с 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 в пару классов C ++. Это сильно упростит дело!
Нужно ли блокировать массивы только для чтения и только для записи?
Это зависит от вашего точного оборудования и программного обеспечения. Обычно массивы только для чтения могут свободно использоваться потоками. Но есть случаи, когда это не так.
Письмо почти такое же. Обычно, пока только один поток записывает в каждую конкретную область памяти, все в порядке. Но есть случаи, когда это не так!
Письмо более проблематично, чем чтение, так как вы можете попасть в эти странные ситуации с забором. Память часто пишется как слова, а не как байты. Когда один поток записывает часть слова, а другой - другую, в зависимости от точного времени того, какой поток что делает, когда (например, недетерминированный), вы можете получить очень непредсказуемые результаты!
Я бы проигнорировал: предоставьте каждому потоку свою копию областей чтения и записи. После того, как они сделаны, скопируйте данные обратно. Все под мьютексом, конечно.
Если вы не говорите о гигабайтах данных, биты памяти очень быстрые. Та пара микросекунд времени исполнения просто не стоит кошмара отладки.
Если бы вы разделяли одну общую область данных между потоками, используя мьютексы, неэффективность столкновения / ожидания мьютексов накапливалась бы и снижала вашу эффективность!
Посмотрите, чистые границы данных - это сущность хорошего многопоточного кода. Когда ваши границы не ясны, вот когда вы попадаете в беду.
Точно так же важно, чтобы все на границе было мьютексированным! И чтобы области мьютекса были короткими!
Старайтесь не блокировать более одного мьютекса одновременно. Если вы блокируете более одного мьютекса, всегда блокируйте их в одном и том же порядке!
По возможности используйте мьютексы с проверкой ошибок или рекурсивными. БЫСТРЫЕ мьютексы просто напрашиваются на неприятности, с очень небольшим фактическим (измеренным) увеличением скорости.
Если вы попали в тупиковую ситуацию, запустите его в gdb, нажмите Ctrl-C, посетите каждый поток и проследите. Таким образом, вы можете быстро найти проблему. (Livelock гораздо сложнее!)
Последнее предложение: создайте его однопоточным, затем начните оптимизацию. В одноядерной системе вы можете получить больше скорости от таких вещей, как foo [i ++] = bar ==> * (foo ++) = bar, чем от многопоточности.
Приложение: Что я сказал о , обеспечивающих короткие области мьютекса выше? Рассмотрим два потока: (учитывая глобальный общий мьютекс-объект класса 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 раз больше времени, чем другой, ну, в конце концов, все выровняется. Хотя из-за слишком большого количества фрагментов накладные расходы на приобретение новых фрагментов работы создают заметные задержки. Это специфический для проблемы балансировочный акт.