Компьютеры, построенные на принципах фон Неймана

В середине 1940-х проект компьютера, хранящего свои программы в общей памяти, был разработан в Институте Мура (англ.) в Пенсильванском Университете. Подход, описанный в этом документе, стал известен как архитектура фон Неймана, по имени единственного из названных авторов проекта Джона фон Неймана, хотя на самом деле авторство проекта было коллективным. Архитектура фон Неймана решала проблемы, свойственные компьютеру ENIAC, который создавался в то время, за счёт хранения программы компьютера в его собственной памяти. Информация о проекте стала доступна другим исследователям вскоре после того, как в 1946 году было объявлено о создании ENIAC. По плану предполагалось осуществить проект силами Муровской школы в машине EDVAC, однако до 1951 года EDVAC не был запущен из-за технических трудностей в создании надёжной компьютерной памяти и разногласий в группе разработчиков. Другие научно-исследовательские институты, получившие копии проекта, сумели решить эти проблемы гораздо раньше группы разработчиков из Муровской школы и реализовали их в собственных компьютерных системах.

SISD компьютеры это обычные, «традиционные» последовательные компьютеры, в которых в каждый момент времени выполняется лишь одна операция над одним элементом данных (числовым или каким-либо другим значением). Большинство персональных ЭВМ до последнего времени, например, попадает именно в эту категорию. Иногда сюда относят и некоторые типы векторных компьютеров, это зависит от того, что понимать под потоком данных. Данная архитектура породила CISC, RISC и архитектуру с суперскалярной обработкой.

Компьютеры с CISC (Complex Instruction Set Computer) архитектурой имеют комплексную (полную) систему команд, под управлением которой выполняются всевозможные операции типа «память-память», «память-регистр», «регистр-память», «регистр-регистр». Данная архитектура характеризуется:

· большим числом команд (более 200);

· переменной длиной команд (от 1 до 11 байт);

· значительным числом способов адресации и форматов команд;

· сложностью команд и многотактностью их выполнения;

· наличием микропрограммного управления, что снижает быстродействие и усложняет процессор.

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

Компьютеры с RISC (Reduced Instruction Set Computer) архитектурой содержат набор простых, часто употребляемых в программах команд. Основными являются операции типа «регистр-регистр».

Данная архитектура характеризуется:

· сокращенным числом команд;

· тем, что большинство команд выполняется за один машинный такт;

· постоянной длиной команд;

· небольшим количеством способов адресации и форматов команд;

· тем, что для простых команд нет необходимости в использовании микропрограммного управления;

· большим числом регистров внутренней памяти процессора.

Компьютеры с RISC-архитектурой «обязаны» иметь преимущество в производительности по сравнению с CISC компьютерами, за которое приходится расплачиваться наличием в программах дополнительных команд обмена регистров процессора с оперативной памятью.

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

В SISD, как уже говорилось, входят однопроцессорные последовательные компьютеры типа VAX 11/780. Однако, многими критиками подмечено, что в этот класс можно включить и векторно-конвейерные машины, если рассматривать вектор как одно неделимое данное для соответствующей команды. В таком случае в этот класс попадут и такие системы, как CRAY-1, CYBER 205, машины семейства FACOM VP и многие другие.

Cray-1 — один из первых суперкомпьютеров. Пиковая производительность — 133 Мфлопса. Cray-1 — первый суперкомпьютер компании Cray Research, созданной " отцом суперкомпьютеров" — Сеймуром Крэем — после ухода из компании CDC.

В данной ВС, С.Крэй отказался от транзисторов в пользу больших интегральных микросхем, которые давали такую плотность упаковки логических элементов при высокой надежности, которую невозможно было достичь с помощью транзисторов. Это позволило снизить тактовую частоту до 12.5 нс (80 МГц), вместо абмициозных 8 нс (125 МГц) в CDC 8600 без потери производительности. Во-вторых, он отказался от многопроцессорной системы в пользу векторного процессора, как у проекта-конкурента CDC STAR-100.

