Персональные инструменты
Вы здесь: Главная seminar

Семинар кафедры системного программирования

 

 

 

 

 

Ближайшее заседание: понедельник 3 июня 2024 17-00 (онлайн)

Михаил Бахтерев
Декартово замкнутая категория рекурсивных динамических потоков данных

Несмотря на долгую историю развития соответствующих инструментов программирования, разработка программ для систем с распределённой памятью остаётся весьма трудоёмким делом. Если обратиться к формальным языковым моделям вычислений: к лямбда-исчислению последовательных программ и пи-исчислению систем взаимодействующих процессов, -- то легко увидеть причину. Программы в лямбда-исчислении конфлюэнтны, то есть, если результат вычисления существует, он будет получен любой цепочкой вычислительных шагов. Поэтому в лямбда-исчислении можно выбрать стратегию выполнения, и тогда каждое следующее продолжение вычисления будет полностью определяться предыдущим. Процессы, напротив, могут демонстрировать экспоненциальный рост не детерминированных предысторией вариантов продолжения вычисления, не приводящих к одинаковому конечному результату. Программирование для машин с распределённой памятью вынужденно построено на процессных абстракциях, программисты вынуждены включать в программу код для работы с неопределённостью даже при описании детерминированных алгоритмов. В ответ на потребность в более простых средствах программирования систем с распределённой памятью были созданы различные инструменты: Map/Reduce, TensorFlow, DVM, OpenTS, Fortress, Akka и т.п. -- количество инструментов и их востребованность указывают на актуальность проблемы. Большинство из этих инструментов не универсальны. А универсальные предлагают завуалированную модель процессов. Возникает поэтому вопрос: а нельзя ли найти форму записи асинхронных параллельных распределённых вычислений универсальную и детерминированную? Вслед за этим вопросом немедленно возникает следующий: как определить, что предлагаемая модель действительно универсальна? Ведь, код для выполнения на узлах распределённой системы уже должен быть написан на универсальном языке.

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

Вход для онлайн-участия: https://join.skype.com/Dt39yGv7LNhZ


Архив семинара

Заседания 2022/2023 учебного года

Заседания 2021/2022 учебного года

Заседания 2020/2021 учебного года

Заседания 2019/2020 учебного года

Заседания 2018/2019 учебного года

Заседания 2017/2018 учебного года

Заседания 2016/2017 учебного года

Заседания 2014/2015 учебного года

Заседания 2013/2014 учебного года

Заседания 2012/2013 учебного года

Заседания 2011/2012 учебного года

Заседания 2010/2011 учебного года

Заседания 2009/2010 учебного года

Действия с Документом