Кафедра автоматизации систем вычислительных комплексов
Зав. кафедрой – лауреат Государственной премии член-корреспондент РАН Лев Николаевич Королев
Сайт:
E-mail: asvk@cs.msu.su
Тел.: (495) 939-56-34, 939-17-95, 939-17-89
Спец семинар «Системы параллельной обработки экспериментальных данных с использованием нейросетей и генетических алгоритмов»
Руководители:
зав. кафедрой чл.-корр. Л.Н. Королев,
доцент Н.Н. Попова
На семинаре изучаются и исследуются теоретические и прикладные аспекты
применения современных информационных технологий – нейросетей и генетических
алгоритмов – в задачах анализа и прогнозирования поведения сложных систем.
Исследуется возможность реализации таких систем на распределенных и
массивно-параллельных вычислительных системах. На семинаре изучаются современные
Web-технологии, необходимые для построения больших информационных систем. Силами
участников семинара ведется разработка проекта по созданию интеллектуальной,
распределенной системы обработки экспериментальных данных. Темы курсовых и
дипломных работ связны с выполнением этого проекта. На семинаре студенты и
аспиранты выступают с докладами, касающимися изученных статей и монографий и с
изложением собственных результатов по тематике семинара и по актуальным
проблемам информатики. Для студентов третьего курса в пятом семестре проводятся
семинары, на которых изучаются базовые концепции и понятия, связанные с
направлениями работы семинара. Семинар имеет собственную локальную подсеть,
состоящую из сервера – рабочей станции Sun UltraSparc и нескольких персональных
компьютеров.
Спец семинар «Вопросы распределенной обработки информации»
Тематика семинара посвящена исследованиям по следующим направлениям:
Инструментальные средства программирования специализированных и высокопроизводительных ЭВМ (кросс-системы, кросс-трансляция, кросс-отладка и пр.).
Автоматизация построения средств оптимизации программ и генерации кода (архитектуры вычислительных систем, алгоритмы распараллеливания, адекватность алгоритмов оптимизации архитектуре вычислительных систем и пр.).
Практические аспекты применения распределенных технологий при создании информационных систем (телекоммуникации, клиент/сервер, базы данных и пр.).
Алгоритмы и методы информационного поиска.
В рамках семинара выполняются практические проекты по созданию программных
систем, как для российских, так и зарубежных заказчиков. Некоторые из созданных
программных продуктов широко используются в США, Канаде и Западной Европе.
Лаборатория вычислительных комплексов
заведующий лабораторией – Руслан Леонидович Смелянский
Лаборатория вычислительных комплексов была образована как научное подразделение
факультета вычислительной математики и кибернетики Московского государственного
университета им. М.В. Ломоносова в 1982 году. Лаборатория является
самостоятельным структурным подразделением факультета вычислительной математики
и кибернетики, подчиненным непосредственно заведующему кафедрой АСВК.
Основные задачи Лаборатории вычислительных комплексов:
Проведение фундаментальных теоретических и экспериментальных исследований в области анализа структур вычислительных комплексов, методов организации на них вычислительного процесса.
Разработка алгоритмов и программ, создание макетов вычислительных комплексов, участие в выполнении комплексных работ, связанных с использованием параллельных вычислений в различных областях жизни.
Разработка методов и средств для сравнительного анализа структур вычислительных комплексов в зависимости от выбираемого класса задач.
Внедрение разработанных методов, алгоритмов, программ и макетов аппаратуры в научные и промышленные предприятия и в вузы.
Организация проведения в лаборатории производственной практики, курсовых и дипломных работ студентов факультета ВМК.
Основные научные направления лаборатории:
Формальные модели функционирования мультипроцессорных вычислительных систем.
Основной отличительной особенностью разрабатываемых моделей является поддержка
так называемого комплексного подхода к анализу функционирования
многопроцессорных вычислительных систем с распределенным управлением.
Основная идея разрабатываемого комплексного подхода заключается в:
описании аппаратных, программных средств и их функционирования единой трехкомпонентной алгебрологической структурой, состоящей из:
физической среды (аппаратных средств);
логической среды (системных программ);
рабочей нагрузки (прикладных программ);
введение соответствующих операций над носителями для отдельных компонент и между компонентами;
использовании одной и той же записи модели как для исследования количественных, так и логических свойств анализируемых/проектируемых объектов.
Разрабатываемые модели позволяют в рамках единого подхода развивать следующие
теоретические и прикладные направления: синтез и оптимизация архитектур,
исследование поведения программ, оценка производительности вычислительных
систем, спецификация и верификация поведения программ, моделирование и анализ
функционирования вычислительных систем, планирование параллельных вычислений.
Синтез и оптимизация архитектур мультипроцессорных вычислительных систем реального времени.
В рамках данного направления разрабатываются два подхода:
Подход обобщения и нисходящего анализа. Подход основан на анализе общности между прикладными алгоритмами рабочей нагрузки, построении и проведении анализа максимально параллельных моделей вычислений, алгоритмов, архитектур и получении оптимальных архитектур для конкретных приложений как частного случая обобщенных максимально-параллельных архитектур. Данный подход может быть строго формализован лишь для конкретного класса прикладных алгоритмов. Например, результаты применения данного подхода для цифровой обработки приведены в работах.
Подход синтеза архитектур, основанный на информации о поведении программ. Данный подход, формализован для общего случая и позволяет получать оптимальные специализированные мультипроцессорные архитектуры по заданному фиксированному набору прикладных алгоритмов и временным ограничениям на их выполнение.
Методы и средства планирования параллельных вычислений. Расширение существующих компиляторов средствами генерации параллельных программ.
В рамках данного направления разрабатываются и исследуются как статические, так
и динамические методы планирования параллельных вычислений:
эвристические методы, основанные на понятиях идеальной и оптимальной параллельных программ;
подходы, основанные на методе ветвей и границ и основной теореме динамического программирования;
генетические алгоритмы и алгоритмы отжига;
списочные расписания.
Для статического распараллеливания программ разрабатывается
модульно-адаптируемая технология генерации кодов параллельных программ, основной
отличительной особенностью которой является автоматическая оптимизация структуры
параллельной программы на языке высокого уровня с использованием глобальных
характеристик, применение существующих компиляторов последовательных программ
для генерации кода отдельной ветви и возможность модульно независимой адаптации
к языку программирования, архитектуре и способу взаимодействия ветвей.
Методы и средства моделирования, оптимизации и оценки характеристик мультипроцессорных вычислительных систем без создания аппаратного прототипа.
В рамках данного направления разрабатываются:
Принципы построения среды моделирования, исследования и оптимизации вычислительных систем: компоненты среды, их взаимодействие, основные типы фиксируемых событий и состояний.
Язык описания программных и аппаратных компонентов вычислительных систем.
Методики и средства оценки времени выполнения процесса: точный метод частичной имитации, основанный на статико-динамическом анализе программ; грубый метод, основанный на использовании меры вычислительной сложности процесса.
Эргономичные средства визуализации поведения компонентов вычислительных систем.
Нейронные сети.
Основное внимание в данном направлении уделяется:
Методам получения оптимальных (по числу нейронов и ошибке) нейроструктур для заданного класса прикладных задач.
Методы вычисления характеристик прикладных задач не заданных на регулярных сетках.
Методы оценки временной сложности вычислений на вычислителях с различной архитектурой.
При выборе той или иной вычислительной системы для решения прикладных задач
пользователи неизбежно сталкиваются с вопросом: насколько данная система
удовлетворяет классу решаемых задач. Основой при ответе на этот вопрос служат
различные характеристики производительности. Как показывает накопленный опыт,
многообразие вычислительных систем, отличных по архитектуре, чрезвычайно
затрудняет использование в качестве средства сравнения единой меры
производительности.
Время выполнения программы на вычислителе - это мера, естественная с точки
зрения восприятия человеком и универсальная при сравнении вычислителей любой
архитектуры. Однако трудность получения значения времени, затрачиваемого на
выполнение некоторой вычислительной работы, состоит в том, что необходимо
выполнить программу (набор программ) на каждой из сравниваемых вычислительных
систем. А это может быть или слишком дорого (например, для сложных
"параллельных" вычислительных систем), или практически недоступно (при наличии
только проекта архитектуры).
В силу указанных выше особенностей становится актуальной задача разработки
методики прогнозирования времени выполнения программ на различных вычислительных
системах.
Нами предложен комплексный статико-динамический подход для решения задачи
прогнозирования времени выполнения последовательных вычислений, позволяющий
получать высокую точность прогнозирования. Новизна подхода заключается в том,
что метод использует статический анализ текста программы с целью получения
временных оценок для линейных фрагментов вычислений, которые затем
корректируются динамически в ходе прогона программы. При прогнозировании
осуществляется частичная имитация работы устройств целевого вычислителя, однако
эмуляция не производится.
Исследованы несколько классов целевых вычислителей (CISC, векторно-конвейерные,
RISC) и построены соответствующие модели. Для каждого класса вычислителей
предложены средства для параметрического описания архитектуры вычислителя, что
позволяет реализовать многоцелевую инструментальную систему прогнозирования
времени выполнения вычислений.
Исследование эффективности методов синхронизации в распределенных системах дискретно-событийного имитационного моделирования.
В рамках данного направления исследуются и разрабатываются соответствующие
алгоритмы временной синхронизации модельных процессов.
В настоящее время проводится исследование эффективности различных консервативных
и оптимистических алгоритмов синхронизации. Основными критериями являются
отношение полезного к общему времени работы модели, количество одновременно
обрабатываемых событий для консервативных алгоритмов, отношение общего числа
сообщений к числу контр-сообщений для оптимистических алгоритмов.
Сделана экспериментальная реализация распределенной системы имитационного
моделирования ДИАНА на основе консервативного алгоритма синхронизации
Chandy-Misra.
Моделирование и анализ функционирования вычислительных сетей.
Основные цели моделирования:
Выбор оптимальной конфигурации вычислительной сети при ее создании или модернизации (расширение).
Оптимальное управление сетью.
Модель сети представляет собой совокупность моделей элементов сетевой
архитектуры: серверов, клиентов, мостов, коммутаторов, концентраторов, линий
передачи данных и т.д. Модель каждого такого элемента собирается из моделей
соответствующих протоколов согласно семиуровневой модели OSI/ISO.
Модели позволяют получать следующие характеристики вычислительной сети:
время отклика (время выполнения запросов) на прикладном уровне;
реальную пропускную способность сети на любом из уровней;
отношение полезного трафика к общему;
эффективность алгоритмов маршрутизации.
Спецификация и верификация логических свойств программ.
В рамках данного направления рассматриваются два подхода:
Подход, основанный на темпоральной логике. В этом подходе моделью процесса является конечная система переходов. В качестве спецификации выступает формула темпоральной логики линейного или ветвящегося времени.
Подход, основанный на исчислении взаимодействующих процессов Р.Миллнера (CCS). В этом подходе процессы строятся из атомарных процессов при помощи набора алгебраических операций. Спецификацией при этом считается уравнение над данным набором операций, которому должны удовлетворять специфицируемые процессы. Проверка спецификации сводится к выводу такого уравнения их аксиом исчисления процессов.
Основное внимание в данном направлении уделяется разработке эвристических
методов верификации логических свойств программ с целью достижения практически
приемлемой сложности.