автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Инструменталные средства для визуализации структур параллельных ЭВМ

Р Г 6 од

НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ О / ИОН 1:ЯЙЧИСЛИТЕЛЬНЫИ ЦЕНТР МГУ

На правах рукописи

ЦЕРЕТЕЛИ Паата Андреевич

УДК 681.3

ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ДЛЯ ВИЗУАЛИЗАЦИИ СТРУКТУР ПАРАЛЛЕЛЬНЫХ ЭВМ

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕР АТ

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 1993

Работа выполнена в Институте вычислительной математик Российской академии наук

Научный руководитель — член-корреспондент РАН,

профессор В. В. ВОЕВОДИН

Официальные оппоненты — доктор технических наук,

профессор О. Б. АРУШАНЯН — кандидат физико-математических наук С. А. КРАСНОВ

Ведущая организация — Институт проблем кибернетики РАН

Защита диссертации состоится «Л » _1993 ]

в. -1$_ часов на заседании специализированного совет

К-053.05.84 при Научно-исследовательском вычислительном центр МГУ по адресу: 119889, г. Москва, ГСП, Ленинские горы, НИВ1 МГУ.

С диссертацией можно ознакомиться в библиотеке НИВ! МГУ.

Автореферат разослан «_»_1993 г.

Ученый секретарь специализированного совета к. ф.-м. н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Работа посвящена проблеме согласования структур численных алгоритмов и вычислительных систем, являющейся в настоящее время исключительно. важной для современных параллельных вычислительных систем.

Для достижения высокой эффективности выполнения программы необходимо обеспечивать во время ее реализации загруженность большинства исполнительных устройств, что влечет за собой необходимость учета . структурных особенностей используемых вычислительных средств. Это требование, в свою очередь, порождает ряд новых проблем. Одна из них связана с тем, что подавляющая часть существующих алгоритмов разработана для последовательных ЭВМ. Поэтому необходимо заново переписывать их для каждого типа параллельных ЭВМ с учетом их особенностей или разрабатывать новые алгоритмы. На первый план здесь выходит проблема автоматизированного переноса программ с одного типа параллельных машин на другой. Прямой перенос без потери эффективности в большинстве случаев невозможен, потому что, как' правило, необходимо осуществлять глубокую переработку программ и алгоритмов.

Согласование структур алгоритма и ЭВМ частично выполняет оптимизирующий компилятор, но большую часть такой работы пользователь вынужден осуществлять вручную. Для этого он должен хорошо понимать как структуру алгоритма, так и организацию работы ЭВМ. Учитывая накопленный алгоритмический багаж, можно сказать, что выполнение этой работы вручную требует больших затрат. Именно поэтому проблема автоматизации процесса согласования структуры алгоритмов со структурами вычислительных систем является актуальной.

Одним из путей решения этой проблемы является совместное исследование вычислительных систем и алгоритмов. Для этого в первую очередь необходимо выбрать взаимосвязанные средства их описания -язык описания структуры алгоритма и язык описания структуры вычислительной системы. Они должны предоставлять возможность задавать и распознавать различные свойства объектов, сравнивать и преобразовывать их описания. При удачном подборе таких средств можно было бы на уровне описаний алгоритмов и вычислительных систем проводить их согласование, возложив всю эту работу на ЭВМ. На первом

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

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

Цель работы

1. Разработать язык описания структуры (ЯОС) вычислительной системы. Язык должен давать возможность идентифицировать основные конструктивы ЭВМ (функциональные устройства, процессоры, регистры, каналы и др.), описывать каналы передачи данных и указывать некоторые технические характеристики. Количество и тип этих характеристик определяются требованиями процесса согласования.

2. Разработать информационную систему по структурам вычислительных систем. Входными данными для нее должны быть описания семейств вычислительных систем на ЯОС. Система должна с помощью изображений на экране монитора показывать структуру вычислительной системы и ее составных частей, выдавать их технические характеристики, пояснения и другую вспомогательную информацию.

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

Научная новизна. Полученные результаты, а именно: математические модели представления структуры вычислительной системы, язык описания структуры вычислительной системы и информационная система по структурам вычислительных систем -являются новыми.

Практическая ценность. Результаты исследований имеют как теоретическое, так и практическое значение. Разработанная

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

Результаты исследований внедрены и используются при реализации проекта "Разработка математических методов и программных средств для визуального анализа параллельной структуры программ и алгоритмов", выполняемого НИВЦ МГУ в рамках научно-исследовательской программы Министерства науки, высшей школы и технической политики РФ "Научная программа по направлению применения перспективных информационных технологий в науке и технике".

Апробация работы. Результаты исследований докладывались на научно-исследовательских семинарах отдела численного анализа НИВЦ МГУ, Института вычислительной математики РАН и Института проблем кибернетики РАН.

Публикации. По теме диссертации опубликованы 3 статьи.

