2006 Ответы на экзаменационные вопросы по ПОД (Lilalbrother)

Ответы на вопросы по курсу «Параллельная обработка данных»БИЛЕТ 1. Виды параллельной обработки данных, их особенности.Параллельная обработка данных, воплощая идею одновременного выполнения несколькихдействий, имеет две разновидности: конвейерность и собственно параллельность.Параллельная обработка. Если некое устройство выполняет одну операцию за единицувремени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, чтоесть пять таких же независимых устройств, способных работать одновременно, то ту жетысячу операций система из пяти устройств может выполнить уже не за тысячу, а задвести единиц времени. Аналогично система из N устройств ту же работу выполнит за1000/N единиц времени.

УВЕЛИЧЕНИЕ КОЛИЧЕСТВА НЕЗАВИСИМОРАБОТАЮЩИХ УСТРОЙСТВ.Конвейерная обработка. Что необходимо для сложения двух вещественных чисел,представленных в форме с плавающей запятой? Целое множество мелких операций таких,как сравнение порядков, выравнивание порядков, сложение мантисс, нормализация и т.п.Процессоры первых компьютеров выполняли все эти "микрооперации" для каждой парыаргументов последовательно одна за одной до тех пор, пока не доходили доокончательного результата, и лишь после этого переходили к обработке следующей парыслагаемых.

УСЛОЖНИТЬ САМО УСТРОЙСТВО, ЧТОБЫ НА РАЗНЫХ ЭТАПАХМОГЛИ НАХОДИТЬСЯ РАЗНЫЕ ДАННЫЕ.Идея конвейерной обработки заключается в выделении отдельных этапов выполненияобщей операции, причем каждый этап, выполнив свою работу, передавал бы результатследующему, одновременно принимая новую порцию входных данных. Получаемочевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных вовремени операций. Предположим, что в операции можно выделить пять микроопераций,каждая из которых выполняется за одну единицу времени.

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

ТЕСУЩЕСТВУЕТ НЕКОТОРАЯ ЗАДЕРЖКА ДЛЯ ТОГО ЧТОБЫ ЗАПОЛНИТЬ ВСЕЭТАПЫ КОНВЕЕРА, НО КОГДА ОНА ЗАПОЛНЕНА ДАЛЬШЕ ПРОИСХОДИТУСКОРЕНИЕ ОБРАБОТКИ.БИЛЕТ 2-3. История появления параллелизма в архитектуре ЭВМ: IBM 701, 704,709, IBM STRETCH, ATLAS, CDC 6600, CDC 7600, ILLIAC IV.IBM 701 (1953), IBM 704 (1955): разрядно-параллельная память, разряднопараллельная арифметика.Все самые первые компьютеры (EDSAC, EDVAC, UNIVAC) имели разряднопоследовательную память, из которой слова считывались последовательно бит за битом.Первым коммерчески доступным компьютером, использующим разрядно-параллельнуюпамять (на CRT) и разрядно-параллельную арифметику, стал IBM 701, а наибольшуюпопулярность получила модель IBM 704 (продано 150 экз.), в которой, помимосказанного, была впервые применена память на ферритовых сердечниках и аппаратноеАУ с плавающей точкой.

ПЕРВЫЕ ЭВМ СЧИТЫВАЛИ СЛОВА ПО БИТАМ, ИБРАБАТЫВАЛИ ИХ ТОЖ ПО БИТАМ,IBM701 IBM704 СЧИТЫВАЛИ ЗА РАЗ ВСЕСЛОВО, И ИМЕЛИ РАЗРЯДНО ПАРАЛЛЕЛЬНУЮ АРИФМЕТИКУ.IBM 709 (1958): независимые процессоры ввода/вывода.Процессоры первых компьютеров сами управляли вводом/выводом. Однако скоростьработы самого быстрого внешнего устройства, а по тем временам это магнитная лента,была в 1000 раз меньше скорости процессора, поэтому во время операций ввода/выводапроцессор фактически простаивал. В 1958г. к компьютеру IBM 704 присоединили 6независимых процессоров ввода/вывода, которые после получения команд могли работатьпараллельно с основным процессором, а сам компьютер переименовали в IBM 709.ПРИДУМАЛИ СНОБЖАТЬ УСТРОЙСТВА ВВОДА\ВЫВОДА СОБСТВЕНЫМИПРОЦЕССОРАМИ ДЛЯ ТОГО ЧТО БЫ ВСЯ СКОРОСТЬ СИСТЕМЫ НЕ БЫЛА ТАКСИЛЬНО ОГРАНИЧЕНА СКОРОСТЬЮ ЕЕ САМОГО МЕДЛЕННОГО УЗЛА.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 слово (байт)растет. В настоящее время, подобная иерархия поддерживается даже на персональныхкомпьютерах.БИЛЕТ 4. Оценка вычислительной сложности больших задач.Задача 1.Рассмотрим модель атмосферы как важнейшей составляющей климата и предположим,что мы интересуемся развитием атмосферных процессов на протяжении, например, 100лет. При построении алгоритмов нахождения численных решений используетсяупоминавшийся ранее принцип дискретизации. Общее число элементов, на которыеразбивается атмосфера в современных моделях, определяется сеткой с шагом в 1° пошироте и долготе на всей поверхности земного шара и 40 слоями по высоте.

Это дает около 2,6*10^6 элементов (360 * 180 * 40 = 2,592,000). Каждый элемент описываетсяпримерно 10 компонентами. Следовательно, в любой фиксированный момент временисостояние атмосферы на земном шаре характеризуется ансамблем из 2,6*10^7 чисел. Условия обработки численных результатов требуют нахождения всех ансамблей черезкаждые 10 минут, т. е. за период 100 лет необходимо определить около 5,З*10^6(5,256,000 = 5,2*1^6) ансамблей. Итого, только за один численный экспериментприходится вычислять 1,4*10^14 значимых результатов промежуточных вычислений.Если теперь принять во внимание, что для получения и дальнейшей обработки каждогопромежуточного результата нужно выполнить 102— 103 арифметических операций, то этоозначает, что для проведения одного численного эксперимента с глобальной модельюатмосферы необходимо выполнить порядка 1016—1017 арифметических операций сплавающей запятой.Таким образом, вычислительная система с производительностью 1012 операций в секундубудет осуществлять такой эксперимент при полной своей загрузке и эффективномпрограммировании в течение нескольких часов.