Параллельный способ обработки данных это

Библиографическая ссылка на статью:
Новиков Д.Ю. Методы параллельной обработки данных в распределенных системах // Современная техника и технологии. 2015. № 5 [Электронный ресурс]. URL: https://technology.snauka.ru/2015/05/6560 (дата обращения: 04.10.2021).

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

Так как методов соединения этих компьютеров на тот момент времени не существовало, данные компьютеры работали независимо друг от друга. В середине 80-х годов, с разработкой новейших технологий обстановка в корни изменилась. Такой разработкой была разработка мощных микропроцессоров. Вначале микропроцессоры были 8-битными.Следом начали появляться16-, 32-, а также 64-битные процессоры. Большая часть из них обладали вычислительной мощностью больших компьютеров или мейнфреймов.

Темп развития и совершенствования компьютеров в последние полвека буквально ошеломляет. От компьютеров, стоивших несколько сотен миллионов долларов, которые выполняли одну операцию в секунду, мы перешли к компьютерам, несколько сотен долларов, которые выполняют десятки миллионов команд в секунду. Эта ощутимая разница в отношении цена/производительность стала порядка 10 12 .

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

Рассмотрим несколько примеров распределенных систем. Первым примером распределенной системы можно рассмотреть сеть рабочих станций в ВУЗе или в отделе некой компании. Данная распределенная система иметь единую файловую систему, хранящиеся файлы в которой одинаково доступны всем машинам с использование постоянного пути доступа. Помимо этого, когда некий пользователь вводит команду, система находит наилучшее место для выполнения запрашиваемого действия, возможно, на собственной рабочей станции пользователя или даже на простаивающей рабочей станции, принадлежащей какому-то другому пользователю, а возможно и на одном из свободных процессором машинного зала. Если некая система выглядит и ведет себя как обычная однопроцессорная система с разделением времени, эта система считается распределенной системой. В качестве второго примера рассмотрим WorldWideWeb. Интернет представляет собой простую модель распределенных данных. Для того чтобы пользователь смог увидеть документ, достаточно активировать ссылку, после чего пользователю откроется на экране этот документ. Нет никакой необходимости знать, какой сервер предоставляет пользователю документ, достаточно лишь информации о том, где он расположен. Любой документ публикуется следующим образом: для начала необходимо дать документу уникальное имя в формате унифицированного указателя ресурса (URL), которая ссылается на локальный файл с содержимом документа. Обычный пользователь в наше время осознает, что все документы глобальной сети расположены в разных местах и распределены по различным серверам. В случае если б интернет представлялся пользователям гигантской системой документооборота, она также могла бы считаться распределенной системой. К сожалению, этот момент еще не наступил.

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

• Распределенная система— это совокупность нескольких компьютеров, воспринимаемых пользователями, как единая объединенная система.
• Распределенная информационная система (РИС)–это совокупность взаимодействующих друг с другом программных компонент. Каждая из которых, может рассматриваться как приложение, исполняемое в рамках отдельного процесса.

Эти определения оговаривают два момента:

— Первый относится к аппаратуре: все машины автономны.

— Второй касается программного обеспечения: пользователь уверен, что он работает с единой системой.

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

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

Параллельная обработка данных, воплощая идею одновременного выполнения нескольких действий, имеет две разновидности: конвейерность и собственно параллельность.

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

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

Рассмотрим на примере данный метод обработки информации. Пусть какое-то устройство выполняет одну операцию в секунду, то 1000 таких операций оно выполнит уже за 1000 секунд. Предположим, что существует 5 таких устройств, которые будут работать одновременно. Ту же 1000 операций эта система устройств выполнит ту же 1000 операций в пять раз быстрее, т.е. за 200 секунд. Таким образом, система, состоящая из N устройств, способна выполнить 1000 операций за 1000/N секунд. Аналогию этого метода можно привести из жизни: предположим, что один работник вскопает участок за 10 часов, то 10 работников, при условии, что они будут работать одновременно при одинаковых способностях, справятся с той же работой за 12 минут.

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

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

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

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

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

Впервые принцип конвейерной обработки данных использовался в машине ATLAS, разработанной в Манчестерском университете. Команды выполняются в 4 стадии: выборка команды. Вычисление адреса операнда, выборка операнда и выполнение операции. Этот метод позволил уменьшить время выполнения операций с 5 мкс до 1.5 мкс. Эта машина повлияла на архитектуру компьютеров, а также на программное обеспечение: в этом компьютере впервые была использована мультипрограммная операционная система, которая была основана на использовании виртуальной памяти и системы прерываний.

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