Далее Крэй учел недостатки STAR-100. Компьютеру во время исполнения программы требуется выполнять как векторные, так и скалярные вычисления. STAR-100 показывал высокую скорость на векторных вычислениях, но был медленным в скалярных. Из-за этого мощь STAR-100 проявлялась только на специальных задачах, где требовалась обработка больших массивов данных. Для Cray-1 Сеймур Крэй построил процессор, который быстро выполнял и скалярные и векторные вычисления. Этого удалось добиться через создание так называемых " векторынх регистров" - модулей памяти небольшого объема, которые располагались близко к процессору и работали очень быстро (но стоили очень дорого). Таким образом центральный процессор брал данные из регистров и записывал данные тоже в регистры, реализуя новый принцип работы с памятью " регистр-регистр", в то время как CDC STAR-100 использовал прежний способ работы с памятью — " load-store", т.е. чтение и запись в память (которая была медленной) напрямую. В CDC STAR-100 основная память была на ферромагнитных сердечниках, а в Cray-1 для памяти использовались полупроводники. Кроме того CDC STAR-100 строился совместимым с предыдущими моделями компании CDC 6600 и CDC 7600, а Cray-1 начинался с нового листа, и совместимости с предыдущими моделями не требовалось, что значительно облегчало задачу Крэю. В 1974 году первые тесты машины показали производительность 80 MFLOPS.

ОП (от 1 до 4 мегаслов), большой набор процессорных регистров, состоящих из группы векторных регистров по 64 элемента, блок скалярных регистров, блок адресных регистров. Каждая группа регистров связана со своим конвейерным процессором.

Данная система могла выполнять скалярные операции над векторными данными, над адресами, числами с плавающей запятой (порядок — 15, мантисса — 49). Быстродействие 180 млн операций в секунду с плавающей запятой. В данной ВС используются команды длиной 16 или 32 разряда. В коротких командах 7 разрядов выделяется под код операции, 3 адресных поля по 3 разряда, определяли номер регистра для хранения операндов. В длинных — 22 разряда для того, чтобы можно было найти операнд в общем поле ОП. Один из регистров определяет длину вектора, второй — регистр маски.

Центральный процессор Cray-1 состоял из 500 печатных плат, на каждой их которых с обеих строн располагалось по 144 микросхемы. Всего получалось 144.000 микросхем, которые охлаждались фреоном. Для лучшего охлаждения и циркуляции фреона в охладительной системе центральный процессор был выполнен в стиле " башни" c 12 колоннами, составенными в форме дуги длиной 270 градусов (в виде буквы " C" - от " Cray", если смотреть сверху), а охладительная система была расположена в основании этой башни. Так был создан характерный, оригинальный и узнаваемый вид компьютера, напоминающий диван.

2.

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

Требуется построить па­раллельный алгоритм, вычисляющий произведение двух прямоугольных матриц 3 1 2 3

H [1: K, 1: M] x B [1: N, 1: K]

Элементы матрицы С [1: N, 1: M] вычисляются по формуле:

(1)

Допустим также, что параллельный алгоритм ориентирован на реали­зацию в ВС, состоящей из п вычислителей. Пусть размеры N х К и К х М матриц H и В достаточно большие и таковы, что имеют место неравенства N > > n, К > > n, М > > п. При параллельной обработке необходимо, чтобы ка­ждый вычислитель производил расчет своих элементов матрицы С. При этом легко заметить, что размещение матриц H и В целиком в каждом вычислителе требует большой суммарной емкости памяти. Минимум емкости памяти бу­дет достигнут, если каждая из исходных матриц будет разбита на п равных частей, и в каждый вычислитель будет размещено по одной такой части мат­риц H и В. Например, каждую из матриц H и B можно разрезать на п равных соответственно горизонтальных и вертикальные полос.

