Параллельная симуляция. Часть 3. Оптимистичные схемы

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

Оптимистичные модели

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

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

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

 

Рис. 6. Симуляция с периодическими точками сохранения. Штрихами показана часть симуляции, приведшая к нарушению корректности и откату к ближайшему сохранённому состоянию

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

  • Для сохранения состояния симуляции требуется как место в памяти хозяина, так и некоторый интервал хозяйского времени, в течение которого вся симуляция остановлена. Способ минимизировать обе величины — сохранять в новой точке лишь изменения в состояниях устройств относительно предыдущей, т.е. использовать инкрементальные точки сохранения.
  • Чем ближе к потенциальному месту нарушения имеется записанное состояние симуляции, тем меньше шагов необходимо переисполнять в случае отката.
  • Как и создание, откаты можно сделать инкрементальными, то есть затрагивающими лишь те части симуляции, которые изменились с момента последнего сохранения.

Разработаны многочисленные варианты оптимистичных алгоритмов параллельной дискретной симуляции. Рассмотрим наиболее известный протокол, получивший название Time Warp [14]. Его авторы описывают свой протокол как «виртуальное время» по аналогии с существующим понятием «виртуальная память».

Time Warp

Определим основные понятия, используемые при описании алгоритма Time Warp.

  • Сообщение — набор данных, описывающих событие, которое должно быть добавлено в одну из очередей событий. Оно характеризуется, кроме своего непосредственного содержимого, виртуальными временами отправки tsend и обработки treceive.
  • LVT (local virtual time) — значение симулируемого времени отдельного потока, участвующего в симуляции. Для создаваемых событий их время отправки tsend равно значению LVT отправителя. В отличие от консервативных схем, эта величина может как расти в процессе симуляции, так и убывать в случае отката процесса.
  • GVT (global virtual time) — глобальное время для всей симуляции, определяющее, до какой степени возможно её откатывать. Глобальное время всегда монотонно растёт, всегда оставаясь позади локального времени самого медленного потока, а также оно меньше времени отправки самого раннего ещё не доставленного события:

  • Отставшее сообщение (straggler) — событие, пришедшее в очередь с меткой времени treceivestraggler, меньшей, чем LVT получателя. Его обнаружение вызывает откат текущего состояния, при этом LVT уменьшается, пока не станет меньше, чем treceivestraggler, после чего оно может быть обработано. После этого возобновляется прямая симуляция.

Антисообщение (antimessage) — механизм обеспечения откатов в Time Warp. Каждое антисообщение соответствует одному ранее созданному сообщению, порождённому в интервале симулируемого времени [tstraggler, LVTi] и вызывает эффект, обратный его обработке (т.е. возвращает состояние в исходное). Поток, обнаруживший прибытие в свою очередь отставшего сообщения, при своём откате рассылает антисообщения всем потокам, с которыми он успел провзаимодействовать, таким образом сообщая о том, что необходимо отменить часть их прямой симуляции, на которую он успел повлиять. Каждый получатель запроса на отмену исполняет его, тем самым уничтожая эффекты от предыдущего события. Если же получатель обнаружит, что антисообщение имеет метку времени меньше его LVT (т.е. оно для него является отставшим), то он также производит откат, рассылая новые антисообщения. Благодаря этому последствия некорректной симуляции постепенно отменяются глобально.

Сбор окаменелостей (fossil collection) — своеобразное название механизма сбора мусора (garbage collection). Как будет показано дальше, из всех обработанных всеми потоками событий безопасно удаляемы только те, что имеют метку времени, меньшую чем GVT. Для того, чтобы объём потребляемой при симуляции памяти не рос безгранично, необходимо регулярно её освобождать для последующего переиспользования. Непосредственно сбором окаменелостей может заниматься или специально выделенный для этого поток, или же сами потоки симуляции, для чего их придётся периодически освобождать от задачи обработки событий.

На рис. 7 приведены все компоненты схемы Time Warp. Рассмотрим подробнее процессы, происходящие при работе такой модели.