Источник

PARALLEL.RU — Информационно-аналитический центр по параллельным вычислениям

© Воеводин Вл.В.
Курс лекций
«Параллельная обработка данных»

Лекция 1. Введение в предмет

Параллельные компьютеры и супер-ЭВМ

О том, что где-то существуют некие мистические «очень мощные» компьютеры слышал, наверное, каждый. В самом деле, не так давно было много разговоров о поставке в Гидрометеоцентр России могучих компьютеров фирмы Cray Research. В ноябре 1999 года состоялось официальное открытие Межведомственного суперкомпьютерного центра, который в настоящий момент имеет компьютер с 768 процессорами. Опять же, если компьютер с именем Deep Blue обыграл самого Гарри Каспарова, то он, согласитесь — и здесь интуиция Вас не подвела, ну никак не может быть простой персоналкой.

Для многих подобные компьютеры так и остаются тайной за семью печатями, некой TERRA INCOGNITA, с которой ассоциации всегда связаны с чем-то большим: огромные размеры, большие задачи, крупные фирмы и компании, невероятные скорости работы или что-то иное, но обязательно это будет «на грани», для чего «обычного» явно мало, а подойдет только «супер», суперкомпьютер или супер-ЭВМ. В этом интуитивном восприятии есть изрядная доля истины, поскольку к классу супер-ЭВМ принадлежат лишь те компьютеры, которые имеют максимальную производительность в настоящее время.

Быстрое развитие компьютерной индустрии определяет относительность данного понятия — то, что десять лет назад можно было назвать суперкомпьютером, сегодня под это определение уже не попадает. Например, производительность персональных компьютеров, использующих Pentium-III/500MHz, сравнима с производительностью суперкомпьютеров начала 70-х годов, однако по сегодняшним меркам суперкомпьютерами не являются ни те, ни другие.

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

Так о чем же речь и какие суперкомпьютеры существуют в настоящее время в мире? Вот лишь несколько параметров, дающих достаточно красноречивую характеристику машин этого класса. Компьютер ASCI WHITE, занимающий первое место в списке пятисот самых мощных компьютеров мира, объединяет 8192 процессора Power 3 с общей оперативной памятью в 4 Терабайта и производительностью более 12 триллионов операций в секунду.

Супер-ЭВМ и сверхвысокая производительность: зачем?

Простые рассчеты показывают, что конфигурации подобных систем могут стоить не один миллион долларов США — ради интереса прикиньте, сколько стоят, скажем, лишь 4 Тбайта оперативной памяти? Возникает целый ряд естественных вопросов: какие задачи настолько важны, что требуются компьютеры стоимостью несколько миллионов долларов? Или, какие задачи настолько сложны, что хорошего Пентиума не достаточно? На эти и подобные им вопросы хотелось бы найти разумные ответы.

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

Примем упрощенную схему, при которой моделируемая область отображается в куб, однако и ее будет достаточно для оценки числа необходимых арифметических операций. Разумные размеры куба, при которых можно получать правдоподобные результаты — это 100*100*100 точек. В каждой точке куба надо вычислить от 5 до 20 функций: три компоненты скорости, давление, температуру, концентрацию компонент (вода, газ и нефть — это минимальный набор компонент, в более реалистичных моделях рассматривают, например, различные фракции нефти). Далее, значения функций находятся как решение нелинейных уравнений, что требует от 200 до 1000 арифметических операций. И наконец, если исследуется нестационарный процесс, т.е. нужно понять, как эта система ведет себя во времени, то делается 100-1000 шагов по времени. Что получилось:

10 6 (точек сетки)*10(функций)*500(операций)*500(шагов по времени) = 2.5*10 12

2500 миллиардов арифметических операций для выполнения одного лишь расчета! А изменение параметров модели? А отслеживание текущей ситуации при изменении входных данных? Подобные расчеты необходимо делать много раз, что накладывает очень жесткие требования на производительность используемых вычислительных систем.

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

• автомобилестроение
• нефте- и газодобыча
• фармакология
• прогноз погоды и моделирование изменения климата
• сейсморазведка
• проектирование электронных устройств
• синтез новых материалов
• и многие, многие другие

