Специалисты исследовательской лаборатории компании IBM в г. Токио совместно с учеными Токийского технологического института разработали платформу для построения крупномасштабных симуляторов транспортных потоков с использование нового языка для параллельного программирования X10. Эксперименты с разработанными моделями для более 100 городов всего мира продемонстрировали практически линейный прирост производительности в зависимости от числа используемых процессорных ядер.

Помимо упомянутой платформы был разработан симулятор транспортных потоков, называемый Megaffic (от IBM Mega Traffic Simulator), в котором также используется язык программирования X10, разработанный для параллельного программирования, по сути представляющий собой расширение языка Java с дополнительной поддержкой массивов и процессов, а также разделяемого глобального адресного пространства.

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

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

Рис. 1. Конструкция симулятора Megaffic

Программная инфраструктура на основе X10 с использованием агентного подхода (X10-based Agent eXecutive Infrastructure for Simulation (XAXIS)) –платформа для имитационного моделирования с использованием крупномасштабных агентных моделей и нового языка для параллельного программирования X10. Этот язык – разработка исследовательской лаборатории компании IBM, позволяющий конструировать высокопроизводительные приложения в распределенных системах с различной конфигурацией. В Х10 используется разделенное глобальное адресное пространство (Partitioned Global Address Space (PGAS)) и, таким образом, вся память вычислительной системы делится на логические разделы, каждый из которых локален для какого-то процесса или потока. В Х10 используется концепция при которой выполняемая задача может порождать подзадачи, которые, в свою очередь также могут порождать подзадачи. При этом, подзадачи не могут ожидать завершения работы от породивших их задач, но возможно обратное ожидание. Такая концепция оптимизирует время простоя системы.

Архитектура XAXIS

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

Рис. 2. Архитектура XAXIS

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

Симулятор транспортных потоков XAXIS реализуется в основном на TSUBAME 2.0 – суперкомпьютере петафлопсного класса с гетерогенной архитектурой, находящемся в Международном научно-информационном вычислительном центре Токийского технологического института (Global Scientific Information and Computing Center, Tokyo Institute of Technology). Также отметим, что данный суперкомпьютер постоянно находится в топе мирового рейтинга «зеленых» суперкомпьютеров (т.е. наиболее энергоэффективных).

Виртуальная проекция дорожной сети Японии включает в себя 2 552 160 дорожных отрезков и 993 731 перекрестков. В свою очередь TSUBAME 2.0 содержит 52 ГБ на 1 узел, что позволяет хранить всю дорожную сеть в памяти. 

Для увеличения производительности симулятора дорожная карта Японии, с помощью сторонней утилиты (METIS), была разделена на 100 областей с равномерным количеством перекрестков (в среднем по 10 000), а при тестировании приложения использовалось 100 узлов суперкомпьютера с 1200 ядрами. В рамках одной симуляции осуществлялось 3600 шагов (условно соответствующих одному часу) и около 180 000 поездок. На рис. 3 показано время выполнения симуляций для всех 100 областей, где среднее время выполнения составило 269,95 секунд. Несмотря на то, что число перекрестков для всех областей было примерно одинаковым, для некоторых из них, к примеру, для № 5 (Осака), №12 (юго-восточная часть г. Нагоя и префектура Айти), №46 (Хоккайдо с административным центром – Саппоро), №72 (префектура Фукуока с одноименным центром) потребовалось заметно больше времени для исполнения. Это связано с более плотным трафиком, и, как следствие, с большим числом агентов в данных областях. Решением проблемы может быть дополнительное разделение сложных областей на подобласти, используя METIS. 

Рис. 3. Время выполнения симуляций для 100 областей дорожной сети Японии, в секундах

Далее были проведены симуляции для дорожных сетей наиболее крупных 127 городов мира (Сингапур, Лондон, Мехико и др.) с использованием карт проекта OpenStreetMap. На рис. 4 приведены результаты для 1 000 шагов и 50 000 поездок, где на оси абсцисс отложены ID городов, а на оси ординат – время в секундах. Отметим, что размерности виртуальных дорожных сетей варьируются от десятков тысяч до двух миллионов перекрестков. 

Рис. 4. Время выполнения симуляций для рассматриваемых городов мира

На рис. 5 отображен результат работы симулятора для Рио-де-Жанейро, сконвертированный с помощью Megaffic в область просмотра для наблюдения передвижений транспортных средств.

Рис. 5. Визуализация симуляций для Рио-де-Жанейро

Более подробно про симулятор XAXIS можно прочитать здесь.