Структура и объем работы. Диссертация состоит из введения, трех глав и приложения. Общий объем 130 страниц, включая 19 рисунков. В списке литературы 96 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

Глава 1 посвящена вопросам взаимосвязи алгоритмов и вычислительных систем.

1-2

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

В параграфе 2 приведены некоторые сведения из теории построения математических моделей алгоритмов. Алгоритмы хорошо описываются графами. Исследуя гра$ы алгоритмов, можно оценить время реализации алгоритма, объем требуемой памяти, найти параллельные формы, удовлетворяющие определенным условиям.

В параграфе 3 рассматриваются вопросы согласования структуры вычислительной системы и алгоритмов. На компьютере с большим числом параллельно работающих устройств нельзя эффективно реализовывать любые алгоритмы. Быстро реализуются лишь те совокупности операций, которые либо не связаны между собой по информации, либо связаны специальным образом, соответствующим быстрым связям коммуникационной сети конкретного компьютера. Эффективная реализация конкретного алгоритма на конкретном компьютере во многом зависит от степени представления алгоритма через те специальные операции, которые наиболее успешно реализуются на компьютере. На компьютерах разной архитектуры специальные операции разные.

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

Глава 2 посвящена' моделям представления структуры вычислительной системы и языку описания структуры вычислительных систем.

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

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

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

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

1-3

элементов вычислительной системы, идентифицируемые в НОС и соответствующие наборы характеристик.

1. Функциональное устройство - пиковая производительность, длина слова, длина конвейера, время цикла, время обработки вектора в зависимости от его длины,

2. Процессор - пиковая производительность, длина слова, время цикла, объем локальной памяти процессора, количество одновременно работающих устройств внутри процессора.

3. Регистр - объем, длина слова, длина вектора.

4. Память - объем, длина слова, время доступа, количество банков памяти.

5. Сеть. Характеристики для нее определяются не в ЯОС, а во время создания изображения топологии сети.

6. Канал передачи данных - кратность и тип канала (симплексный, дуплексный, полудуплексный), ширина, пропускная способность, время передачи цепочки данных в зависимости от ее длины, число и тип активных каналов.

7. Неопределенное устройство. Этот тип устройства введен для идентификации того элемента вычислительной системы, который не попадает ни в один из вышеперечисленных типов. Для него не предусмотрены какие-либо характеристики из-за его неопределенности.

Приведем некоторые основные понятия языка.

ИОеншфшаторы. Допускаются следующие типы идентификаторов.

1. Идентификатор устройств и узлов. Он состоит из корня и индекса. Индекс предназначен для того, чтобы указывать имя устройства и различать идентификаторы одинаковых устройств. Индекс в идентификаторе может отсутствовать". Корнем идентификатора может быть один из следующих символов: Г, Р, И, М, и, Б, определяющий тип устройства (соответственно: функциональное устройство, процессор, регистр, память, неопределенное устройство, сеть). Допускается использование нескольких модификаторов, указывающих, например, конвейерность вычислительного устройства, тип регистра, уровень иерархии и др. Примеры: Р1, 1Г\"Ас1с1"\2, ОТ, М\\2. Идентификатором процессора может также быть и имя компьютера.

Возможно также идентифицирование элемента внутри вычислительного узла. Такой идентификатор называется идентификатором с расширением и состоит из идентификатора узла и идентификатора элемента, разделенных точкой. Например, Р1.8ИУ - блок из 8 регистров процессора с идентификатором Р1.

2. Идентификатор канала состоит из двух символов, которые соответствуют типам устройств, соединяющихся этим каналом. Это символы: р (функциональное устройство или процессор), г (регистр), т (память), и (неопределенное устройство), з (сеть). Примеры: рт -канал процессор-память; та - канал регистр-память.

Группы устройств образуются устройствами одного типа указанием коэффициента перед идентификатором или перечислением в фигурных скобках идентификаторов. Примеры: 4Р\"СРи", {8RV.8RS.8RA}, {Р1,М\\1,Р2). Простой идентификатор' также можно считать группой устройств.

Соединения между двумя группами устройств определяется соответствующими конструкциями групп, соединенными символом

Описание канала состоит из идентификатора канала, символа '=' и перечисления соединений между группами. Типы каналов, определенные идентификатором канала и соединениями между двумя группами, должны совпадать. Характеристики канала указываются как значения ключевых параметров. Они могут отсутствовать. В конце всей конструкции ставится Например, рг=8НУ-М1(Ъ=8Ш,1?=64). Существуют также

различные модификации описания канала.

