Параллельная симуляция. Часть 2. Консервативные схемы

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

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

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

Последовательные модели

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

Симуляция нескольких гостевых процессоров

Ранее был описан способ моделирования многопроцессорных систем в однопоточной симуляции: отдельные процессоры выполняются последовательно друг за другом, выдерживая определённый максимально допустимый разброс в значениях симулируемого времени. Остальные процессоры при этом «заморожены». Очевидно, что для такого алгоритма работы для модели системы N процессоров относительное замедление относительно модели с одним процессором составит в лучшем случае N; на практике оно будет больше из-за необходимости периодического переключения контекста — состояния модели от одного процессора к другому.

Дискретные события

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

Параллельные модели

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

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

Рис. 1. Общая схема распределения симуляции на несколько потоков. Устройства и процессоры содержатся целиком внутри одного потока, тогда как модель памяти необходимо сделать доступной для всех

Симуляция многопроцессорной системы.

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

PDES.

При построении параллельной модели дискретных событий мы получаем т.н. parallel DES (PDES) [8-10, 18]. При этом с каждым потоком исполнения ассоциируется собственная очередь дискретных событий, текущее значение симулируемого времени и архитектурное состояние одного или нескольких моделей устройств. Поскольку два взаимодействующих устройства могут оказаться в разных потоках, необходимо предусмотреть возможность создавать события в очередях, отличных от той, в которой находится порождающее событие.

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

Препятствия на пути к созданию корректной параллельной модели

Параллельное программирование в целом является на удивление сложным занятием по сравнению с написанием классических последовательных программ. Этому есть много причин, вызванных техническими трудностями проектирования и психологическими особенностями человеческого восприятия, которые достаточно подробно рассмотрены в обширной литературе [3,13,29]. Здесь лишь отметим четыре обстоятельства, важных для дальнейшего обсуждения и напрямую влияющих на задачу проектирования симуляторов.

  1. Возможность гонок данных (data race) при одновременном доступе к общим данным и необходимость использования различных механизмов синхронизации, чтобы избежать их.
  2. Возможность взаимоблокировок двух или более процессов, пытающих получить доступ к общим ресурсам.
  3. Неэффективная работа параллельного приложения из-за интенсивной или неправильной синхронизации его потоков, из-за чего значительная часть их простаивает, не выполняя полезной работы.
  4. Результат исполнения параллельного приложения при идентичных входных данных может отличаться при различных его запусках из-за неопределённости порядка исполнения отдельных потоков. Недетерминистичность значительно усложняет отладку приложений.

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

Атомарные инструкции в моделях многопроцессорных систем

Для обеспечения работы примитивов синхронизации параллельных программ современные процессоры предоставляют так называемые атомарные инструкции, при исполнении которых гарантируется, что чтение и/или модификация региона общей памяти, указанной в них, не будет пересекаться с доступом к той же памяти другими потоками. Существует множество вариантов этих инструкций в разных архитектурах [32]. В последовательном симуляторе атомарность гостевых инструкций (вообще всех инструкций, даже тех, которые в реальности не являются атомарными и могут участвовать в гонках данных) обеспечивается автоматически: в любой момент времени максимум один процессор активен, никто не может повлиять на результат исполнения. Корректная поддержка этих инструкций в случае параллельного симулятора требует явных усилий со стороны разработчика. Рассмотрим известные для этого способы.

Использование атомарных хозяйских инструкций.

Идея использовать существующие хозяйские атомарные инструкции для симуляции атомарных гостевых достаточно проста. Она позволяет переложить задачу обеспечения корректной синхронизации с программы на аппаратуру. К сожалению, применимость этого способа ограничена случаями, когда набор атомарных инструкций хозяина достаточен для реализации всех инструкций гостя. Например, IA-32 содержит более десятка инструкций, которые можно использовать с префиксом LOCK, т.е. атомарных, тогда как ARM имеет только две инструкции данного типа — LDREX и STREX (атомарные инструкции SWP и SWPB, присутствующие в ARMv5, объявлены устаревшими в последующих расширениях [4]). Несомненно, этот подход применим для случаев совпадения архитектур хозяина и гостя [17].

Использование критических секций.

Следующим достаточно простым возможным решением проблемы обеспечения эксклюзивного доступа к памяти при симуляции гостевых атомарных операций является использование критических секций (или семафоров, замков, мьютексов и т.п.) в симуляторе. Прежде чем исполнять часть гостевой инструкции, модифицирующую память, соответствующий поток симулятора обязан получить эксклюзивное право на модификацию региона памяти, содержащего операнд [23]. Этим регионом может выступать вся физическая память (в таком случае есть только один замок на все потоки) или её блок, например, страница.