В 1995 году корпус автомобиля Nissan Maxima удалось сделать на 10% прочнее благодаря использованию суперкомпьютера фирмы Cray (The Atlanta Journal, 28 мая, 1995г). С помощью него были найдены не только слабые точки кузова, но и наиболее эффективный способ их удаления.

По данным Марка Миллера (Mark Miller, Ford Motor Company), для выполнения crash-тестов, при которых реальные автомобили разбиваются о бетонную стену с одновременным замером необходимых параметров, съемкой и последующей обработкой результатов, компании Форд понадобилось бы от 10 до 150 прототипов новых моделей при общих затратах от 4 до 60 миллионов долларов. Использование суперкомпьютеров позволило сократить число прототипов на одну треть.

Совсем недавний пример — это развитие одной из крупнейших мировых систем резервирования Amadeus, используемой тысячами агенств со 180000 терминалов в более чем ста странах. Установка двух серверов Hewlett-Packard T600 по 12 процессоров в каждом позволила довести степень оперативной доступности центральной системы до 99.85% при текущей загрузке около 60 миллионов запросов в сутки.

И подобные примеры можно найти повсюду. В свое время исследователи фирмы DuPont искали замену хлорофлюорокарбону. Нужно было найти материал, имеющий те же положительные качества: невоспламеняемость, стойкость к коррозии и низкую токсичность, но без вредного воздействия на озоновый слой Земли. За одну неделю были проведены необходимые расчеты на суперкомпьютере с общими затратами около 5 тысяч долларов. По оценкам специалистов DuPont, использование традиционных экспериментальных методов исследований потребовало бы около трех месяцев и 50 тысяч долларов и это без учета времени, необходимого на синтез и очистку необходимого количества вещества.

Увеличение производительности ЭВМ, за счет чего?

А почему суперкомпьютеры считают так быстро? Вариантов ответа может быть несколько, среди которых два имеют явное преимущество: развитие элементной базы и использование новых решений в архитектуре компьютеров.

Попробуем разобраться, какой из этих факторов оказывается решающим для достижения рекордной производительности. Обратимся к известным историческим фактам. На одном из первых компьютеров мира — EDSAC, появившемся в 1949 году в Кембридже и имевшем время такта 2 микросекунды (2*10-6 секунды), можно было выполнить 2*n арифметических операций за 18*n миллисекунд, то есть в среднем 100 арифметических операций в секунду. Сравним с одним вычислительным узлом современного суперкомпьютера Hewlett-Packard V2600: время такта приблизительно 1.8 наносекунды (1.8*10-9 секунд), а пиковая производительность около 77 миллиардов арифметических операций в секунду.

Что же получается? За полвека производительность компьютеров выросла более, чем в семьсот миллионов раз. При этом выигрыш в быстродействии, связанный с уменьшением времени такта с 2 микросекунд до 1.8 наносекунд, составляет лишь около 1000 раз. Откуда же взялось остальное? Ответ очевиден — использование новых решений в архитектуре компьютеров. Основное место среди них занимает принцип параллельной обработки данных, воплощающий идею одновременного (параллельного) выполнения нескольких действий.

Параллельная обработка данных на ЭВМ

Параллельная обработка данных, воплощая идею одновременного выполнения нескольких действий, имеет две разновидности: конвейерность и собственно параллельность. Оба вида параллельной обработки интуитивно понятны, поэтому сделаем лишь небольшие пояснения.

Параллельная обработка. Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени. Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени. Подобные аналогии можно найти и в жизни: если один солдат вскопает огород за 10 часов, то рота солдат из пятидесяти человек с такими же способностями, работая одновременно, справятся с той же работой за 12 минут — принцип параллельности в действии!

Кстати, пионером в параллельной обработке потоков данных был академик А.А.Самарский, выполнявший в начале 50-х годов расчеты, необходимые для моделирования ядерных взрывов. Самарский решил эту задачу, посадив несколько десятков барышень с арифмометрами за столы. Барышни передавали данные друг другу просто на словах и откладывали необходимые цифры на арифмометрах. Таким образом, в частности, была расчитана эволюция взрывной волны. Работы было много, барышни уставали, а Александр Андреевич ходил между ними и подбадривал. Это, можно сказать, и была первая параллельная система. Хотя расчеты водородной бомбы были мастерски проведены, точность их была очень низкая, потому что узлов в используемой сетке было мало, а время счета получалось слишком большим.

