Однородные вычислительные структуры

Размещено на http://www.allbest.ru/

РЕФЕРАТ

ОДНОРОДНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СТРУКТУРЫ

Однородные вычислительные структуры (среды)

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

Каждый ПЭ обладает алгоритмически полным набором операций, а также операциями обмена или взаимодействия с другими ПЭ. Например, решетка с регулярными связями процессоров может быть такой, какая изображена на рис. 9.1. многопроцессорный вычислительный память

Рис. 9.1. Однородная вычислительная среда

ОВС относится к ВС с распределенной памятью. Реализуется на основе микропроцессоров.

С 1985 г. стало развиваться направление разработки транспьютеров -- в интегральном исполнении соответствующих ПЭ ОВС. Т.е. ОВС в этом случае строится как транспьютерная сеть.

Транспьютер -- интегрально (в одном чипе или кристалле) выполненное семейство системных компонент, в составе которых: процессор, таймер, память, каналы последовательного ввода-вывода, контроллер внешней оперативной памяти.

Транспьютер вместе с языком программирования Occam (основной язык программирования транспьютеров) позволяет создавать ВС типа МКМД.

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

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

Систолическая схема вычислений. Представляет собой конвейер, в котором данные проходят обработку "волной" с одной границы ОВС -- входа к другой границе -- выходу. Следом за одной может следовать другая волна и т.д. (рис. 9.2). В этом случае ОВС -- систолическая матрица.

Рис. 9.2. Схема систолических вычислений

На рисунке: в первом такте на вход подаются данные задачи 2, а задача 1 решается процессорами первой строки систолической матрицы; в следующем такте задача 2 решается первым уровнем, а задача 1 -- вторым уровнем процессоров, на вход подаются данные задачи 3; на третьем уровне происходит очередное аналогичное смещение и т.д. Стрелками показано возможное перемещение обрабатываемой информации.

Ранее отмечалось, что фактически конвейеры в составе многофункциональных АЛУ строятся для каждой операции отдельно. Есть конвейеры сложения, умножения и т.д.

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

Таким образом, в систолической матрице процессоров, ориентированной на применение в АЛУ, распараллеливание "в длину" успешно сочетается с распараллеливанием "в ширину", как и при решении произвольного потока задач.

С помощью ОВС реализуется и ВС типа "гиперкуб".

Гиперкуб -- пространственное обобщение рассмотренной плоской решетки, где адресация процессоров (и соответственно, блоков распределенной памяти) ставится в зависимость от структуры связей между ними. Проводится аналогия с n-мерным пространством.

Рис. 9.3. Вычислительная система "гиперкуб": а -- двумерный, б -- трёхмерный, в -- четырёхмерный

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

То же самое можно обнаружить для n = 3 (рис. 9.3,б), n = 4 (рис. 9.3,в) и т.д.

Значит, в общем случае ВС типа "гиперкуб" формируется следующим образом. Ее образуют 2ⁿ ПЭ, каждый ПЭ соединен ровно с n ПЭ. При длине адреса ПЭ, равной n, непосредственно связаны ПЭ, у которых адреса разнятся не более чем в одном разряде.

Структура типа "гиперкуб" обладает важными свойствами.

Из структуры "гиперкуб" легко получаются более простые структуры. Например, при n = 3 легко получается матричная ВС, на которой, в частности, хорошо решать задачи в конечных разностях. Как мы видели ранее, для этого удобна плоская решетка, где существуют непосредственные (не транзитные) связи между тремя ПЭ (столбец составляют только два ПЭ, поэтому нет необходимости в связях в двух направлениях), как показано на рис. 9.4. Здесь можно в дополнение к адресам ввести (временно) нумерацию ПЭ и поставить эти номера в соответствие адресам.

Рис. 9.4. Матричная ВС на основе двумерного гиперкуба

Процессоры образовали фрагмент плоской решетки для реализации конечно-разностного метода (метода сеток). Процессоры "прокатываются" по области, на которой строится решение, например, задачи численного интегрирования.

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

Например, предположим, что в предыдущем примере мы располагали не 3-мерным, а 6-мерным "гиперкубом". Пусть планирующая система в составе ОС из всего адресного пространства ПЭ 000000 ч 111111 выделила нам массив 101000 ч 101111, т.е. определенное 3-хмерное подпространство всего пространства процессоров. В это же время пусть другой задаче выделен массив 000000 ч 001111, т.е. четырехмерное подпространство и т.д.

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

Рассматриваются некоторые "нетрадиционные" архитектуры, отражающие альтернативный поиск и эффективные решения при создании современных архитектур многопроцессорных вычислительных систем. Среди таких архитектур: однородные вычислительные среды, легшие в основу транспьютерных сетей; "гиперкуб", совмещающий адресацию со структурой связей, систолические матрицы. Исследуется способ построения самообучающихся систем управления на основе применения ассоциативной памяти. Приводится пример практического построения масспроцессорной системы. Изучаются вопросы построения нейрокомпьютеров.

