Параллельное программное обеспечение стало неотъемлемой частью существования современного общества - провал или успех больших проектов или повседневных дел каждого из нас может зависеть теперь от недостаточной эффективности параллельных программ или наличия ошибок в них. Современные подходы к разработке параллельных программ в основном являются архитектурно-ориентированными, когда для достижения эффективной работы создаваемые программы тесно связаны с архитектурами параллельных вычислительных систем, на которых они выполняются и, как правило, разрабатываются. Поэтому требования к квалификации разработчиков параллельных программ весьма высоки, тем более, что протестировать и отладить параллельную программу намного сложнее, чем последовательную, а проблема верификации параллельных программ весьма далека от решения не только практически, но и теоретически. Причем, лишь у узкого круга отечественных пользователей есть доступ к высокопроизводительной вычислительной технике, которая по числу суперкопьютеров и их суммарной мощности весьма уступает имеющейся в развитых странах и сосредоточена в сравнительно небольшом числе мест, вне которых разработка параллельных программ не ведется, но работает основная масса прикладных программистов. Более того, в современной вычислительной технике идет постоянная смена архитектурных парадигм, что, в свою очередь, ведет к проблеме переносимости уже разработанных параллельных программ. Приходится постоянно адаптировать уже созданный продукт под изменившиеся аппаратные средства. Это обуславливается тем, что различные параллельные вычислительные системы имеют свойственные только им ресурсные ограничения, которые необходимо учитывать во время разработки программы. Проведение таких адаптаций является весьма интеллектуальной задачей, требующей существенного переписывания параллельных программ и выполнения практически заново их верификации и отладки. В результате адаптированные параллельные программы зачастую содержат новые ошибки и не являются столь эффективными, как хотелось бы и могли быть. Следует отметить, что для ряда частных случаев проработаны вопросы распараллеливания последовательных программ. Однако изначальное отталкивание от последовательных алгоритмов связано во многих случаях с различными ограничениями, обусловленными спецификой последовательного выполнения операций. Зачастую программист при написании такой программы использует алгоритмы, которые эффективно реализуются на последовательных компьютерах, но плохо поддаются распараллеливанию, тем более автоматическому.
В рамках данного проекта предлагается оригинальный подход к решению задачи повышения эффективности и надежности параллельных программ, связанный с разработкой методов и средств архитектурно-независимого параллельного программирования для поддержки облачных высокопроизводительных вычислений (супервычислений) на основе функционально-потоковой парадигмы и трансформационного подхода. Этот подход требует решения следующих новых научных задач.
- Развитие методов и декларативных средств описания параллельных научных вычислений, и разработка языковых средств конструирования переносимых (архитектурно-независимых) параллельных аннотированных программ, эффективно адаптируемых к конкретным параллельным вычислительным системам (язык Cloud Sisal);
- Исследование и разработка методов и алгоритмов конструирования, верификации и отладки переносимых параллельных аннотированных Cloud-Sisal-программ на персональных компьютерах без потери функциональности и с использованием развитых средств визуализации.
- Исследование и разработка методов и алгоритмов управляемой оптимизирующей трансляции, позволяющей корректно адаптировать переносимые параллельные аннотированные Cloud-Sisal-программы к архитектуре конкретных параллельных вычислительных систем с целью достижения высокой эффективности их исполнения.
Результаты реализации данного проекта обеспечат прикладных программистов эффективными методами и средствами поддержки супервычислений в рамках телекоммуникационных сетей и центров коллективного пользования (ЦКП). Будут разработаны методы и создана экспериментальная версия облачной расширяемой интегрированной визуальной среды параллельного программирования на языке Cloud Sisal, который продолжает традицию предыдущих версий языка SISAL, оставаясь функциональным потоковым языком, ориентированным на написание больших научных программ, и расширяет их возможности средствами поддержки облачных вычислений. Функциональная семантика языка Cloud Sisal гарантирует детерминированные результаты для параллельной и последовательной реализации — то, что невозможно гарантировать для традиционных языков, подобных языку Фортран или Си. Более того, неявный параллелизм языка снимает необходимость переписывания исходного кода при переносе его с одного вычислителя на другой. Гарантировано, что Cloud-Sisal-программа, правильно исполняющаяся на персональном компьютере, будет гарантированно правильно исполняться на любом высокоскоростном параллельном или распределенном вычислителе. При этом, методы аннотированного программирования и конкретизирующих преобразований, используемые в облачной системе, позволят в рамках декларативного стиля программирования настраивать процессы адаптации переносимых параллельных программ на классы задач и архитектуру вычислителя при сохранении их корректности, а также получать более эффективный параллельный код за счет использования при адаптации знаний пользователя о задаче, программе и вычислителе, выраженные в аннотациях.
В рамках создаваемой расширяемой визуальной среды прикладной программист будет иметь возможность через браузер создавать, верифицировать и отлаживать Cloud-Sisal-программу в визуальном стиле и без учета целевого вычислителя, а затем с помощью оптимизирующего кросс-компилятора производить настройку отлаженной программы на тот или другой супервычислитель, доступный ему по сети, с целью достижения высокой эффективности исполнения получаемой параллельной программы, а также передавать построенную программу супервычислителю на счет и получать результаты. Созданная версия облачной среды должна поддерживать исполнение конструируемых параллельных Cloud-Sisal-программ на вычислителях Сибирского суперкомпьютерного центра СО РАН (ССКЦ СО РАН) и быть пригодной для учебных применений.
Выполнен первый этап проекта.
Проведено исследование сложно структурированых классов задач, приводящих к супервычислениям, а также методов и декларативных средств описания и реализации параллельных вычислений, и уточнена реализуемая версия языка SISAL (язык Cloud Sisal) в создаваемой облачной системе параллельного программирования CPPS.
Разработанный язык Cloud Sisal продолжает традицию предыдущих версий языка SISAL, оставаясь функциональным потоковым языком, ориентированным на написание больших научных программ, и расширяет их возможности средствами поддержки облачных вычислений и аннотированного программирования. Функциональная семантика языка Cloud Sisal гарантирует детерминированные результаты для параллельной и последовательной реализации — то, что невозможно гарантировать для традиционных языков, подобных языку Фортран или языку С. Более того, неявный параллелизм языка снимает необходимость переписывания исходного кода при переносе его с одного вычислителя на другой. Гарантировано, что Cloud-Sisal-программа, правильно исполняющаяся на персональном компьютере, будет правильно исполняться на любом высокоскоростном параллельном или распределенном вычислителе. При этом, средства аннотированного программирования, поддерживаемые языком, позволят в рамках декларативного стиля программирования настраивать процессы адаптации переносимых параллельных программ на классы задач и архитектуру вычислителя при сохранении их корректности, а также получать более эффективный параллельный код за счет использования при кросс-компиляции знаний пользователя о задаче, программе и вычислителе, выраженные в аннотациях.
Система CPPS разрабатывается как интегрированная облачная среда программирования на языке Cloud Sisal, которая содержит как интерпретатор, поддерживающий диалоговое взаимодействие с пользователем при построении и отладке программы, так и оптимизирующий кросс-компилятор, осуществляющий построение параллельной программы по ее функциональной спецификации. Проведено исследование моделей аннотированных функциональных потоковых программ, и разработано единое внутреннее теоретико-графовое представление IR (Intermediate Representation) Cloud Sisal программ, которое ориентировано на их семантическую и визуальную обработку и основано на атрибутированных иерархических графах. В рамках этого представления производится сборка Cloud Sisal программ из модулей (как в интерпретаторе, так и в компиляторе) перед их интерпретацией и конструированием параллельных программ. Предполагается, что представления Cloud Sisal программ в виде IR-графов будут демонстрироваться пользователям системы наряду с их текстовыми представлениями и будут использоваться пользователями для целей визуальной отладки Cloud Sisal программ и управляемой их оптимизации.
IR-графы в отличие управляющих графов, обычно используемых в качестве внутреннего представления программ в оптимизирующих компиляторах для императивных языков (таких как языки С или Фортран), выражают не потоки управления, а потоки данных в программах. Они обладают рядом полезных для требуемого внутреннего представления программ свойств, включая следующие.
1. Явно заданные информационные (семантические) связи (дуги) между операндами операций (портами вершин) делают процесс интерпретации осуществимым без дополнительных преобразований. Это влечет отсутствие побочных эффектов вычислений (ввиду отсутствия понятия переменной) — естественного свойства чисто функциональных языков.
2. Явно выражен параллелизм на уровне отдельных информационно независимых операций, не зависящий от машинной архитектуры.
Проведено исследование методов и алгоритмов управляемой оптимизирующей трансляции, позволяющей адаптировать переносимые Cloud-Sisal-программы к архитектуре конкретных параллельных вычислительных систем, разработаны фрагменты кросс-компилятора для языка Cloud Sisal, связанные с поддержкой и визуализацией внутреннего представления Cloud Sisal программ и трансляцией Cloud Sisal программ в их внутреннее представление.
Исследовалась задача автоматического построения наглядного изображения IR-графа Cloud-Sisal-программы, а также наглядного визуального отображения в нем процессов исполнений программы. Данная задача является нетривиальной, так как основным пользователем системы является человек, для которого построенное изображение IR-графа и демонстрируемые его изменения должны обладать рядом свойств, упрощающих процесс понимания потоковой программы и приводящих к корректному представлению пользователя о том, как происходит вычисление в данной программе. Часть из этих свойств является обязательными требованиями к виду изображения, а другая часть имеет вид критериев, по которым следует улучшать изображение.
Основные трудности решения построения наглядного изображения IR графов связаны с тем, что в отличие от стандартной задачи укладки графа на плоскости в IR графе вершины графа соединяются дугами через свои порты, а также то, что они могут иметь разный размер, поскольку вершины-фрагменты должны содержать изображения тех графов, которые вложены в них. Причем, если вопросы укладки графов с вершинами разного размера как-то решены, и универсальные системы визуализации графов, как правило, содержат алгоритмы укладки для некоторых подклассов так называемых простых иерархических графов, то задача укладки графа с портами является полностью новой.
Впервые рассмотрена и решена задача построения изображения иерархического графа с портами. Предложены методы и эффективные алгоритмы наглядного визуального представления IR-графов и их динамических изменений, ориентированных на отладку Cloud-Sisal-программ.
Проведено исследование методов верификации и автоматизации тестирования оптимизирующих компиляторов, разработаны методы и программные средства автоматизации тестирования для проверки преобразований циклов в оптимизирующих компиляторах с языка Cloud Sisal. Разработанные методы автоматизации тестирования основаны на использовании параметрической КС-грамматики, описываемой при помощи особого метаязыка, и ориентированы на порождение синтаксически корректных исполняемых тестов.
Проведено исследование методов и средств облачных супервычислений, разработана начальная версия облачной визуальной системы параллельного программирования CPPS, которая доступна по адресу http://pco.iis.nsk.su/CPPS и состоит из интерпретатора для языка Cloud Sisal, подсистемы регистрации/авторизации и учёта пользователей портала, а также подсистемы хранения пользовательских программ и данных.
Подготовлено 6 публикаций с описанием полученных результатов в рецензируемых изданиях, 3 из которых индексируются в базе данных «Scopus». Сделано 5 докладов на Международных конференциях с представлением полученных результатов.
Выполнен второй этап проекта.
Проведено исследование методов отладки, верификации и визуализации аннотированных переносимых параллельных программ, разработаны методы и средства визуальной отладки Cloud-Sisal-программ и осуществлено включение их в среду параллельного программирования. Впервые предложены методы и алгоритмы наглядного визуального представления иерархических графов с портами и их динамических изменений, связанных с отладкой Cloud Sisal программ. Построена аксиоматическая семантика для представительного подмножества языка Cloud Sisal.
Проведено исследование методов и алгоритмов оптимизирующей трансляции, позволяющей адаптировать переносимые Cloud-Sisal-программы к архитектуре конкретных параллельных вычислительных систем, разработаны методы и фрагменты оптимизирующего распараллеливающего кросс-компилятора для языка Cloud Sisal, связанные с порождением программ на языке C# по IR-представлению Cloud Sisal программ.
Проведено исследование методов статической и динамической визуализации графовых моделей и алгоритмов, разработаны методы и средства визуализации работы компилятора с языка Cloud Sisal и профилирования исполнений оттранслированных Cloud-Sisal-программ. Подсистема визуализации работы компилятора с языка Cloud Sisal разработана как расширение системы Visual Graph, в основе которого разработанные алгоритмы работы с атрибутированными иерархическими графами с портами, представляющие IR- и EIR-графы Cloud Sisal программ.
Проведено исследование методов верификации и автоматизации тестирования оптимизирующих компиляторов. Разработан метод верификации циклических выражений Cloud-Sisal-программ и доказана его корректность. С использованием данного метода проведен успешный эксперимент по верификации Cloud-Sisal-программы, проверяющей, упорядочен ли массив в заданном диапазоне. Разработаны методы и программные средства автоматизации тестирования оптимизаций в Cloud-Sisal-компиляторе.
Подготовлено 10 публикаций с описанием полученных результатов, 5 из которых индексируются в базах данных «WoS» и «Scopus». Сделано 7 докладов на Международных конференциях с представлением полученных результатов.
1. Касьянов В.Н., Касьянова Е.В. Методы и система облачного параллельного программирования // Информатика: проблемы, методология, технология : Сборник материалов XIX международной научно-методической конференции. Под ред. Д.Н. Борисова – Воронеж: Вэлборн, 2019. – С.1552-1556.
2. Касьянов В.Н., Золотухин Т.А., Гордеев Д.С. Методы и алгоритмы визуализации графовых представлений функциональных программ // Программирование, 2019, № 4, c. 19-27.
3. Kasyanov, V. and Kasyanova, E. Methods and system for cloud parallel programming // Proceedings of the 21st International Conference on Enterprise Information Systems (ICEIS 2019), 2019, Vol. 1, pp. 623-629.
4. Kasyanov V.N., Kasyanova E.V., Zolotuhin T.A. Visualization of data-flow programs // Lecture Notes in Electrical Engineering, Springer, 2019, Vol. 574, pp. 119-124.
5. Kasyanov V.N., Kasyanova E.V. Methods and system for cloud parallel programming // 9th International Congress on Industrial and Applied Mathematics (ICIAM 2019): Program & Abstract book, Valencia, 2019, pp. 457-457.
6. Kondratyev D., Promsky A. Proos strategy for automated Sisal program verification // Notes in Computer Science, 2019, Vol. 11171, pp. 113-120.
7. Kasyanov V.N., Zolotuhin T.A., Gordeev D.S. Visualization methods and algorithms for graph representation of functional programs // Programming and Computer Software, 2019, Vol. 45, No. 4, pp. 156–162.
8. Kondratyev D., Promsky A. Automated Sisal program verification with ACL2 // A. P. Ershov Informatics Conference: PSI Conference Series, 12th Edition: Preliminary Proceedings, Novosibirsk: IPC NSU, 2019. pp. 172-185.
9. Kondratyev D., Promsky A. Correctness of Proof Strategy for the Sisal Program Verification // Proceedings of 2019 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2019, pp. 641-646.
10. Касьянов В.Н., Касьянова Е.В. Языковые и программные средства облачного параллельного программирования // IT-технологии: развитие и приложения: Сборник докладов Международной научно-технической конференции, Владикавказ: Изд-во «Терек», 2019, C. 90-98.