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

Question

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

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

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

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

Любые предложения будут чрезвычайно оценены.

ОБНОВЛЕНИЕ 16 марта 2009 г.

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

Answer 1

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

  

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

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

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

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

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

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

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

Answer 7

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

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

Answer 8

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

Answer 9

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

Answer 10

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

  

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

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

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

Answer 11

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

Answer 12

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

Эта синхронизация может быть довольно простой, например проверка переменной «цикл выполнен» для каждого потока во время выполнения вычислений, но избежать этого невозможно.

Answer 13

Работая над управлением двигателями, я использовал некоторую математику для поддержания скорости в стабильном состоянии. Система имеет ПИД-регулятор, пропорциональный, интегральный и производный. Но это аналоговая / цифровая система. Может быть, можно использовать аналогичным образом, чтобы определить, сколько времени должен работать каждый поток, но самый большой совет, который я могу вам дать, это то, что все потоки будут иметь синхронизацию часов.

Answer 14

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

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