Как я могу убедиться, что N потоков работают примерно с одинаковой скоростью?

Question

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

У этого подхода было бы несколько преимуществ. Концептуально это было бы очень близко к тому, как работает реальный мир. Было бы намного проще масштабировать систему на несколько машин.

Однако, чтобы это работало, мне нужно убедиться, что все потоки работают с одинаковой скоростью, с довольно либеральной интерпретацией «то же самое». Скажите в пределах 1% друг от друга.

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

Буду очень признателен за любые предложения.

ОБНОВЛЕНИЕ 2009-03-16

Я хотел бы поблагодарить всех, кто ответил на этот вопрос, в частности всех, чей ответ был, по сути, «НЕ ДЕЛАЙТЕ ЭТОГО». Теперь, благодаря всем комментариям, я понимаю свою проблему намного лучше, и я не уверен, что мне следует продолжать, как я планировал изначально. Тем не менее, я чувствовал, что ответ Петра был лучшим ответом на сам вопрос, поэтому я принял его.

Answer 1

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

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

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

Answer 2

Вам понадобится какая-то синхронизация. CyclicBarrier класс имеет то, что вам нужно:

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

После каждого «тика» вы можете позволить всем своим потокам ждать других, которые были медленнее. Когда оставшиеся нити достигнут барьера, все они продолжатся.

Answer 3

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

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

Когда поток завершает обновление, он должен перевести себя в спящий режим; жду следующего тика. В Java используйте wait () для блокировки «галочка получена» и разбудите все потоки с помощью «notifyAll ()».

Answer 4

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

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

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

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

Answer 5

Как вы упоминаете, есть много ответов "НЕ ДЕЛАЙТЕ ЭТОГО". Большинство, кажется, читают потоки как потоки ОС, используемые Java. Поскольку вы упомянули Erlang в своем посте, я хотел бы опубликовать более эрланг-центрированный ответ.

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

Простым решением было бы создание процесса Erlang для каждого объекта, отправка тиков всем им и сбор результатов моделирования, прежде чем переходить к следующему тику. Это на практике синхронизирует все. Это, конечно, скорее детерминированное решение и не гарантирует каких-либо свойств в реальном времени. Также нетривиально, как процессы взаимодействуют друг с другом, чтобы получить данные, необходимые для расчетов. Вам, вероятно, нужно сгруппировать их хитроумными способами (группы столкновений и т. Д.), Использовать процессы гибернации (которые поддерживает Erlang) для спящих объектов и т. Д., Чтобы ускорить процесс.

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

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

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

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

Answer 6

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

Самым близким к вашему видению масштабируемости, которое я считаю работоспособным, является использование рабочих потоков, размер которых приблизительно соответствует количеству имеющихся у вас ядер, и распределение работы между ними. Черновик: определите класс ActionTick, который выполняет обновление для одной частицы, и пусть рабочий поток выбирает ActionTicks для обработки из общей очереди. Я вижу несколько проблем даже с таким решением.

1. Потоковые накладные расходы: вы получаете издержки на переключение контекста между различными рабочими потоками. Потоки сами по себе дороги (если на самом деле не так разрушительны, как процессы): тестируйте производительность с различными размерами пула потоков. Добавление большего количества потоков помимо количества ядер приводит к снижению производительности!
2. Затраты на синхронизацию: вы получаете несколько споров: доступ к рабочей очереди для одного, но хуже, доступа к моделируемому миру. Вам необходимо ограничить эффекты каждого ActionTick или реализовать много блокировок / разблокировок.
3. Сложность оптимизации физики. Вы хотите ограничить количество объектов / частиц, на которые смотрит каждый ActionTick (отрезок расстояния? 3D-дерево-подразделение пространства моделирования?). В зависимости от предметной области моделирования вы можете устранить большую часть работы, изучив необходимость каких-либо изменений в подмножестве элементов. Выполнение этих видов оптимизаций проще перед постановкой в ​​очередь рабочих элементов, а не как распределенный алгоритм. Но затем эта часть вашего моделирования становится потенциальным узким местом масштабируемости.
4. Сложность. Потоки и параллелизм вводят несколько банок червей в решение. Всегда сначала рассматривайте другие варианты, но если они вам нужны, попробуйте потоки, прежде чем создавать собственные стратегии планирования, блокировки и выполнения рабочих элементов ...

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

Answer 7

Erlang по умолчанию попытается равномерно распределить свои процессы по доступным потокам. Он также по умолчанию попытается запустить потоки на всех доступных процессорах. Поэтому, если у вас достаточно запущенных процессов Erlang, вы получите относительно равномерный баланс.

Answer 8

Даже с совершенным программным обеспечением, аппаратное обеспечение не позволит вам сделать это. Аппаратные потоки обычно не имеют достаточной производительности. В течение короткого периода вам повезет, если потоки будут работать с производительностью + -10%.

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

Answer 9

Я бы сделал своего рода "генератор часов" - и регистрировал бы каждый новый объект / поток там. Часы сообщат всем зарегистрированным объектам, когда delta-t пройдет. Однако это не означает, что вам нужен отдельный поток для каждого объекта. В идеале у вас будет столько потоков, сколько и процессоров. С точки зрения дизайна вы могли бы отделить выполнение объектных задач через Executor или пул потоков, например. когда объект получает событие тика, он отправляется в пул потоков и планирует себя для выполнения.

Answer 10

Я думаю, у вас есть фундаментальное заблуждение в вашем вопросе, где вы говорите:

Это было бы концептуально очень близко к тому, как работает реальный мир

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

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