Конвейерная обработка. Что необходимо для сложения двух вещественных чисел, представленных в форме с плавающей запятой? Целое множество мелких операций таких, как сравнение порядков, выравнивание порядков, сложение мантисс, нормализация и т.п. Процессоры первых компьютеров выполняли все эти «микрооперации» для каждой пары аргументов последовательно одна за одной до тех пор, пока не доходили до окончательного результата, и лишь после этого переходили к обработке следующей пары слагаемых.

Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят — ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени — ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

Казалось бы конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. В самом деле, пять устройств предыдущего примера обработают 100 пар аргументов за 100 единиц времени, что быстрее времени работы конвейерного устройства! В чем же дело? Ответ прост, увеличив в пять раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость. Представьте себе, что на автозаводе решили убрать конвейер, сохранив темпы выпуска автомобилей. Если раньше на конвейере одновременно находилась тысяча автомобилей, то действуя по аналогии с предыдущим примером надо набрать тысячу бригад, каждая из которых (1) в состоянии полностью собрать автомобиль от начала до конца, выполнив сотни разного рода операций, и (2) сделать это за то же время, что машина прежде находилась на конвейере. Представили себестоимость такого автомобиля? Нет? Согласен, трудно, разве что Ламборгини приходит на ум, но потому и возникла конвейерная обработка.

Краткая история появления параллелизма в архитектуре ЭВМ

Сегодня параллелизмом в архитектуре компьютеров уже мало кого удивишь. Все современные микропроцессоры, будь то 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 7600 (1969): конвейерные независимые функциональные устройства.
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 слово (байт) растет. В настоящее время, подобная иерархия поддерживается даже на персональных компьютерах.

А что же сейчас используют в мире?

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

1. Векторно-конвейерные компьютеры. Конвейерные функциональные устройства и набор векторных команд — это две особенности таких машин. В отличие от традиционного подхода, векторные команды оперируют целыми массивами независимых данных, что позволяет эффективно загружать доступные конвейеры, т.е. команда вида A=B+C может означать сложение двух массивов, а не двух чисел. Характерным представителем данного направления является семейство векторно-конвейерных компьютеров CRAY куда входят, например, CRAY EL, CRAY J90, CRAY T90 (в марте 2000 года американская компания TERA перекупила подразделение CRAY у компании Silicon Graphics, Inc.).

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 q раз не менее, чем (1-1/q)-ю часть программы. Следовательно, если есть желание ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение не менее, чем на 99.99% кода, что почти всегда составляет значительную часть программы!

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

В ряде случаев последовательный характер алгоритма изменить не так сложно. Допустим, что в программе есть следующий фрагмент для вычисления суммы n чисел: (можно тоже самое на любом другом языке)

По своей природе он строго последователен, так как на i-й итерации цикла требуется результат с (i-1)-й и все итерации выполняются одна за одной. Имеем 100% последовательных операций, а значит и никакого эффекта от использования параллельных компьютеров. Вместе с тем, выход очевиден. Поскольку в большинстве реальных программ (вопрос: а почему в большинстве, а не во всех?) нет существенной разницы, в каком порядке складывать числа, выберем иную схему сложения. Сначала найдем сумму пар соседних элементов: a(1)+a(2), a(3)+a(4), a(5)+a(6) и т.д. Заметим, что при такой схеме все пары можно складывать одновременно! На следующих шагах будем действовать абсолютно аналогично, получив вариант параллельного алгоритма.

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

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

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

Заключительный вопрос. Как вы думаете, верно ли утверждение: чем мощнее компьютер, тем быстрее на нем можно решить данную задачу?

Заключительный ответ. Нет, это не верно. Это можно пояснить простым бытовым примером. Если один землекоп выкопает яму 1м*1м*1м за 1 час, то два таких же землекопа это сделают за 30 мин — в это можно поверить. А за сколько времени эту работу сделают 60 землекопов? За 1 минуту? Конечно же нет! Начиная с некоторого момента они будут просто мешаться друг другу, не ускоряя, а замедляя процесс. Так же и в компьютерах: если задача слишком мала, то мы будем дольше заниматься распределением работы, синхронизацией процессов, сборкой результатов и т.п., чем непосредственно полезной работой.

Совершенно ясно, что не все так просто.

Содержание курса

Далее: Лекция 2. Архитектура векторно-конвейерных супер-ЭВМ CRAY C90

© Лаборатория Параллельных Информационных Технологий, НИВЦ МГУ

Источник