Параллельное программирование

Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего образования «Тульский государственный университет» Институт прикладной математики и компьютерных наук Кафедра «Вычислительная техника» КОНСПЕКТ ЛЕКЦИЙ по дисциплине Параллельное программирование Уровень профессионального образования: (высшее образование – бакалавриат.) Направление подготовки: 09.03.01 «Информатика и вычислительная техника» Профиль подготовки: Системы автоматизированного проектирования Квалификация выпускника: 62 - бакалавр Форма обучения: очная, очно-заочная, заочная, заочная сокращенная Тула 2017 г. 2 СОДЕРЖАНИЕ 1. 1.1. 1.1.1. 1.1.2. 1.1.3. 1.1.4. 1.1.5. 1.2. 1.2.1. 1.2.2. 1.2.3. 1.2.4. 1.3. 1.3.1. 1.3.2. Архитектура параллельных вычислительных систем Основные классы параллельных вычислительных систем Классификация параллельных вычислительных систем Векторно-конвейерные системы и векторно-параллельные (SIMD-системы) Многопроцессорные системы (MIMD-системы) Многопроцессорные системы (MIMD-системы). Вычислительные кластеры Производительность параллельных вычислительных систем Коммуникационная среда параллельных вычислительных систем Компоненты коммуникационной среды Топологии коммуникационных сетей Сетевые коммутаторы Основные характеристики коммуникационных сетей Параллельные системы нетрадиционной архитектуры Нейросетевые вычислительные системы Вычислительные машины потока данных и ассоциативные вычислительные маши- ны 2. Программное обеспечение параллельных вычислительных систем 2.1. Классификация и основные понятия операционных систем параллельных вычислительных систем 2.1.1. Классификация мультипроцессорных операционных систем 2.1.2. Основные понятия многопроцессорных операционных систем 2.2. Операционные системы параллельных вычислительных систем. Синхронизация и коммуникации процессов. 2.2.1. Операционные системы мультипроцессоров. Синхронизация процессов 2.2.2. Операционные системы мультикомпьютеров. Коммуникации процессов 2.2.3. Операционные системы мультикомпьютеров. Управление распределенной памятью 2.3. Операционные системы параллельных вычислительных систем. Планирование процессов 2.3.1. Задача оптимального отображения параллельных процессов на архитектуру многопроцессорной вычислительной системы 2.3.2. Операционные системы мультипроцессоров. Планирование процессов 2.3.3. Операционные системы мультикомпьютеров. Планирование процессов 2.3.4. Операционные системы мультикомпьютеров. Спектральный алгоритм балансировки загрузки 2.3.5. Отображение процессов с регулярной структурой на типовые архитектуры мультикомпьютеров 2.4. Языки высокого уровня для программирования векторно-конвейерных и векторнопараллельных вычислительных систем 2.4.1. Выборка элементов массива 2.4.2. Функции обработки массивов для получения соответствия 2.4.3. Параллельные операторы Литература 3 Классификация параллельных вычислительных систем Под архитектурой вычислительной системы понимаются абстрактное представление ЭВМ с точки зрения программиста. Полное описание архитектуры системы включает в себя:    основные форматы представления данных; способы адресации данных в программе; состав аппаратных средств вычислительной машины, характеристики средств, принципы организации вычислительного процесса. этих В курсе рассматриваются только последние аспекты архитектуры вычислительной системы. Структуру вычислительной системы можно определить как совокупность аппаратных средств ЭВМ с указанием основных связей между ними. Имеется много различных классификаций вычислительных систем. Рассмотрим наиболее часто используемые классификации. Классификация Флина. Наибольшее распространение получила классификация вычислительных систем, предложенная в 1966 г. профессором Стенфордского университета М.Д.Флином (M.J.Flynn) - классификация Флина. Эта классификация охватывает только два классификационных признака – тип потока команд и тип потока данных (см. Рис.1, 2). Рис. 1. К классификации Флина. Классификация по типу потока команд. В одиночном потоке команд в один момент времени может выполняться только одна команда. В этом случае эта единственная команда определяет в данный момент времени работу всех или, по крайней мере, многих устройств вычислительной системы. Во множественном потоке команд в один момент времени может выполняться много команд. В этом случае каждая из таких команд определяет в данный момент времени работу только одного или лишь нескольких (но не всех) устройств вычислительной системы. В одиночном потоке последовательно выполняются отдельные команды, во множественном потоке – группы команд. 4 Рис. 2. К классификации Флина. Классификация по типу потока данных. Одиночный поток данных обязательно предполагает наличие в вычислительной системе только одного устройства оперативной памяти и одного процессора. Однако при этом процессор может быть как угодно сложным, так что процесс обработки каждой единицы информации в потоке может требовать выполнения многих команд. Множественный поток данных состоит из многих зависимых или независимых одиночных потоков данных. В соответствии со сказанным, все вычислительные системы делятся на четыре типа:     SISD (ОКОД); MISD (МКОД); SIMD (ОКМД); MIMD (МКМД). Вычислительная система SISD представляет собой классическую однопроцессорную ЭВМ фон-неймановской архитектуры. На вычислительную системы MISD существуют различные точки зрения. По одно них – за всю историю развития вычислительной техники системы MISD не были созданы. По другой точке зрения (менее распространенной, чем первая) к MISD-системам относятся векторно-конвейерные вычислительные системы. Мы будем придерживаться первой точки зрения. Вычислительная система SIMD содержит много процессоров, которые синхронно (как правило) выполняют одну и ту же команду над разными данными. Системы SIMD делятся на два больших класса:   векторно-конвейерные вычислительные системы; векторно-параллельные вычислительные системы или матричные вычислительные системы. Вычислительная система MIMD содержит много процессоров, которые (как правило, асинхронно) выполняют разные команды над разными данными. Подавляющее большинство современных суперЭВМ имеют архитектуру MIMD (по крайней мере, на верхнем уровне иерархии). Системы MIMD часто называют многопроцессорными системами. Детально классификация этих систем рассмотрена в параграфе 3. Рассмотренная классификации Флина позволяет по принадлежности компьютера к классу SIMD или MIMD сделать сразу понятным базовый принцип его работы. Часто этого бывает достаточно. Недостатком классификации Флина является "переполненность" класс MIMD. Классификация по типу строения оперативной памяти. 5 По типу строения оперативной памяти системы разделяются на системы с общей (разделяемой) памятью, системы с распределенной памятью и системы с физически распределенной, а логически общедоступной памятью (гибридные системы). В вычислительных системах с общей памятью (Common Memory Systems или Shared Memory Systems) значение, записанное в память одним из процессоров, напрямую доступно для другого процессора. Общая память обычно имеет высокую пропускную способность памяти (bandwidth) и низкую латентность памяти (latency) при передачи информации между процессорами, но при условии, что не происходит одновременного обращения нескольких процессоров к одному и тому же элементу памяти. К общей памяти доступ разных процессорами системы осуществляется, как правило, за одинаковое время. Поэтому такая память называется еще UMA-памятью (Unified Memory Access) — памятью с одинаковым временем доступа. Система с такой памятью носит название вычислительной системы с одинаковым временем доступа к памяти . Системы с общей памятью называются также сильносвязанными вычислительными системами. В вычислительных системах с распределенной памятью (Distributed Memory Systems) каждый процессор имеет свою локальную память с локальным адресным пространством. Для систем с распределенной памятью характерно наличие большого числа быстрых каналов, которые связывают отдельные части этой памяти с отдельными процессорами. Обмен информацией между частями распределенной памяти осуществляется обычно относительно медленно. Системы с распределенной памятью называются также слабосвязанными вычислительными системами. Вычислительные системы с гибридной памятью - (Non-Uniform Memory Access Systems) имеют память, которая физически распределена по различным частям системы, но логически разделяема (образует единое адресное пространство). Такая память называется еще логически общей (разделяемой) памятью (logically shared memory). В отличие от UMA-систем, в NUMA-системах время доступа к различным частям оперативной памяти различно. Заметим, что память современных параллельных систем является многоуровневой, иерархической, что порождает проблему ее когерентности. Классификация по типу коммуникационной сети. Классификация параллельных вычислительных систем по типу коммуникационной сети рассмотрена в следующем параграфе. Заметим лишь, что по количеству уровней иерархии коммуникационной среды различают системы с одноуровневой коммутационной сетью (один уровень коммутации) и системы с иерархической коммутационной сетью (когда группы процессоров объединены с помощью одной системы коммутации, а внутри каждой группы используется другая). Классификация по степени однородности По степени однородности различают однородные (гомогенные) и неоднородные (гетерогенные) вычислительные системы. Обычно при этом имеется в виду тип используемых процессоров. В однородных вычислительных системах (гомогенных вычислительных системах) используются одинаковые процессоры, в неоднородных вычислительных системах (гетерогенных вычислительных системах) – процессоры различных типов. Вычислительная система, содержащая какой-либо специализированный вычислитель (например, Фурье-процессор), относится к классу неоднородных вычислительных систем. 6 В настоящее время большинство высокопроизводительных систем относятся к классу однородных систем с общей памятью или к классу однородных систем с распределенной памятью. Рассмотренные классификационные признаки параллельных вычислительных систем не исчерпывают всех возможных их характеристик. Существует, например, еще разделение систем по степени согласованности режимов работы (синхронные и асинхронные вычислительные системы), по способу обработки (с пословной обработкой и ассоциативные вычислительные системы), по жесткости структуры (системы с фиксированной структурой и системы с перестраиваемой структурой), по управляющему потоку (системы потока команд -instruction flow и системы потока данных — data flow) и т.п. Современные высокопроизводительные системы имеют, как правило, иерархическую структуру. Например, на верхнем уровне иерархии система относится к классу MIMD, каждый процессор которой представляет собой систему MIMD или систему SIMD. Отметим также тенденцию к построению распределенных систем с программируемой структурой. В таких системах нет общего ресурса, отказ которого приводил бы к отказу системы в целом – средства управления, обработки и хранения информации распределены по составным частям системы. Такие системы обладают способностью автоматически реконфигурироваться в случае выхода из строя отдельных их частей. Средства реконфигурирования позволяют также программно перестроить систему с целью повышения эффективности решения на этой системе данной задачи или класса задач. Векторно-конвейерные системы и векторно-параллельные (SIMD-системы) Векторно-конвейерные вычислительные системы. Векторно-конвейерные вычислительные системы относятся SIMD-систем. Основные принципы, заложенные в архитектуру конвейерных систем:   к классу векторно- конвейерная организация обработки потока команд; введение в систему команд набора векторных операций, которые позволяют оперировать с целыми массивами данных. Длина обрабатываемых векторов в современных векторно-конвейерных системах составляет, как правило, 128 или 256 элементов. Основное назначение векторных операций состоит в распараллеливании выполнения операторов цикла, в которых обычно сосредоточена большая часть вычислительной работы. Первый векторно-конвейерный компьютер Cray-1 появился в 1976 году. Архитектура этого компьютера оказалась настолько удачной, что он положил начало целому семейству компьютеров. Современные векторно-конвейерные системы имеют иерархическую структуру:  на нижнем уровне иерархии расположены конвейеры операций (например, конвейер (pipeline) сложения вещественных чисел, конвейер умножения таких же чисел и т.п.); 7     некоторая совокупность конвейеров операций объединяется в конвейерное функциональное устройство; векторно-конвейерный процессор содержит ряд конвейерных функциональных устройств; несколько векторно-конвейерных процессоров (2-16), объединенных общей памятью, образуют вычислительный узел; несколько таких узлов объединяются с помощью коммутаторов, образуя либо NUMA-систему либо MPP-систему. Типичными представителями такой архитектуры являются компьютеры CRAY J90/T90, CRAY SV1, NEC SX-4/SX-5. Уровень развития микроэлектронных технологий не позволяет в настоящее время производить однокристальные векторноконвейерные процессоры, поэтому эти системы довольно громоздки и чрезвычайно дороги. Каждая часть конвейера операций называется ступенью конвейера операций, а общее число ступеней - длиной конвейера операций. Пример 1 Рассмотрим следующий 4-х ступенчатый конвейер операций сложения вещественных чисел Таблица 1 Номер ступени Положим, сел рис. 1 что Наименование 1 Вычитание порядков 2 Сдвиг одной из мантисс 3 Сложение мантисс 4 Нормализация выполняется сложение двух -векторов вещественных чи- . Диаграмма сложения этих векторов приведена на 8 Рис. 1. К примеру 1. Временная диаграмма сложения (n*1)-векторов вещественных чисел X ,Y на 4-х ступенчатом конвейере операции сложения. В векторно-конвейерных системах в рамках одного конвейерного функционального устройства широко используется (т.е. аппаратно поддерживается) зацепление конвейеров операций. Покажем суть этой процедуры на примере. Пример 2 Положим, что в некоторой прикладной программе, исполняемой на векторноконвейерной системе , необходимо вычислить (1) где -векторы вещественных чисел, под произведением и делением векторов понимается их покомпонентное умножение и деление, соответственно. Иными словами, операции, указанные в выражении (1), понимаются в смысле (2) Положим также, что конвейерное функциональное устройство данной векторноконвейерной системы имеет следующие конвейеры операций:    конвейер сложения вещественных чисел; конвейер умножения вещественных чисел; конвейер деления вещественных чисел Тогда для повышения скорости вычисления компонент вектора E целесообразно использовать зацепление указанных конвейеров (см. рис. 2). В результате, можно сказать, получается новый конвейер, который выполняет сложную операцию (2) Рис. 2. К примеру 2. К зацеплению конвейеров. Конвейер операций не следует путать с конвейером команд, в котором при исполнении одной команды готовится к исполнению несколько следующих команд. Так же, как в конвейере операций каждая часть конвейера команд называется ступенью конвейера команд, а общее число ступеней – длиной конвейера команд. Конвейеры команд широко используются в современных процессорах. Так процессор Intel 486 имеет 5-ти ступенчатый конвейер выполнения целочисленных команд, ступенями которого являются следующие операции: 9      предвыборка (команда извлекается из КЭШ-памяти и размещается в одном из двух 16байтовых буферах); декодирование; генерация адреса; исполнение в АЛУ; запись результата в КЭШ-память. Процессор Pentium 2 (суперскалярная архитектура) имеет два 8-ми ступенчатых конвейера целочисленных команд. Кроме конвейеров в векторно-конвейерных системах для ускорения работы используют различные механизмы адресации, операции с автоинкрементом (автодекрементом) адреса, механизмы ускоренной выборки и записи (многопортовая память, память с расслоением и т.д.), отдельное адресное обрабатывающее устройство, отдельное скалярное устройство для выполнения скалярных операций и пр.. Недостатком векторно-конвейерных систем является невысокая загрузка процессорных элементов. Высокая производительность достигается только на операциях с длинными векторами. На скалярных операциях и при обработке векторов и матриц невысокой размерности значительная часть устройств может простаивать. В целом, векторно-конвейерные системы характеризуются высокой производительностью при полной загрузке их вычислительных устройств, которая имеет место только при решении определенного, достаточно узкого, круга задач. В качестве примера векторно-конвейерной системы приведем легендарную супер-ЭВМ CYBER-205 фирмы CDC. CYBER-205 имеет следующие конвейерные функциональные устройства:  o o o o o o  o o o o o одно конвейерное функциональное устройство «скалярных» операций с конвейерами сложения (5-ти ступенчатый); умножения (5-ти ступенчатый); логических операций сложения (3-х ступенчатый); цикла; извлечения корня; деления; 1, 2 или 4 конвейерных функциональных устройства «векторных» операций с конвейерами сложения; умножения; сдвига; логических операций; задержки. В качестве примера современной супер-ЭВМ, использующей векторноконвейерные процессоры, приведем японскую систему Fujitsu-VPP5000. На верхнем уровне Fujitsu-VPP5000 имеет MPP архитектуру. Производительность одного процессора системы составляет 9.6 Гфлопс, пиковая производительность системы может достигать 1249 Гфлопс, максимальная емкость памяти - 8 Тб. Система масштабируется до 512 узлов. Векторно-параллельные системы. Как и векторно-конвейерные системы, векторно-параллельная вычислительная система обычно имеет иерархическую структуру. На нижнем уровне 10 иерархии находятся векторно-параллельные процессоры, представляющие собой совокупность скалярных процессоров (процессорных элементов), которые объединены некоторой коммуникационной сетью и в каждом такте синхронно выполняют одну и ту же команду над разными данными. На верхнем уровне иерархии векторно-параллельные процессоры объединяются общей памятью или коммуникационной сетью, образуя NUMA-систему либо MPP систему. Векторно-параллельные процессоры имеют в своих системах команд специальные векторные (матричные) операции, такие, как векторное и матричное сложение, умножение вектора на матрицу, умножение матрицы на константу, вычисление скалярного произведения, свертки и т.д. При выполнении векторных операций различные компоненты векторов и матриц обрабатываются параллельно на различных процессорных элементах. Основными компонентами векторно-параллельного процессора являются     совокупность скалярных процессоров (Р); совокупность модулей оперативной памяти (М); коммуникационная среда; устройство общего управления. Выделим две группы векторно-параллельных процессоров: процессоры с одинаковым числом скалярных процессоров и модулей памяти; векторные процессоры с различным количеством скалярных процессоров и модулей памяти. В векторно-параллельном процессоре с одинаковым числом скалярных процессоров и модулей памяти каждый скалярный процессор подключается к своему модулю памяти (см. рис. 3). Команда, выдаваемая устройством управления, содержит одинаковый адрес для всех скалярных процессоров. С помощью специального «флага» можно запретить выполнение команды на данном скалярном процессоре – «маскирование команды». В векторно-параллельном процессоре с различным количество скалярных процессоров и модулей памяти (см. рис. 4) основной проблемой является проблема исключения конфликтов при обращении к памяти (поскольку к одному модулю памяти могут одновременно обращаться в переделе все скалярные процессоры). Для преодоления этой проблемы в системах этого класса используют изощренные схемы хранения массивов данных. Рис. 3. Структура векторно-параллельного процессора с одинаковым числом скалярных процессоров и модулей памяти. 11 Рис. 4. Структура векторно-параллельного процессора с различным количеством скалярных процессоров и модулей памяти. В историческом плане наиболее известной векторно-параллельной системой является ILLIAC-IV (Burroughs). ЭВМ имела 64 процессора, объединенных в 8*8 плоскую решетку. Пиковая производительность равнялась 100 Мфлопс. Недостатком векторно-параллельных систем, как и векторно-конвейерных систем, является низкая, как правило, загрузка процессорных элементов. Высокая производительность векторно-параллельных систем достигается только на векторных операциях, в то время как на скалярных операциях, а также при обработке векторов и матриц небольшой размерности, значительная часть процессорных элементов может простаивать. Программирование векторнопараллельных систем сложнее, чем векторно-конвейерных систем. В целом, векторно-параллельные системы, как и векторно-конвейерные системы, характеризуются высокой производительностью только при полной загрузке их вычислительных устройств, которая достигается при решении достаточно узкого класса задач. В качестве примера достаточно современной векторно-параллельной системы приведем вычислительную систему nCube-3 (1995 г.). Система nCube-3 масштабируется от 8 до 64 К процессорных блоков, объединенных коммуникационной сетью типа «гиперкуб» (размерностью от 3D до 16D). Максимальная производительность nCube-3 составляет несколько TFLOPS. Процессоры системы могут быть объединены в группы, каждая из которых может решать свою задачу (MIMDрежим). Многопроцессорные системы (MIMDсистемы) Как уже отмечалось, MIMD-система содержит много процессоров, которые (как правило, асинхронно) выполняют разные команды над разными данными. Подавляющее большинство современных высокопроизводительных ЭВМ на верхнем уровне иерархии имеют архитектуру MIMD. Для MIMD-систем в настоящее время общепризнанна классификация, основанная на используемых способах организации оперативной памяти в этих системах. По этой классификации, прежде всего, различают мультипроцессорные вычислительные системы (или мультипроцессоры) или вычислительные систе- 12 мы с разделяемой памятью (multiprocessors, common memory systems, sharedmemory systems) и мультикомпьютерные вычислительные сист емы(мультикомпьютеры) или вычислительные системы с распределенной памятью (multicomputers, distributed memory systems). Структура мультипроцессорной и мультикомпьютерной систем приведена рис. 1, где памяти. - процессор, - модуль Рис. 1. а) - структура мультипроцессора; б) – структура мультикомпьютера. Мультипроцессоры. В мультипроцессорах адресное пространство всех процессоров является единым. Это значит, что если в программах нескольких процессоров мультипроцессора встречается одна и та же переменная, то для получения или изменения значения этой переменной эти процессоры будут обращаться в одну физическую ячейку общей памяти. Это обстоятельство имеет как положительные, так и отрицательные последствия. С одной стороны, не нужно физически перемещать данные между коммутирующими программами, что исключает затраты времени на межпроцессорный обмен. С другой стороны, так как одновременное обращение нескольких процессоров к общим данным может привести к получению неверных результатов, необходимы системы синхронизации параллельных процессов и обеспечения когерентности памяти. Поскольку процессорам необходимо очень часто обращаться к общей памяти, требования к пропускной способности коммуникационной среды чрезвычайно высоки. Последнее обстоятельство ограничивает число процессоров в мультипроцессорах несколькими десятками. Остроту проблемы доступа к общей памяти частично удается снять разделением памяти на блоки, которые позволяют распараллелить обращения к памяти от различных процессоров. Отметим еще одно преимущество мультипроцессоров – мультипроцессорная система функционирует под управлением единственной копией операционной системы (обычно, UNIX-подобной) и не требует индивидуальной настройки каждого процессорного узла. Однородные мультипроцессоры с равноправным (симметричным) доступом к общей оперативной памяти принято называть SMP-системами (системами с симметричной мультипроцессорной архитектурой). SMP-системы появились как аль- 13 тернатива дорогим мультипроцессорным системам на базе векторно-конвейерных процессоров и векторно-параллельных процессоров (см. Рис.2). Мультикомпьютеры. Вследствие простоты своей архитектуры наибольшее распространение в настоящее время получили мультикомпьютеры. Мультикомпьютеры не имеют общей памяти. Поэтому межпроцессорный обмен в таких системах осуществляется обычно через коммуникационную сеть с помощью передачи сообщений. Каждый процессор в мультикомпьютере имеет независимое адресное пространство. Поэтому наличие переменной с одним и тем же именем в программах разных процессоров, приводит к обращению к физически разным ячейкам собственной памяти этих процессоров. Это обстоятельство требует физического перемещения данных между коммутирующими программами в разных процессорах. Чаще всего основная часть обращений производится каждым процессором к собственной памяти. Поэтому требования к коммутационной среде ослабляются. В результате число процессоров в мультикомпьютерных системах может достигать нескольких тысяч, десятков тысяч и даже сотен тысяч. Пиковая производительность крупнейших систем с общей памятью ниже пиковой производительности крупнейших систем с распределенной памятью; стоимость систем с общей памятью выше стоимости аналогичных по производительности систем с распределенной памятью. Однородные мультикомпьютеры с распределенной памятью называются вычислительными системами с массивно-параллельной архитектурой (MPP-системами) - см. рис.2. Нечто среднее между SMP-системами и MPP-системами представляют собой NUMA-системы. Кластерные системы (вычислительные кластеры). Кластерные системы (вычислительные кластеры) представляют собой более дешевый вариант MPP-систем. Вычислительный кластер состоит из совокупности персональных компьютеров или рабочих станций), объединенных локальной сетью в качестве коммуникационной среды. Детально вычислительные кластеры рассмотрены позже. 14 Рис. 2. Классификация мультипроцессоров и мультикомпьютеров. SMP-системы Все процессоры SMP-системы имеют симметричный доступ к памяти, т.е. память SMP-системы представляет собой UMA-память. Под симметричностью понимается следующее: равные права всех процессоров на доступ к памяти; одна и та же адресация для всех элементов памяти; равное время доступа всех процессоров системы к памяти (без учета взаимных блокировок). Общая структура SMP-системы приведена на рис. 3. Коммуникационная среда SMP-системы строится на основе какой-либо высокоскоростной системной шины или высокоскоростного коммутатора. Кроме одинаковых процессоров и общей памяти M к этой же шине или коммутатору подключаются устройства вводавывода. За кажущейся простотой SMP-систем скрываются значительные проблемы, связанные в основном с оперативной памятью. Дело в том, что в настоящее время скорость работы оперативной памяти значительно отстает от скорости работы процессора. Для того чтобы сгладить этот разрыв, современные процессоры снабжаются высокоскоростной буферной памятью (кэш-памятью). Скорость доступа к этой памяти в несколько десятков раз превышает скорость доступа к основной памяти процессора. Однако наличие кэш-памяти нарушается принцип равноправного доступа к любой точке памяти, поскольку данные, находящиеся в кэш-памяти одного процессора, недоступны для других процессоров. Поэтому после каждой модификации копии переменной, находящейся в кэш-памяти какоголибо процессора, необходимо производить синхронную модификацию самой этой переменной, расположенной в основной памяти. В современных SMP-системах когерентность кэш-памяти поддерживается аппаратно или операционной системой. 15 Рис. 3. Общая структура SMP-системы Наиболее известными SMP-системами являются SMP-cерверы и рабочие станции IBM, HP, Compaq, Dell, Fujitsu и др. SMP-система функционирует под управлением единой операционной системой (чаще всего – UNIX и подобной ей). Из-за ограниченной пропускной способности коммуникационной среды SMPсистемы плохо масштабируются. В настоящее время в реальных системах используется не более нескольких десятков процессоров. Известным неприятным свойством SMP-систем является то, что их стоимость растет быстрее, чем производительность при увеличении числа процессоров в системе. MPP-системы. MPP-системы строится из процессорных узлов, содержащих процессор, локальный блок оперативной памяти, коммуникационный процессор или сетевой адаптер, иногда - жесткие диски и/или другие устройства ввода/вывода. По сути, такие модули представляют собой полнофункциональные компьютеры (см. рис. 4.). Доступ к блоку оперативной памяти данного модуля имеет только процессор этого же модуля. Модули взаимодействуют между собой через некоторую коммуникационную среду. Используются два варианта работы операционной системы на MPP-системах. В одном варианте полноценная операционная система функционирует только на управляющей ЭВМ, а на каждом отдельном модуле работает сильно урезанный вариант операционной системы, поддерживающий только базовые функции ядра операционной системы. Во втором варианте на каждом модуле работает полноценная UNIX-подобная операционная система. Заметим, что необходимость наличия (в том или ином виде) на каждом процессоре MPP-системы операционной системы, позволяет использовать только ограниченный объем памяти каждого из процессоров. По сравнению с SMP-системами, архитектура MPP-системы устраняет одновременно как проблему конфликтов при обращении к памяти, так и проблему когерентности кэш-памяти. Главным преимуществом MPP-систем является хорошая масштабируемость. Так супер-ЭВМ серии CRAY T3E, способны масштабироваться до 2048 процессоров. Практически все рекорды по производительности на сегодняшний день установлены именно на MPP-системах, состоящих из нескольких тысяч процессоров. 16 Рис. 4. Общая структура MPP-системы. С другой стороны, отсутствие общей памяти заметно снижает скорость межпроцессорного обмена в MPP-системах. Это обстоятельство для MPP-систем выводит на первый план проблему эффективности коммуникационной среды. Кроме того, в MPP-системах требуется специальная техника программирования для реализации обмена данными между процессорами. Этим объясняется высокая цена программного обеспечения для MPP-систем. Этим же объясняется то, что написание эффективных параллельных программ для MPP-систем представляет собой более сложную задачу, чем написание таких же программ для SMP-систем. Для широкого круга задач, для которые известны хорошо зарекомендовавшие себя последовательные алгоритмы, не удается построить эффективные параллельные алгоритмы для MPP-систем. NUMA-системы. Логически общий доступ к данным может быть обеспечен и при физически распределенной памяти. При этом расстояние между различными процессорами и различными элементами памяти, вообще говоря, различно и длительность доступа различных процессоров к различным элементам памяти различна. Т.е. память таких систем представляет собой NUMA-память. NUMA-система обычно строится на основе однородных процессорных узлов, состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью некоторой высокоскоростной коммуникационной среды (см. рис. 5). Поддерживается единое адресное пространство, аппаратно поддерживается доступ к удаленной памяти, т.е. к памяти других модулей. При этом доступ к локальной памяти осуществляется в несколько раз быстрее, чем к удаленной. По существу, NUMA-система представляет собой MPP-систему, где в качестве отдельных вычислительных элементов используются SMP-узлы. Среди NUMA-систем выделяют следующие типы систем:    COMA-системы, в которых в качестве оперативной памяти используется только локальная кэш-память процессоров (cache-only memory architecture - COMA); CC-NUMA-системы, в которых аппаратно обеспечивается когерентность локальной кэш-памяти разных процессоров (cache-coherent NUMA - CC-NUMA); NCC-NUMA-системы, в которых аппаратно не поддерживается когерентность локальной КЭШ памяти разных процессоров (non-cache coherent NUMA - NCCNUMA). К данному типу относится, например, система Cray T3E. 17 Рис. 5. Общая структура NUMA-системы. Логическая общедоступность памяти в NUMA-системах, с одной стороны, позволяет работать с единым адресным пространством, а, с другой стороны, позволяет достаточно просто обеспечить высокую масштабируемость системы. Данная технология позволяет в настоящее время создавать системы, содержащие до нескольких сот процессоров. NUMA-системы серийно производятся многими компьютерными фирмами как многопроцессорные серверы и прочно удерживают лидерство в классе малых суперкомпьютеров. Многопроцессорные системы (MIMDсистемы). Вычислительные кластеры Как мы уже отмечали вычислительный кластер – это MIMD-система (мультикомпьютер), состоящая из множества отдельных компьютеров (узлов вычислительного кластера), объединенных единой коммуникационной средой. Каждый узел имеет свою локальную оперативную память. При этом общей физической оперативной памяти для узлов, как правило, не существует. Коммуникационная среда вычислительных кластеров обычно позволяет узлам взаимодействовать между собой только посредством передачи сообщений. В целом, вычислительный кластер следует рассматривать как единую аппаратно-программную систему, имеющую единую коммуникационную систему, единый центр управления и планирования загрузки. Узлы вычислительного кластера могут функционировать под управлением разных операционных систем. Однако чаще всего используются стандартные UNIX-подобные системы. Заметим, что точки зрения разработки прикладных параллельных программ нет каких-либо принципиальных различий между однородными вычислительными кластерами и MPP-системами. Вычислительные кластеры классифицируются, прежде всего, по характеру узловых процессоров (см. рис. 1). Классификация вычислительных кластеров по типу узловых процессоров. В качестве узлов вычислительного кластера обычно используют персональные компьютеры, рабочие станции и SMP-сервера. Если в качестве узла кластера используются SMP-система, то такой вычислительный кластер называетсяSMPкластером. Если в качестве узлов вычислительного кластера используются персональные ЭВМ или рабочие станции, то обычной является ситуация, когда во время решения задачи на кластере на узлах этого кластера продолжают выполняться после- 18 довательные задания пользователей. В результате относительная производительность узлов кластера меняется случайным образом и в широких пределах. Решением проблемы было бы написание самоадаптирующейся пользовательской программы. Однако эффективное решение этой задачи представляется весьма проблематичным. Ситуация усугубляется, если среди узловых компьютеров вычислительного кластера имеются файловые серверы. При этом во время решения задачи на кластере в широких пределах может меняться загрузка коммуникационной среды, что делает непредсказуемыми коммуникационные расходы задачи. Рис. 1. Классификация узлов вычислительных кластеров. Классификация вычислительных кластеров по однородности узлов. Как и всякие MIMD-системы, вычислительные кластеры разделяются на однородные кластерные системы (однородные вычислительные кластеры) и гетерогенные кластерные системы (гетерогенные вычислительные кластеры). Обычно, когда говорят о вычислительных кластерах, подразумевают однородные вычислительные кластеры. Однако часто при наращивании кластера приходится использовать процессоры, отличающиеся не только по производительности, но и по архитектуре, от узловых процессоров кластера. Поэтому постепенно однородный вычислительный кластер может стать неоднородным. Эта неоднородность создает следующие проблемы. Различие в производительности процессоров усложняет задачу распределения работ между процессорами. Различие в архитектуре процессоров требует подготовки разных выполняемых файлов для разных узлов, а в случае различий в представлении данных, может потребовать и преобразования их форматов при передаче сообщений между узлами. Классификация вычислительных кластеров по функциональности узлов. Узлы вычислительного кластера могут представлять собой полнофункциональные компьютеры, которые могут работать и как самостоятельные единицы. Производительность такого кластера обычно невысока. Для создания высокопроизводительных вычислительных кластеров системные блоки узловых компьютеров делают значительно более простыми, чем в первом случае (не полнофункциональными). Здесь нет необходимости снабжать компьютеры узлов графическими картами, мониторами, дисковыми накопителями и другим периферийным оборудованием. Периферийное оборудование устанавливается только на одном или немногих управляющих компьютерах (HOSTкомпьютерах). Такой поход позволяет значительно уменьшить стоимость системы. 19 При классификации кластеров используется и ряд других классификационных признаков. Рассмотрим два из них (см. рис. 2.):   классификация по стандартности комплектующих; классификация по функциональной направленности. Рис. 2. Классификация вычислительных кластеров. Классификация вычислительных кластеров по стандартности комплектующих. С точки зрения стандартности комплектующих можно выделить два класса кластерных систем:   вычислительный кластер строится целиком из стандартных комплектующих; при построении кластера используются эксклюзивные или нешироко распространенные комплектующие. Вычислительные кластеры первого класса имеют низкие цены и простое обслуживание. Широкое распространение кластерные технологии получили как средство создания именно относительно дешевых систем суперкомпьютерного класса из составных частей массового производства. Кластеры второго класса позволяют получить очень высокую производительность, но являются, естественно, более дорогими. Классификация вычислительных кластеров по их функциональной направленности. С функциональной точки зрения кластерные системы можно разделить на высокоскоростные кластерные системы (High Performance) - HP-кластеры и кластерные системы высокой готовности (High Availability) – HA-кластеры. Высокоскоростные кластеры используются в областях, которые требуют значительной вычислительной мощности. Кластеры высокой готовности используются везде, где стоимость возможного простоя превышает стоимость затрат, необходимых для построения отказоустойчивой системы. Высокоскоростные кластеры. Производительность вычислительного кластера, очевидно, зависти от производительности его узлов. С другой стороны, производительность кластера, как и сякой системы с распределенной памятью, сильно зависит от производительности коммуникационной среды. Обычно при построении вычислительных кластеров используют достаточно дешевые коммуникационные среды. Такие среды обеспечивают производительность на один – два порядка более низкую, чем производительность коммуникационных сред супер- 20 компьютеров. Поэтому находится не так много задач, которые могут достаточно эффективно решаться на больших кластерных системах. Влияние производительности коммуникационной среды на общую производительность кластерной системы зависит от характера выполняемой задачи. Если задача требует частого обмена данными между подзадачами, которые решаются на разных узлах вычислительного кластера, то быстродействию коммуникационной среды следует уделить максимум внимания. Соответственно, чем меньше взаимодействуют части задачи между собою, тем меньше внимания можно уделить быстродействию коммуникационной среды. Разработано множество технологий соединения компьютеров в кластер. Эти технологии будут рассмотрены в следующей главе. Место HP-кластеров среди современных высокопроизводительных систем иллюстрирует следующий пример: в списке 500 самых высокопроизводительных компьютеров мира «Top500» вычислительные кластеры из недорогих узлов занимают примерно половину списка. В России крупнейший заказчик HP-кластеров — нефтегазовая отрасль, в котрой кластеры все более широко используются для обработки трехмерных сейсмических данных, получаемых в процессе геологоразведки. Кластеры высокой готовности. Среди многообразия типов современных вычислительных систем высокой готовности HA-кластеры обеспечивают высокий уровень отказоустойчивости при самой низкой стоимости. Вообще говоря, для того, чтобы вычислительная система обладала высокими показателями готовности, необходимо, чтобы ее компоненты были максимально надежными, чтобы система была отказоустойчивой, а так же чтобы была возможной «горячая» замена компонентов (без останова системы). Благодаря кластеризации при отказе одного из компьютеров системы, задачи могут быть автоматически (операционной системой) перераспределены между другими (исправными) узлами вычислительного кластера. Таким образом, отказоустойчивость кластера обеспечивается дублированием всех жизненно важных компонент вычислительной системы. Самыми популярными коммерческими отказоустойчивыми системами в настоящее время являются двухузловые кластеры. Вычислительные сети. Выделяется еще один класс вычислительных кластеров - вычислительные сети (GRID), объединяющие ресурсы множества кластеров, многопроцессорных и однопроцессорных ЭВМ, которые могут принадлежать разным организациям и быть расположенными в разных странах. Разработка параллельных программ для вычислительных сетей усложняется из-за следующих проблем. Ресурсы (количество узлов, их архитектура, производительность), которые выделяются задаче, определяется только в момент обработки сетью заказа на выполнение это задачи. Поэтому программист не имеет возможности разработать программу для конкретной конфигурации вычислительной сети. Программу приходится разрабатывать так, чтобы она могла динамически (без перекомпиляции) самонастраиваться на выделенную конфигурацию сети. Кроме того, к неоднородности коммуникационной среды добавляется изменчивость ее характеристик, вызываемая изменениями загрузки сети. В лучшем случае программа должна разрабатываться с учетом этой неоднородности коммуникационной среды, что представляет собой весьма непростую задачу. Как мы отмечали выше, подобная проблема имеет место и для вычислительных кластеров, построенных на основе персональных компьютеров или рабочих станций. 21 Эффективная производительность кластерных вычислительных систем (real applications performance – RAP) оценивается как 5–15% от их пиковой производительности (Peak Advertised Performance, PAP). Для сравнения: у лучших малопроцессорных систем из векторных процессоров это соотношение оценивается как 30–50%. Производительность параллельных вычислительных систем Важнейшими характеристиками любых вычислительных машин являются их производительность и быстродействие. Часто эти две характеристики отождествляют, но иногда используется и та и другая. Под производительностью (performance) понимают количество операций, выполняемых на данной вычислительной системе в единицу времени. Быстродействие (speed) – величина, обратная среднему времени выполнения одной операции. Производительность измеряется в миллионах команд в секунду MIPS (millions instructions per second) или миллионах операций с плавающей запятой в секунду MFLOPS (millions floating point operations per second). Кроме производительности важными характеристиками вычислительных систем являются масштабируемость вычислительной системы (scalability) - способность вычислительной системы к наращиванию и сокращению ресурсов (прежде всего, производительности и оперативной памяти), реконфигурируемость вычислительной системы (programmability) – варьирование числа узлов и графа их связей, надежность и живучесть вычислительной системы (reliability and robustness). Хорошо масштабируемая система обеспечивает линейный рост производительности с ростом количества процессоров в ней. Асимптотическая производительность векторно-конвейерных систем. Как отмечалось выше, основным признаком векторно-конвейерных систем является наличие конвейерных функциональных устройств, содержащих ряд конвейеров операций (например, конвейер сложения вещественных чисел, конвейер умножения таких же чисел и т.п.). Поэтому оценка производительности векторноконвейерных систем основана на оценке производительности конвейеров операций. Методику оценки производительности конвейеров операций рассмотрим на примере конвейера операции сложения. Положим, что имеется -ступенчатый конвейер операции сложения и пусть все ступени конвейера операций требуют одинакового времени выполнения . Тогда для выполнения операции сложения векторов , требуется время (1) где - фиксированное время запуска конвейера, - время "разгона" конвейера. После запуска конвейера и его "разгона" конвейер выдает результат через каждый такт . Т.е. максимальная скорость выдачи результатов конвейером (максимальное быстродействие) равна (2) 22 Быстродействие конвейера принято называть асимптотическим быстродействием. Быстродействие конвейера приближается к асимптотическому быстродействию в случае, когда в формуле (1) можно пренебречь слагаемыми , . Эта ситуация имеет место когда длина обрабатываемых векторов много больше величин . При этом предполагается, что отсутствуют конфликты при обращении к памяти. Аналогичная ситуация имеет место для конвейеров любых операций. Условно принято говорить, что асимптотическое быстродействие конвейера операций достигается на векторах бесконечной длины. При работе конвейера в последовательном режиме, очевидно, максимальная скорость выдачи результатов равна (3) Таким образом, конвейерная обработка увеличивает производительность вычислительной системы в раз (на векторах бесконечной длины). Асимптотическая производительность векторно-параллельных и многопроцессорных систем. Методику оценки производительности векторно-параллельных систем и MIMDсистем рассмотрим на примере операции сложения векторов , на -процессорной системе. Время выполнения этой операции как на векторно-параллельной системе, так на MIMD-системе можно оценить по формуле (4) где ний; - время коммуникаций, - время вычисле- - диаметр коммуникационной сети системы, [ ] - ближайшее целое, большее A, - производительность каналов межпроцессорного обмена, [сек] - время выполнения операции сложения двух чисел на одном процессоре системы. Если пренебречь коммуникационными расходами, то в качестве минимального времени выполнения операции сложения компонент процессорах системы можно принять время , ( векторов , на - время сложения всех компонент векторов , , а - минимальное время сложения двух компонент этих векторов). Таким образом, максимальная скорость выдачи результатов -процессорной векторно-параллельной системой и MIMD-системой (максимальное быстродействие) равна (5) Быстродействие векторно-параллельной системы и MIMD-системы также принято называть асимптотическим быстродействием. Быстродействие векторно- 23 параллельной системы и MIMD-системы приближается к асимптотическому быстродействию в случае, когда в формуле (4) можно пренебречь коммуникационной составляющей и когда величина n кратна количеству процессоров в системе . Заметим, что пренебрежение коммуникационными расходами предполагает также, что команды не конфликтуют между собой при доступе к памяти. При сложении векторов , на одном процессоре системы максимальная скорость выдачи результатов равна, очевидно, (6) Таким образом, параллельное сложение векторов на векторно-параллельных и MIMD-системах увеличивает производительность максимум в раз. Аналогичная ситуация имеет место при выполнении ни векторнопараллельных системах или MIMD-системах любых бинарных операций. Длина полупроизводительности Важной характеристикой параллельных вычислительных систем является величина – длина векторов, на которых достигается половина асимптотического быстродействия системы. Эта величина называется длиной полупроизводительности. Смыслы асимптотического быстродействия и длины полупроизводительности различны. Асимптотическое быстродействие, главным образом, характеризует технологию изготовления ЭВМ, в то время как длина полупроизводительности представляет собой критерий степени параллелизма системы. Относительная производительность различных алгоритмов на данной параллельной вычислительной системе определяется длиной полупроизводительности. Введем в рассмотрение величину где – средняя длина обрабатываемых векторов. Тогда означает, что данный алгоритм может быть эффективно распараллелен для решения на данной вычислительной системе, 1 - означает противоположное. Пример 1 Рассмотрим операцию перемножения двух матриц (для выполнения которой необходима операция скалярного произведения векторов) на параллельных вычислительных системах CYBER-205 и CRAY-1 (см. табл. 1). Таблица 1 ЭВМ Операция CYBER-205 Сложение векторов 100 102 CYBER-205 Скалярное произведение 100 116 CRAY-1 Перемножение двух матриц 153 7 Положим, что средняя длина [MFLOPS] обрабатываемых векторов равна 100. Тогда 24 Т.е. для решения рассматриваемой задачи система CRAY-1 гораздо более эффективна по сравнению с системой CYBER-205 Реальная производительность (производительность на тестах). Существующие тестовые наборы можно разделить на три группы:    тесты производителей (компаний-изготовителей компьютеров), предназначенные, как правило, для сравнения однотипных компьютеров, относящихся к одному семейству; стандартные тесты, разработанные независимыми аналитиками и предназначенные для сравнения широкого спектра компьютеров; пользовательские тесты, учитывающие специфику решаемых пользовательских задач. В вычислительной практике чаще всего применяют стандартные тесты. Рассмотрим некоторые из них. Поскольку большую часть времени выполнения программ обычно занимают циклы, часто именно они применяются в качестве тестов. В настоящее время наиболее известным тестом производительности является набор тестов Linpack, который представляет собой набор программ для решения СЛАУ методом исключения Гаусса. Основным параметром тестов Linpack является порядок СЛАУ . Обычно используются тесты с =100 и тесты =1000. Известно количество операций (как функция размерности СЛАУ ), которые необходимо выполнить для решения систем линейных алгебраических уравнений (СЛАУ) методом исключения Гаусса. Поэтому, зная время решения задачи, легко найти производительность системы в MFLOPS. Известный список TOP 500, включающий в себя 500 самых высокопроизводительных компьютеров мира, строится на основе тестирования с помощью тестов Linpack. Для MPP-систем часто используют набор тестов Linpack-parallel. Приведем результаты исполнения теста Linpack-parallel на некоторых параллельных системах:    6768-процессорный Intel Paragon - 281 GFLOPS при N = 128600; Cray T916 - 522 MFLOPS при N=100; Hitachi S3800 - 6431 MFLOPS при N=1000. Для суперкомпьютеров широко используются набор тестов NAS parallel benchmark. Тесты представляют собой набор алгоритмов решения некоторых задач вычислительной газодинамики и гидродинамики. Гипотеза Минского. Гипотеза Минского. В -процессорной векторно-параллельной вычислительной системе или MIMD-вычислительной системе, в которой производительность каждого процессора равна единице, общая производительность растет как (см. рис. 1) В первых параллельных вычислительных системах, когда количество процессоров было невелико, гипотеза Минского подтверждалась. В современных системах с большим количеством процессоров имеет место зависимость производительности от числа процессоров, показанная на рис. 1 пунктиром. Основные причины такой зависимости:  с ростом количества процессоров растут коммуникационные расходы (вследствие роста диаметра коммуникационной сети); 25  с ростом количества процессоров растет несбалансированность их загрузки. Таким образом, если количество процессоров системы ну мы. превышает величи- , то целесообразно использовать мультипрограммный режим работы систе- Рис. 1. К гипотезе Минского. Компоненты коммуникационной среды Структурно коммуникационная среда состоит из трех следующих компонентов (см. рис. 1), где    - узел сети (процессор или компьютер). сетевые адаптеры; коммуникационная сеть; сетевые коммутаторы. Рис. 1. Структура коммуникационной среды. Сетевые адаптеры. 26 При обмене данными между узлами сети, не являющимися ближайшими соседями, происходит трансляция данных через промежуточные узлы. Очевидно, что в узлах должны находиться какие-то аппаратные средства, которые освобождают процессоры узлов от участия в трансляции данных. Одной из основных функций сетевых адаптеров является обеспечение трансляционных обменов данными в сети. Сетевой адаптер содержит приемопередающую часть, связанную с узловым процессором сети, приемопередающую часть, связанную с сетью, и, обычно, согласующие буферы (см. рис. 2). Основной функцией приемопередающей части адаптера, связанной с шиной узла, является реализация протокола этой шины. Основной функцией приемопередающей части адаптера, связанной с коммуникационной сетью, является реализация протокола сети. Функцией сетевого адаптера может быть также обеспечение когерентности памяти узла сети. Рис. 2. Структура сетевого адаптера. Заметим, что на основе высокоскоростных сетевых адаптеров, поддерживающих протоколы когерентности кэш-памяти, строятся NUMA-системы. Если на узловом процессоре одновременно функционирует несколько прикладных процессов, то сетевой адаптер узла может стать узким местом системы, поскольку за доступ к нему могут бороться прикладные процессы и процессы операционной системы. Поэтому иногда узловой процессор снабжают двумя сетевыми адаптерами: одним - для процессов операционной системы; другим – для прикладных процессов. Коммуникационные сети. Коммуникационные сети подразделяются на широкомасштабные коммуникационные сети (Wide Area Networks) – WAN-сети и локальные коммуникационные сети (Local Area Networks) – LAN-сети. Адресация в сетях. Множество адресов, допустимых в рамках некоторой схемы адресации, называется адресным пространством коммуникационно й сети. Адресное пространство может иметь линейную или иерархическую организацию. 27 В линейном адресном пространстве коммуникационной сети множество адресов не структурировано, все адреса равноправны. Примером линейного адресного пространства является пространство MAC (Media Access Control)-адресов, которые предназначены для однозначной идентификации сетевых интерфейсов в локальных сетях. MAC-адреса распределяются между изготовителями специальным комитетом IEEE и встраиваются в аппаратуру при ее изготовлении. Типичным представителем иерархического адресного пространства ко ммуникационной сети является пространство сетевых 4-байтовых IP (Internet Protocol)-адресов, используемых для адресации узлов в WAN-сетях. IP-адреса являются двухуровневыми: адрес делится на старшую часть (номер сети) и младшую часть (номер узла в сети). Такая организация IP-адресов позволяет передавать сообщения между сетями только на основании номера сети. Номер узла используется после доставки сообщения внутри сети. Сетевые протоколы. Правила, определяющие последовательность и формат сообщений, которыми обмениваются узлы сети, называются сетевым коммуникационным протоколом. Обычно используется набор протоколов различного уровня. В WAN-сетях обычно используются протоколы коммутации пакетов OSI (Open System Interconnection): в пункте отправления сообщение разбивается на порции (пакеты); пакеты посылаются по адресу назначения; в пункте назначения осуществляется сборка сообщения из пакетов. В параллельных вычислительных системах используются LAN-сети и как протоколы коммутации пакетов, так и протоколы коммутации каналов. Для того, чтобы уменьшить накладные расходы в LAN-сетях используют более простые протоколы обмена. Основным стандартом для коммуникационных протоколов является широко известная модель OSI, разработанная в начале 80-х годов. Модель OSI имеет семь уровней (см. рис. 3). Рис. 3. К модели OSI 28 Самой распространенной технологией на физическом и канальном уровнях является технологии Ethernet. Обычно локальные сети строятся на основе именно этих технологи. Технологии Ethernet, Fast Ethernet, Gigabit Ethernet обеспечивают скорость передачи данных, соответственно, 10, 100 и 1000 Мбит/с. Поскольку коммуникационная среда является разделяемым ресурсом, возможны ситуации, когда два узла пытаются одновременно передать кадр данных. Такая ситуация приводит к искажению информации и называетсякоммуникационной коллизией. В технологии Ethernet предусмотрен специальный механизм для разрешения коллизий. Основной недостаток сетей, построенных по технологии Ethernet, состоит в том, что в них в единицу времени может передаваться только один пакет данных. Для обеспечения высокой производительности таких сетей их не следует загружать более чем на 30–40% ее максимальной пропускной способности. Пропускная способность Ethernet-сетей значительно повышается при использовании сетевых коммутаторов. Для построения высокоскоростных коммуникационных сетей используют, например, технологию SCI (Scalable Coherent Interface) с пиковой пропускной способностью на аппаратном уровне 400 Мбит/сек. Важнейшей характеристикой коммуникационной сети является топология коммуникационной сети, под которой понимается способ соединения процессорных узлов между собой каналами передачи данных. Топологию коммуникационной сети принято изображать в виде графа, вершины которого соответствуют процессорным узлам, а ребра – каналам связи. Практически каждая параллельная вычислительная система имеет свою оригинальную топологию коммуникационной сети. Это связано с тем, что невозможно соединить много узлов быстрыми каналами связи по типу «каждый с каждым». Поэтому в параллельных вычислительных системах быстрый обмен информацией осуществляется не между всеми узлами, а только между некоторыми. Все остальные обмены осуществляются относительно медленно. Указанное разделение связей на быстрые и медленные, во-первых, порождает многообразие топологий коммуникационных сетей, а, во-вторых, является одной из основных причин ограниченности класса алгоритмов, которые могут быть эффективно реализованы на параллельной вычислительной системе. Быстрые обмены осуществляются по некоммутируемым линиям связи, медленные – либо через сетевые коммутаторы, либо с помощью последовательных быстрых обменов. Сетевые коммутаторы. Существует много типов сетевых коммутаторов (commutator, switch) - (см. ниже). При построении LAN-сетей широко используются также сетевые концентраторы (concentrator, hub). Концентратор на один из своих портов принимает сигналы от одного из узлов сети и синхронно передает их на все свои остальные порты, соединенные с другими узлами сети (см. рис. 4). 29 Рис. 4. Схема использования сетевого концентратора. Топологии коммуникационных сетей Нам понадобится далее понятие диаметра коммуникационной сети d, которым называется максимальное расстояние между двумя произвольными узлами этой сети. Расстояние между узлами коммуникационной сети - количество ребер, которые образуют кратчайший путь между двумя узлами в графе коммуникационной сети. С точки зрения топологии коммуникационные сети разделяются на сети с фиксированной топологией и на реконфигурируемые сети. С другой стороны, с этой же точки зрения коммуникационные сети разделяются на регулярные сети и нерегулярные сети. Чаще всего в параллельных вычислительных системах используют регулярные сети с фиксированной топологией. Среди этих сетей наиболее распространены топологии сетей, предоставленные на Рис.1–8, где квадратики обозначают процессоры системы. Рис. 1. Некоммутируемая коммуникационная сеть с топологий сети типа «шина» (bus). d=1 . Диаметр сети с топологией типа "шина" - см. рис. 1. Здесь и далее – количество процессоров в системе. Заметим, что шину можно интерпретировать как сетевой коммутатор с временным разделением (см. параграф 3). Рис. 2. Некоммутируемая коммуникационная сеть с топологий сети типа «линейка» (linear array, farm). В сети с топологией типа "линейка" (см. рис. 2) каждый процессор связан непосредственно только с двумя соседними (с предыдущим и последующим) процессорами. Топология является, с одной стороны, просто реализуемой, а? с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач. Диаметр сети с топологий типа «линейка» . 30 Рис. 3. Некоммутируемая коммуникационная сеть с топологий сети типа «кольцо» (ring). Сеть с топологией типа "кольцо" (см. рис. 3) получается из топологии типа «линейка» путем соединения между собой первого и последнего процессоров «линейки». Диаметр сети с топологий типа «кольцо» . Сеть с топологий типа «двумерная решетка» (см. рис. 4) может быть достаточно просто реализована и, вместе с тем, эффективно использована при реализации многих численных алгоритмов (например, при интегрировании многих систем дифференциальных уравнений в частных производных). Диаметр сети с топологий типа . Из сети с топологией типа «двумерная решетка» может быть получена сеть с топологией сети типа «тор». Для этого достаточно соединить , между собой ,…, ,…, граничные и процессоры по по «горизонтали» «вертикали» , . Рис. 4. Некоммутируемая коммуникационная сеть с топологий сети типа «двумерная решетка» (mesh). 31 Рис. 5. Пример (N=6) некоммутируемой полносвязной коммуникационной сети – «клика» (full connect). В полносвязной сети (см. рис. 5) между любой парой процессоров существует непосредственная связь. Полносвязная сеть обеспечивает минимальные время обмена данными между любыми двумя процессорами системы, однако сложно реализуема и имеет высокую стоимость при большом количестве процессоров. Диаметр сети с топологией типа "клика" . Рис. 6. Некоммутируемая коммуникационная сеть с топологий сети типа «бинарное дерево» (tree). Диаметр сети с топологией типа "бинарное дерево" log2 - см. рис. 6. 32 Рис. 7. Пример (N=7) некоммутируемой коммуникационной сети с топологий сети типа «звезда» (star). Сеть с топологией типа "звезда" (см. рис. 7) эффективна, например, при организации централизованных схем параллельных вычислений. Диаметр сети с топологий типа «звезда» =2. Диаметр сети с топологией типа "гиперкуб" =log2 , =2p где – количество измерений гиперкуба – см. рис. 8. В сети с топологий «гиперкуб» диаметр сети медленно растет с ростом числа процессоров в системе. Например, при , при , . заметим, что в p-мерном гиперкубе каждый процессор непосредственно связан ровно с p соседями. Рис. 8. Пример (трехмерный гиперкуб, N=8) некоммутируемых коммуникационных сетей с топологий сети типа «гиперкуб» (hypercube). Процессоры в гиперкубе нумеруют с помощью бинарного отраженного кода Грея по следующему правилу (см. рис. 8): 33  два процессора непосредственно связаны друг с другом, если двоичное представление их номеров имеет только одну различающуюся позицию; Утверждение. Если процессоры в гиперкубе пронумерованы с помощью двоичного отраженного кода Грея по указанному выше правилу, то расстояние между двумя любыми процессорами равно количеству различающихся битовых значений в номерах этих процессоров Отсутствие в коммуникационной сети непосредственной связи между двумя некоторыми процессорами приводит к необходимости определения оптимального пути передачи данных между этими процессорами (если, конечно, они коммутируют). В общей постановке эта задача представляет собой одну из трудоемких задач теории графов. Для гиперкубов решение этой задачи существенно упрощает сделанное выше утверждение. Заметим, что вычислительные системы, имеющее большое количество процессоров, имеют обычно иерархическую коммуникационную сеть . В такой сети все процессоры разбиваются на группы с одинаковым и относительно небольшим количеством процессоров (~32 - 64) в каждой. Физически группа процессоров монтируется в один блок или стойку. Каждая из этих групп процессоров имеет коммуникационную сеть одной топологии. Группы процессоров объединяются между собой коммуникационной сетью той же или другой топологии. Бинарный отраженный код Грея. Далее нам понадобятся некоторые сведения о бинарном отраженном коде Грея (binary reflected Gray code). В бинарном отраженном коде Грея соседние по величине числа отличаются лишь в одной кодовой позиции, т.е. при последовательном переходе от одного числа к соседнему в коде Грея изменяется только один из двоичных разрядов. В отличие от обычного двоичного кода, например, 112=310, 1002=410. Число число , записанное в двоичном коде, можно преобразовать в в коде Грея следующим образом (см. пример 1): где означает сложение по модулю два, т.е. сложение по правилу 0 0=0; 0 1=1; 1 0=1; 1 1=0. Аналогично, число зовать в двоичное число , записанное в коде Грея, можно преобра= ... следующим образом (см. пример 2): Свойство кода Грея изменяться только в одном разряде при последовательном переходе от одного числа к другому определяет его преимущество перед другими кодами при создании кодирующих дисков. Это же свойство кода Грея делает целесообразным его применение при решении дискретных задач оптимизации с помощью генетического алгоритма. Пример 1 Преобразуем двоичное число 110101 в двоичный код Грея (см. рис. 9). 34 Рис. 9. К примеру 1. (110101)B=(101111)G. Пример 2 Преобразуем число в коде Грея 101111 в двоичное (см. рис. 10). Рис. 10. К примеру 2. (101111)G=(110101)B. Сетевые коммутаторы Сетевые коммутаторы разделяются на простые сетевые коммутаторы и составные сетевые коммутаторы. Простые коммутаторы имеют малую задержку, но могут быть использованы только для построения систем с малым числом узлов. Составные коммутаторы строятся путем объединения простых коммутаторов. Простые коммутаторы. Простые коммутаторы делятся на коммутаторы с временным разделен ием и коммутаторы с пространственным разделением . Коммутаторы с временным разделением представляют собой шины. Так как шина является разделяемым ресурсом, процессорные узлы вынуждены конкурировать за доступ к этому ресурсу. Для разрешения конфликтов в узлах используются различные алгоритмы арбитража. Имеется несколько стандартов на шинные структуры, например, стандарты PCI, VME, Fastbus и др. Шина является достаточно дешевым и надежным коммутатором. Однако при коммутации большого количества коротких сообщений накладные расходы на арбитраж становятся значительными, что существенно ограничивает пропускную ее способность. Коммутаторы с пространственным разделением (координатный коммутатор). Коммутатор с пространственным разделением представляет собой совокупность мультиплексоров, число которых равно количеству выходов коммутатора (см. рис. 1). 35 Коммутаторы с пространственным разделением имеют минимальное время задержки на коммутацию, но высокую сложность, а потому и недостаточно высокую надежность. Одним из самых важных свойств коммутаторов с пространственным разделением является то, что он представляет собой неблокирующую коммуникационную сеть. Т.е. ни один из входов не может получить отказа от соединения изза занятости какого-либо мультиплексора (конечно, при условии, что свободен требуемый выход). Еще одним важным достоинством такого коммутатора является отсутствие необходимости планирования схемы соединений. Рис. 1. Структура простого пространственного 3*3 коммутатора. МП – мультиплексор. Свое второе название (координатные коммутаторы) простые коммутаторы с пространственным разделением получили по той причине, что схему коммутации с помощью этого коммутатора можно представить в виде, представленном на рис. 2. Рис. 2. Другой вид координатного коммутатора, представленного на рис. 1. Составные коммутаторы. Основная идея создания составных коммутаторов состоит в объединении простых коммутаторов каналами типа «точка - точка». Составной коммутатор требует меньше оборудования, чем простой коммутатор с таким же количеством входов – выходов. Однако составной коммутатор при этом имеет большую задержку на коммутацию, которая растет пропорционально количеству уровней коммутации (см. ниже). 36 Чаще всего составные коммутаторы строятся на основе 2*2 простых коммутаторов с пространственным разделением - см. Рис.3. Рис. 3. Упрощенная схема 2*2 простого коммутатора с пространственным разделением. Функционированием блока коммутации управляет блок управления с помощью бинарной переменной : если =0 - выполняется прямое соединение входов и выходов (Вход 1 – с Выходом 1, а Вход 2 – с Выходом 2); если =1 - выполняется перекрестное соединение входов и выходов (Вход 1 – с Выходом 2, а Вход 2 – с Выходом 1). Блок управления также производит арбитраж запросов входов, если они требуют соединения с одним выходом. Управление производится на основе бинарных управляющих сигналов . К примеру, означает запрос Входа 1 на коммутацию; при означает, что требуется соединение Входа 1 с Выходом 1. В случае конфликта (когда и , и ), выполняется запрос , а источнику второго входного сигнала передается сигнал занятости =1. Заметим, что управляющие сигналы могут быть выработаны в самом блоке управления, если данные, поступающие на вход коммутатора, предварить требуемым номером выхода (в составных коммутаторах именно так и делается). Коммутатор Клоза. В качестве примера составного коммутатора рассмотрим коммутатор Клоза. Коммутатор состоит из трех уровней коммутации – входного, промежуточного и выходного. Коммутатор Клоза имеет одинаковое количество входов и выходов и состоит из входных таторов, из таких же выходных коммутаторов и из простых коммутаторов. простых комму- промежуточных 37 Рис. 4. Пример коммутатора Клоза (управляющие сигналы не показаны).m=3, l=4. K – простой коммутатор. Соединения простых коммутаторов в коммутаторе Клоза выполняется по следующему правилу (см. рис. 4):  -й выход коммутатора  -й вход коммутатора соединяется с соединяется с -м входом коммутатора -м выходом коммутатора Общее количество простых коммутаторов в коммутаторе Клоза равно Коммутатор Клоза представляет собой блокирующую коммуникационную сеть. Вход здесь может получить отказа от соединения из-за занятости какоголибо простого коммутатора. Омега коммутатор. Пример 3-х уровневого омега-коммутатора, имеющего =8 входов и столько же выходов, приведен на рис. 5. Коммутатор содержит 12 простых 2*2 коммутаторов. В общем случае входов и выходов требуется уровней коммутации с простых 2*2 коммутаторов на каждом уровне. Таким образом, омега-коммутатор требует простых коммутаторов, где - количество простых коммутаторов в аналогичном координатном коммутаторе. 38 Рис. 5. Пример омега-коммутатора. Схема соединений простых коммутаторов в омега-коммутаторе называется идеальным тасованием. Данные, поступающие на входы омега-коммутатора, предваряются требуемым двоичным номером выхода. Правило коммутации: если соответствующий разряд номера выхода содержит «0», то коммутатор соединяет вход с верхним выходом, а если «1» - с нижним выходом. Поясним логику переключений простых коммутаторов в омега-коммутаторе на следующем примере. Пример 1 Положим, что входу 011 необходимо соединение с выходом 110. Тогда коммутатор анализирует первый (старший) разряд номера выхода. Он равен «1», поэтому коммутатор ром соединяет вход 011 со своим нижним выходом, т.е. с коммутато- . Аналогично, на основе анализа второго разряда требуемого номера входа коммутатор соединяет свой вход со своим нижним выходом, т.е. с коммутато- ром . Наконец, на основе анализа третьего (младшего) разряда коммутатор единяет свой вход со своим верхним выходом со- Омега-коммутатор также представляет собой блокирующую коммуникационную сеть. Основные характеристики коммуникационных сетей Параметры графа межузловых связей. Расстоянием между узлами коммуникационной сети называется количество ребер, которые образуют кратчайший путь между этими узлами в графе коммуникационной сети. Например, расстояние между процессорами (см. рис. 1) равно 2. Диаметром коммуникационной сети d называется максимальное расстояние между двумя произвольными узлами этой сети. Например, диаметр сети, представленной на рис. 1. равен 3 (поскольку расстояние процессорами примеру, равно 3). , , к 39 Средним диаметром коммуникационной сети называется среднее расстояние между двумя узлами этой сети. Уменьшение диаметра коммуникационной сети и среднего диаметра коммуникационной сети, очевидно, уменьшает количество транзитных обменов данными. Важной характеристикой топологии коммуникационной сети является также связность коммуникационной сети. Связность сети характеризует количество различных маршрутов передачи данных между процессорами сети. Числовая характеристика связности может быть определена разными способами. Например, в качестве меры связности можно использовать минимальное количество межпроцессорных связей, которое необходимо удалить для разделения сети на две несвязные подсети. Связность сети, представленной на рис. 1, в этой мере равна 2, поскольку для образования двух подсетей (например, первая подсеть – процессор , вторая подсеть - процессоры ) необходимо удалить минимум две связи. Связность коммуникационной сети в значительной мере определяет отказоустойчивость вычислительной системы. Высокая связность позволяет системе продолжить свое функционирование при выходе из строя большего количества узлов и связей между ними. Производительность. Производительность коммуникационной сети определяется две следующими основными характеристиками: латентность коммуникационной сети – время подготовки к передаче информации по каналу сети; пропускная способность коммуникационной сети - скорость передачи информации по каналам сети или, более строго, количество информации, передаваемой между узлами сети в единицу времени. Рис. 1. Пример графа коммуникационной сети. Квадратики изображают процессоры. 40 Наряду с латентностью коммуникационной сети используют понятие полной латентности коммуникационной сети, которая складывается из программной и аппаратной составляющих. Заметим сразу, что наличие латентности определяет тот факт, что максимальная скорость передачи по сети не может быть достигнута на сообщениях с небольшой длиной. При этом скорости передачи данных на сообщениях с большой и малой длины могут отличаться на порядок. Отсюда следует важный практический вывод – при разработке параллельных алгоритмов и их программной реализации следует стремиться к сокращению не только общего объема передаваемых данных, но и к сокращению количества пересылок «коротких» данных. Одним из путей достижения этого является объединение данных в крупные блоки данных. Полная пропускная способность коммуникационной сети, которую «видит» приложение, снижается программным обеспечением за счет передачи разного рода служебной информации. Так, например, уже упоминавшаяся коммуникационная технология SCI обладает пиковой пропускной способностью на аппаратном уровне около 400 Мбайт/cек. А реальная пропускная способность на уровне MPIприложений (см. главу 2.7) достигает всего примерно 80 Мбайт/cек. (при использовании в узловом процессоре 32-разрядной шины PCI с частотой 33 МГц). Заметим. что скорость обмена процессора со своей оперативной памятью составляет 3 Гбайт/сек и выше. В целом для любой коммуникационной технологии имеет место следующая оценка: на реальных задачах скорости передачи данных получаются на 20-40%, а иногда на все 100% хуже, чем максимально возможные. Различают следующие виды пропускной способности сети:   пропускная способность «точка-точка» (uni-directional bandwidth); пропускная способность двунаправленных пересылок (bi-directional bandwidth). Пропускная способность «точка-точка» равна максимальной скорости, с которой процесс в одном узле сети может передавать данные другому процессу в другом узле сети. Пропускная способность двунаправленных пересылок равна максимальной скорости, с которой процессы, функционирующие на разных узлах сети, могут одновременно обмениваться данными по сети. Полное время деляется , необходимое на передачу сообщения длины , опреследующим образом: где – латентность, – длина сообщения, – пропускная способность канала связи. Если параллельная вычислительная система предназначена для решения задач, в которых велика доля коммуникационных операций, то грубо требуемую пропускную способность каналов коммуникационной сети можно определить по следующему правилу: ―Скорость межпроцессорных обменов между двумя узлами, измеренная в Мбайт/сек, должна быть не менее 1/10 пиковой производительности вычислительного узла, измеренной в MFLOPS‖. Заметим, для примера, что для коммуникационной сети суперкомпьютера Cray T3D латентность составляет ~1 мкс, пропускная способность - 480 Мбайт/сек, Масштабируемость. Важным свойством топологии коммуникационной сети является возможность обеспечения масштабируемости вычислительной системы, которая использует эту 41 сеть. С этой точки зрения хорошо масштабируются вычислительные системы, имеющие топологию сети типа «линейка», «кольцо», «клика». Здесь наращивание системы возможно по одному процессору. В сети с топологией «клика» каждый процессор связан каналом связи с другими процессорами. Поэтому добавление одного процессора в данном случае требует добавления каналов связи, что затрудняет масштабирование систем с топологией этого типа. Для построения сетей с топологией «плоская * двумерная решетка» (а также «тор») требуется процессоров, а значит, наращивание числа процессоров в данном случае возможно только квантами по или процессоров. Для построения сетей с топологией «гиперкуб» требуется, как мы уже отмечали, процессоров, где – количество измерений гиперкуба. Это значит, что система каждого следующего измерения должна содержать вдвое больше процессоров, чем предыдущая система. Кроме того, система с топологией «гиперкуб» требует для своей реализации наличия p каналов связи на каждом процессорном узле. Это обстоятельство также ограничивает возможности наращивания числа узлов в системе. Нейросетевые вычислительные системы Рассмотренные выше классы параллельных вычислительных систем ориентированы на решение хорошо формализованных задач, сводящиеся к расчетам по формулам для заданных исходных данных. Однако существуют широкий класс практически важных, но плохо формализованных задач, например, таких как    распознавание образов; кластеризация данных; оптимизация ( -полные задачи). Нейросетевые вычислительные машины предназначены для решения именно таких задач. Искусственный нейрон. Нейрон (см. Рис.1) задается вектором входов нейрона ром весов входов нейрона ), функцией активации нейрона векто- , функцией состояния нейрона и выходом нейрона ( . Рис. 1. Условное изображение искусственного нейрона. Функция состояния нейрона определяет состояние нейрона в зависимости от его входов, весов входов и, возможно, предыдущих состояний нейрона. Чаще 42 всего используют следующие функции состояния нейрона, не зависящие от предыдущего состояния. 1. Скалярное произведение векторов , : (1) 2. 3. Расстояние между векторами мер, , измеренное в некоторой метрике. Напри- (2) 4. Нейрон с функцией состояния (1) называется персептроном, с функцией состояния (2) – нейроном с радиальными базисными функциями . Функция активации нейрона определяет выход нейрона как функцию его входа тивации: . Наиболее распространенными являются следующие функции ак- Рис. 2. Ступенчатая пороговая функция активации.  ступенчатая где  функция активации (см. рис. 2) – некоторая константа; линейная где пороговая пороговая функция – некоторые константы; активации (см. рис. 3) 43 Рис. 3. Линейная пороговая функция активации.  сигмоидальная где функция активации (см. рис. 4) – некоторые константы; Рис. 4. Сигмоидальная функция активации.  гауссова где функция активации (см. Рис.5) – некоторые константы; Рис. 5. Функция активации - гауссиан. Нейронные сети. Нейронная сеть образуется путем объединения выходов нейронов с входами нейронов. В зависимости от вида графа межнейронных соединений нейронные сети делятся на следующие два класса сетей:   ациклические нейронные сети (см. рис. 6); циклические нейронные сети (см. рис. 7). 44 Рис. 6. Пример ациклической нейронной сети. Рис. 7. Пример циклической нейронной сети. Нейронная сеть, построенная на основе персептронов, называется персептронной нейронной сетью. Нейронная сеть, построенная на основе нейронов с радиальными базисными функциями, называется нейронной сетью с радиальными базисными функциями. Нейронные сети делятся на конструируемые и обучаемые сети. В конструируемых нейронных сетях число нейронов, их тип, граф межнейронных связей и веса входов нейронов определяются при создании сети, исходя из задачи, которую должна решать сеть. Конструируемые нейронные сети используются, например, в качестве ассоциативной памяти (памяти, адресуемой по содержанию). В обучаемых нейронных сетях их графы межнейронных связей и веса входов нейронов изменяются в процессе обучения нейронной сети. Обучение обучаемых нейронных сетей Различают наблюдаемое обучение нейронных сетей , ненаблюдаемое обучение и смешанное обучение:    наблюдаемое обучение нейронных сетей имеет место в том случае, когда известны правильные выходы нейронной сети; при ненаблюдаемом обучении нейронных сетей добиваются того, чтобы «близкие» входные векторы формировали «близкие» выходы нейронной сети. Ненаблюдаемое обучение используется, например, при решении задачи кластеризации; при смешанном обучении нейронных сетей часть параметров определяется при наблюдаемом обучении, а часть – при ненаблюдаемом обучении. 45 Введем в рассмотрение пространство входов нейронной сети . Оси ко- ординат этого пространства соответствуют входам нейронной сети пространстве (см. рис. 8). . В определим множество допустимых входов нейронной сети Рис. 8. Пространство входов нейронной сети X и множество допустимых входов нейронной сети DX. n=2. В задачах, которые эффективно решаются нейронными сетями, точки множества образуют связные области, все точки каждой из которых обладают одним и тем же свойством, например, принадлежат одному и тому же кластеру. Задача конструирования или обучения нейронной сети в этих терминах состоит в том, чтобы при принадлежности входного вектора нейронной сети разным областям формировались различные выходные сигналы нейронной сети. Можно сказать, что в результате обучения нейронной сети она запоминает расположение этих областей во множестве . Запоминание расположения областей по разному реализуется в персептронных нейронных сетях и в нейронных сетях с радиальными базисными функциями. В персептронных нейронных сетях запоминание областей реализуется с помощью гиперплоскостей (см. рис. 9). Каждый нейрон такой сети весами своих входов задает гиперплоскость Изменение весов входов, числа нейронов и графа межнейронных связей меняет набор и расположение разделяющих гиперплоскостей. В нейронных сетях с радиальными базисными функциям каждый нейрон задет значениями весов своих входов координаты центра гипершара, а коэффициентом, связывающим и – радиус этого гипершара (см. рис. 10). 46 Рис. 9. К запоминанию областей в персептронных нейронных сетях. N=2. Рис. 10. К запоминанию областей в нейронных сетях с радиальными базисными функциям. N=2. Большинство алгоритмов обучения нейронных сетей используют эвристические алгоритмы формирования графов межнейронных сетей и весов входов нейронов. Обучение персептронной нейронной сети производится по следующей схеме. 1. Выбор начальной межнейронной сети. Число входов и выходов сети определяется постановкой задачи. Граф межнейронных связей обычно выбирается эвристически. Например, по одной из эвристик в качестве начальной рекомендуется взять трех-слойную нейронную сеть с числом нейронов внутреннего слоя, равным полусумме числа входов и выходов нейронной сети. При этом каждый нейрон внутреннего слоя должен быть связан с выходами всех входных нейронов сети, а каждый выходной нейрон должен быть связан с выходами всех нейронов внутреннего слоя. 2. Подбор весов входов нейронов так, чтобы нейронная сеть решала поставленную задачу. Известным алгоритмом определения весов нейронов для персептронных нейронных сетей является алгоритм обратного распространения (см. ниже), для которого доказана его сходимость. Широко используются для подбора 47 весов нейронов различные алгоритмы случайного поиска, например, генетические алгоритмы. 3. Изменение графа межнейронных связей (если подбор весов не удался) и переход к п. 2. Для этого используют различные эвристики, например, эвристики на основе генетических алгоритмов. Алгоритм обратного распространения. Рассмотрим простейшую нейронную сеть - обучаемый нейрон с пороговой функцией активации. Пусть имеется обучающий набор примеров Здесь - входные значения -го примера, - правиль- ное выходное значение -го примера. Считается, что нейрон правильно обучен, если (3) ки. - выход нейрона в j-ом примере, – заданная допустимая величина ошиб- Алгоритм обратного распространения состоит из следующих основных шагов: 1. Присвоить весам входов нейрона и порогу функции активации случайные малые значения; 2. Начиная с первого примера, подать на входы нейрона очередной пример 3. Изменить и определить значение выхода нейрона веса по ; правилу 4. Производить шаги 2 – 4 до тех пор, пока не выполнится условие (3). В алгоритме обратного распространения для многоуровневых нейронных сетей изменяется шаг 3 приведенного выше алгоритма (значительно усложняется). Интерпретация нейронных сетей. Алгоритм, который реализует данная нейронная сеть, может быть интерпретирован универсальной ЭВМ или некоторым специализированным устройством. Интерпретация нейронной сети на универсальной ЭВМ выполняется с помощью специальных программ для однопроцессорных и многопроцессорных ЭВМ. Широко известны программные эмуляторы фирм Brain Maker, Neural Works. Интерпретация нейронной сети специализированными устройствами. Известны цифровые, аналоговые и гибридные нейрочипы для интерпретации нейронных сетей. Базисной операцией нейрочипов для персептронных нейронных сетей является операция скалярного произведения векторов, для нейронных сетей с радиальными базисными функциям – операция вычисления расстояния между векторами (в некоторой метрике). 48 Чаще всего используются цифровые нейрочипы. Одним из первых коммерчески доступных нейрочипов был 16-ти разрядный нейрочип Micro Devices MD 1220, который интерпретировал 8 нейронов (разрядность нейрочипа относится к разрядности весов входов и разрядности операций сложения и умножения). Современные цифровые нейрочипы интерпретируют сотни нейронов. На основе нейрочипов выпускаются нейросетевые платы и нейрокомпьютеры. Принято производительность нейрокомпьютерных устройств измерять в количестве соединений в секунду – CPS (connections per second). Под соединением понимается умножение вектора входа нейрона на вектор весов и сложение результата с накопленной функцией. Для измерения производительность нейрокомпьютерных устройств используется также величина «число изменений весов в секунду» - CUPS (connections update per second), которая позволяет оценить скорость обучения нейронной сети. Современные нейрочипы имеют производительность порядка нескольких сотен MCPS. Производительность нейросетевых плат достигает десятков GCPS. Вычислительные машины потока данных и ассоциативные вычислительные машины Вычислительные машины потока данных. По типу управления параллельные вычислительные машины можно разделить на традиционные вычислительные машины с программно-логическим управлением и вычислительные машины потока данных (Data Flow Machine). Большинство современных вычислительных систем являются системами с программнологическим управлением. В машинах потока данных вычисления инициируется не очередными командами программы, а готовностью к обработке необходимых данных. Операнды каждой команды снабжаются флагами готовности к обработке – тэгами: где КОП – код операции. О готовности операнда сигнализирует состояние «1» соответствующего тэга. Если не все тэги операции установлены в состояние «1», то команда находится в состояние «ожидание». При установке всех тэгов в состояние «1» команда переводится в состояние «готова к выполнению». На каждом такте готовые к исполнению команды распределяются коммутатором по процессорам (см. рис. 1). Потенциально такой подход позволяет достичь высокой степени параллелизма. Эффективность потоковых машин во многом определяется программированием, от которого требуется формулировка задачи в терминах параллельных и независимых операций. Одной из основных проблем при создании потоковых машин является проблема реализации циклов. Рассмотрим поток данных, который имеются два цикла, подготавливающие данные друг для друга - см. рис. 2, где a1 – d1, a2 – d2 – операторы программы, а стрелки показываю направление потока данных. Если, к примеру, первый цикл вторично подошел к точке d1, где требуются данные a2 от второго цикла, то необходим механизм, который позволял бы первому циклу узнать, не устарели ли требуемые ему данные a2 и не нужно ли подождать, пока они обновятся? Кроме того, из приведенного примера видно, что без специально- 49 го механизма инициализации циклов вычисления в обоих циклах не сможет начаться. Рис. 1. Структура вычислительной системы потока данных. Рис. 2. Поток данных с взаимодействующими циклами. Известно много проектов потоковых вычислительных машин, например, машины Tagged Token и Monsoon (США); Sigma, EMS и EMC-4 (Япония) и др. В России также ведутся работы в области потоковых вычислений. ЭВМ с архитектурой потока данных в настоящее время промышленно не выпускаются. С другой стороны, элементы потоковых машин нашли применение в современных суперскалярных процессорах (например, в микропроцессорах Intel Pentium Pro, HP РА-8000) и процессорах с длинным командным словом (VLIW). Ассоциативные вычислительные машины. Во все возрастающей степени вычислительные машины используются не для решения вычислительных задач, а для задач хранения, поиска и преобразования данных. Для решения таких задач традиционные архитектуры вычислительных машин, ориентированных на адресную обработку данных, оказываются малоприспособленными. Рассмотрим, например, типичный запрос к базе данных SELECT имя FROM сотрудники WHERE возраст < 30 AND зарплата > 10000. Здесь имена служащих выбираются из базы данных не по адресу, а по содержимому полей "возраст" и "зарплата". Этот способ адресации называется ассоциативной адресацией. В современных компьютерах с традиционной архитектурой ассоциативная адресация, по сути, эмулируется путем создания специальных таблица для перевода ассоциативного запроса в соответствующий адрес. В ассоциативных вычислительных машинах ассоциативная адресация реализуется с помощью ассоциативного запоминающего устройства (АЗУ) – см. 50 рис. 3, где РгАП - регистр ассоциативных признаков; РгМ - регистр маски; РгИА регистр индикаторов адреса. В АЗУ могут быть и другие элементы, наличие и функции которых определяются способом использования АЗУ. Рис. 3. Структура ассоциативного запоминающего устройства. Выборка информации из ассоциативного запоминающего устройства происходит по следующей схеме (принято, что разрядность ячеек запоминающего массива равна m и в исходном состоянии все разряды регистра индикаторов адреса имеют значение «1»). 1. В регистр ассоциативных признаков из устройства управления передается бинарный вектор признаков искомой информации, имеющий от 1 до разрядов. 2. Если для выборки информации должен использоваться весь вектор признаков, то он без изменения поступает на схему сравнения; в противном случае - ненужные разряды этого вектора маскируются с помощью регистра маски. Будем говорить, что на схему сравнения поступает маскированный вектор признаков. 3. Производится сравнение содержимого первого разряда всех ячеек запоминающего массива с содержимым первого разряда маскированного вектора признаков. Если содержимое первого разряда ячейки с номером не совпадает с содержимым первого разряда регистра ассоциативных признаков, то соответствующий этой ячейке разряд регистра индикаторов адреса устанавливается в состояние «0». 4. Аналогично производится сравнение второго разряда всех ячеек запоминающего массива с содержимым второго разряда регистра ассоциативных признаков. И т.д. до исчерпания всех разрядов. В результате в регистре индикаторов адреса в состоянии «1» останутся те разряды, которые соответствуют ячейкам запоминающего массива, содержащим информацию, совпадающую с записанной в маскированном векторе признаков. 5. Информация из отобранных ячеек считывается в некоторой последовательности, определяемой устройством управления Запись новой информации в запоминающий массив производится без указания номера ячейки. Для этого один из разрядов каждой ячейки используется для ука- 51 зания ее занятости, что позволяет осуществлять поиск свободных ячеек по рассмотренной выше схеме. Обычно ассоциативные запоминающие устройства строятся таким образом, что кроме ассоциативной допускается и прямая адресация данных. Из описанной схемы работы ассоциативного запоминающего устройства видно, что время поиска информации в запоминающем массиве зависит только от числа разрядов в маскированный вектор признаков, но не зависит от числа ячеек запоминающего массива. Этим обстоятельством определяется важное преимущество ассоциативного запоминающего устройства перед адресными запоминающими устройствами (поскольку в адресных запоминающих устройствах при операции поиска может быть необходим перебор всех ячеек запоминающего массива). С точки зрения предмета курса, главным достоинством ассоциативного запоминающего устройства является то, что с помощью этого устройства быстро и просто формируется нескольких параллельных потоков идентичной информации, которая может обрабатываться параллельно. Именно это обстоятельство позволяет на основе ассоциативных запоминающих устройств строить ассоциативные вычислительные машины, относящиеся к классу SIMD-систем. В этих машинах разные процессоры параллельно обрабатывают указанные потоки информации. Наиболее характерным представителем группы ассоциативных вычислительных машин является система STARAN (США). В отличие от рассмотренной выше схемы ассоциативной памяти, ассоциативная память STARAN является ассоциативной памятью с многомерным доступом , т. е. в нее можно обратиться как поразрядно, так и пословно. Каждому слову памяти в системе соответствует процессорный элемент. Классификация мультипроцессорных операционных систем Программное обеспечение параллельных вычислительных си стем можно разделить на системное программное обеспечение (операционные системы) и инструментальное программное обеспечение, из которого мы выделим:    компиляторы языков программирования высокого уровня; анализаторы кода и выполнения; библиотеки прикладных программ. Операционные системы для параллельных вычислительных систем можно разделить на три следующих класса: ОС мультипроцессоров (ЭВМ с общей памятью); ОС мультикомпьютеров (систем с распределенной памятью) – распределенные ОС; сетевые ОС. В данном курсе рассматриваются два первых класса ОС для параллельных вычислительных систем. Можно выделить следующие типы мультипроцессорных операционных систем. 1.Каждый процессор имеет свою ОС. Такая организация мультипроцессорных ОС использовалась на заре развития мультипроцессоров. В этом случае вся оперативная память статически разделяется на области по числу процессоров, каждому процессору выделяется своя область оперативной памяти и своя копия ОС. Т.е. процессоры работают как независимые компьютеры. Для оптимизации использования оперативной памяти возможно совместное использование всеми процессорами одного кода ОС и раздельно хранить только копии данных 52 ОС - см. рис. 1, где - процессор, - общая память, - область памяти для хранения данных операционной системы, обслуживающей процессор , и прочих данных этого процессора. При данной организации ОС каждый процессор имеет свой набор пользовательских процессов (ПП), и возможности перераспределения процессов между процессорами нет. Поэтому возможна ситуация, когда один из процессоров перегружен, а остальные (или некоторые) процессоры простаивают. Кроме того, в этом случае каждый процессор может использовать только свою область памяти. Поэтому одному из процессоров памяти может не хватать и он будет вынужден постоянно заниматься свопингом, а у других процессоров может быть излишек свободной памяти. Рис. 1. К организации операционной системы мультипроцессора «каждый процессор имеет свою ОС». 2. ОС имеет только один процессор - "хозяин". При таком способе организации операционной системы мультипроцессора используется (положим, процессором ) всего одна копия ОС (см. рис. 2). Процессоры выполняют только пользовательские процессы. Процессор , если у него есть свободное время, также может выполнять пользовательские процессы. При данной организации ОС возможно перераспределение процессов между процессорами. Поэтому невозможна ситуация, когда один из процессоров перегружен, а другие процессоры простаивают. Оперативная память здесь также может перераспределяться между процессорами. Недостатком данной организации ОС является то, что при большом количестве процессоров процессор может стать узким местом системы. Таким образом, такая модель применима только для небольших мультипроцессоров. Рис. 2. К организации операционной системы мультипроцессора «ОС имеет только один процессор». 53 3. ОС может иметь любой процессор. Здесь, как и в предыдущей схеме, в оперативной памяти находится всего одна копия операционной системы, но выполнять ее может любой из процессоров системы (см. рис. 3). Операционную систему с такой организацией естественно использовать на SMP-системах. При этом может быть обеспечена загрузка всех процессоров системы, возможно перераспределение памяти между процессорами и по сравнению с предыдущей организацией устраняется перегрузка процессора . Однако в системах с такой организацией узким местом становится код ОС, поскольку любой процессор может выполнять код ОС, но в каждый момент времени только один процессор может делать это (реализуется с помощью блокировок). Поэтому с точки зрения эффективности данная организация ОС также плоха, как и предыдущая организация. Последний недостаток рассматриваемой организации ОС в значительной мере преодолевается расщеплением операционной системы на такие части, как планирование вычислительных процессов, обращение к файловой системе, обработка страничных прерываний. В этом случае один процессор может выполнять ту часть операционной системы, которая осуществляет планирование процессов. В это же время другой процессор может выполнять файловую подсистему ОС и т.д. В этом случае, очевидно, также возможны взаимные блокировки, но степень распараллеливания работы ОС в общем случае выше. Реализация такой операционной системы представляет собой весьма сложное дело. Однако подобная организация ОС используется в большинстве современных мультипроцессоров. Рис. 3. К организации операционной системы мультипроцессора «ОС может иметь каждый процессор». Заметим, что в настоящее время становится общепринятым введение в операционные системы средств, поддерживающих мультипроцессорную обработку данных. Основные понятия многопроцессорных операционных систем ОС многопроцессорной вычислительной системы должна, прежде всего, выполнять функции обычной операционной системы: обрабатывать вызовы; управлять памятью; поддерживать файловую систему; управлять устройствами вводавывода. Кроме того, многопроцессорная операционная система должны выполнять ряд специфических функций. Выделим из них четыре следующие функции, рассматриваемые в данном курсе:  функция синхронизации параллельных процессов; 54    функция коммуникации параллельных процессов; функция управления распределенной памятью (в системах с распределенной памятью); функция планирования параллельных процессов. Отметим, что три первые функции находят непосредственное отражение в языках программирования высокого уровня. Четвертая функция в значительной мере определяет производительность многопроцессорной системы. Кроме очевидных требований надежности и производительности к ОС многопроцессорной ЭВМ предъявляются следующие требования. Прозрачность операционной системы – пользователь не должен знать, где расположены те или иные ресурсы; пользователи должны разделять ресурсы автоматически (средствами ОС). Масштабируемость операционной системы - выход из строя одного из процессоров системы или увеличение количества процессоров в ней не должны приводить к отказу ОС. Для обеспечения масштабируемости системы ни один из процессоров не должен иметь полной информации о состоянии системы, процессоры должны принимать решения на основе только локальной информации, не должны использоваться глобальные часы. Центральным понятием операционной системы для многопроцессорных вычислительных систем является понятие процесса. Процессы. Единицы работы, между которыми операционная система разделяет процессоры и другие ресурсы вычислительной системы, называется процессом. Любая работа вычислительной системы состоит в выполнении некоторой программы. Поэтому можно сказать, что процесс – это выполнение вычислительной системой некоторой системной или прикладной программы или их фрагмента. Каждому процессу в операционной системе соответствует контекст процесса. Этот контекст включает в себя:    пользовательский контекст (соответствующий программный код, данные, размер виртуальной памяти, дескрипторы открытых файлов и пр.); аппаратный контекст (содержимое регистра счетчика команд, регистра состояния процессора, регистр указателя стека, а также содержимое регистров общего назначения); системный контекст (состояние процесса, идентификатор соответствующего пользователя, идентификатор процесса и пр.). Важно, что из-за большого объема данных контекста процесса, переключение процессора системы с выполнения одного процесса на выполнение другого процесса (смена контекста процесса) является относительно дорогостоящей операцией. Для уменьшения времени смены контекста процесса в современных ОС (например, в ОС UNIX) наряду с понятием процесса широко используется понятие легковесного процесса ―light-weight process‖ или понятие потока, нити "thread". Легковесный процесс можно определить как подпроцесс некоторого процесса, выполняемый в контексте этого процесса - см. рис. 1. Контекст процесса содержит общую для всех его легковесных процессов информацию - виртуальная память, дескрипторы открытых файлов и т.д. Остальная информация из контекста процесса переходит в контексты его легковесных процессов. 55 Рис. 1. К определению легковесного процесса. Простейшим процессом является процесс, состоящий из одного легковесного процесса. Принципиальным является то обстоятельство, что нити одного процесса выполняются в общей виртуальной памяти, т.е. имеют равные права доступа к любым частям виртуальной памяти процесса. Операционной системой основной ресурс вычислительной системы – процессорное время – выделяется не процессу, а легковесному процессу. На основе сказанного, процесс можно определить как некоторый контекст, включающий виртуальную память и другие системные ресурсы, в котором выполняется, по крайней мере, один легковесный процесс, обладающий своим собственным (более простым) контекстом. ОС «знает» о существовании двух указанных уровней контекстов и способна сравнительно быстро изменять контекст легковесного процесса, не изменяя общего контекста процесса. Заметим, что для синхронизации легковесных процессов, работающих в общем контексте процесса, можно использовать более дешевые средства, чем для синхронизации процессов. Понятие легковесного процесса направлено на организацию вычислений в многопроцессорной вычислительной системе в случае, когда приложение, выполняемое в рамках одного процесса, обладает внутренним параллелизмом. Разумеется, параллельное выполнение приложения можно организовать и на пользовательском уровне – путем создания для одного приложения нескольких процессов для каждой из параллельных работ. Однако при этом не учитывается тот факт, что эти процессы решают общую задачу, а, значит, могут иметь много общего – общие данные, программные коды, права доступа к ресурсам системы и пр. Кроме того, как отмечалось выше, каждый процесс требует значительных системных ресурсов, которые при такой организации параллельных вычислений неоправданно дублируются. Средства создания и завершения процессов. Рассмотрим основные средства создания и завершения процессов на примере операционной системы UNIX. Системный вызов fork. Для создания нового процесса используется системный вызов fork. Все процессы ОС UNIX, кроме начального, запускаемого при «раскрутке» системы, образуются при помощи системного вызова fork. После создания процесса-потомка процесс-предок и процесс-потомок начинают «жить» своей собственной жизнью, произвольным образом изменяя свой контекст. Например, и процесс-предок, и процесс-потомок могут выполнить системный вызов exec (см. ниже), приводящий к полному изменению контекста процесса. Системный вызов wait. Системный вызов wait используется для синхронизации процесса-предка и процессов-потомков. Выполнение этого системного вызова приводит к приостановке выполнения процесса-предка до тех пор, пока не завершится выполнение какого-либо из процессов, являющегося его потомком. 56 Сигналы. Сигнал - это способ информирования процесса со стороны ядра операционной системы о происшествии некоторого события (event) в системе, например:     исключительная ситуация (выход за допустимые границы виртуальной памяти, попытка записи в область виртуальной памяти, которая доступна только для чтения и т.д.); ошибка в системном вызове (несуществующий системный вызов, ошибки в параметрах системного вызова и т.д.); прием сообщения от другого процесса; нажатия пользователем определенных клавиш на клавиатуре терминала, связанного с процессом. Все возможные в системе сигналы имеют уникальные номера и идентификаторы. С помощью системного вызова signal пользовательская программа может осуществить «перехват» указанного в вызове сигнала – вызвать соответствующую функцию, которая выполнит обработку этого сигнала. Например, вызов signal(SIGFPE, error) вызовет выполнение функции error при переполнении или делении на ноль во время выполнения операции с плавающей запятой. ОС Unix предоставляет возможность пользовательским процессам направлять сигналы другим процессам. Например, системный вызов kill(PID, signum) посылает процессу с идентификатором PID сигнал с номером signum. Системный вызов exec. При выполнении системного вызова exec(filename,…), где filename – имя выполняемого файла, операционная система производит реорганизацию виртуальной памяти вызывающего процесса, уничтожая в ней сегменты старого программного кода и образуя новые сегменты, в которые загружаются программный код из файла filename. Операционные системы мультипроцессоров. Синхронизация процессов Синхронизация параллельных процессов необходима в двух случаях:   когда определенное действие одного процесса должно быть выполнено после определенного действия другого процесса; когда необходимо обеспечить заданную дисциплину доступа к разделяемым ресурсам (памяти, файлам и пр.). Основным способом предотвращения проблем, связанных с совместным использованием разделяемых ресурсов, является запрет одновременного доступа к разделяемым ресурсам более чем одному процессу, т.е. взаимное исключение. Обычно проблему исключения формулируют с использованием понятия критическая область или критическая секция. Критической областью называется часть программы, в которой содержится обращение к разделяемому ресурсу. Для решения проблемы взаимного исключения необходимо выполнение следующих условий (см. рис. 1):  любые два процесса не могут одновременно находиться в одной критической области; 57    процесс, находящийся вне данной критической области, не может блокировать доступ других процессов к этой области; попеременно данную критическую секцию может использовать любое количество процессов; ни одни из процессов не может занимать критическую область бесконечно долго. На рис. 1 момент времени - момент, когда процесс A получает доступ к не- которой критической области; - момент времени, когда процесс Б пытается получить доступ к этой критической области, но не получает его и блокируется; - момент, когда процесс A завершает использование критической области и покидает ее, а процесс Б - получает доступ к критической области; - момент, когда процесс Б завершает использование критической области и покидает ее; - период нахождения процесса А в критической области; риод блокирования процесса Б; ческой области. - пе- - период нахождения процесса Б в крити- Рис. 1. К проблеме взаимного исключения с использованием критических областей. Во многих операционных системах средства синхронизации процессов относят к средствам межпроцессорного взаимодействия - Inter Process Communications (IPS), в которые входят также средства межпроцессного обмена данными. Семафоры. Современным низкоуровневым решением проблемы взаимного исключения является использование семафоров Дейкстры (E.W.Dijkstra), 1965г. Семафор (semaphore) – это специальный тип переменных, которые могут принимать только неотрицательные значения, и над которыми определены только три следующие операции ( – переменная типа «семафор»): - операция инициализации семафора;   операция - значение переменной уменьшается на единицу, если это возможно; операция интерпретируется как операция опускания (закрытия) семафора;  операция - значение переменной увеличивается на единицу; операция интерпретируется как операция поднятия (открытия) семафора. Если семафор закрыт (процессом 1, с помощью операции P(S)), то процесс 2, вызвавший операцию , ждет, пока семафор откроется (процессом 1, с помощью операции V(S)). Любые процессы могут изменять состояния семафора только с помощью операций , . Выполнение операций , не может быть прервано. 58 Во время выполнения операций , доступ к семафору других процессов запрещен. Если одной и той же критической секции достигли несколько процессов, то они образуют очередь к семафору. Простейшим семафором является двоичный семафор, который может принимать лишь два состояния – 0 и 1. Иногда двоичный семафор называют мьютексом (mutex – сокращение от mutual exclusion). Пример 1 Схема организации взаимного исключения процессов с помощью семафоров: begin semaphore S; --описание process2 общих (глобальных) переменных процессов process1, INIT(S); parbegin process1: begin --описание локальных переменных процесса process1 ... P(S); <критическая секция> V(S); ... end; process2: begin --описание локальных переменных процесса process1 ... P(S); <критическая секция> V(S); ... end; parend; end; Положим, что процесс 1 первым критической секции. На входе в критическую секцию процесс выполнил операцию (закрыл семафор ). Если до окончания выполнения критической секции первым процессом, второй процесс достиг критической секции, то при попытке выполнить операцию этот процесс переходит в режим ожидания. В режиме ожидания второй процесс находится до тех пор, пока процесс 1 не выполнит операцию цию фор (откроет семафор (закрывает семафор ). После этого второй процесс выполняет опера- ), исполняет критическую секцию и открывает сема- 59 Семафоры в ОС Unix. Прежде отметим, что в стандарте POSIX семафоры полностью аналогичны семафорам Дейкстры. Для инициализации значения таких семафоров применяется функция sem_init(), аналогом операции служит функция sem_wait(), а аналогом операции – функция sem_post(). В современных операционных системах Unix набор операций над семафорами отличается от классического набора операций Дейкстры. Этот набор включает в себя три операции:  ( , ) – увеличить значение семафора  ( , ) – пока значение семафора случае выполняется присваивание  = на величину < - ; , процесс блокируется; в противном ; ( ) – процесс блокируется до тех пор, пока значение семафора равным 0. не станет Изначально все семафоры инициируются нулевым значением. Легко видеть, что операции Дейкстры ( ) соответствует операция ( ,1), а операции ( ) - операция ( ,1). Системный вызов semget(key, nsems, semflag) обеспечивает создание набора семафоров. Здесь параметр key можно интерпретировать как имя набора семафоров, nsems – количество семафоров в наборе, параметр semflag определяет, главным образом, права различных пользователей при доступе к данному набору семафоров. Системный вызов semop(). Системный вызов semop() обладает довольно сложной семантикой и используется для выполнения рассмотренных выше операций A, D и Z над семафорами из заданного набора семафоров. Системный вызов semctl() используется для получения информации о наборе семафоров, изменения его атрибутов, а также для удаления из системы набора семафоров после завершения использовавших этот набор процессов. Особенности использования семафоров в мультипроцессорах. Для того чтобы во время выполнения операций , запретить доступ к семафору других процессов, в мультипроцессорах приходится с помощью специальной линии использовать блокировку шины, связывающую коммуникационную среду с памятью. Процесс, который достиг критической секции, занятой другим процессом, переходит в состояние спин-блокировки. В это время он непрерывно и с максимальной скоростью опрашивает состояние семафора. Это приводит, во-первых, к напрасной трате времени соответствующего процессора, а, во-вторых, накладывает значительную нагрузку на коммуникационную сеть и память, снижая тем самым скорость работы остальных процессоров. Одним из способов решения указной проблемы является использование алгоритма двоичного экспоненциального отката , который применяется в сетях Ethernet. Между опросами вставляется цикл задержки. Вначале задержка равна времени выполнения одной команды. Если семафор занят, задержка удваивается, учетверяется и т.д. до некоторого максимального уровня. Этот уровень устанавливается, исходя из следующих соображений: низкий уровень обеспечивает высокую реактивность, но и высокую загрузку коммуникационной среды; высокий уровень, напротив, - низкую загрузку среды, но и низкую реактивность. 60 Операционные системы мультикомпьютеров. Планирование процессов В мультикомпьютере каждый процессор имеет собственный набор процессов. Поэтому планирование процессов для мультикомпьютера сводится к двум следующим задачам:   планирование процессов на каждом из процессоров с помощью некоторого локального алгоритма планирования (аналогично планированию процессов в традиционной однопроцессорной системе); распределение появляющихся в системе новых процессов по процессорам. Последняя задача состоит в поиске такого распределения процессов по процессорам, при котором эффективность системы максимальна. Обычно в операционных системах эта задача решается как задача балансировки загрузки. Алгоритм балансировки загрузки, инициируемой отправителем. Алгоритм балансировки загрузки, инициируемой отправителем , требует оценки текущей загрузки каждого из процессоров мультикомпьютера. Текущая загрузка процессора может оцениваться по количеству процессов, выполняемых на этом процессоре, суммарной вычислительной сложности этих процессов и пр. Схема алгоритма имеет следующий вид (см. рис. 1). 1. Если у процессора появляется новый процесс, то этот процессор проверяет свою текущую загрузку. 2. Если текущая загрузка процессора процессор ему запрос. случайным образом выбирает другой процессор 3. Если загрузка процессора сор и посылает меньше некоторой заданной загрузки, то процес- посылает этому процессору свой новый процесс. 4. Если процессор цессор выше некоторой заданной загрузки, то также перегружен, то процессор выбирает другой про- (опять же случайным образом). И т.д. В случае, когда все или большинство процессоров мультикомпьютера перегружены, они будут в соответствии с этим алгоритмом постоянно посылать в коммуникационную сеть запросы. При этом загрузку удастся уменьшить немногим из них, но сеть может оказаться перегруженной. 61 Рис. 1. К алгоритму балансировки загрузки, инициируемой отправителем. Загрузка процессора Pi (отправителя) выше максимально допустимой загрузки, а загрузка процессора Pj - ниже минимально допустимой загрузки. Процессор Piпередает процессору Pj процесс Qf. Алгоритм балансировки загрузки, инициируемой получателем. Схема алгоритма балансировки загрузки, инициируемой получателем , имеет следующий вид (см. рис. 2). 1. Если процессор завершает выполнение некоторого процесса, то этот процессор проверяет свою текущую загрузку. 2. Если текущая загрузка процессора процессор ему запрос. случайным образом выбирает другой процессор 3. Если загрузка процессора сор Qd). посылает процессору 4. Если процессор цессор ниже некоторой заданной загрузки, то и посылает больше некоторой заданной величины, то процесодин из своих процессов (на Рис.2 - процесс также недогружен, то процессор выбирает другой про- (опять же случайным образом). И.т.д. Преимущество данного алгоритма состоит в том, что он не оказывает дополнительную нагрузку на коммуникационную сеть в момент, когда мультикомпьютер перегружен. Очевидно, что в случае, когда почти все процессоры мультикомпьютера простаивают, данный алгоритм создает существенную нагрузку на коммуникационную сеть. Однако, поскольку система недогружена, эта нагрузка не слишком обременительна. 62 Рис. 2. К алгоритму балансировки загрузки, инициируемой получателем. Иерархический графовый алгоритм балансировки загрузки. Как отмечалось, задачу балансировки можно поставить как задачу разрезания графа на (по числу процессоров в системе) непересекающихся подмножеств так, чтобы суммы весов узлов в каждом подмножестве были приблизительно равны, а сумма весов ребер, которые инцидентны узлам из разных подмножеств, была минимальна. Известно несколько алгоритмов приближенного решения этой задачи, наиболее известными из которых являются иерархический алгоритм и спектральный алгоритм. Иерархический графовый алгоритм балансировки загрузки достаточно хорошо зарекомендовал себя для графов большого размера. В соответствии с этим алгоритмом разрезание графа этапа:    на подграфы осуществляется в три рекурсивное огрубление графа; рекурсивная бисекция огрубленного графа; восстановление исходного графа. Рекурсивное огрубление графа. В процессе рекурсивного огрубления графа строится последователь- ность графов меньшего размера. При этом в графе выделяется некоторое количество подмножеств узлов и узлы каждого из этих подмножеств стягиваются в один мультиузел графа (см. рис. 3). Вес мультиузла принимается равным сумме весов входящих в него узлов. Аналогично в мультиребра графа стягиваются ребра графа . Вес мультиребра определяется путем суммирования весов соответствующих ребер графа . Из гра- фа по той же схеме получается граф и т.д. до достижения приемлемого размера графа. Для формирования подмножеств, узлы которых стягиваются в один мультиузел, используется два подхода:   подход на основе паросочетаний; подход на основе создании мультиузлов из сильно связных групп узлов. 63 первом подходе мультиузел получается путем стягивания смежных узлов. Формально идея этого подхода обычно формулируется в терминах паросочетаний - наборов ребер графа и инцидентных им вершин, в котором любые два ребра не инцидентны общему узлу. Граф, огрубленный с использованием паросочетаний, сохраняет многие свойства первоначального графа. Например, если граф планарен, то граф также планарен. Достаточно эффективным алгоритмом формирования паросочетаний является алгоритм случайных паросочетаний: если мультиузел не включен ни в одно из паросочетаний, то случайным образом выбирается один из его смежных мультиузлов включается в паросочетание. В качестве мультиузла ся узел с максимальным весом мультиребра тяжелых ребер). и мультиребро может также выбирать- (алгоритм паросочетаний из Рис. 3. К огрублению графа. 1- 5 – мультиузлы. втором подходе в мультиузлы стягиваются группы сильно связанных узлов (с высоким уровнем внутригруппового трафика), которые слабо взаимодействуют с другими группами узлов (низкий межгрупповой трафик). Для выделения таких групп используются различные эвристические алгоритмы, например, алгоритм паросочетаний из тяжелых клик . Напомним, что кликой графа называется его полный подграф, а полным графом называется неориентированный граф, все вершины которого смежны между собой. В качестве меры близости графа к клике можно использовать реберную плотность графа , где - количество вершин графа, а - количество его дуг. Если граф близок к клике, то его реберная плотность блика к единице, в противном случае – реберная плотность близка к нулю. Заметим, что величина представляет собой ни что иное, как общее количество дуг в полном графе (клике) с вершинами. В алгоритме паросочетаний из тяжелых клик паросочетание образуется свободным мультиузлом и тем из его смежных мультиузлов , который обеспечивает 64 максимальную реберную плотность мультиузла, полученного объединением мультиузлов , . Рекурсивная бисекция огрубленного графа. На втором этапе иерархического графового алгоритма балансировки загрузки выполняется рекурсивное деление пополам графа, полученного на первом этапе алгоритма. Деление выполняется таким образом, чтобы каждая из частей содержала примерно половину узлового веса первоначального графа. Бисекция графа может быть выполнена с использованием различных алгоритмов:    алгоритм спектрального деления пополам (см. ниже); поисковый алгоритм; алгоритм бисекции графа путем наращивания . алгоритма бисекции графа состоит в следующем: задается некоторое исходное разбиение графа на два подграфа; итерационно делается попытка перенести один или несколько узлов из одного подграфа в другой так, чтобы уменьшить критерий оптимальности разбиения. В качестве критерия оптимальности целесообразно использовать суммарный объем обменов между подграфами при условии, что суммарные вычислительные сложности подграфов примерно равны. Поскольку данный критерий оптимальности является многоэкстремальным, результирующее разбиение графа сильно зависит от исходного приближения. Поэтому обычно приходится решать задачу многократно – для некоторого количества случайных исходных разбиений (по некоторым оценкам достаточно ~10 разбиений). Алгоритм бисекции путем наращивания. Другой простой путь деления графа пополам состоит использовании алгоритма бисекции графа путем наращивания. Идея алгоритма состоит в том, чтобы начать с одного узла и наращивать область вокруг этого первого узла до тех пор, пока не будет получено два удовлетворительных (с точки зрения выбранного критерия оптимальности) подграфа. Данный алгоритм чувствителен к выбору узла, с которого начинается рост графа. Поэтому, как и в предыдущем алгоритме, приходится решать задачу многократно – для некоторого количества случайных исходных узлов. Поисковый алгоритм. Идея поискового Восстановление исходного графа. На данном этапе каждый из подграфов, на которые был разделен огрубленный граф на предыдущем этапе, восстанавливается до соответствующей части исходного графа. В простейшем случае этап заканчивается этим восстановлением подграфов. Поскольку полученные подграфы имеют значительно большее количество степеней свободы, чем огрубленные подграфы, можно попытаться улучшить полученное разделение с помощью какого-либо алгоритма локального уточнения. Можно, например, использовать модификацию рассмотренного поискового алгоритма, разрешив перемещение между подграфами только граничных узлов. Основная цель локального уточнения заключается в том, чтобы определить для каждого из граничных узлов тот подграф, при перемещении в который вес разрезанных ребер будет минимален при сохранении равномерного распределе- 65 ния узлов по подграфам. Поскольку количество граничных узлов относительно невелико, локальное уточнение может быть выполнено за приемлемое время. Операционные системы мультикомпьютеров. Спектральный алгоритм балансировки загрузки Спектральный графовый алгоритм балансировки загрузки также использует рекурсивное деление пополам графа. Данный алгоритм производит хорошие разделения для широкого класса графов, но имеет высокую вычислительную сложность, поскольку требует вычисления собственного вектора матрицы Лапласа, соответствующей исходному графу. Положим, что вычислительные сложности всех процессов одинако- вы и величина четна. Рассмотрим задачу разделения графа на два подграфа таким образом, чтобы (*) их суммарные вычислительные сложности были равны (т.е. были равны количества процессов в каждом из подграфов) и (**) количество разрезанных ребер было минимально. Как мы уже отмечали выше, последнее условие позволяет с высокой точностью сбалансировать коммуникационную загрузку процессоров в случае, когда объемы данных, передаваемых между процессорами невелики. Положим, что граф замкнут (т.е. не содержит узлов, которые "висят" на одной ветви или вообще «в воздухе»). Определим вершины , матрицу смежности графа такую, что связаны между собой ребром, и =0 - в противном случае. Матрицу смежности графа легко получить из матрицы ; если , то ). Определим также ( пеней вершин графа пени вершины дем в : , * =1, если (если , то ) диагональную матрицу сте, где величина равна сте- (числу ребер, инцидентных этой вершине). Кроме того, вве- рассмотрение матрицу Лапласа для Введенные обозначения иллюстрирует рис. 1 (в матрицах стоты записи не показаны нулевые элементы). графа , , для про- 66 Рис. 1. Пример построения матриц A,B,L и оптимальной бисекции графа. Определим нормализованные собственные векторы матрицы а также соответствующие собственные значения этой матрицы. Утверждение 1. Искомая оптимальная бисекция графа найдена следующим образом: •находим взвешенное среднее компонентов вектора •если < , то относим вершину противном случае – ко второму подграфу; , графа может быть = ; к первому подграфу, в •если несколько величин имеют значение , то распределяем соответствующие вершины между подграфами равномерно. В рассмотренном виде спектральный алгоритм бисекции может приводить к получению несвязанного подграфа. Поэтому в практической реализации на каждом шаге рекурсивного деления пополам следует контролировать связность полученных подграфов и в случае ее нарушения вводить (а затем удалять) виртуальные дуги. Заметим, что для вычисления собственных векторов матрицы Лапласа обычно используют итерационный алгоритм Ланцоша. Продолжим рассмотрение примера, приведенного на рис. 1. Собственные значения матрицы Лапласа для графа, приведенного на этом рисунке, равны (0.0000, 0.4384, 3.0000, 3.0000, 3.0000, 4.5616), а соответствующие нормализованные собственные векторы - есть столбцы матрицы Приведенные программы: результаты получены с помощью следующей MATLAB- L=[2 0 -1 0 -1 0;0 2 0 -1 0 -1;-1 0 3 -1 -1 0;0 -1 -1 3 0 -1;-1 0 -1 0 2 0;0 -1 0 -1 0 2] [U,lambda]=eig(L) Таким 0.4647)T, ны образом, вектор =(0.4647 -0.4647 0.2610 -0.2610 0.4647 - как и следовало ожидать, к первому подграфу относятся верши- , , , а ко второму подграфу – вершины , , (см. рис. 1). Приведем краткое обоснование спектрального алгоритма бисекции графа. Введем в рассмотрение -мерный отображающий вектор компоненты которого могут принимать только значения лагать, что ситуация означает, что вершина 1 и =( , ,..., )T , . Будем по- должна быть включена в 67 первый подграф, а ситуация - вершина рой подграф. Заметим, что условие Легко видеть, что значение функции должна быть включена во вто- формализует условие ( ). (1) при заданном отображающем векторе равно количеству разрезанных ребер (количеству ребер, соединяющих первый и второй подграфы между собой). Действительно, величина ничего не вносит в сумму (1), если , имеют один знак (принадлежат одному подграфу). С другой стороны, величина вносит 4 в сумму (1), если графам). имеют разные знаки (принадлежат разным под- Поскольку записана в виде а , функция (1) может быть (2) Таким образом, в сделанных предположениях задачу бисекции графа можно поставить как следующую задачу дискретного программирования: найти минимум функции (2) при условии (3) где – -мерный единичный вектор. Заметим, что это условие экви- валентно условию Нам понадобятся Пусть - . далее некоторые нормализованные свойства матрицы Лапласа . собственные векторы матрицы , а - соответствующие собственные значения этой матрицы. Тогда имеет место следующая теорема. Теорема 1. Матрица Лапласа обладает следующими свойствами: (I) матрица симметрична и вещественна, (II) собственные векторы попарно ортогональны, (III) первое собственное значение матрицы лю , а ее первый собственный вектор равен ные значения матрицы , кроме первого, отличны от нуля матрицы равно ну- , (IV) все собствен- 68 Заметим, что свойство (II) следует из свойства (I). По свойству (II) матрицы Лапласа вектор X может быть представлен в виде (4) где - некоторые вещественные константы такие, что ставляя выражение (4) в формулу (2), получим . Под- (5) Обратим внимание на то, что, воспользовавшись разложением (4), мы отказались от требования дискретности компонент вектора . Поскольку собственные значения матрицы Лапласа упорядочены по убыванию, из (5) следует, что Отсюда вытекает, жив нию что достичь значения ( . Важно, что так найденный вектор . Действительно, поскольку (см. )= можно, поло- удовлетворяет ограничесвойство (III)), = =0 (по свойству II). Таким образом, решение удовлетворяет ограничению и ми- нимизирует функцию ( ), т.е. является непрерывным решением задачи (2), (4). Теперь остается только перейти к дискретному решению задачи (2), (4) – см. Утверждение 1. Отображение процессов с регулярной структурой на типовые архитектуры мультикомпьютеров Для процессов с регулярной типовой структурой связей (2-х и 3-х мерные решетки, деревья и т.п.) известны точные оптимальные отображения на однородные мультикомпьютеры с регулярной топологией коммуникационной с ети (линейка, решетка, гиперкуб и пр.). Ограничимся рассмотрением отображения процессов с графами информационных связей в виде кольца и решетки на мультикомпьютеры с топологией гиперкуба. Методику отображения покажем на примерах. Отображение кольца процессов на гиперкуб. 69 Рассмотрим совокупность процессов , связанных информацион- ными связями в двунаправленное кольцо (см. Рис.1а) с графом , где матрица информационных связей имеет вид, представленный на Рис.1б. Рис. 1. а) Топология «кольцо» информационных связей процессов Q0,...,Q7 в графе (Q,D). б) Соответствующая матрица D. Рассмотрим также 8-ми процессорный мультикомпьютер с топологией коммуникационной сети типа 3-х мерный гиперкуб, процессоры в которой пронумерованы с помощью бинарного отраженного кода Грея (см. Рис.2а). Граф коммуникационной сети этого мультикомпьютера обозначим ( - процессоры системы, а ров между собой (см. Рис.2б). ным ( , ={ ,..., } на мульти: отображается на процессор с бинарным номером кода Грея, рав), где ( , ) - код Грея длиной Пусть, например, как в нашем случае, Легко видеть, что сор ), где матрица двунаправленных связей процессо- Общее правило отображения кольца процессов компьютер с архитектурой гиперкуба размерности •процесс , (см. Рис.2а) и процесс десятичного числа . =3. Рассмотрим процесс . должен быть отображен на процес- 70 Рис. 2. а) Коммуникационная сеть мультикомпьютера в виде 3-х мерного гиперкуба и отображение процессов Q0,...,Q7 на эту сеть. Жирным выделены используемые межпроцессорные связи. б) Соответствующая матрица C. Рисунок 2а показывает, что используемая нумерация процессоров МВС, дает возможность выполнить отображение соседних процессов на соседние процессоры. В результате при одинаковых временах межпроцессорных связей , (см. §1), это отображение оптимально (независимо от вычислительной сложности процессов вующая отображающая диагональной. и объема обменов между ними). Соответстматрица в данном случае, очевидно, является Отображение решетки процессов на гиперкуб. Рассмотрим совокупность процессов , связанных ин- формационными связями в двумерную сеть (см. Рис.3а) с графом где матрица информационных связей на Рис.3б. , имеет структуру, представленную Рассмотрим также 8-ми процессорный мультикомпьютер с графом коммуникационной сети типа 3-х мерный гиперкуб, процессоры в которой аналогично предыдущему примеру пронумерованы с помощью бинарного кода Грея (см. Рис.4). матрица двунаправленных связей процессоров этой системы между собой представлена на Рис.2б). 71 Рис. 3. а)Топология «решетка» информационных связей процессов Q={Qi,j, i∈[0,1], j∈[0,3]} в графе (Q,D). б)Структура соответствующей матрицы D (звездочки соответствуют ненулевым элементам). Рис. 4. Отображение двумерной решетки процессов Q={Qi,j, i∈[0,1],j∈[0,3]} на мультикомпьютер с архитектурой 3-х мерного гиперкуба. Общее правило оптимального отображения сов размерности •процесс равным Пусть, на мультикомпьютер с архитектурой гиперкуба : отображается на процессор с бинарным номером кода Грея, , где например, как цесс =101 и процесс двумерной решетки процес- - символ конкатенации. в нашем случае, =1, . Легко видеть, что =3. ,а должен быть отображен на процессор Рассмотрим про- . Тогда (см. рис. 4). Отображению двумерной решетки процессов на мультикомпьютер с архитектурой 3-х мерного гиперкуба, которое представлено на рис. 4, соответствует следующая отображающая матрица. 72 Рис. 5. Выборка элементов массива Существует несколько разных подходов к программированию параллельных вычислительных систем:     использование специализированных языков параллельного программирования и параллельных расширений последовательных языков (параллельные реализации Fortran и C и пр.); использование средств автоматического и полуавтоматического распараллеливания последовательных программ (PGI, BERT 77, FORGE, KAP и др.); программирование на последовательных языках программирования с использованием коммуникационных библиотек и интерфейсов для организации межпроцессорного взаимодействия (MPI, PVM, OpenMP и др.); программирование на последовательных языках с использованием параллельных библиотечных процедур (ScaLAPACK, HP Mathematical Library, PETSc и др.). Существует также большое количество инструментальных средств, которые упрощают проектирование параллельных программ (CODE, TRAPPER и др.). Данная глава открывает рассмотрение первого из указанных подходов к программированию параллельных вычислительных систем. Заметим, что языки типа Ассемблер отражают в себе систему команд и все особенности структуры параллельной вычислительной системы: число процессоров, состав и распределение регистров и оперативной памяти, систему коммутации и т. д. Ассемблер потенциально позволяет в наибольшей степени приспособить параллельный алгоритм к особенностям структуры конкретной параллельной ЭВМ и обеспечить наивысшую производительность ЭВМ. Несмотря на это, Ассемблер не используется широко для прикладного программирования параллельных ЭВМ по следующим причинам:   программирование параллельных ЭВМ на ассемблере является очень трудоемким; быстрая смена элементной базы параллельных ЭВМ и самих этих ЭВМ означает переработку всего запаса ассемблерных программ. 73 Имеется три основных подхода к созданию параллельных языков высокого уровня (ЯВУ). Первый подход заключается во введении в состав традиционных последовательных ЯВУ средств поддержки параллелизма на уровне языковых конструкций или библиотечных функций. Достоинством подхода является простота освоения ЯВУ, а недостатками – противоречие концепций базового языка и параллельных средств, что затрудняет их реализацию и делает менее эффективной. Второй подход состоит в создании оригинальных языков параллельной обработки, ориентированных на конкретную архитектуру или тип параллельных вычислительных систем (OCCAM, например). Достоинства подхода – возможность использования эффективно реализуемых, гибких языковых конструкций. Недостатки подхода – трудность освоения, низкая мобильность. - создание новых параллельных ЯВУ, не зависящих от конкретной архитектуры или типа параллельных вычислительных систем (АДА, например). Достоинство подхода состоит в возможности использования в ЯВУ концепций, повышающих эффективность и надежность написанных на этом языке программ; недостатки подхода – в трудности освоения и сложности создания эффективных объектных кодов при трансляции. Третий Примеры в данном и ряде последующих параграфов приводятся с использованием ЯВУ Actus, который представляет собой расширение языка Pascal - см. R. H. Perrott, "A language for array and vector processors," ACM Transactions on Programming Languages and Systems, Vol. 1, October 1979, pp. 177-195. Векторно-конвейерные вычислительные системы и векторно-параллельные вычислительные системы ориентированы и имеют высокую эффективность при выполнении векторных операций. Векторы представляются в ЯВУ в виде массивов данных. Рассмотрим поэтому конструкции параллельных ЯВУ, используемые для работы с массивами. Напомним понятия ранг массива и размерность массива. Рангом массива называется количество его измерений. Т.е. слова « -мерный массив» и «массив имеет ранг » являются синонимами. Размерностью массива называется количество элементов данных по каждому из измерений. Например, массив является трехмерным массивом (ранг равен трем) с размерностями , , . В параллельных ЯВУ можно выделить три подхода к представлению массивов: 1. Массивы - как последовательные объекты. В этом случае массивы описываются так же, как в последовательных ЯВУ. Параллелизм указывается только при обработке массивов (путем спецификации набора индексов элементов массивов, над которыми должна быть выполнена операция). 2. Массивы - как параллельные объекты. Здесь все массивы описываются как особые объекты заданной размерности. Любое обращение к массиву при этом подразумевает весь массив (хотя, естественно, не отменяется использование массива в качестве набора объектов меньшего ранга). 3. Массивы - как параллельные объекты Массивы - как смесь последовательных и параллельных объектов. В этом случае ограничивается количество размерностей, по которым массив может рассматриваться как параллельный объект. Любые следующие размерности должны быть индексированы. Данный подход неявно учитывает архитектуру используемой параллельной вычислительной системы. Пример 1 74 В языке Actus массивы могут содержать массивы всех указанных типов: var (*одномерный параллельный массив*) parvar: array [1:100] of integer; (*одномерный последовательный массив*) scalvar: array [1..50] of integer; (*двумерный массив параллельных строк*) grid: array [1:50, 1..100] of real; Выборка объектов пониженного ранга. Пусть имеется 2-х мерный -массив . Тогда выборка объектов пониженного ранга может выполняться с помощью следующих языковых конструкций: или  - весь этот массив; или  - или  -я строка массива - -й столбец массива - элемент массива  ; ; , находящийся в -й строке и в -ом столбце. Выборка диапазона значений. Для выборки диапазона значений (сужение диапазона значений) по каждой из размерностей специфицируют начальное значение индекса, его приращение и конечное значение. Например, - выборка внутренних точек массива; - выборка первых трех элементов из всех нечетных строк. Выборка с помощью целочисленных массивов. Пусть , , , Рассмотрим одномерные массивы из . 2-х и мерный положим, элементов, причем (4*4) -массив что , т.е. . Возможны два существенно разных способа выборки с помощью целочисленных массивов, имеющих одинаковый синтаксис: проекционная выборка и линейное отображение. Проекционная выборка с помощью целочисленных массивов. В этом случае результирующий объект имеет ранг меньший, чем ранг исходного объекта. Если результирующий объект имеет вид элементы определяются по правилу:  в первую позицию массива строки исходного массива; , то ранг его равен единице и записывается элемент из той же позиции 75  во вторую позицию массива  строки и т.д. записывается элемент из той же позиции исходного массива; Таким образом, . Если результирующий объект имеет вид це и элементы определяются по правилу:  в первую позицию массива строки , ранг его также равен едини- записывается элемент из той же позиции исходного массива;  во вторую позицию массива  строки и т.д. записывается элемент из той же позиции исходного массива; Таким образом, . Линейное отображение с помощью целочисленных массивов. В этом случае результирующий объект имеет тот же ранг, что и ранг исходного объекта. Если результирующий объект имеет вид , то ранг его равен двум и элементы определяются по правилу:  в первую строку массива   во вторую строку массива и т.д. записывается строка исходного массива; записывается строка исходного массива; Таким образом, Если результирующий объект имеет вид двум и элементы определяются по правилу:  в первый столбец массива   во вторую столбец массива и т.д. Таким образом,  , то ранг его также равен записывается столбец записывается столбца исходного массива; исходного массива; . Если результирующий объект имеет вид двум и элементы определяются по правилу: , то ранг его также равен в первую позицию первой строки массива записывается элемент выбранный из строки исходного массива; , 76  во вторую позицию первой строки массива выбранный из строки   записывается элемент , записывается элемент , записывается элемент , исходного массива; в четвертую позицию первой строки массива выбранный из строки , исходного массива; в третью позицию первой строки массива выбранный из строки записывается элемент исходного массива;  в первую позицию второй строки массива  выбранный из строки и т.д. исходного массива; Таким образом, . Пример 2 В ЯВУ Actus используется линейное отображение с помощью параллельных целочисленных массивов. Пусть имеют место спецификации const (*параллельная константа*) diagonal = 1:100 of integer; var (*параллельный массив*) diag: array [1:100] of integer; (*массив параллельных строк*) para: array [1:100, 1..100] of real; и присваивание (параллельное) diag [1:100] := diagonal. Тогда конструкция para[1:100,diag] означает все диагональные элементы массива para, доступ к которым может выполняться параллельно. Выборка с помощью булевых массивов. Пусть одномерный булевый массив из элементов. Так же, как в преды- дущем разделе рассмотрим 2-х мерный (4*4) -массив = . И в данном случае возможны два существенно разных способа выборки с помощью булевых массивов, имеющих одинаковый синтаксис: проекционная выборка и линейное отображение. Проекционная выборка с помощью булевых массивов. В этом случае результирующий объект имеет ранг меньший, чем ранг исходного объекта. Массив , с помощью которого осуществляется выборка, должен иметь только один отличный от нуля элемент. Положим, что Если результирующий объект имеет вид элементы определяются по правилу:  . , то ранг его равен единице и в массив записываются все элементы строки исходного массива, которая соответствует единичному элементу массива . 77 Таким образом, . Если результирующий объект имеет вид нице и элементы определяются по правилу  , то ранг его также равен еди- в массив записываются все элементы столбца исходного массива, который соответствует единичному элементу массива . Таким образом, . Линейное отображение с помощью булевых массивов. В этом случае результирующий объект имеет тот же ранг, что и ранг исходного объекта. Массив , с помощью которого осуществляется выборка, может иметь более одного отличного от нуля элемента. Положим, что . Если результирующий объект имеет вид элементы определяются по правилу: , то ранг его равен двум и  в первую строку массива записывается та строка исходного массива, которая соответствует первому единичному элементу массива ;  во вторую строку массива записывается та строка исходного массива, которая соответствует второму единичному элементу массива ; и т.д.  Таким образом, . Если результирующий объект имеет вид и элементы определяются по правилу: , то ранг его также равен двум  в первый столбец массива записывается тот столбец исходного массива, который соответствует первому единичному элементу массива ;  во вторую столбец массива записывается тот столбец исходного массива, который соответствует второму единичному элементу массива ; и т.д.  Таким образом, . Выборка с помощью индексных множеств. При данном способе выборки используются индексные множества. Поясним метод выборки с помощью индексных множеств примером. Пример 3 Рассмотрим следующие спецификации и присваивания на языке Actus: var (*массив параллельных строк*) para: array [1:100,1..100] of real; 78 index (*множество целых чисел от 1 до 100, исключая числа 11 - 90*) i=1:10,91:100; (*множество нечетных чисел от 1 до 100*) odd=1:(2)99; (*множество четных чисел от 1 до 100*) even=2:(2)100; Тогда конструкция para [i,1..100] означает строки массива para, из которого исключены строки 11 – 90. Доступ к оставшимся строкам может выполняться параллельно. Аналогично, конструкция para [odd,1..100] означает нечетные строки массива para, а para [even,1..100] - четные строки массива para. Доступ к указанным строкам может выполняться параллельно. Над индексными множествами в языке Actus определены теоретикомножественные операции объединения, пересечения и разности. Индексация сдвигом. Суть индексации сдвигом покажем на примере. Пример 4 Рассмотрим фрагмент Actus-программы var (*параллельные одномерные массивы*) para, parb: array [1:100] of integer; index (*множество целых чисел от 1 до 50*) first50=1:50; Тогда конструкция para [first50] := parb [first50] + parb [first50 shift 1] определяет параллельное сложение элементов 1 – 50 массива parb с элементами 2 – 51 этого же массива. Если значение целого выражения после операторовshift, rotate положительно, то сдвиг осуществляется «справа налево». В противном случае – «слева направо». Функции обработки массивов для получения соответствия В параллельных ЯВУ для векторно-конвейерных вычислительных систем и векторно-параллельных вычислительных систем имеется множество арифметических, реляционных и логических бинарных операций над массивами, которые выполняются параллельно над всеми элементами этих массивов. Имеются также унарные операции, относящиеся ко всем элементам массивов. При выполнении бинарных операций над массивами оба массива должны иметь одинаковые ранги и размерности. Равенство рангов и размерностей массивов будем называть соответствием массивов. Такое ограничение требует введения в язык программирования конструкций, предоставляющих возможность сжатия, расширения или переформирования массивов с целью достижения их соответствия. Средства, рассмотренные в параграфе 1, могут быть использованы для этой цели. Другие средства рассмотрены в данном параграфе. Заметим, что альтернативой является дополнение компилятором неопределенных элементов массивом, например, нулями. Функции понижения ранга. Функции понижения ранга массива основаны на использовании некоторого бинарного оператора ко всем элементам массива в одной размерности. 79 Положим, что – числовой массив, а – логический массив. Пусть масси- вы , имеют ранг и все размерности этих массивов одинаковы и равны Приведем примеры наиболее распространенных функций понижения ранга. . Пример 1 Функция ой размерности: вызывает суммирование элементов числового массива по - . Результирующий массив имеет ранг то . Например, если , и , . Заметим, что все суммирования при выполнении операции параллельно. производятся Пример 2 Функция ой размерности: вызывает перемножение элементов числового массива по - . Результирующий массив имеет ранг ции , все произведения при выполнении опера- производятся параллельно. Пример 3 Функция вызывает логическое перемножение элементов логического массива по -ой размерности: . Результирующий и массив имеет ранг . Например, , то если , . Все логические умножения при выполнении операции раллельно. производятся па- Пример 4 Функция вызывает логическое сложение элементов логического массива по -ой размерности: . Результирующий массив имеет ранг , все логические суммирования при выполнении операции ( , ) производятся параллельно. Пример 5 80 Функция вызывает замену элементов числового массива мерности максимальным элементом: по -ой раз- . Результирующий и массив имеет ранг , то . Например, если если , . Все операции отыскания максимума при выполнении операции дятся параллельно. произво- Пример 6 Функция вызывает замену элементов числового массива мерности минимальным элементом: по -ой раз- . Результирующий массив имеет ранг выполнении операции . Все операции отыскания минимума при производятся параллельно. Функции повышения ранга. Примером функции ция повышения ранга массива является функ- . Результатом выполнения этой функции является матрица, по- лученная повторением раз матрицы по -ой размерности. Пусть, напри- мер, , тогда = . Любое повышение ранга может быть выполнено с помощью повторного использовании этой функции. Операции переформирования. Операции переформирования массивов могут быть необходимы при выполнении операций, над массивами, имеющими различные ранги и/или размерности, но одинаковое количество элементов. Положим, что матрица элемент матрицы гда описание ния, которая имеет ранг цию качестве . Каждый , положим, занимает в памяти один байт. Напомним, что товводит определяет ти В и размерности примера операции , где байтов памяти и функцию отображеположение элемента в памя. переформирования . рассмотрим опера- 81 Операция элементов, вводит новый массив с таким же количеством что и в массиве , ния и новой функций отображе- . Параллельные операторы Условные операторы. Обычно в параллельных ЯВУ для векторно-конвейерных вычислительных систем и векторно-параллельных вычислительных систем определены традиционные для последовательных ЯВУ условные конструкции вида if then ; if then else ; Здесь - условное выражение, - простые или составные операторы. Если в условных выражениях сравниваются элементы двух соответствующих параллельных массивов, то эти приведенные условные конструкции вызывают параллельное исполнение операторов , . Пример 1 Условная конструкция (здесь и далее полагается, что все переменные определены) на языке Actus if a[10:90] < a[10:90 shift-1] then a[#]:=a[#]+1 else a[#]:=a[#]-1; вызывает увеличение значений элемента , массива на единицу, если он меньше своего левого соседа; иначе значение элемента уменьшается на единицу. Обработка все элементов , производится параллельно В параллельных ЯВУ обычно определены также операторы выбора вида case of : ; : ; ... : end; Здесь простые или составные операторы. Пример 2 Рассмотрим фрагмент Actus-программы с оператором выбора type colour = (black, white, red, brown, green); var flower: array[1:50] of colour; begin case flower [1:50] of white: statement1; red, green: statement2; black, brown: statement3 end; Программа вызывает параллельную обработку всех элементов массива висимости от значений этих элементов параллельно выполняются Например, если в массиве имеется по 10 элементов со значениями . В за1, 2 или 3. , 82 , , десять раз 50!) , , то при исполнении программы будет параллельно выполняться 1, двадцать раз 2 и двадцать раз 3 (всего Циклические операторы. В параллельных ЯВУ для векторно-конвейерных вычислительных систем и векторно-параллельных вычислительных систем определены также традиционные операторы цикла вида: while do ; repeat until ; for := by to do ; Здесь - условное выражение, - простой или составной оператор, INDEX – массив параметров цикла, LOWER, UPPER, INC – массивы, содержащие нижние, верхние границы и инкременты соответствующих параметров цикла. Пример 3 Оператор цикла языка Actus while a[1:50]