Рис. 7. Оптимистичная симуляция Time Warp. Точками обозначены события, подлежащие процессу сборки окаменелостей, штриховыми линиями — уже обработанные, к которым симуляция потенциально может откатиться, жирным — текущее событие, тонкой линией — запланированные в будущем. Серым фоном выделено отставшее сообщение, а двойной линией — антисообщение

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

Если при обработке очередного сообщения оно оказывается отставшим, получивший его поток начинает процесс отката. При этом он продвигает своё локальное время в обратном направлении, обрабатывая встречающиеся события «наоборот», т.е. вызывая изменения, обратные записанным в них. При этом вместо обычных рассылаются антисообщения. Этот процесс происходит до тех пор, пока исходное отставшее сообщение не перестанет быть таковым, т.е. пока tstraggler < LVT. После этого события начинают вновь обрабатываться в порядке возрастания LVT.

Ни один поток по определению не имеет значение времени, меньшее GVT, и ни одно необработанное сообщение (в том числе те, что впоследствии окажутся отставшими) во всей симуляции не может иметь treceive < GVT. Из этого следует, что при дальнейшей симуляции ни один поток не будет вынужден откатывать значение своего LVT в прошлое дальше, чем до значения GVT. Таким образом, эта величина имеет принципиальный смысл и обозначает границу между свершившимся и потенциально отменяемым прошлым симуляции. В отличие от последовательной DES и консервативных схем, обработка события в оптимистичной PDES ещё не означает, что занимаемые им ресурсы можно освободить. Это происходит потому, что в дальнейшем в случае отката это же событие могут исполнить ещё раз. Лишь когда оно окажется слева от границы глобального времени, у нас есть гарантия того, что оно «на самом деле свершилось».

Распределённая общая память

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

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

В литературе описаны различные решения данной задачи [5, 11]. Рассмотрим основные приёмы, описанные в них.

Главная задача системы DSM — поддержка иллюзии единого пространства. Это означает, что все обращения узлов к памяти должны перехватываться и обрабатываться таким образом, чтобы исполняющиеся процессы имели консистентное представление о значениях, хранящихся в ней. С другой стороны, ненулевая вероятность того, что требуемые приложению данные находятся на другом узле, и что для их получения приходится использовать относительно медленный (по сравнению с обращениями к локальной памяти) канал передачи данных, может серьёзно ограничить производительность и масштабируемость всей системы. Таким образом, приходится использовать ухищрения, минимизирующие число таких «дальних» запросов.

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

Во-вторых, если обнаружено, что большую часть времени блок данных читается одним и тем же узлом, то разумным представляется переместить такие данные непосредственно на этот узел, т.е. провести миграцию данных. Возможен и обратный подход — переместить само приложение ближе к данным, т.е. провести миграцию кода [15].

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

Используемая в системе DSM гранулярность хранения регионов памяти влияет на требуемый объём служебной информации и на издержки при передаче изменённых блоков по сети. Как правило, она выбирается равной размеру страницы физической памяти и составляет от 4 кбайт до нескольких мегабайт.

Существуют коммерческие продукты, предназначенные для виртуализации группы вычислительных узлов, соединённых сетью, в представление единой системы с общей памятью и объединённым числом вычислительных ядер [25, 28]. Они позволяют исполнять программы, написанные для систем с единой памятью, без изменений в их коде и логике работы.

Отметим, что, кроме общей оперативной памяти, аналогичные подходы могут использоваться для обеспечения прозрачного распределённого доступа к другим ресурсам, например, энергонезависимому хранилищу, файловой системе [19,24] и т.д.

Балансировка скорости отдельных потоков

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

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

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

Барьерная синхронизация

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

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

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

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

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

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

Рис. 8. Симуляция с барьерной синхронизацией. Жирными сплошными линиями показаны активные участки симуляции, штриховыми — ожидание остальных потоков без выполнения полезной работы

Детерминизм параллельных моделей

