Исследователи из Наньянского технологического университета (Nanyang Technological University, Сингапур) отмечают, что крупномасштабные агент-ориентированные модели являются одним из самых перспективных инструментов для решения проблем современных мегаполисов, связанных с транспортными заторами и высокой плотностью проживающего населения. Однако симуляции, проводимые с использованием таких моделей весьма ресурсоемкие, что вызывает необходимость их параллелизации. По мнению разработчиков, наиболее эффективным способом распараллеливания агент-ориентированных транспортных симуляторов является декомпозиция моделируемого пространства на субрегионы. Агенты каждого из них вычисляются соответствующими логическими процессами (Logical Processes, LP), которые необходимо синхронизировать для целостности взаимозависимых данных. В описываемой ниже работе для синхронизации распределенных вычислений используются методы барьерной синхронизации, при которой выполнение программы разделяется барьерами на несколько этапов. Также авторы приводят оригинальную стратегию консервативной синхронизации асинхронных операций, названную стратегией «взаимного назначения» (Mutual Appointment, MA). MA позволяет повысить эффективность барьерной синхронизации и разрешает логическим процессам взаимодействовать непосредственно друг с другом. Упомянутые методы нашли воплощение в параллельном агент-ориентированном транспортном симуляторе SEMSim, использующем реальные данные. Эксперименты показали, что MA позволяет увеличить эффективность параллельных вычислений, а стратегия ослабленного взаимного назначения (Relaxed Mutual Appointment, RMA) совершенствует MA за счет существенного снижения сообщений при синхронизации.
1. Параллельный агент-ориентированный транспортный симулятор
1.1. Выполнение модели
Пространство для симуляций в агент-ориентированной модели представляет собой дорожную сеть, содержащую пути и узлы (nodes). В терминах модели отрезки пути, которые могут иметь одну или несколько полос движения, являются контейнерами для агентов. В свою очередь узлы содержат информацию о соответствующих отрезках и полосах движения. Пример небольшой дорожной сети приведен на рис. 1, для упрощения без полос.
Рис. 1. Агенты с определенным горизонтом видимости в рамках дорожной сети
Агент в симуляции является композитной единицей, которая совмещает в себе модели поведения как водителя, так и транспортного средства. Реализованные в модели водителя функции включают в себя изменение скорости, смену полосы и др., а реализация модели транспортного средства предусматривает модификацию двигателя, батареи (в случае электродвигателя) и др. Также агенты модели определяются набором состояний, которые могут активироваться в различные моменты времени в зависимости от значений переменных, относящихся к двум группам: (1) переменные агента; (2) переменные внутреннего состояния. Деление на группы обусловлено видимостью их значений для других агентов модели. Так, к первой группе относятся скорость, координаты и др., а ко второй – невидимые другими агентами характеристики (к примеру, уровень заряда батареи для электромобилей). Состояния агента меняются в процессе симуляций в результате срабатывания событий, упорядоченных по времени до момента их активации. При этом каждый упорядоченный список событий (event list) обрабатывается отдельным процессом LP в рамках повторяющегося трехтактного цикла, который включает в себя инициализацию списка, планирование выполнения событий и удаление событий из списка. В свою очередь планировка событий осуществляется с учетом моделей водителей и транспортных средств.
Каждый агент имеет определенный горизонт видимости, в рамках которого состояния других агентов могут оказывать влияние на его состояние (рис. 1), причем, даже если движение всех агентов является однонаправленным, горизонт видимости остается всенаправленным, поскольку агент перед возможным маневром должен отслеживать поведение едущих сзади водителей с целью обеспечения безопасного движения.
1.2. Разбиение симуляции по логическим процессорам
Как уже говорилось, дорожная сеть симулятора декомпозируется на субрегионы. Пример такого разделения приведен на рис. 2, где градациям серого цвета соответствуют различные субрегионы. Отдельный LP отвечает за выполнение событий для агентов в одном субрегионе и имеет доступ только к агентам в этом пространстве. Разделение пространства осуществляется посредством ссылок (links), при этом ссылки, разделяющие два субрегиона, называются граничными ссылками (boundary links).
Рис. 2. Дорожная сеть Сингапура, разделенная на 4 субрегиона
К примеру, на рис. 3, ссылка link2 является граничной – левая половина относится к логическому процессу LP1, а правая к LP2. Поскольку направление движения (и, соответственно, направленность ссылки link2) агентов задано от LP1 к LP2, то link2 является исходящей граничной ссылкой процесса LP1 и входящей граничной ссылкой процесса LP2, а сами процессы – соседними.
Рис. 3. Разделенная дорожная сеть: (a) пример границы субрегионов и буферных областей; (b) видимость ссылки link2 из процесса LP1; и (c) видимость ссылки link2 из процесса LP2.
В рамках имитационного процесса, при перемещении агента из одного субрегиона в другой, инициируется процедура миграции (migration). К примеру, агент B (на рис. 3), обслуживаемый процессом LP1 и ссылкой link2, попадает в момент времени t в новый субрегион и, таким образом, дальнейшие его действия будут обрабатываться процессом LP2. При этом если местоположение агента C, обрабатываемого процессом LP2, попадает в горизонт видимости агента B, обслуживаемого процессом LP1, переменные состояния агента C, оказывающие влияние на поведение агента B, будут переданы процессу LP1 для обновления. Таким образом, в модели поддерживается корректность данных при симуляции, а передаваемые переменные состояния являются переменными общих состояний (shared states). Для определения последних назначаются буферные субрегионы (buffered regions), т.е. области пространства находящиеся рядом с границами субрегионов, а их размер соответствует горизонту видимости агентов. Так, на рис. 3a затемненная область на ссылке link2 представляет собой два буферных субрегиона – первый из которых относится к процессу LP1 (левая сторона затемненной области), а второй к процессу LP2 (правая сторона), причем размеры субрегионов определяются горизонтом видимости агентов. Также видно, что агенты B и C находятся внутри буферного пространства и общие состояния агента B передаются процессу LP2, а общие состояния агента C процессу LP1.
Кроме того, процессы LP, получающие общие состояния агентов, использует переменные этих состояний для создания нелокальных прокси-агентов (non-local proxy agents), которые действуют в качестве представителей реальных агентов в других локальных процессах с тем, чтобы агенты видели общие состояния в качестве агентов. К примеру, на рис. 3b приведен прокси-агент C' (от реального агента C), обслуживаемый процессом LP1, а на рис. 3c прокси-агент B' (от реального агента B), обслуживаемый процессом LP1. Такой механизм упрощает управление общими состояниями и всей моделью в целом.
1.3. Синхронизация логических процессов
В процессе синхронизации между процессами происходит обмен информацией относительно миграции агентов и их общими состояниями, причем процессы не могут продолжать дальнейшую работу до момента завершения всех необходимых операций чтения и записи совместно с сопряженными процессами. Отметим, что стратегии синхронизации можно классифицировать как консервативные и оптимистичные. Консервативные стратегии запрещают процессу выполнять инструкции в ином порядке, чем он получает их от процесса-источника. Тем самым предотвращаются временные парадоксы. В свою очередь оптимистичные стратегии допускают нарушение программных инструкций, исключив проверку событий, запланированных другими логическими процессами, а при возникновении ошибок, для их исправления инициируется механизм отката. В данной работе используются только консервативные стратегии. Стратегии синхронизации являются синхронными (synchronous) если в них используются глобальные точки синхронизации (в которых участвуют все процессы). Все LP блокируются до тех пор, пока синхронизация не будет завершена. В отличие от синхронных стратегий, при асинхронных (asynchronous) стратегиях глобальной блокировки не происходит. Так, когда процесс LP2 сообщает процессу LP1 о том, что он может быть вызван в момент времени t, он блокируется в момент времени t. Все остальные несвязанные процессы продолжают выполняться без участия в этой операции синхронизации. Асинхронные стратегии синхронизации имеют определенные преимущества по сравнению с синхронными, поскольку в случае их реализации снижается время ожидания процессов симуляции и уменьшается количество соответствующих сообщений.
Одним из ключевых элементов консервативной синхронизации является использование предварительного просмотра (lookahead), позволяющее процессу LP прогнозировать поведение, которое может быть вызвано другими процессами. В рассматриваемой модели предварительный просмотр (или предсказание поведения) может быть определен следующим образом: если процесс LP1 находится в момент времени t и он предсказывает, что до момента времени t + ∆t он не будет зависеть от процесса LP2, то тогда «процесс LP1 предсказывает поведение ∆t в направлении процесса LP2». Для определения точных значений предварительного просмотра необходимо спрогнозировать, когда зависимые переменные будут меняться.
2. Стратегия взаимного назначения
2.1 Взаимное назначение
Основная идея взаимного назначения (mutual appointment) заключается в том, что процесс взаимодействует с другими процессами для согласования индивидуальных назначений в определенные моменты времени моделирования. Таким образом, выполнение процесса будет заблокировано до реализации соответствующего назначения, причем блокировка происходит только между парой процессов.
Взаимное назначение состоит из двух задач: 1) обмен информацией о текущей зависимости и 2) согласование следующего назначения. Логика синхронизации взаимного назначения приведена в листинге 1.
Листинг 1. Событие синхронизации во время взаимного назначения
Определения:
t – момент времени наступления события синхронизации в процессе LPi;
Ai,t – множество агентов в процессе LPi в момент времени t;
Ci,t – множество процессов, имеющих назначение с процессом LPi в момент времени t;
Mij,t – множество агентов, мигрирующих из процесса LPi в процесс LPj в момент времени t;
Sij,t – множество общих состояний, пересылаемых из процесса LPi в процесс LPj в момент времени t;
lij,t – предварительный просмотр процесса LPi в направлении процесса LPj в момент времени t;
∆tij,t – интервал времени до следующего назначения между процессами LPi и LPj в момент времени t.
foreach LPj ∈ Ci,t do
// 1. подготовка содержимого сообщения
determine Mij,t, Sij,t, lij,t
// 2. обмен сообщениями
send Mij,t, Sij,t, lij,t to LPj
receive Mji,t, Sji,t, lji,t from LPj
// 3. обновление множества локальных агентов
Ai,t ← Ai,t ∪ Mji,t \ Mij,t
// 4. обновление прокси-агентов с общими состояниями
update proxy agents with Sji,t
// 5. согласование следующего назначения
∆tij,t ← min (lij,t, lji,t)
make an appointment with LPj at time t + ∆tij,t
end
В момент времени t в процессе LPi наступает событие синхронизации, в котором будет участвовать множество процессов Ci,t, имеющих назначение с процессом LPi. Отдельный процесс LP синхронизируется только с непосредственными соседями и, таким образом, множество Ci,t содержит только соседние процессы, но при этом может включать не все соседние процессы (да и вообще быть пустым). Для каждого процесса LPj в множестве Ci,t процессор LPi выполняет следующие пять шагов:
1. Подготовка данных для выполнения процедур чтения и записи, а также вычисление предварительного просмотра для следующего назначения. При этом мигрирующие агенты Mij,t и общие состояния Sij,t определяются посредством сканирования граничных ссылок между LPi и LPj.
2. На втором шаге процессор LPi отправляет всю подготовленную информацию процессору LPj с использованием двухточечной связи (point-to-point communication). Для уменьшения количества сообщений используются объединенные синхронизационные сообщения, содержащие три информационные части (о миграционных агентах, общих состояниях и предварительном просмотре). Одновременно с этим, процессор LPi получает от процессора LPj сообщение такого же содержания, но относящегося к LPj (т.е. Mji,t, Sji,t, lji,t).
3. После получения сообщений, на третьем шаге происходит обновление множества локальных агентов Ai,t с учетом мигрирующих агентов Mij,t и Mji,t.
4. На четвертом шаге происходит обновление множества прокси-агентов процесса LPi с общими состояниями Sji,t – ненужные прокси-агенты удаляются, а новые прокси-агенты по мере необходимости создаются.
5. Последний шаг – согласование следующего назначения. Процесс LPi определяет временной интервал до следующего назначения с процессом LPj следующим образом ∆tij,t = min (lij,t, lji,t), а также следующее событие синхронизации с LPj в момент времени t + ∆tij,t.
Начальные взаимные назначения планируются во время процедуры инициализации модели для всех процессов и их целями являются соседние процессы, а все последующие взаимные назначения создаются на основе предварительных просмотров.
2.2. Определение предварительного просмотра
Предварительный просмотр во время стратегии синхронизации на основе взаимного назначения является направленным (directed), что означает наличие разных значений предварительного просмотра по отношению к каждому соседнему процессу в определенный момент времени. В свою очередь значения предварительного просмотра используются для индивидуальных назначений. В зависимости от сложившихся условий можно выделить три варианта оценки предварительного просмотра.
Первый вариант – в локальном пространстве нет агентов. Это обычно происходит в самом начале симуляции, и тогда процедура предварительного просмотра занимает минимум времени для вновь создаваемых агентов. Пусть NA = {na1, na2, …, na|NA|} – множество локальных агентов; агент nak (1≤k≤|NA|) запланирован к созданию в момент времени natk и он потребует минимальное количество времени ttk для перемещения от точки создания до буферного субрегиона, относящегося к процессу LPj (в случае, если агент не затронет упомянутый регион ttk = ∞). Таким образом, минимальное время для достижения новым агентом буферного субрегиона min(natk + ttk), соответствующее также времени предварительного просмотра по отношению к LPj. Если расписание для создания новых агентов отсутствует, то действие новых агентов следует рассматривать по-другому. Предположим, что OLij – множество исходящих граничных ссылок в направлении LPj, а минимальное время для перемещения от начала ссылки l(l∈Lij) до буферного региона, относящегося к этой ссылке, составляет obtl, тогда минимальное время для созданного агента, перемещающегося к буферному субрегиону составляет min(obtl). Пример obtl показан на рис. 4a. Значение предварительного просмотра предполагается как min(obtl), однако следует отметить, что оценки времени перемещения изначально занижены, поскольку фактическое время по разным причинам обычно больше.
Рис. 4. Сценарии расчета времени предварительного просмотра на основе взаимного назначения: (а) в локальном пространстве нет агентов, а новые создаются в дорожной сети; (b) буферные субрегионы пустые и нет мигрирующих агентов; (c) аналогичен сценарию (b), но с создаваемыми агентами; (d) буферные субрегионы не пусты.
Второй вариант – в локальном пространстве есть агенты, но буферные субрегионы пустые и нет мигрирующих агентов (рис. 4b), либо они создаются (рис. 4c), но при этом значение предварительного просмотра равно минимальному времени, требующемуся локальным агентам для перемещения к буферным регионам. Миграция локальных агентов возможна только по исходящим ссылкам, поэтому в модели происходит проверка агентов, маршруты которых проходят по исходящим граничным ссылкам (отметим также что на них могут создаваться агенты (рис. 4c)). Предположим, что минимальное время для перемещения к буферному субрегиону, относящемуся к процессу LPj, равно atj. Тогда значение предварительного просмотра будет равно min(atj, min(natk + ttk)). Если расписание для создания новых агентов отсутствует, то как и в первом варианте минимальное время для перемещения будет составлять min(obtl) вместо min(natk + ttk), а значение предварительного просмотра min(atj, min(obtl)).
Третий вариант – в буферных субрегионах есть агенты или они мигрируют туда до наступления следующего события по перемещению. Время предварительного просмотра соответствует интервалу перемещения, поскольку общие состояния должны быть обновлены до следующего события по перемещению. Соответствующий пример показан на рис. 4d, где один агент находится внутри буферного субрегиона на ссылке link1 относящейся к процессу LPi, а другой агент внутри буферного субрегиона на ссылке link2.
Примерный алгоритм определения предварительного просмотра во время взаимного назначения приведен в листинге 2.
Листинг 2. Определение предварительного просмотра во время взаимного назначения
Определения:
Ai – множество агентов в процессе LPi;
Lij – множество граничных ссылок между процессами LPi и LPj;
Ml – множество агентов, мигрирующих по ссылке l, l ∈ Lij;
Sl – множество общих состояний, передающихся по ссылке l в процессе LPi, l ∈ Lij;
natk – интервал времени до создания нового агента k;
ttk – минимальное время, требуемое агенту k для перемещения по любой граничной ссылке в направлении LPj;
obtl – время, требуемое для перемещения от начала ссылки l до соответствующего буферного субрегиона;
obtl – минимальное время, требуемое агенту Ai для перемещения от текущей позиции до буферного субрегиона по любой граничной ссылке в направлении LPj;
sa – логическая переменная, определяющая возможность создания расписания агентов.
Результат:
Предварительный просмотр в направлении LPj.
Initialize lookahead ← maximum double;
// первый случай
if Ai = ∅ then
if sa then
lookahead ← min(natk + ttk);
else
lookahead ← min(obtl);
end
// второй случай
else if ∀l ∈ Lij: Ml = ∅ ∧ Sl = ∅ then
if sa then
lookahead ← min(atj, min(natk + ttk));
else
lookahead ← min(atj, min(obtl));
end
// третий случай
else
lookahead ← one move interval;
end
lookahead ← max(lookahead; one move interval);
3. Ослабленная стратегия взаимного назначения
В этом разделе мы рассмотрим возможность улучшения механизма предварительного просмотра за счет использования неопределенности в симуляции и компромисса в точности моделирования.
3.1. Неопределенность в симуляции
Транспортные симуляторы имитируют поведение участников реального мира, но по понятной причине полностью дублировать его невозможно (даже с учетом суперкомпьютеров) и в этой связи в модели всегда есть неопределенность, которую авторы подразделяют на алеаторную (aleatory uncertainty), связанную с большой стохастической составляющей симулятора и эпистемическую (epistemic uncertainty), являющуюся следствием неполноты знаний о моделируемой системе. Алеаторная неопределенность может быть снижена путем многочисленных прогонов модели со случайно генерируемыми значениями стохастических переменных. Что касается эпистемической неопределенности, то поскольку наши знания об исследуемом процессе никогда не будут всеобъемлющими, то этот вид неопределенности будет иметь место всегда, однако его снижение возможно за счет применения дополнительных инструментов анализа.
Ниже рассматривается возможность использования неопределенности для улучшения процесса синхронизации в параллельном транспортном симуляторе.
3.2. Предварительный просмотр в ослабленной стратегии взаимного назначения
Рассмотрим ситуацию, когда в транспортном симуляторе на граничной ссылке образовалась пробка, и соответственно агенты не имеют возможности перемещаться, а их состояния практически не меняются, но синхронизация, в соответствии с алгоритмом предварительного просмотра на основе взаимного назначения, выполняется довольно часто.
В ряде случаев такая частота может быть избыточной, поскольку некоторые события могут не оказывать заметного влияния на общие результаты симуляции. Кроме того, в силу большого количества стохастических переменных, результаты параллельных вычислений могут заметно отличаться от результатов последовательной версии модели. В этой связи разработчики использовали алгоритм ослабленного предварительного просмотра (relaxed lookahead algorithm), в котором перемещение агентов может быть незакончено к определенному моменту времени, а общие состояния также не обновлены. Таким образом, агенты модели учитывают неактуальные состояния прокси-агентов до следующей синхронизации. С целью уменьшения расхождений между реальными и прокси агентами, для обновления последних используется метод счисления координат (dead-reckoning). На рис. 5 проиллюстрировано возможное расхождение между строгой и расслабленной синхронизацией.
Рис. 5. Эффект использования расслабленной синхронизации: (a) реальный агент B и прокси-агент C' в момент времени t; (b) прокси-агент C' в момент времени t + ∆t, рассчитанный с помощью метода счисления координат; (c) прокси-агент C' в момент времени t + ∆t, обновленный посредством синхронизации; (d) то же, что и (c), но агент C' дополнительно поменял полосу.
Предположим, что агент B является локальным агентом, агент C' – прокси-агент в процессе LP в момент времени t (рис. 5a), а реальный агент C находится в другом процессе. В процессе симуляции, в момент времени t + ∆t (∆t – время перемещения) для агентов B и C рассчитываются их новые состояния. В этот же момент времени, посредством синхронизации происходит обновление прокси-агента C' с использованием общих состояний агента C. Если операция синхронизации не выполняется, C' обновляется с помощью метода счисления координат, но в этом случае может произойти расхождение в состояниях C' (пример показан на рис. 5b и 5c). Расхождение в состояниях агента C' может оказать влияние на расхождение в состояниях агента B в будущем, в зависимости от их относительных положений, скоростей, поведения водителей и ряда других параметров (рис. 5d).
На ослабление предварительного просмотра могут оказать влияние два фактора: метод счисления координат и дорожные условия. В самом простом варианте, в функции счисления координат принимается что агенты (а соответственно и прокси-агенты) двигаются с постоянной скоростью до следующей синхронизации, а несоответствия будут определяться расхождениями с реальными скоростями. Таким образом, предварительный просмотр может быть увеличен в случае незначительных расхождений. Что касается дорожных условий, то они определяются плотностью (density) (количеством транспортных средств на фиксированном участке проезжей части), средней скоростью (speed) движения и потоком (flow) – количеством транспортных средств, пересекающих контрольную отметку за единицу времени.
Зависимости между изменениями скоростей агентов и упомянутыми метриками приведены на рис. 6. Для расчетов использовалась дорожная сеть с двумя ссылками l1 и l2, на первой из которых образуются агенты.
Рис. 6. Изменение скоростей агентов в зависимости от: (a) плотности; (b) средней скорости движения; (c) потока
Значения переменных, измеряющих поток, плотность и среднюю скорость на участке ссылки l1 записываются через определенный интервал.
Для создания различных дорожных условий на l1 разработчики варьировали временем прибытия агентов, ограничением скорости движения и количеством полос на l2. Изменение средней скорости агентов вычисляется по формуле 
, где N – количество агентов на соответствующем дорожном сегменте, v(a, t) – скорость агента a в момент времени t, а ∆t – время передвижения. На рис. 6 видно, что есть статистически значимая корреляция между изменениями скоростей и потоком. Зависимость между изменениями скоростей, плотностью и средней скоростью движения нелинейная, а это является следствием ослабленной синхронизации, и расхождение, скорее всего, будет возрастать по мере увеличения потока.
Модель предварительного просмотра может быть разработана также с учетом потока. Определим windowl,t – временное окно для граничной ссылки l в момент времени t в качестве временного периода, в течение которого синхронизация может быть пропущена без изменения результатов симуляции. Окно рассчитывается следующим образом: windowl,t = α ∙ (1 / flowl,t), где α – параметр, влияющий на горизонт видимости, а flowl,t – поток по ссылке l в момент времени t. Если flowl,t = 0, то windowl,t = mwl, где mwl – максимальное окно. Фактически, 1 / flowl,t – временной промежуток, представляющий собой разницу во времени пересечения двумя транспортными средствами контрольной точки на дороге.
Предварительный просмотр двух процессов соответствует минимальному окну всех граничных ссылок между ними. Поскольку назначения согласовываются всеми участвующими в синхронизации процессами, рассматриваются только исходящие граничные ссылки. Пусть OLij – множество граничных ссылок между процессами LPi и LPj, тогда предварительный просмотр процесса LPi в направлении процесса LPj в момент времени t определяется так: lookaheadij,t = min (windowl,t), l ∈ OLij.
Оптимальное значение параметра α позволяет максимизировать предварительный просмотр и при этом не искажает статистический результат симуляции. Алгоритм определения предварительного просмотра для ослабленной стратегии взаимного назначения приведен в листинге 3. Сначала производится проверка множества локальных агентов: если их нет, то в качестве значения предварительного просмотра устанавливается минимальное значение среди максимальных окон. Если множество не пустое, то последовательно перебираются граничные ссылки и минимальное значение временных окон присваивается предварительному просмотру.
Листинг 3. Определение предварительного просмотра для ослабленной стратегии взаимного назначения
Определения:
Ai – множество агентов в процессе LPi;
OLij – множество граничных ссылок между процессами LPi и LPj;
flowl – текущий поток по ссылке l, l ∈ OLij;
mwl – максимальное окно для ссылки l, l ∈ OLij;
Результат:
Предварительный просмотр в направлении LPj.
Initialize lookahead ← maximum double;
if Ai = ∅ then
lookahead ← min(mwl), l Î OLij;
else
foreach l ∈ OLij do
if flowl = 0 then
lookahead ← min(lookahead, mwl);
else
lookahead ← min(lookahead, α ∙ (1 / flowl,t));
end
end
else
lookahead ← max(lookahead; one move interval);
4. Эксперименты
С целью оценки производительности стратегий взаимного назначения и ослабленного взаимного назначения были проведены эксперименты, в которых отслеживались усредненные значения предварительного просмотра, общее количество отправленных синхронизирующих сообщений и ускорение на уровне всей симуляции. Также было проведено сравнение с методом барьерной синхронизации. Отметим, что в алгоритме определения предварительного просмотра во время взаимного назначения, расписание для создания новых агентов не использовалось, а сама модель была реализована на C++ с использованием с использованием программного интерфейса OpenMPI.
4.1. Настройка
Для модели использовались реальные данные: дорожная сеть Сингапура – 43 392 перекрестков (в модели – узлов) и 83 343 дорожных отрезков (в модели – ссылок) и 124 589 полос движения, а также матрица корреспонденций, построенная на основе данных обследований домашних хозяйств и опросах о путешествиях (Household Interview and Travel Survey (HITS)). Однако для снижения вычислительной нагрузки число агентов было снижено до 75 000, что, конечно же, меньше реального числа перемещающихся в течение дня автомобилей. Первоначальное значение времени интервала перемещения составляет 0.5 сек., распараллеливание вычислительной нагрузки производится только один раз при инициализации модели и в ходе расчетов балансировка не производится.
4.2. Предварительный просмотр и сообщения для синхронизации
Параметр горизонта видимости α оказывает непосредственное влияние на предварительный просмотр и количество сообщений для синхронизации. Средние значения предварительного просмотра симуляции, в которой используется методы MA и RMA с соответствующими значениями α (1.0 для 4 LP, 0.5 для 8 и16 LP, и 0.4 для 32 LP), приведены на рис. 7, а общее число сообщений для синхронизации на рис. 8. Как видно значения предварительного просмотра, получающиеся с использованием метода MA, незначительно превышают один интервал перемещения, а в случае RMA метода – существенно его превышают. Вместе с тем, более высоким значениям предварительного просмотра соответствует меньшее количество синхронизирующих сообщений (для одинакового количества процессов LP, см. рис. 8).
Рис. 7. Средние значения предварительного просмотра симуляции, в которой используется методы MA и RMA
Рис. 8. Общее число сообщений для синхронизации в симуляции (с методами MA и RMA)
4.3. Ускорение
Далее была получена оценка ускорения для стратегий синхронизации с использованием методов MA и RMA по сравнению с методом барьерной синхронизации. Для метода RMA использовались те же значения α (1.0 для 4 LP, 0.5 для 8 и16 LP, и 0.4 для 32 LP), а полученные результаты приведены на рис. 9.
Рис. 9. Ускорение для трех стратегий синхронизации
Соответствующие значения были рассчитаны путем соотнесения последовательной версии модели к ее параллельным реализациям, причем каждая конфигурация прогонялась несколько раз. Имитация одного дня дорожного движения с использованием последовательной версии модели требует приблизительно 4 часа, а реализация параллельных версий с использованием 32 LP занимает от 50 до 70 минут.
Как видно, наибольшую эффективность продемонстрировала реализация параллельной версии с использованием метода RMA. По сравнению с методом барьерной синхронизации, метод MA продемонстрировал прирост производительности в 2.14% (для 4 LP) и 13.6% (для 32 LP), а для метода RMA прирост производительности еще выше – 17.2% (для 8 LP) и 40.7% (для 32 LP). Преимуществом обоих методов перед барьерной синхронизацией заключается в меньшем времени ожидания от LP и сокращении обмена данными за счет отсутствия глобальной связи «каждый – каждому». Оптимизация механизма синхронизации происходит за счет снижения объема передаваемых данных, а также за счет снижения количества пересылаемых сообщений (данные упаковываются в сообщения большего размера).
Более подробно про разработанные стратегии синхронизации можно прочитать здесь: [Xu Yadong, Cai Wentong, Aydt Heiko, Lees Michael, Zehe Daniel (2015): An Asynchronous Synchronization Strategy for Parallel Large-scale Agent-based Traffic Simulations Inproceedings / Proceedings of the 3rd ACM Conference on SIGSIM-Principles of Advanced Discrete Simulation, pp. 259–269, ACM 2015.]
Партнеры
