?
Применение параллельных вычислений для решения задач планирования движения поездов метрополитена
Конечной целью автоматизированного построения планового графика движения (ПГД) пассажирских поездов на Московском Метрополитене является получение траекторий движения всех маршрутов при соблюдении:
- заданных параметров и ограничений;
- заданной парности движения, которая может изменяться во времени;
- правил ночной расстановки составов;
- графика оборота электроподвижного состава;
- устойчивости к воздействию возмущающих факторов;
- рациональности с точки зрения выбранных критериев.
Для достижения поставленной цели осуществляется разбиение процедуры построения ПГД на множество процессов, каждый из которых ассоциируется с происходящими в течении рабочего времени на линии метрополитена процессами. С целью реализации процедуры построения ПГД используется детализация операций, происходящих в процессе жизнедеятельности метрополитена. Прямое использование узкоспециализированных (простых) операций приводит к излишней сложности алгоритмов построения ПГД.
Существует два способа укрупнения операций: групповые и комплексные операции. Основным отличием групповых операций от комплексных заключается в количестве используемых типов простых операций во время обработки данных. Групповые операции используют один тип простой операции, многократно повторяя ее для множества подобных объектов. Комплексные операции используют более одного типа простых операций. В дополнение к простым операциям, комплексные могут использовать в обработке данных групповые.
Такой подход к распределению сложности построения ПГД позволяет гибко менять алгоритмическую составляющую любой операции, не вмешиваясь в логику обработки каждого процесса в отдельности. Любые изменения алгоритма конкретной операции скрытым образом вносятся во все, которые на ней базируются. Это позволяет при работе над отдельной операцией абстрагироваться от особенностей обработки данных, в которых она задействуется или которые она использует.
Создана одна выделенная операция, называемая базовой. Главное ее назначение заключается в абстрагировании методов взаимодействия с любой другой операцией. Базовая является шаблоном для организации всех остальных операций.
Обобщения имеющихся знаний об устройстве операций работы над нитками и имеющихся алгоритмах их автоматизации, многоуровневое
исследование процесса автоматизированного построения ПГД позволяет провести анализ возможности ввода параллельных вычислений.
Одновременно для реализации преимуществ от использования параллельных вычислений необходимо решить проблемы, связанные с синхронизацией работы потоков. Эта задача подразумевает защиту потоков от взаимного влияния на совместно используемые ресурсы. Для решения данной задачи требуется установить атомарные операции, которые влияют на ресурсы в ходе выполнения программного обеспечения. С другой стороны, знание атомарных операций позволяет строить приложения с большей производительностью, так как при написании программного кода появляется возможность избегать обращения к разделяемым ресурсам в одно и то же время из разных потоков. Отличительной чертой задачи автоматизации планирования движения поездов является то, что в ней существует широкое множество атомарных операций, обладающих указанным свойством, что делает актуальным реализацию программного обеспечения средств автоматизации с использованием параллельных вычислений.
Однако для того, чтобы использовать параллельные вычисления также потребуется изучить имеющиеся разделяемые данные. Это представляет интерес ввиду опасности использования таких данных разными потоками примерно в одно и то же время. Опасность заключается в их повреждении или неправильной интерпретации одним из потоков, что может привести к недопустимым ошибкам при вычислениях.
Когда будет определен полный перечень разделяемых данных потребуется произвести их защиту от негативного влияния потоков. Для этого потребуется осуществить сравнение различных способов их хранения с целью минимизации возможных пересечений вычислительных процессов во время исполнения алгоритмов и или сравнить различные способы реализации потоковой системы проекта с целью минимизации возможных пересечений. Оставшиеся пересечения необходимо разграничить с помощью механизма синхронизации потоков.
После разграничения данных потребуется формализовать предлагаемое хранение данных, а также организацию взаимодействия между потоками. Сделать это необходимо с целью последующего синтеза получившихся примитивов обратно в цельный проект для получения общего представления о предлагаемой архитектуре нового программного продукта.