Тем не менее, использование критических секций для симуляции только атомарных инструкций оказывается недостаточно для корректной работы гостевых приложений. В [6] приводится пример практически важного гостевого сценария, приводящего к некорректной блокировке при исполнении на симуляторе. Это происходит из-за того, что обычные, не атомарные, гостевые доступы в память не требуют вхождения в критическую секцию и тем самым способны создать гонку данных при одновременной симуляции с атомарными. Решение — обязать все обращения в симулируемую память использовать вход в критическую секцию. Однако такое решение практически сведёт на нет весь выигрыш от параллельного исполнения, т.к. обращения к памяти из разных потоков приложения очень часты на практике.

Использование операций compare-and-swap и load-linked/ store-conditional.

Проанализируем оба описанных выше приёма ещё раз и попытаемся наметить путь к общему решению.

Если удастся выразить все существующие атомарные инструкции несколькими универсальными операциями, то для хозяйских архитектур, реализующих этот базовый набор, удастся симулировать все инструкции гостевых систем. В работе по теоретическим основаниям параллельных алгоритмов [12] показано, что существующие синхронизационные примитивы могут быть реализованы с помощью атомарной операции «сравнить и обменять значения» (compare-and-swap, CAS). Однако также показано, что алгоритмы для некоторых структур данных, использующие CAS, могут работать некорректно (так называемая «проблема ABA» [7]). Решением является использование расширенной операции, известной как «сравнение и обмен двух ячеек» (double compare-and-swap, DCAS). Однако ни одна современная архитектура не имеет машинных инструкций, соответствующих DCAS.

Следующий вариант — использование пары инструкций, называемых load-link и store-conditional (LL/SC) [15], позволяющих проверить, что цикл «загрузить-изменить-сохранить» для некоторого адреса в памяти прошёл без внешнего вмешательства, и сообщить об успехе или неудаче, что позволит повторить попытку провести операцию. Использование этой пары инструкций позволяет реализовать алгоритмы DCAS, CAS и другие примитивы.

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

Использование LL/SC можно считать частным случаем так называемой транзакционной памяти для оптимистичной синхронизации.

Модели консистентности памяти

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

Подробное рассмотрение существующих моделей консистентности памяти выходит за рамки этого обзора. Интересующийся читатель может найти подробную информацию об этой теме в обширной литературе [2], [21], [27, глава 9 и приложение A.7].. Тем не менее, различия в используемых моделях могут повлиять на корректность симуляции в случае, если гарантии хозяйской системы слабее тех, которые требуются для работы гостевого окружения.

Для целей контроля над порядком исполнения в точках приложения, для которых такой порядок критически важен, все современные архитектуры предоставляют так называемые инструкции-барьеры (fence), которые гарантируют, что на момент их завершения все доступы в память определённого типа (чтения и/или записи) или завершились (для инструкций, предшествующих барьеру), или ещё не начались (для находящихся после неё в потоке исполнения). Для IA-32 это инструкции LFENCE, SFENCE, MFENCE, для IA-64 — mf [1], для ARM — DMB, DSB, ISB, для PowerPC — sync, eieio.

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

Нарушения каузальности

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

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

Рис. 2. Нарушение корректности относительного положения событий в случае T2 < T1. Новое событие оказалось в прошлом и не может быть обработано

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

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

Что же делать? Прежде всего, достаточно легко сформулировать, как распознавать ситуацию нарушения каузальности и корректировать её для первого случая T2 > T1. Достаточно к сообщениям об обращении к разделяемому состоянию добавлять метку времени того события, которое производит доступ. Поток, получающий сообщение (или использующий модифицированные данные), сравнивает значение этой метки со своим локальным временем, корректирует момент обработки события, а при обнаружении логического несоответствия (например, если новое событие оказывается в прошлом) сигнализирует о проблеме (рис. 3). Конечно, этот метод не позволяет разрешать возникшее затруднение, но только обнаруживать его.

Рис. 3. Пересылка меток времени создания событий вместе с самим событием. Поток-приёмник корректирует положение события и принимает решение о том, соответствует ли ситуация условиям корректной симуляции

Пути решения проблемы нарушения каузальности

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

  1. Расширить схему PDES таким образом, чтобы в принципе не допускать каузальных ошибок. Такие системы назовём консервативными.
  2. Детектировать нарушения уже после их возникновения, а затем исправлять ситуацию, возможно, с помощью частичного перезапуска симуляции. Назовём этот класс оптимистические системы.

Консервативные модели