Детерминистичный (deterministic) симулятор — модель, которая в независимых своих запусках вычисляет идентичное конечное состояние моделируемой системы для любого начального состояния при условии, что исходное состояние при каждом запуске было одинаковое. Такая программа будет повторять своё поведение при последовательных запусках на каждом своём шаге, таким образом проходя через одну и ту же последовательность состояний.

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

Условия детерминизма

Для последовательного симулятора DES для повторяемости исполнений достаточно соблюдения следующих условий.

Он написан без ошибок типа «обращение к неинициализированной памяти». При нарушении этого условия сложно утверждать даже о корректности симуляции, не говоря уже об её детерминистичности.

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

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

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

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

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

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

События с одинаковой меткой времени

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


Рис. 9. Различный порядок получения сообщений от внешних потоков

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

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

В данном подходе принимаются меры, чтобы времена событий никогда полностью не совпадали. Для этого метка времени должна содержать дополнительные «младшие» биты, уникальные для всех событий во всей симуляции. При этом для любых двух симулируемых событий расширенные таким образом метки времени никогда не могут совпасть. Уникальные младшие биты могут формироваться на основе двух чисел: порядкового номера создаваемого события, монотонно возрастающего для каждого потока-отправителя, и порядкового номера создающего его хозяйского потока. Альтернативный подход заключается в использовании генератора псевдослучайных чисел, инициируемого одним и тем же начальным значением так, что производимая им последовательность одинакова при всех запусках симуляции (отметим, что построение генератора, пригодного для детерминистичной многопоточной генерации псевдослучайных чисел, нетривиально [18]).

Домены синхронизации

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

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

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

На практике при симуляции многомашинных конфигураций в составе одного домена размещается один гостевой компьютер, а моделирование передачи сетевых пакетов (Ethernet, Infiniband и т.п.) производится через описанную схему. При этом достигается наилучший баланс между скоростью симуляции (т.к. характерные задержки сетевых устройств больше, чем наблюдаемые между, скажем, памятью и процессором) и её точностью (протоколы сетевого взаимодействия толерантны к большим задержкам и высокой неопределённости времени доставки пакетов). Однако с ростом скоростей (для современных серверных и HPC сетевых карт скорость доставки пакетов приближается к скорости работы локальных жёстких дисков) квант синхронизации уменьшается, что приводит к повышению частоты организации барьеров с соответствующим падением скорости симуляции.

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

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

Параллельная симуляция одного процессора

У наблюдательного читателя может возникнуть вопрос об «обратной» ситуации: можно ли получить выигрыш от многих ядер хозяйской системы, если требумое число симулируемых ядер при этом значительно меньше? То есть — возможно ли каким-то образом ускорить симуляцию одного гостевого процессора, используя для этого несколько параллельных хозяйских потоков?

Ответ зависит от того, на каком уровне абстракции лежит модель. Для уровня архитектуры (набора инструкций) ответ почти всегда отрицательный. Эффективное решение этой задачи — параллельное исполнение нескольких машинных инструкций последовательной программы — равносильно построению быстрой модели внеочередного исполнения (out of order execution), способной «на лету» находить независимые по данным инструкции и исполнять их. Весь эффект от параллельного исполнения при этом будет нивелирован длительным анализом. Если даже упростить задачу, позволив проводить статический, а не динамический анализ, мы сводим её к проблеме построения автопараллелизующего компилятора. Как известно, далеко не всякий код подвержен такому преобразованию.

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

Заключение

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

  • Оптимизации, используемые для минимизации числа необходимых синхронизаций в консервативных моделях.
  • Решения, позволяющие уменьшить частоту и стоимость откатов в схемах оптимистичных.
  • Потребление памяти параллельным симулятором по сравнению с последовательной версией.
  • Построение консервативных и оптимистичных схем с нулевым предпросмотром, и проблематика обеспечения детерминизма для этого случая.
  • Эффективное взаимодействие планировщика потоков хозяйской системы и симуляции.
  • Проблема учёта событий, уже отправленных, но ещё не полученных, т.е. находящихся «в полёте».
  • Способы эффективного вычисления GVT, организации барьеров, создания точек сохранения и другие распределённые алгоритмы, необходимые для нормальной работы параллельного симулятора.

