Содержание к диссертации
ВВЕДЕНИЕ 5
ГЛАВА 1. АРХИТЕКТУРА СОВРЕМЕННЫХ ПОТОКОВЫХ
ВЬНИСЛИТЕЛЬНЫХ СТРУКТУР 13
Место потоковых ЭВМ среди параллельных вычислительных машин 13
Программирование ЭВМ управляемых потоком данных .... 16
Потоковые программы 16
Языки программирования ЭВМ УПД 21
1.3 Архитектура ЭВМ УПД 23
Процессорный элемент 23
Коммуникация 28
1.4 Обзор существующих ЭВМ УПД 33
Машины с непосредственной коммуникацией ... 33
Потоковые машины статической архитектуры
с пакетной передачей 35
Машины с копированием кодов 38
Машины с тегированием токенов 39
Машины с одновременным использованием тегирования токенов и копирования кодов ... 41
1.5 Постановка задачи исследования производительности
ЭВМ УПД статической архитектуры 42
1.5.1 Основные параметры задач, решаемых
на ЭВМ УПД 42
Структуры потоковых ЭВМ статической архитектуры 44
Постановка задачи 51
1.6 Выводы 54
ГЛАВА 2. ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ ПОТОКОВЫХ ВЫЧИСЛИТЕЛЬНЫХ СТРУКТУР ПРИ предельной загрузке
ПРОЦЕССОРОВ 56
2.1 Исследование производительности потоковых машин
при слабой загрузке процессоров 56
2.2 Исследование производительности потоковых машин
при сильной загрузке процессоров 59
ЭВМ УПД с общим ресурсом СОР) 59
ЭВМ УПД с частично доступным ресурсом СЧДР) 67
ЭВМ УПД с локально доступным ресурсом (ЛДР) 78
2.3 Выводы 85
ГЛАВА 3. ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ ПОТОКОВЫХ ВЫЧИСЛИТЕЛЬНЫХ СТРУКТУР ПРИ ПРОИЗВОЛЬНОЙ ЗАГРУЗКЕ
ПРОЦЕССОРОВ ' 89
3.1 Вероятностная модель ЭВМ УПД с общим ресурсом при
произвольной загрузке процессоров 89
3.1.1 Методика определения стационарных вероят
ностей в модели потоковой ЭВМ~С"0Р 92
Анализ производительности ЭВМ УПД с ЧДР при произвольной загрузке процессоров 100
Анализ производительности ЭВМ УПД с ЛДР при произвольной загрузке процессоров 107
Влияние пропускной способности сети на производительность потоковых структур 116
Сравнительный анализ производительности потоковых структур и ЭВМ традиционной архитектуры 118
3.6 Выводы 125
ГЛАВА 4. ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ МОДЕЛИРОВАНИЯ
ПОТОКОВЫХ ВЫЧИСЛИТЕЛЬНЫХ СТРУКТУР 127
4.1 Методика определения параметров распараллеливания
решаемой задачи , 127
Программы аналитического и численного моделирования потоковых структур 131
Имитационное моделирование потоковых вычислительных структур 132
Методика оценки производительности структур управляемых потоком данных 146
4.5 Выводы 148
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 151
СПИСОК ЛИТЕРАТУРЫ 152
ПРИЛОЖЕНИЯ 163
МАТЕРИАЛЫ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ
ЛИССЕРТА1Ш0Н0И РАБОТЫ 180
Введение к работе
Актуальность темы диссертации. Одной из основных проблем развития средств вычислительной техники и их математического обеспечения на современном этапе является увеличение производительности вычислительных структур (BCD, а также поиск путей их наиболее эффективного использования. Достижение производительности ВС порядка нескольких миллиардов операций в секунду для эффективного решения дифференциальных уравнений в вычислительной аэродинамике, моделирования по методу Монте-Карло при разработке ядерных систем, обработки сигналов в реальном масштабе времени, управления быстрыми и сложными ядерными и химическими реакциями, точного прогнозирования погоды ~и т.п. остается первостепенной задачей в области ВТ. С другой стороны, все большее значение приобретает надежность вычислений и живучесть ВС, особенно при решении задач в реальном масштабе времени Суправление ядерным реактором, летательными аппаратами и т.д.X
Модель вычислений, предложенная фон-Нейманом, имеет две важные характеристики. Во-первых, она имеет глобальную адресуемую память для хранения программы и информационных объектов, при этом команды программы в процессе вычисления часто обновляют содержимое памяти. Во-вторых, она имеет счетчик команд, который содержит адрес следующей выполняемой команды. Этот счетчик явно или неявно обновляется, обеспечивая машину последовательностью команд для выполнения, что означает единственность местоположения управления - фундаментальное ограничение модели фон-Неймана для параллельной обработки.
Ограничение, вносимое счетчиком команд, можно преодолеть в некоторых приложениях, в которых структуры данных, такие как массивы, являются естественными единицами, которыми можно опери-
ровать, И тип данных "массив", и команды для манипулирования ими могут поддерживаться аппаратно. Декодирование одной команды обеспечивает выполнение операции над массивами, включая сюда накладные расходы на управление циклом. Производительность машины при выполнении векторных команд часто ограничивается только размером памяти, и компьютеры, основанные на таком подходе, являются достаточно удачными Снапример, компьютер Cray Х-МР [31]Э. Однако,
могут быть векторизованы не все прикладные программы с параллелизмом, даже если они закодированы непосредственно с использованием векторных команд. Часть программного кода, которая может быть векторизована, колеблется от 10 до 90 процентов в зависимости от области приложений. В то время когда эффективность векторных команд увеличивается, невекторизуемый код имеет тенденцию становиться узким местом. Более сложно повысить производительность компьютера с векторными операциями, если исходный код написан на одном из языков высокого уровня и векторизация выполнена компилятором. Автоматическая векторизация требует сложного анализа потока данных, который затруднен в этих языках из-за побочных эффектов, вызываемых глобальной областью действия и наложением переменных. Уменьшить некоторые из этих трудностей компилятора могут различные векторные расширения языков высокого уровня, но программирование при использовании этих расширений сложное, и результирующие программы являются машинно-зависимыми и негибкими.
другой подход к быстрому выполнению одной программы состоит в распределении работы между несколькими фон-неймановскими процессорами имеющими общую память. Наиболее серьезной проблемой, возникающей при использовании мультипроцессоров с совместно используемой памятью, является модель основных вычислений, которая включает в себя глобальную, обновляемую объектно-ориентируемую память. Для обеспечения корректности результатов требуется
специальная архитектурная поддержка, так как, возможно, процессоры будут состязаться при обновлении ячейки памяти. Фрагменты программы, которые разделяют данные и выполняются параллельно, должны синхронизироваться такими операциями, как "проверить и установить", семафорами и т.п.. Накладные расходы на каждую операцию синхронизации могут быть велики, и высокая производительность достигается только тогда, когда прикладная программа может быть разбита на длинные цепочки вычислений с малым числом операций синхронизации. Это не всегда возможно, и даже если удается выполнить подходящее разбиение, обеспечение корректности программы, полученной в результате этого, остается трудной задачей. До сих пор спроектировано очень мало машин, базирующихся на этом подходе; те же, которые были созданы, не имели заметного успеха в использовании параллелизма.
Параллелизм обработки данных на всех уровнях организации вычислительного процесса Сот логического до системного), являющийся основным структурным резервом повышения производительности, не
может быть реализован в рамках структуры машин фон-Неймана. Увеличение степени параллельности обработки путем модульного расширения системы дополнительным оборудованием Сдобавление новых ЭВМ, процессоров, блоков ввода-вывода), добавление к системе специализированных устройств, очень эффективных для определенного класса применений, максимальное использование параллельности, присутствующей в программах, применение конвейерной, матричной, ассоциативной организации вычислений, оптимизация обмена между
отдельными устройствами приводят к чрезмерному усложнению программирования и управления ЭВМ, что, в свою очередь, снижает их надежность и производительность. Добиться же значительного скачка в повыиении производительности ЭВМ на несколько порядков невозможно в рамках традиционной архитектуры [36]. Это подтверждается
опытом разработки универсальных высокопроизводительных ЭВМ всех зарубежных фирм.
Для повыления производительности современных ЭВМ исследуются и применяются новые архитектурные решения и перспективные методы параллельной обработки. Один из таких методов - управление вычислительным процессом потоком данных.
ЭВМ управляемые потоком данных (УГШ свободны от основных недостатков ВС фон-неймановской архитектуры Сглобальная обновляемая память и единственный счетчик команд). Во-первых, потоковая модель имеет дело только со значениями, а не с адресами, содержащими значения. Эта концепция является основной также и для чисто функциональных или аппликативньк языков, и, следовательно эти языки не имеют заложенного в них понятия глобальной обновляемой памяти. Оператор в этих языках порождает значение, которое используется другими операторами. Во-вторых, потоковая модель не имеет ничего похожего на счетчик команд: команда активизируется тогда и только тогда, когда все требуемые входные значения будут вычислены. Активизированные команды потребляют входные значения, выполняют вычисление и порождают наборы выходных значений, которые посылаются другим командам, которым эти значения требуются. В потоке данных команда не имеет побочных эффектов, и языки, основанные на концепциях потока данных, не вносят других ограничений на порядок выполнения вычислительного процесса, кроме ограничений, накладываемых зависимостями по данным, имеющимися в алгоритме. Таким образом, в принципе возможно выявить весь параллелизм потоковой программы.
Программа, написанная на потоковом языке высокого уровня, транслируется непосредственно в граф, узлы которого представляют собой функции, а ребра - зависимости по данным между функциями. Преимущество потоковых языков состоит в том, что граф может быть
сгенерирован после небольшого анализа Св отличии от оптимизирующих компиляторов, применяемых в ЭВМ традиционной архитектуры). Фактически, потоковые язьки были первоначально определены как графические.
ЭВМ УПД - это компьютеры с хранимой программой, которая является представлением графа потока данных. Сам процессор спроектирован таким образом, чтобы распознавать, какие из команд в его памяти для команд активизируются, и все эти команды направляются в исполнительные устройства как только ресурсы становятся доступными. Здесь нет понятия единственности местоположения управления. Любое количество команд из памяти для программ может быть выполнено одновременно. Если обеспечиваются достаточные ресурсы, процессор может использовать всю параллельность, присутствующую в программе. Этот подход естественным образом распространяется на произвольное число процессоров.
Вьше был представлен потенциал, имеющийся у ЭВМ УПД и у по-
токовых языков для достижения высокой производительности. Некото-
< рыми из других преимуществ ВС УПД являются более простая верифи-
кация программ, большая модульность и расширяемость аппаратных средств, уменьшенные проблемы защиты данных и лучшее предотвращение ошибок программного обеспечения.
Предмет исследований. Предметом исследований настоящей работы являются вычислительные структуры управляемые потоком данных статической архитектуры.
Целью диссертационной работы является разработка методики оценки производительности потоковых ВС статической архитектуры при обработке классов задач с различным потенциальным паралле-л из ном.
В соответствии с поставленной задачей исследования проводились по следующим направлениям:
анализ состояния основных проблем, возникающих при организации управления вычислительным процессом потоком данных;
постановка задачи об определении параметров рабочей нагрузки потоковых структур наиболее полно характеризующие ее потенциальный параллелизм при данном методе управления вычислительным процессом;
выбор методов оценки производительности ЭВМ управляемых потоком данных в зависимости от их структурных параметров, количества компонент в системе, класса обрабатываемых задач;
разработка аналитических и имитационных моделей потоковых вычислительных структур с целью получения комплексной методики оценки их производительности.
Методы исследования. Решение перечисленных задач основывается на изучении и обобщении опыта оценки и измерения производительности вычислительных структур, использования математического аппарата теории массового обслуживания, основных положений вы-числительной математики, теории построения и анализа аналити-* ческих и имитационных моделей.
Основные положения, выносимые на защиту: метод задания потенциального параллелизма задач, решаемых в потоковых структурах; методика определения стационарных вероятностей в моделях ЭВМ управляемых потоком данных; методика оценки производительности потоковых структур.
Научные результаты, В результате проведения исследований автором получены следующие результаты:
Разработана методика задания рабочей нагрузки в потоковых структурах, адекватная, применяемому принципу управления вычисли-тельным процессом;
Разработана методика оценки производительности потоковых ВС в зависимости от класса решаемых задач, загрузки процессоров и
количества компонент в системе;
Разработана модель ЭВМ УПД с общим ресурсом при предельных случаях загрузки процессоров;
Разработана методика определения стационарных вероятностей для рассматриваемых моделей;
Разработаны вероятностные модели потоковых вычислительных структур с локально доступным ресурсом и с частично доступньм ресурсом при сильной» слабой и произвольной загрузке процессоров;
С целью сравнения эффективности применения потоковых вычислительных структур и ЭВМ классической архитектуры, разработана вероятностная модель многопроцессорной ЭВМ фон-неймановского типа с опережающей выборкой команд.
Практическую ценность представляют:
- полученные соотношения для моделей потоковых вычислитель
ных структур, позволяющие априорно оценить эффективность их при
менения для решения того или иного класса задач
- разработанный пакет программ, позволяющий оценить произво-
f дительность ЭВМ УПД при заданном количестве процессоров и блоков
памяти, их быстродействии при решении задачи конкретного класса.
Реализация и внедрение результатов исследований. Разработанная на основе аналитических и имитационных моделей методика и комплекс программ оценки производительности потоковых вычислительных структур внедрены в НИИ "Аргон", г. Москва, а также использовались в учебном процессе в двух ВУЗах, что подтверждается соответствующими актами о внедрении.
Апробация работы. Основные результаты работы докладывались и обсуждались на 8 Всесоюзных и республиканских конференциях и се-минарах:
- Всесоюзный симпозиум "Перспективы развития вычисли
тельных систем".- Рига, 1989
Белорусская зимняя школа-семинар по теории массового обслуживания "Математические методы исследования сетей связи и сетей ЭВМ".- Минск, 1990
Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. - Москва, 1990
Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. - Москва, 1991
Всесоюзная конференция "Однородные вычислительные среды и систолические структуры".- Львов, 1990
Республиканская научно-техническая конференция, посвященная 25-летию образования КПИ им. С.Лазо. - Кишинев, 1989
Научно-техническая конференция "Автоматизация проектирования РЭА и ЭВА". - Пенза, 1991
Всесоюзная конференция "Интеллектуальные системы". Туапсе, 1991.
Публикации. Основные положения и результаты диссертационной работы опубликованы в 13 печатных работах, г Структура диссертационной работы. Диссертация состоит из введения, четырех глав, списка литературы С101 наименование) и приложения. Объем работы - 161 страница, 51 рисунков, 3 таблицы.
Похожие диссертации на Оценка производительности структур ЭВМ, управляемых потоком данных, статической архитектуры