Мы хотим исключить возможность возникновения ситуаций, когда сообщение от потока, отставшего в симулируемом времени, приходит другому потоку «в прошлое». Предлагаемое решение — придержать (блокировать) исполнение отправителя сообщения до тех пор, пока приёмник сам не продвинется в симулируемом времени до точки приёма [20]. Пример такой ситуации изображён на рис. 4. Очевидно, что блокировать процесс следует, если он посылает новое событие в чужую очередь, но не в собственную — в этом случае порядок нарушиться не может. Описанная схема позволяет добиться корректности с помощью того, что потоки, вырывающиеся вперёд, вынуждены впоследствии ожидать более медленных.

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

Необходимость предпросмотра

Предпросмотр (lookahead) — определение того, на какое значение продвижение виртуального времени потока безопасно, т.е. не может вызвать нарушения каузальности. Чем больше это значение, тем большую «независимость» имеют отдельные потоки симуляции в своей работе, и тем выше её производительность в целом. Чрезмерно большое значение этой величины будет вызывать нарушения в логике работы гостевых приложений. Наиболее естественный выбор значения для предпросмотра равен характерной задержке передачи сообщений между устройствами в реальной системе. Необходимость использования предпросмотра для консервативных схем [8] обусловлена невозможностью узнать состояние других потоков без получения от них сообщений.

Проблема взаимоблокировок

К сожалению, такая схема совсем не гарантирует, что сообщения в системе будут передаваться и симуляция будет прогрессировать [20] — возможна ситуация взаимоблокировки (deadlock). На рис. 5 приведён пример такой ситуации.

Рис. 5. Ситуация взаимной блокировки в системе с тремя потоками. Каждый процесс ожидает сигнала окончания блокировки от какого-либо другого потока

В случае большого числа потоков в симуляции взаимоблокировка может затронуть только часть из них, при этом остальные будут продолжать исполняться до тех пор, пока не посылают сообщения к заблокированной группе. Как разрешать сложившуюся ситуацию? Если уметь обнаруживать взаимоблокировку, то возможно принудительно освободить один из участвующих в ней поток, разрешив ему исполняться. Это не нарушит условий корректности симуляции. Для определённости освобождать будем тот процесс, который имеет наименьшее значение текущего симулируемого времени. На рис. 5 им будет поток номер 1. Его разблокировка также оправдана с точки зрения выдерживания наименьшего разброса значений времён в разных потоках. Продвижение освобождённого потока в конечном счёте активирует и другие процессы, избавив их от блокировок, и симуляция продолжится в полном объёме.

Как можно детектировать ситуацию взаимоблокировки? В литературе описывается ряд алгоритмов, некоторые подразумевают присутствие центрального наблюдателя, некоторые являются децентрализованными. Кратко рассмотрим алгоритм, предложенный в [20]. Он основана на передаче специального сообщения (маркера) между процессами. Каждый процесс обязан передать его в течение ограниченного времени. В состоянии маркера хранится количество и состояния (блокирован или обрабатывает сообщения) посещённых процессов. Если в некоторый момент число обнаруженных маркером блокированных процессов достигает критического значения, то объявляется обнаружение ситуации взаимоблокировки.

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

Можно ли полностью исключить ситуацию блокировок? Поскольку сам факт их возникновения связан с тем обстоятельством, что отдельные потоки не имеют знания о симулируемом времени в остальных потоках, необходимого, чтобы самостоятельно принять решение, безопасно ли им продвигать вперёд своё время и посылать сообщения другим процессам, не опасаясь нарушения причинной связи. Как было описано ранее, метки времени приходят вместе с сообщениями. Но что делать, если архитектурных событий, вызывающих сообщения, не предвидится? В таком случае можно отправлять т.н. пустые сообщения (null messages), несущие только метку времени. Они должны периодически (в терминах физического времени) рассылаться/получаться всем и всеми агентами внутри одной симуляции; при приёме очередной метки поток может оценить, до какого момента следует продвигать своё время без опасности при этом послать некорректное сообщение. Блокировка всех потоков исключена, т.к. самый медленный поток не блокируется.

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

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

Следующий аспект функционирования такой схемы — в каком порядке и каким адресатам должны слаться пустые сообщения. Это можно делать как минимум двумя способами:

  • Всем агентам в системе. При таком сценарии мы обеспечиваем наиболее актуальную информацию всем потокам о глобальном симулируемом времени. Однако с ростом их числа эта схема плохо масштабируется из-за квадратичного роста числа передаваемых сообщений.
  • Случайным адресатам [10]. При таком подходе отправитель каждый раз выбирает случайным образом небольшую долю от полного числа потоков для сообщения им своего состояния. Благодаря постоянно изменяющемуся списку адресатов можно ожидать, что информация о каждом потоке будет распространяться по всей системе за конечное время.

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

Categories:
For more complete information about compiler optimizations, see our Optimization Notice.