Haskell для имитации многолинейного кругового движения? - PullRequest
4 голосов
/ 13 апреля 2009

Мне было трудно найти реальный пример параллелизма:

Представьте себе ситуацию выше, где Есть много переулков, много перекрестков и большое количество автомобилей. Кроме того, есть человеческий фактор.

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

Можете ли вы смоделировать это в Haskell? Действительно ли Haskell такой параллельный? Каковы пределы для параллелизации таких параллельных событий в Haskell?

Ответы [ 6 ]

6 голосов
/ 13 апреля 2009

Я не уверен, что именно вопрос. На Haskell 98 ничего не указано для параллелизма. Определенные реализации, такие как GHC, предоставляют расширения, которые реализуют параллелизм и параллелизм.

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

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

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

5 голосов
/ 15 апреля 2009

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

type Sim r a = ContT r (StateT ThreadQueue IO a)

newtype ThreadQueue = TQ [() -> Sim r ()]

ThreadQueue внутри состояния содержит очередь текущих запланированных потоков. Вы также можете иметь другие типы очереди потоков для хранения потоков, которые не запланированы, например, в семафоре (на основе «IORef (Int, ThreadQueue)»). Если у вас есть семафоры, вы можете создать эквивалент MVars и MQueues.

Чтобы запланировать поток, используйте "callCC". Аргументом для callCC является функция "f1", которая сама принимает функцию "c" в качестве аргумента. Этот внутренний аргумент "c" является продолжением: вызов его возобновляет поток. Когда вы делаете это, с точки зрения этого потока, "callCC" просто возвращает значение, которое вы дали в качестве аргумента "c". На практике вам не нужно передавать значения обратно приостановленным потокам, поэтому тип параметра равен нулю.

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

4 голосов
/ 13 апреля 2009

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

Подробнее об Эрланге

2 голосов
/ 13 апреля 2009

Я полагаю, вы спрашиваете, можете ли вы иметь один поток для каждого объекта в системе?

Среда выполнения GHC прекрасно масштабируется до миллионов потоков и мультиплексирует эти потоки на доступное оборудование через абстракции, упомянутые Крисом Смитом. Так что, безусловно, возможно иметь тысячи потоков в вашей системе, если вы используете Haskell / GHC.

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

0 голосов
/ 18 апреля 2009

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

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

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

(Подсказка: все модели ошибочны, но некоторые модели полезны).

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

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

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

0 голосов
/ 13 апреля 2009

Erlang, Scala, Clojure - это языки, которые могут вам подойти.

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

Я могу рассказать вам о MASON, Swarm и Repast. Но это библиотеки Java и C ...

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