ВС Connection Machine

В упомянутом выше "Японском вызове" провозглашалась необходимость объединения в одну систему десятков и сотен тысяч микропроцессоров. А есть ли опыт создания таких систем?

К такому опыту можно отнести семейство ВС, разработанное фирмой Thinking Machine. Оно является единственной крупной коммерческой реализацией идей ОВС. СМ-1 выпущена в 1986 г. Через год была выпущена СМ-2 с удвоенной производительностью в 2,5 млрд.оп./с. О ней следует говорить в связи с попытками воспроизвести ее в нашей стране на архитектурном уровне.

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

Рис. 9.5 Схема масспроцессорной системы Connection Machine

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

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

Основные операции производятся над 32-разрядными данными. Для выполнения их используются по 32 элементарных процессора. Поэтому каждые 32 ЭП имеют акселератор для выполнения операций с плавающей запятой, в том числе -- с двойной точностью.

Память (RAM -- прямоадресуемая, с произвольным доступом) распределенная. Каждый ЭП имеет 64 Кбит. Т.е. общий объем памяти -- 512 Мбайт (в 64 К-процессорном варианте).

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

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

Нейронные сети и нейрокомпьютеры

Применяемые нейросети являются моделями нейросетей живых организмов, принципы которых были известны уже в 1940-1950 годах, а с развитием микроэлектроники стали реализуемыми.

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

Предварительным знакомством с системами ИИ можно считать рассмотрение ассоциативных ВС. Характерно то, что исследование и воспроизводство нейросетей первоначально проводились в рамках решения задачи построения ассоциативной памяти в совокупности с операциями ее заполнения, ведения и использования.

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

Рис. 9.6 Фрагмент нейронной сети

Либо каждый нейрон управляем извне, либо сети строятся по принципу самоуправления, используя обратные связи. А именно, можно регулировать значения весов синапсических связей {w_i} и значения порогов h_i. Функции f бывают различны, но просты по объему вычислений.

В простейшем случае f cовпадает с линейной формой -- указанным аргументом. Т.е. по всем дендритам с учетом их весов производится суммирование и сравнение с порогом. Величина превышения порога является величиной возбуждения нейрона. Она передается через его ветвящийся аксон в соответствии со связями данного нейрона. В некоторых сетях величина возбуждения нейрона может принимать только два значения: возбужден (1), не возбужден (0).

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

Рис. 9.7 Сигмоидный нейроподобный элемент

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

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

Существуют два режима работы сети: режим обучения и режим распознавания.

Пусть мы на входной слой подали и поддерживаем некоторый образ, например, букву A.

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

Тогда по некоторому алгоритму (один из известных и весьма распространенных алгоритмов называется алгоритмом обратного распространения ошибки; в нем воспроизводится подход, используемый в динамическом программировании) мы меняем веса и пороги в сети на пути прохождения возбуждения так, чтобы заставить возбудиться нужный нейрон.

Так, предъявляя множество эталонов и регулируя параметры сети, мы производим ее обучение данному образу. (Математические проблемы несовместимости управления параметрами для разных эталонов оставим в стороне: в живой природе такой процесс проходит успешно.)

Обучение заканчивается тогда, когда вероятность "узнавания" достигнет требуемого значения, т.е. необходимость корректировки параметров по предъявляемым эталонам возникает все реже. Теперь можно работать в режиме распознавания -- в том ответственном режиме, для которого сеть создавалась. Предъявляем сети различные буквы. Можем быть уверены, что с большой вероятностью, если мы предъявим случайно искаженную и даже зашумленную букву A (конечно, в допустимых пределах), сеть ее распознает, т.е. возбудится соответствующий нейрон выходного слоя.

Продолжим обсуждение применимости.

Так, в экспертных системах требуются точные данные о ситуации, чтобы выдать соответствующее ей заключение. Нейронной сети такой подход "чужд". Она выдает ответ на вопрос: "на что похожа данная ситуация" и, следовательно, какое должно быть заключение. Т.е. нейросеть имитирует ассоциативное мышление.

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

Известны применения для оценки состояния электроэнергетической системы, распознавания рукописных текстов и т.д.

Важная область применения -- ситуационное управление.

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

Однако обращает на себя внимание несложность вычислений и возможность распараллеливания.

Известен опыт построения нейросетей на транспьютерах. Нейрон -- один транспьютер. Транспьютеры жестко связаны между собой в соответствии с топологией сети.

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

Здесь целесообразно вернуться к рассмотрению ВС типа SPMD в качестве нейропроцессора. Она идеально соответствует требованиям задачи, если производить распределение нейронов между процессорами. Легко просматривается план обработки нейросети как в режиме обучения (например, при реализации метода "обратного прохождения ошибки"), так и в режиме распознавания.

Размещено на Allbest.ru