Интересующийся читатель может найти подробное описание этих и других вопросов распределённой симуляции в [8]. Тем не менее, хотелось бы ответить на два важных вопроса: почему именно параллельный симулятор так сложно построить? и если он таки построен, то возможно ли получить выигрыш в скорости?

Почему параллельная симуляция настолько сложна?

В работе [9] в секции «Why PDES is hard?» приводится достаточно краткий и одновременно подробный ответ на этот вопрос. Приведём свободный перевод: «…необходимо определить, может или нет сообщение E1 быть обработано одновременно с E2. Но каким образом узнать, влияет или нет E1 на E2, без его симуляции?»

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

Потолок ускорения от параллелизма.

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

 

Литература

  1. Intel Corporation. A Formal Specification of Intel® Itanium® Processor Family Memory Ordering. — Intel Corporation, окт. 2002. — URL: http://download.intel.com/design/itanium/downloads/25142901.pdf
  2. Adve Sarita V., Gharachorloo Kourosh Shared memory consistency models: A tutorial // IEEE Computer. — 1996. — Т. 29. — С. 66– 76. — DOI: 10 . 1 . 1 . 106 . 5742. — URL: http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
  3. Andrews Greg R Foundations of Parallel and Distributed Programming. — 1st ed.— Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1999. — ISBN: 0201357526.
  4. ARM. ARM Synchronization Primitives Development Article. Appendix A. SWP and SWPB. — ARM. http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dht0008a/CJHIGEFG.html
  5. Bugnion Edouard, Devine Scott, Rosenblum Mendel Disco: Running commodity operating systems on scalable multiprocessors // ACM Transactions on Computer Systems. — 1997. — 143–156. — URL: http://www.cis.upenn.edu/~cis700-6/04f/papers/bugnion-disco.pdf
  6. COREMU: a scalable and portable parallel full-system emulator / Zhaoguo Wang [и др.] // Proceedings of the 16th ACM symposium on Principles and practice of parallel programming. — San Antonio, TX, USA: ACM, 2011. — 213–222. — (PPoPP ’11). — ISBN: 978-1-4503-0119-0. — DOI: 10 . 1145 / 1941553 . 1941583. — URL: http://doi.acm.org/10.1145/1941553.1941583.
  7. Dechev Damian, Pirkelbauer Peter, Stroustrup Bjarne Understanding and Effectively Preventing the ABA Problem in Descriptor-Based Lock-Free Designs // 2008 11th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC). — 2010. — 185–192. — ISSN: 1555-0885. — DOI: 10 . 1109 / ISORC . 2010 . 10. — URL: http://www.stroustrup.com/isorc2010.pdf
  8. Fujimoto Richard M. Parallel and Distributed Simulation Systems. — 1st ed. — New York, NY, USA: John Wiley & Sons, Inc., 2000. — ISBN: 0471183830.
  9. Fujimoto Richard M. Parallel discrete event simulation // Commun. ACM. — 1990. — Окт. — Т. 33, No 10. — С. 30–53. — ISSN: 0001-0782. — DOI: 10.1145/84537.84545. — URL: http://doi.acm.org/10.1145/84537.84545 .
  10. Graphite: A Distributed Parallel Simulator for Multicores / Jason E. Miller [и др.] // the 16th IEEE International Symposium on High-Performance Computer Architecture (HPCA). — 2010. — Янв.
  11. Herlihy Maurice Wait-free synchronization // ACM Trans. Program.Lang. Syst. — 1991. — Янв. — Т. 13, No 1. — С. 124–149. — ISSN: 0164-0925. — DOI: 10 . 1145 / 114005 . 102808. — URL: http://doi.acm.org/10.1145/114005.102808 .
  12. Herlihy Maurice, Shavit Nir The Art of Multiprocessor Programming. — San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2008. — ISBN: 0123705916, 9780123705914.
  13. Jefferson David R. Virtual Time // ACM Transactions on Programming Languages and Systems. — 1985. — Т. 7, No 3. — С. 404–425.
  14.  Jensen Eric H., Hagensen Gary W., Broughton Jeffrey M. A New Approach to Exclusive Data Access in Shared Memory Multiprocessors //. — 1987. — Ноя. — Technical Report UCRL-97663. — URL: https://e-reports-ext.llnl.gov/pdf/212157.pdf
  15. Khan Omer, Lis Mieszko, Devadas Srinivas Instruction-Level Execution Migration. — Тех. отч. MIT-CSAIL-TR-2010-019. — 2010. — URL: http://dspace.mit.edu/bitstream/handle/1721.1/53748/MIT-CSAIL-TR-2010-019.pdf
  16. Lantz Robert E. Parallel SimOS: Performance and Scalability for Large System Simulation. — Докт. дисс. Computer Systems Laboratory, Stanford University, 2007. — URL: http://cs.stanford.edu/~rlantz/papers/lantz-thesis.pdf
  17. Leiserson Charles E., Schardl Tao B., Sukha Jim Deterministic parallel random-number generation for dynamic-multithreading platforms // SIGPLAN Not. — 2012. — Фев. — Т. 47, No 8. — С. 193–204. — ISSN: 0362-1340. —  URL: http://doi.acm.org/10.1145/2370036.2145841
  18. Liu Jason Parallel Discrete-Event Simulation. — 2009. — URL: http://www.cis.fiu.edu/~liux/research/papers/pdes-eorms09.pdf
  19. LustreFS. — Xyratex, 2013. — URL: http://lustre.org/
  20. Misra Jayadev Distributed discrete-event simulation // ACM Computing Surveys. — 1986. — Т. 18. — 39–65. — URL: http://www.cis.udel.edu/~cshen/861/papers/p39-misra.pdf
  21. Mosberger David Memory Consistency Models. — 1993. — URL: http://citeseerx.ist.psu.edu/viewdoc/download;?doi=10.1.1.44.5376
  22. Peschlow Patrick, Honecker Tobias, Martini Peter A Flexible Dynamic Partitioning Algorithm for Optimistic Distributed Simulation // PADS. — IEEE Computer Society, 2007. — С. 219–228. —ISBN: 0-7695-2898-8.
  23. PQEMU: A Parallel System Emulator Based on QEMU /Jiun-Hung Ding, Po-Chun Chang, Wei-Chung Hsu, Yeh-Ching Chung // Proceedings of the 2011 IEEE 17th International Conference on Parallel and Distributed Systems. — Washington, DC, USA: IEEE Computer Society, 2011. — С. 276–283. — (ICPADS ’11). — ISBN: 978-0-7695-4576-9. — DOI: 10 . 1109 / ICPADS . 2011 . 102. — URL: http://dx.doi.org/10.1109/ICPADS.2011.102
  24. Schmuck Frank, Haskin Roger GPFS: A Shared-Disk File System for Large Computing Clusters // In Proceedings of the 2002 Conference on File and Storage Technologies (FAST. — 2002. — С. 231–244.
  25. SGI UV: Big Brain for No-Limit Computing. — SGI, 2013. — URL: http://www.sgi.com/products/servers/uv/
  26. Simics Accelerator User’s Guide 4.6. — Wind River, 2011.
  27. Smith James E., Nair Ravi. Virtual machines – Versatile Platforms for Systems and Processes. — Elsevier, 2005. — ISBN: 978-1-55860-910-5.
  28. vSMP Foundation Free. — ScaleMP, 2013. — URL: http://www.scalemp.com/products/vsmp-foundation-free/
  29. В.В. Топорков. Модели распределенных вычислений. — Физматлит, 2004. — ISBN: 5-9221-0495-0.
  30. Зайцев Роман. Atomic operations. — 2012. — URL: http://habrahabr.ru/post/157163/
  31. М.Г. Иванов Как понимать квантовую механику. — РХД, 2012. — ISBN: 978-5-93972-944-4. — URL: http://mezhpr.fizteh.ru/biblio/q-ivanov.html
For more complete information about compiler optimizations, see our Optimization Notice.
Categories: