Краткая история появления параллелизма в архитектуре ЭВМ
Краткая история появления
параллелизма в архитектуре ЭВМ
Сегодня
параллелизмом в архитектуре компьютеров уже мало кого удивишь. Все современные
микропроцессоры, будь то Pentium III или PA-8700, MIPS R14000, Е2К или Power3
используют тот или иной вид параллельной обработки. В ядре Pentium 4 на разных
стадиях выполнения может одновременно находиться до 126 микроопераций. На
презентациях новых чипов и в пресс-релизах корпораций это преподносится как
последнее слово техники и передовой край науки, и это действительно так, если
рассматривать реализацию этих принципов в миниатюрных рамках одного кристалла.
Вместе
с тем, сами эти идеи появились очень давно. Изначально они внедрялись в самых
передовых, а потому единичных, компьютерах своего времени. Затем после должной
отработки технологии и удешевления производства они спускались в компьютеры
среднего класса, и наконец сегодня все это в полном объеме воплощается в
рабочих станциях и персональных компьютерах.
Для
того чтобы убедиться, что все основные нововведения в архитектуре современных
процессоров на самом деле используются еще со времен, когда ни
микропроцессоров, ни понятия суперкомпьютеров еще не было, совершим маленький экскурс
в историю, начав практически с момента рождения первых ЭВМ.
IBM 701
(1953), IBM 704
(1955): разрядно-параллельная
память, разрядно-параллельная арифметика.
Все
самые первые компьютеры (EDSAC, EDVAC, UNIVAC) имели разрядно-последовательную
память, из которой слова считывались последовательно бит за битом. Первым
коммерчески доступным компьютером, использующим разрядно-параллельную память
(на CRT) и разрядно-параллельную арифметику, стал IBM 701, а наибольшую
популярность получила модель IBM 704 (продано 150 экз.), в которой, помимо
сказанного, была впервые применена память на ферритовых сердечниках и
аппаратное АУ с плавающей точкой.
IBM 709
(1958): независимые
процессоры ввода/вывода.
Процессоры
первых компьютеров сами управляли вводом/выводом. Однако скорость работы самого
быстрого внешнего устройства, а по тем временам это магнитная лента, была в
1000 раз меньше скорости процессора, поэтому во время операций ввода/вывода
процессор фактически простаивал. В 1958г. к компьютеру IBM 704 присоединили 6
независимых процессоров ввода/вывода, которые после получения команд могли
работать параллельно с основным процессором, а сам компьютер переименовали в
IBM 709. Данная модель получилась удивительно удачной, так как вместе с
модификациями было продано около 400 экземпляров, причем последний был выключен
в 1975 году - 20 лет существования!
IBM STRETCH
(1961): опережающий
просмотр вперед, расслоение памяти.
В
1956 году IBM подписывает контракт с Лос-Аламосской научной лабораторией на разработку
компьютера STRETCH, имеющего две принципиально важные особенности: опережающий
просмотр вперед для выборки команд и расслоение памяти на два банка для
согласования низкой скорости выборки из памяти и скорости выполнения операций.
ATLAS (1963):
конвейер команд.
Впервые
конвейерный принцип выполнения команд был использован в машине ATLAS,
разработанной в Манчестерском университете. Выполнение команд разбито на 4
стадии: выборка команды, вычисление адреса операнда, выборка операнда и выполнение
операции. Конвейеризация позволила уменьшить время выполнения команд с 6 мкс до
1,6 мкс. Данный компьютер оказал огромное влияние, как на архитектуру ЭВМ, так
и на программное обеспечение: в нем впервые использована мультипрограммная ОС,
основанная на использовании виртуальной памяти и системы прерываний.
CDC 6600
(1964): независимые
функциональные устройства.
Фирма
Control Data Corporation (CDC) при непосредственном участии одного из ее
основателей, Сеймура Р.Крэя (Seymour R.Cray) выпускает компьютер CDC-6600 -
первый компьютер, в котором использовалось несколько независимых функциональных
устройств. Для сравнения с сегодняшним днем приведем некоторые параметры
компьютера:
время
такта 100нс,
производительность
2-3 млн. операций в секунду,
оперативная
память разбита на 32 банка по 4096 60-ти разрядных слов,
цикл
памяти 1мкс,
10
независимых функциональных устройств.
Машина
имела громадный успех на научном рынке, активно вытесняя машины фирмы IBM.
CDC
выпускает компьютер CDC-7600 с восемью независимыми конвейерными
функциональными устройствами - сочетание параллельной и конвейерной обработки.
Основные параметры:
такт
27,5 нс,
10-15
млн. опер/сек.,
8
конвейерных ФУ,
2-х
уровневая память.
ILLIAC IV
(1974): матричные
процессоры.
Проект:
256 процессорных элементов (ПЭ) = 4 квадранта по 64ПЭ, возможность
реконфигурации: 2 квадранта по 128ПЭ или 1 квадрант из 256ПЭ, такт 40нс,
производительность 1Гфлоп;
работы
начаты в 1967 году, к концу 1971 изготовлена система из 1 квадранта, в 1974г.
она введена в эксплуатацию, доводка велась до 1975 года;
центральная
часть: устройство управления (УУ) + матрица из 64 ПЭ;
УУ
это простая ЭВМ с небольшой производительностью, управляющая матрицей ПЭ; все
ПЭ матрицы работали в синхронном режиме, выполняя в каждый момент времени одну
и ту же команду, поступившую от УУ, но над своими данными;
ПЭ
имел собственное АЛУ с полным набором команд, ОП - 2Кслова по 64 разряда, цикл
памяти 350нс, каждый ПЭ имел непосредственный доступ только к своей ОП;
сеть
пересылки данных: двумерный тор со сдвигом на 1 по границе по горизонтали;
Несмотря
на результат в сравнении с проектом: стоимость в 4 раза выше, сделан лишь 1
квадрант, такт 80нс, реальная произв-ть до 50Мфлоп - данный проект оказал
огромное влияние на архитектуру последующих машин, построенных по схожему
принципу, в частности: PEPE, BSP, ICL DAP.
|
CRAY 1
(1976): векторно-конвейерные
процессоры
В 1972 году С.Крэй покидает CDC и основывает свою компанию Cray
Research, которая в 1976г. выпускает первый векторно-конвейерный компьютер
CRAY-1: время такта 12.5нс, 12 конвейерных функциональных устройств, пиковая
производительность 160 миллионов операций в секунду, оперативная память до
1Мслова (слово - 64 разряда), цикл памяти 50нс. Главным новшеством является
введение векторных команд, работающих с целыми массивами независимых данных и
позволяющих эффективно использовать конвейерные функциональные устройства.
|
Иерархия
памяти.
Иерархия
памяти пямого отношения к параллелизму не имеет, однако, безусловно, относится
к тем особенностям архитектуры компьютеров, которые имеет огромное значение для
повышения их производительности (сглаживание разницы между скоростью работы
процессора и временем выборки из памяти). Основные уровни: регистры,
кэш-память, оперативная память, дисковая память. Время выборки по уровням
памяти от дисковой памяти к регистрам уменьшается, стоимость в пересчете на 1
слово (байт) растет. В настоящее время, подобная иерархия поддерживается даже
на персональных компьютерах.
А что же сейчас используют в мире?
По
каким же направлениям идет развитие высокопроизводительной вычислительной
техники в настоящее время? Основных направлений четыре.
2.
Массивно-параллельные компьютеры с распределенной памятью. Идея построения
компьютеров этого класса тривиальна: возьмем серийные микропроцессоры, снабдим
каждый своей локальной памятью, соединим посредством некоторой коммуникационной
среды - вот и все. Достоинств у такой архитектуры масса: если нужна высокая
производительность, то можно добавить еще процессоров, если ограничены финансы
или заранее известна требуемая вычислительная мощность, то легко подобрать
оптимальную конфигурацию и т.п.
Однако
есть и решающий "минус", сводящий многие "плюсы" на нет.
Дело в том, что межпроцессорное взаимодействие в компьютерах этого класса идет
намного медленнее, чем происходит локальная обработка данных самими
процессорами. Именно поэтому написать эффективную программу для таких
компьютеров очень сложно, а для некоторых алгоритмов иногда просто невозможно.
К данному классу можно отнести компьютеры Intel Paragon, IBM SP1, Parsytec, в
какой-то степени IBM SP2 и CRAY T3D/T3E, хотя в этих компьютерах влияние
указанного минуса значительно ослаблено. К этому же классу можно отнести и сети
компьютеров, которые все чаще рассматривают как дешевую альтернативу крайне
дорогим суперкомпьютерам.
3.
Параллельные компьютеры с общей памятью. Вся оперативная память таких
компьютеров разделяется несколькими одинаковыми процессорами. Это снимает
проблемы предыдущего класса, но добавляет новые - число процессоров, имеющих
доступ к общей памяти, по чисто техническим причинам нельзя сделать большим. В
данное направление входят многие современные многопроцессорные SMP-компьютеры
или, например, отдельные узлы компьютеров HP Exemplar и Sun StarFire.
4.
Последнее направление, строго говоря, не является самостоятельным, а скорее
представляет собой комбинации предыдущих трех. Из нескольких процессоров
(традиционных или векторно-конвейерных) и общей для них памяти сформируем
вычислительный узел. Если полученной вычислительной мощности не достаточно, то
объединим несколько узлов высокоскоростными каналами. Подобную архитектуру называют
кластерной, и по такому принципу построены CRAY SV1, HP Exemplar, Sun StarFire,
NEC SX-5, последние модели IBM SP2 и другие. Именно это направление является в
настоящее время наиболее перспективным для конструирования компьютеров с
рекордными показателями производительности.
Использование параллельных вычислительных систем
К
сожалению чудеса в жизни редко случаются. Гигантская производительность
параллельных компьютеров и супер-ЭВМ с лихвой компенсируется сложностями их
использования. Начнем с самых простых вещей. У вас есть программа и доступ,
скажем, к 256-процессорному компьютеру. Что вы ожидаете? Да ясно что: вы вполне
законно ожидаете, что программа будет выполняться в 256 раз быстрее, чем на
одном процессоре. А вот как раз этого, скорее всего, и не будет.
Закон Амдала и его следствия
Предположим,
что в вашей программе доля операций, которые нужно выполнять последовательно,
равна f, где 0<=f<=1 (при этом доля понимается не по статическому числу
строк кода, а по числу операций в процессе выполнения). Крайние случаи в
значениях f соответствуют полностью параллельным (f=0) и полностью
последовательным (f=1) программам. Так вот, для того, чтобы оценить, какое
ускорение S может быть получено на компьютере из 'p' процессоров при данном
значении f, можно воспользоваться законом Амдала:
Если
9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то
ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от
качества реализации параллельной части кода и числа используемых процессоров
(ясно, что 10 получается только в том случае, когда время исполнения
параллельной части равно 0).
Посмотрим
на проблему с другой стороны: а какую же часть кода надо ускорить (а значит и
предварительно исследовать), чтобы получить заданное ускорение? Ответ можно
найти в следствии из закона Амдала: для того чтобы ускорить выполнение
программы в q раз необходимо
ускорить не менее, чем в q раз не менее, чем (1-1/q)-ю часть программы. Следовательно, если есть желание
ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то
необходимо получить не меньшее ускорение не менее, чем на 99.99% кода, что
почти всегда составляет значительную часть программы!
Отсюда
первый вывод - прежде, чем основательно переделывать код для перехода на
параллельный компьютер (а любой суперкомпьютер, в частности, является таковым)
надо основательно подумать. Если оценив заложенный в программе алгоритм вы
поняли, что доля последовательных операций велика, то на значительное ускорение
рассчитывать явно не приходится и нужно думать о замене отдельных компонент
алгоритма.
В
ряде случаев последовательный характер алгоритма изменить не так сложно.
Допустим, что в программе есть следующий фрагмент для вычисления суммы n
чисел:
s = 0
Do i = 1, n
s = s + a(i)
EndDo
(можно
тоже самое на любом другом языке)
По
своей природе он строго последователен, так как на i-й итерации цикла требуется
результат с (i-1)-й и все итерации выполняются одна за одной. Имеем 100%
последовательных операций, а значит и никакого эффекта от использования
параллельных компьютеров. Вместе с тем, выход очевиден. Поскольку в большинстве
реальных программ (вопрос: а почему в большинстве, а не во всех?) нет
существенной разницы, в каком порядке складывать числа, выберем иную схему
сложения. Сначала найдем сумму пар соседних элементов: a(1)+a(2), a(3)+a(4),
a(5)+a(6) и т.д. Заметим, что при такой схеме все пары можно складывать
одновременно! На следующих шагах будем действовать абсолютно аналогично,
получив вариант параллельного алгоритма.
Казалось
бы в данном случае все проблемы удалось разрешить. Но представьте, что
доступные вам процессоры разнородны по своей производительности. Значит будет
такой момент, когда кто-то из них еще трудится, а кто-то уже все сделал и
бесполезно простаивает в ожидании. Если разброс в производительности компьютеров
большой, то и эффективность всей системы при равномерной загрузке процессоров
будет крайне низкой.
Словом,
заставить параллельную вычислительную систему или супер-ЭВМ работать с
максимальной эффективность на конкретной программе это, прямо скажем, задача не
из простых, поскольку необходимо
тщательное согласование структуры программ и алгоритмов с особенностями
архитектуры параллельных вычислительных систем.
Заключительный вопрос. Как вы
думаете, верно ли утверждение: чем мощнее компьютер, тем быстрее на нем можно
решить данную задачу?
Заключительный ответ. Нет, это не
верно. Это можно пояснить простым бытовым примером. Если один землекоп выкопает
яму 1м*1м*1м за 1 час, то два таких же землекопа это сделают за 30 мин - в это
можно поверить. А за сколько времени эту работу сделают 60 землекопов? За 1
минуту? Конечно же нет! Начиная с некоторого момента они будут просто мешаться
друг другу, не ускоряя, а замедляя процесс. Так же и в компьютерах: если задача
слишком мала, то мы будем дольше заниматься распределением работы,
синхронизацией процессов, сборкой результатов и т.п., чем непосредственно
полезной работой.
Совершенно
ясно, что не все так просто...
Список литературы
Для
подготовки данной работы были использованы материалы с сайта http://parallel.ru