Лаборатория Параллельных Алгоритмов
и Структур

Заведующий лабораторией: Сергей Владиславович ПИСКУНОВ
[English]

РЕЗЮМЕ.

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

БОЛЕЕ ДЕТАЛЬНО.

Современная технология организации параллельных вычислений опирается на два вида параллелизма: крупноблочный и мелкозернистый. Это деление достаточно условно, но тем не менее можно заметить следующее.
Крупноблочный параллелизм свойственен вычислительным системам, составленным из небольшого числа (десятки, сотни) мощных компьютеров, соединенных сетью связи того или иного вида.
Мелкозернистый параллелизм свойственен вычислительным системам, составленным из огромного числа (десятки, сотни тысяч) относительно простых процессорных элементов. Связи между процессорными элементами регулярны и очень часто (но не всегда!) организованы по принципу близкодействия. Как правило, такие системы узко специализированы. Сам термин "мелкозернистый параллелизм" говорит об элементарности и скоротечности отдельного вычислительного действия. Характерной чертой мелкозернистого параллелизма является примерно одинаковая интенсивность вычислений и обменов информацией.

Мелкозернистый параллелизм имеет давнюю историю: это самая "древняя" разновидность параллелизма. Развитие его теории шло одновременно с развитием теории последовательных вычислений и связано с именем Дж. фон Неймана. Широко известна его теоретическая модель вычислителя с мелкозернистым параллелизмом - клеточный автомат.

В лаборатории широко представлены исследования по мелкозернистому параллелизму.
Привлекательность для нас мелкозернистого параллелизма объясняется тем, что в его рамках часто возможно отыскание наилучших (например, по временным характеристикам) параллельных алгоритмов решения многих практически важных задач как числового, так и нечислового характера. Более того, решение некоторых задач возможно только в рамках некоторой модели мелкозернистых вычислений (например, решение трудно формализуемых задач на нейронных сетях с использованием методов обучения). Практическая важность мелкозернистого параллелизма определяется тем, что он служит источником методов решения задач на современных многопроцессорных вычислительных системах, а также тем, что многие как реальные, так и гипотетические спецпроцессоры являются устройствами с мелкозернистым параллелизмом.

Исследования по мелкозернистому параллелизму, проводимые в
лаборатории.

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

В русле выше сказанного в лаборатории выполняются следующие работы.
  1. Разработка клеточной технологии синтеза параллельных алгоритмов и структур, основанной на модели распределенных вычислений, называемой Алгоритмом Параллельных Подстановок [ENGLISH].
  2. Анализ и синтез многослойных клеточных структур (универсальных (!ссылка 2!) и специализированных (!ссылка 3!)), ориентированных на 3D конвейерные вычисления.
  3. Разработка и исследование ассоциативных параллельных алгоритмов решения задач нечисловой (!ссылка 4!) обработки (в первую очередь, графовых теоретических задач).
  4. Проектирование и исследование распределенных функциональных структур (!ссылка 5!) и построение высокопроизводительных спецпроцессоров на их основе.
  5. Разработка и исследование клеточно-нейронных алгоритмов решения задач обработки изображений (!ссылка 6!), распознавания искаженных образов (!ссылка 7!), дискретной оптимизации (!ссылка 8!).
  6. В мире достаточно активно развиваются исследования, связанные с имитационным моделированием физических явлений в дискретном пространстве (клеточном автомате, клеточно-нейронной сети). Мы не остаемся в стороне от этого направления исследований: выполняется постановка задач, связанных с решением уравнений математической физики на клеточно-нейронных сетях. В частности исследуются клеточно-нейронные сети, моделирующие автоволны и диссипативные структуры (!ссылка 9!).
  7. Исследования мелкозернистого параллелизма выполняются с использованием программных инструментов, разработанных в лаборатории. Для исследования ассоциативных алгоритмов используются системы моделирования на базе языков STAR и VEPRAN (!ссылка 11!). Эти системы пополняются и совершенствуются. Для исследования клеточных алгоритмов и структур (в том числе, нейронных и клеточно-нейронных сетей) применяется система имитационного моделирования ALT (!ссылка 12!). Разрабатывается новая, более мощная система WinALT.
  8. Разработка комбинированных архитектур (!ссылка 14!) вычислительных систем, включающих в свой состав спецпроцессоры с мелкозернистым параллелизмом.
  9. Разработка и исследование ассоциативных алгоритмов для числовой обработки. Эта работа трансформировалась в работу по созданию пакета программ для организации высокоточных вычислений на инструментальных средствах разного типа (!ссылка 15!). В настоящее время она продолжается в лаборатории синтеза параллельных программ (!ссылка 16!).
  10. Очень часто, новое - это хорошо забытое старое. Чтобы двигаться вперед, нужно знать прошлое. В лаборатории выполняется работа по исследованию истории информатики (!ссылка 17!) в России.

ПЕРСПЕКТИВЫ.

Дальнейшие перспективы исследований мы видим:

Последний раз изменения внесены 23 октября 2000.
Ответственная за страницу Эльвира Кукшева.