Описание структурного элемента вычислительной системы состоит из спецификации, пояснения и тела элемента. В спецификации указываются идентификатор элемента и, в качестве значений ключевых параметров, его технические характеристики (аналогично описанию канала). Тело описания для узла содержит описание каналов передачи данных, соединяющих структурные элементы узла, а также некоторые специальные записи. Оно для устройств - пусто. Пояснение есть текст, помещенный между символами "". В нем дается дополнительная информация, относящаяся к данному элементу вычислительной системы. Из этих составных частей описания элемента обязательным является идентификатор, остальные могут отсутствовать. Примеры: НУ(1=64, е=128):; Р1\"Ехатр10и(у=12Ош1,з=1МЬ,1=б4): "Процессор состоит из векторной и скалярной части" рг=1Р\"Уес1;ог"-8Н7, Р\"Зса1аг"-8ПЗ; рт={8НУ,8ЕЗ}-М,

Описание структуры вычислительной системы состоит из описания элементов вычислительной системы, соответствующих вершинам иерархической модели. В одном файле, представляющем собой фрагмент текста на ЯОС, могут быть описаны несколько компьютеров. Их имена

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

Глава 3 посвящена описанию информационной системы по структурам вычислительных систем. Входными данными для системы являются файлы с описанием структуры ЭВМ на ЯОС. Интерпретируя эти записи ЯОС, система строит изображения различных узлов вычислительной системы. Показ структуры осуществляется согласно иерархической модели. Пользователь может рассмотреть все элементы ЭВМ (вершины графа иерархической модели), начиная с выбранной корневой вершины и передвигаясь по дугам графа. Изображения узлов строятся по канальной модели. Система выдает технические характеристики .структурных элементов и каналов передачи данных, а также дополнительную информацию. Кроме того, она выдает информацию об особенностях вычислительных систем и тех требований и ограничений, которые накладываются на алгоритмы для достижения высокой эффективности.

В параграфе 1 приведены визуальные изображения, которые выводятся на экране во время просмотра структуры вычислительной системы. Все визуальные изображения, кроме изображения топологии динамической и статической сети, строятся на основе анализа записей на ЯОС. Изображения топологий заранее подготавливаются и хранятся в отдельных файлах. Информационная система включает в себя средства создания этих файлов.

В параграфе 2 описывается работа информационной системы и ее структура. Обсуждаются вопросы, связанные с применением информационной системы в учебных целях. Работа системы начинается с составления таблицы кратких характеристик описанных семейств вычислительных систем. Пользователь может либо выбрать нужный ему компьютер, либо перейти в режим просмотра учебного материала, либо получить информацию об особенностях данного семейства компьютеров и накладываемых ограничений. При выборе компьютера информационная система начинает считывание файла и первичную его обработку. На этом этапе извлекаются все необходимые данные из описания вычислительных систем на ЯОС.

Следующий этап работы - вывод таблицы описанных модификаций. По

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

Команды информационной системы позволяют выбрать новый вычислительный узел и просмотреть его структуру, возвратиться к предшествующему узлу, получить характеристики изображенного узла, получить информацию о производительности изображенного узла на реальных программах, получить информацию о временах ' выполнения отдельных операций и вычислительных конструкций, выбрать элемент изображенного узла и получить его характеристики, выбрать канал передачи данных и получить его характеристики, получить изображение топологии сети.

Для применения информационной системы в процессе обучения пользователю предоставляется возможность подготовить учебный текст. Он является обычным текстовым файлом, созданным с соблюдением определенных правил, которые позволяют выделить в тексте некоторые фрагменты, создать оглавление, включить в текст динамические иллюстрации. По оглавлению можно переходить к отдельным фрагментам текста. Динамические иллюстрации являются отдельными программами, которые готовятся независимо от информационной системы и языка, а в тексте указывается имя этой программы. Кроме того, разработанная версия информационной системы содержит описания на ЯОС 21 семейств вычислительных систем (таких, как СDC CYBER, CRAY-X, Fujitsu VP, NEC, FPS и др.). Они также могут быть использованы в процессе обучения.

В приложении приведен язык описания структуры ЭВМ в нормальной форме Бэкуса.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Для целей согласования структур численных алгоритмов и ЭВМ предложены модели представления структуры вычислительной системы, которые охватывают большинство существующих типов параллельных ЭВМ.

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

-iQ-

3. Разработана и реализована на IBM PC информационная система по структурам вычислительных систем. Она с помощью изображений, которые строятся на основе интерпретации записей на ЯОС, показывает структуру ЭВМ, выдает информацию о ее особенностях и характерных данных, дает общие рекомендации с целью адаптации программ для данного типа ЭВМ. Для применения информационной системы в учебных целях в ней реализована возможность подготовки и выдачи на экране монитора учебного материала, а также динамических визуальных иллюстраций.

Результаты диссертации опубликованы в следующих работах:

1. Церетели П.А. Обзор структур вычислительных систем // Архитектура ЭВМ и вычислительные методы. - М.: ОВМ АН СССР, 1991, -С.101-119.

2. Церетели П.А. Принципы построения средств математического описания структуры вычислительной системы. - М., 1992. - 24с. (Препринт ИВМ РАН N 286).

3. Церетели П.А. Информационная система по структурам ЭВМ // Матричные методы и алгоритмы. - М.: ИВМ РАН, 1993, - С.112-123.