Причем в первом вычислителе можно разместить строки 1, 2,..., ]N/п[ и столбцы 1, 2, …., ]М/п[;

в l -м вычислителе — строки (l -1)• ]N/п[ +1, (l -1) • ] N/п[ + 2,..., l ]N/n[

и столбцы (l -1) •] М / n [ + 1, (l -1) •]М / п[ +2, …, l ]М/п[;

в п- м вычислите­ле — строки (n-1)•]N/п[ +1, (п-l) • ] N/n [ + 2,..., n ]N/п[ и столбцы (n-1) • ]М / n[ + 1, (п-1) • ]М/п[ + 2, …, п]М/п[

матриц H и В соответственно.

Через ]х[ обозначено такое ближайшее к х целое число, для которого справедливо неравенство ]х[ ≥ х. При N и (или) М, некратном п, n]N/n[-N и (или) п]М/п[- М последних строк и (или) столбцов соответствующих полос для п- го вычислителя заполняются нулями. В результате будет получено однородное распределение данных по вычислителям коллектива (Рис. 2).

Параллельный вычислительный процесс можно организовать следующим способом: сначала первый вычислитель передает остальным вычислителям первую строку из своей полосы матрицы H. После этого каждый из вычислителей по формуле (1) рассчитывает ]М/п[ элементов первой строки своей полосы для результирующей матрицы С. Затем первый вычислитель рассылает во все остальные вычислители вторую строку своей полосы матрицы H и производятся вычисления элементов второй строки матрицы С и так до тех пор, пока первый вычислитель не перешлет все строки своей части матрицы H. После этого пересылками будут заниматься последовательно второй вычислитель, третий вычислитель и далее до п-го вычислителя. Матрица С получается распределенной по вычислителям, причем в каждом будет своя вертикальная полоса (см. рис. 2). При этом следует учитывать, что в результирующую матрицу С не должны включаться n]N/n[ - N последних строк из полученных вертикальных полос любого из вычислите­лей, а также п]М/п[ - М последних столбцов из полосы п-го вычислителя.

Итак, вследствие однородного распределения данных получены одинаковые ветви параллельного алгоритма, однако при этом ветви используют различные части данных. Поскольку для каждой ветви своих данных недостаточно, то ветви (точнее, реализующие их вычислители) вступают во взаимодействия (между ними осуществляются обмены информацией). Опера­торная схема l -й ветви P -алгоритма, реализуемая на вычислителе с номером l, 1 ≤ l ≤ п, представлена на рис. 3.

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

где — значение i -й переменной, рассчитываемое в (k + 1)-й итерации;

и — коэффициенты, составляющие матрицу-столбец (вектор-столбец) и матрицу соответственно. Условием окончания итераций является:

Прием

Вычисление

передача

— номер передающего вычислителя; {1, 2, …, …, n} — номера принимающих вычислителей; ] M/n [ (l -1) < j ≤ ] M/n [ l

Коэффициентом накладных раходов называется:

, (2)

где t — время, расходуемое ВС на организацию и реализацию всех обменов информацией между ветвями;

Т — время, необходимое на выполнение арифметических и логических операций при реализации Р-алгоритма.

Рассчитаем показатель (2) для алгоритма умножения матриц боль­шого размера (см. рис. 4). Ясно, что после приема строки из К элементов матрицы H в каждом вычислителе выполняется К * ]М/п[ операций умно­жения и (К – 1)*]М/п[ операций сложения.

При достаточно большом зна­чении К можно считать, что на каждый принятый элемент матрицы H при­ходится = ]М/ п[ операций умножения и сложения.

Пусть — время пересылки одного слова (элемента матрицы); и

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

Очевидно, что максимум накладных расходов будет при = 1, или, что то же самое, равенство = е достигается при п = М.

Величина = 1 информирует о минимально допустимом размере матриц, при котором еще целесообразно решение задачи на п вычислителях. С другой стороны, при фиксированном п увеличение размера матриц приводит к росту р и, следо­вательно, к уменьшению накладных расходов. Ясно, что чем больше размеры матриц (чем больше объем вычислений), тем выше эффективность параллельного алгоритма

Зависимость коэффициента н.р. от количества эл-ов в матрицах и от числа вычислителей системы:

Время пересылки одного слова :

=

= =

Коэффициент накладных раходов ( = 1):

2.909

Список использованных источников:

1. Хорошевский В.Г. Архитектура вычислительных систем. – М.: МГТУ им. Н.Э. Баумана, 2008.-520 с.

1. Конспект лекций по курсу “Архитектура вычислительных систем”

1. Методическое пособие “Параллельные методы матричного умножения“, НГУ им. Н.И Лобачевского

www.hpcc. unn.ru

1. Википедия — свободная энциклопедия

ru. wikipedia. org