Компьютерные системы и сети Часть 1 (Архитектура ВС) Мельникова ЕВ, БГУИР 2009 (Мет пособие). Компьютерные системы и сети Часть 1 (Архитектура ВС) Мельникова. Учебнометодический комплекс по дисциплине компьютерные системы и сети для студентов специальности Т. 10 02 00 Программное обеспечение информационных технологий
 Скачать 0.76 Mb.
|
|
4.Основные этапы развития параллельной обработки Идея параллельной обработки возникла одновременно с появлением первых вычислительных машин. В начале 50-х гг. американский математик Дж. фон Нейман предложил архитектуру последовательной ЭВМ, которая приобрела классические формы и применяется практически во всех современных ЭВМ. Однако фон Нейман разработал также принцип построения процессорной матрицы, в которой каждый элемент был соединен с четырьмя соседними и имел 29 состояний. Он теоретически показал, что такая матрица может выполнять все операции, поскольку она моделирует поведение машины Тьюринга. Практическая реализация основных идей параллельной обработки началась только в 60-х гг. нашего столетия. Это связано с появлением транзистора, который благодаря малым размерам и высокой надежности по сравнению с электронными лампами позволил строить машины, состоящие из большого 73 количества логических элементов, что принципиально необходимо для реализации любой формы параллелизма. Появление параллельных ЭВМ с различной организацией (конвейерные ЭВМ, процессорные матрицы, многопроцессорные ЭВМ) вызвано различными причинами. Совершенствование этих ЭВМ происходило по внутренним законам развития данного типа машин. Рассмотрим основные этапы совершенствования параллельных ЭВМ для каждого типа структур. Конвейерные ЭВМ. Основополагающим моментом для развития конвейерных ЭВМ явилось обоснование академиком С.А.Лебедевым в 1956 г. метода, названного "принципом водопровода" (позже он стал называться конвейером). Прежде всего был реализован конвейер команд, на основании которого практически одновременно были построены советская ЭВМ БЭСМ-6 (1957- 1966 гг., разработка Института точной механики и вычислительной техники АН СССР) и английская машина ATLAS (1957-1963 гг.). Конвейер команд предполагал наличие многоблочной памяти и секционированного процессора, в котором на разных этапах обработки находилось несколько команд. Конвейер команд позволил получить в ЭВМ БЭСМ-6 быстродействие в 1 млн. оп/с. В дальнейшем конвейеры команд совершенствовались и стали необходимым элементом всех быстродействующих ЭВМ, в частности, использовались в известных семействах ЭВМ IBM/360 и ЕС ЭВМ. Следующим заметным шагом в развитии конвейерной обработки, реализованном в ЭВМ CDC-6600 (1964 г.), было введение в состав процессора нескольких функциональных устройств, позволяющих одновременно выполнять несколько арифметико-логических операций: сложение, умножение, логические операции. В конце 60-х гг. был введен в использование арифметический конвейер, который нашел наиболее полное воплощение в ЭВМ CRAY-1 (1972-1976 гг.). Арифметический конвейер предполагает разбиение цикла выполнения арифметико-логической операции на ряд этапов, для каждого из которых отводится собственное оборудование. Таким образом, на разных этапах обработки нахо-дится несколько чисел, что позволяет производить эффективную обработку вектора чисел. Сочетание многофункциональности, арифметического конвейера для каждого функционального блока и малой длительности такта синхронизации позволяет получить быстродействие в десятки и сотни миллионов операций в секунду. Такие ЭВМ называются суперЭВМ. Процессорные матрицы. Идея получения сверхвысокого быстродействия в первую очередь связывалась с процессорными матрицами (ПМ). Предполагалось, что, увеличивая в нужной степени число процессорных элементов в матрице, можно получить любое заранее заданное быстродействие. Именно этим объясняется большой объем теоретических разработок по организации процессорных матриц. 74 В 60-х гг. в Институте математики Сибирского отделения АН СССР под руководством доктора технических наук Э.В.Евреинова сформировалось комплексное научное направление "Однородные системы, структуры и среды", которое получило развитие не только в СССР, но и за рубежом. Книга "Однородные универсальные вычислительные системы высокой производительности", изданная в 1966 г., была одной из первых в мире монографий, посвященных этой теме. В работах по однородным средам и системам исследовались матрицы с различными связями между элементами и конфигурацией, а также с элементами разной сложности и составом функций. Поскольку в 60-е гг. логические схемы с большим уровнем интеграции отсутствовали, то напрямую реализовать принципы функционирования процессорной матрицы, содержащей множество элементарных процессоров, не представлялось возможным. Поэтому для проверки основных идей строились однородные системы из нескольких больших машин. Так, в 1966 г. была построена система Минск-222, спроектированная совместно с Институтом математики Сибирского отделения АН СССР и минским заводом ЭВМ им. Г.К.Орджоникидзе. Система содержала до 16 соединенных в кольцо ЭВМ Минск-2. Для нее было разработано специальное математическое обеспечение. Другое направление в развитии однородных сред, основанное на построении процессорных матриц, состоящих из крупных процессорных элементов с достаточно большой локальной памятью, возникло в США и связано с именами Унгера, Холланда, Слотника. Была создана ЭВМ ILLIAC-IV (1966-1975 гг.), которая надолго определила пути развития процессорных матриц. В машине использовались матрицы 8*8 процессоров, каждый с быстродействием около 4 млн. оп/с и памятью 16 кбайт. Для ILLIAC-IV были разработаны кроме Ассемблера еще несколько параллельных языков высокого уровня. ЭВМ ILLIAC-IV позволила отработать вопросы коммутации, связи с базовой ЭВМ, управления вычислительным процессом. Особенно ценным является опыт разработки параллельных алгоритмов вычислений, определивший области эффективного использования подобных машин. Примерно в то же время в СССР была разработана близкая по принципам построения ЭВМ М-10. Затем процессорные матрицы стали разрабатываться и выпускаться в ряде стран в большом количестве. Широко известной советской ЭВМ этого класса являлась машина ПС-2000, разработанная Институтом проблем управления АН СССР и запущенная в 1982 г. в производство. Одной из наиболее сложных частей процессорных матриц является система коммутации. Самые простые ее варианты - кольцо и регулярная матрица соединений, где каждый узел связан только с двумя или четырьмя соседними, сильно ограничивают класс эффективно решаемых задач. Поэтому на протяжении всего времени существования параллельной обработки разрабатывались коммутаторы с более широкими возможностями: многомерные кубы, универсальные коммутаторы, коммутационные среды. В 75 СССР работы, связанные с коммутаторами для ПМ, наибольшее развитие получили в Таганрогском радиотехническом институте. Многопроцессорные ЭВМ. Одной из первых полномасштабных многопроцессорных систем явилась система D825 фирмы "BURROUGHS". Начиная с 1962 г. было выпущено большое число экземпляров и модификаций D825. Выпуск первых многопроцессорных систем, в частности D825, диктовался необходимостью получения не высокого быстродействия, а высокой живучести ЭВМ, встраиваемых в военные командные системы и системы управления. С этой точки зрения параллельные ЭВМ считались наиболее перспективными. Система D825 содержала до четырех ПЭ и 16 модулей памяти, соединенных матричным коммутатором, который допускал одновременное соединение любого процессора с любым блоком памяти. Существует мнение, что система D825 получила широкое распространение потому, что для нее впервые была разработана полноценная операционная система ASOR, обеспечившая синхронизацию процессов и распределение ресурсов. В дальнейшем в СССР и на Западе были разработаны многопроцессорные системы, в которых все большее внимание уделялось операционным системам, языкам программирования, параллельной вычислительной математике. Совершенствование микроэлектронной элементной базы, появление в 80-х годах БИС и СБИС позволили перейти к реализации структур с очень большим количеством ПЭ. Появились разработки по систолическим массивам, реализации многопроцессорных систем с программируемой архитектурой, ЭВМ с управлением от потока данных.Большая плотность упаковки транзисторов на кристалле позволила разместить в одной микросхеме несколько АЛУ. Это позволило реализовать принцип суперскалярной обработки. Если в последовательной ЭВМ пользователь в процессе программирования задачи в основном следит за логикой метода вычислений, то в параллельной ЭВМ ему приходится дополнительно заниматься размещением данных и синхронизацией вычислительных процессов. Это означает, что процесс программирования существенно усложняется, особенно если программирование ведется на уровне Ассемблера, чтобы повысить эффективность использования дорогостоящих параллельных ЭВМ. Такое программирование доступно только профессионально подготовленным программистам. 76 5. Принципы конвейерной организации 5.1.Простейшая организация конвейера и оценка его производительности Разработчики архитектуры компьютеров издавна прибегали к методам проектирования, известным под общим названием "совмещение операций", при котором аппаратура компьютера в любой момент времени выполняет одновременно более одной базовой операции. Этот общий метод включает два понятия: параллелизм и конвейеризацию. Хотя у них много общего и их зачастую трудно различать на практике, эти термины отражают два совершенно различных подхода. При параллелизме совмещение операций достигается путем воспроизведения в нескольких копиях аппаратной структуры. Высокая производительность достигается за счет одновременной работы всех элементов структур, осуществляющих решение различных частей задачи. Конвейеризация (или конвейерная обработка) в общем случае основана на разделении подлежащей исполнению функции на более мелкие части, называемые ступенями, и выделении для каждой из них отдельного блока аппаратуры. Так обработку любой машинной команды можно разделить на несколько этапов (несколько ступеней), организовав передачу данных от одного этапа к следующему. При этом конвейерную обработку можно использовать для совмещения этапов выполнения разных команд. Производительность при этом возрастает благодаря тому, что одновременно на различных ступенях конвейера выполняются несколько команд. Конвейерная обработка такого рода широко применяется во всех современных быстродействующих процессорах. Для иллюстрации основных принципов построения процессоров мы будем использовать простейшую архитектуру, содержащую 32 целочисленных регистра общего назначения (R0,...,R31), 32 регистра плавающей точки (F0,...,F31) и счетчик команд PC. Будем считать, что набор команд нашего процессора включает типичные арифметические и логические операции, операции с плавающей точкой, операции пересылки данных, операции управления потоком команд и системные операции. В арифметических командах используется трехадресный формат, типичный для RISC- процессоров, а для обращения к памяти используются операции загрузки и записи содержимого регистров в память. Выполнение типичной команды можно разделить на следующие этапы: выборка команды - IF (по адресу, заданному счетчиком команд, из памяти извлекается команда); декодирование команды / выборка операндов из регистров - ID; выполнение операции / вычисление эффективного адреса памяти - EX; обращение к памяти - MEM; запоминание результата - WB. Работу конвейера можно условно представить в виде временных диаграммы (рисунок 5.1.1), на которых обычно изображаются выполняемые команды, номера тактов и этапы выполнения команд. 77 Номер команды Номер такта 1 2 3 4 5 6 7 8 9 Команда i IF ID EX MEM WB Команда i+1 IF ID EX MEM WB Команда i+2 IF ID EX MEM WB Команда i+3 IF ID EX MEM WB Команда i+4 IF ID EX MEM WB Рис. 5.1.1 Диаграмма работы простейшего конвейера Конвейеризация увеличивает пропускную способность процессора (количество команд, завершающихся в единицу времени), но она не сокращает время выполнения отдельной команды. В действительности, она даже несколько увеличивает время выполнения каждой команды из-за накладных расходов, связанных с управлением регистровыми станциями. Однако увеличение пропускной способности означает, что программа будет выполняться быстрее по сравнению с простой неконвейерной схемой. Тот факт, что время выполнения каждой команды в конвейере не уменьшается, накладывает некоторые ограничения на практическую длину конвейера. Кроме ограничений, связанных с задержкой конвейера, имеются также ограничения, возникающие в результате несбалансированности задержки на каждой его ступени и из-за накладных расходов на конвейеризацию. Частота синхронизации не может быть выше, а, следовательно, такт синхронизации не может быть меньше, чем время, необходимое для работы наиболее медленной ступени конвейера. Накладные расходы на организацию конвейера возникают из-за задержки сигналов в конвейерных регистрах (защелках) и из-за перекосов сигналов синхронизации. Конвейерные регистры к длительности такта добавляют время установки и задержку распространения сигналов. В предельном случае длительность такта можно уменьшить до суммы накладных расходов и перекоса сигналов синхронизации, однако при этом в такте не останется времени для выполнения полезной работы по преобразованию информации. В качестве примера рассмотрим неконвейерную машину с пятью этапами выполнения операций, которые имеют длительность 50, 50, 60, 50 и 50 нс соответственно.Пусть накладные расходы на организацию конвейерной обработки составляют 5 нс. Тогда среднее время выполнения команды в неконвейерной машине будет равно 260 нс. Если же используется конвейерная организация, длительность такта будет равна длительности самого медленного этапа обработки плюс накладные расходы, т.е. 65 нс. Это время соответствует среднему времени выполнения команды в конвейере. Таким образом, ускорение, полученное в результате конвейеризации, будет равно: 78 Среднее время выполнения команды в неконвейерном режиме 260 Среднее время выполнения команды в конвейерном режиме = 65 = 4 Конвейеризация эффективна только тогда, когда загрузка конвейера близка к полной, а скорость подачи новых команд и операндов соответствует максимальной производительности конвейера. Если произойдет задержка, то параллельно будет выполняться меньше операций и суммарная производительность снизится. При реализации конвейерной обработки возникают ситуации, которые препятствуют выполнению очередной команды из потока команд в предназначенном для нее такте. Такие ситуации называются конфликтами. Конфликты снижают реальную производительность конвейера, которая могла бы быть достигнута в идеальном случае. Существуют три класса конфликтов: Структурные конфликты, которые возникают из-за конфликтов по ресурсам, когда аппаратные средства не могут поддерживать все возможные комбинации команд в режиме одновременного выполнения с совмещением. Конфликты по данным, возникающие в случае, когда выполнение одной команды зависит от результата выполнения предыдущей команды. Конфликты по управлению, которые возникают при конвейеризации команд переходов и других команд, которые изменяют значение счетчика команд. Конфликты в конвейере приводят к необходимости приостановки выполнения команд (pipeline stall). Обычно в простейших конвейерах, если приостанавливается какая-либо команда, то все следующие за ней команды также приостанавливаются. Команды, предшествующие приостановленной, могут продолжать выполняться, но во время приостановки не выбирается ни одна новая команда. 5.2.Структурные конфликты и способы их минимизации Совмещенный режим выполнения команд в общем случае требует конвейеризации функциональных устройств и дублирования ресурсов для разрешения всех возможных комбинаций команд в конвейере. Если какая- нибудь комбинация команд не может быть принята из-за конфликта по ресурсам, то говорят, что в машине имеется структурный конфликт. Наиболее типичным примером машин, в которых возможно появление структурных конфликтов, являются машины с не полностью конвейерными функциональными устройствами. Время работы такого устройства может составлять несколько тактов синхронизации конвейера. В этом случае последовательные команды, которые используют данное функциональное устройство, не могут поступать в него в каждом такте. Другая возможность появления структурных конфликтов связана с недостаточным дублированием некоторых ресурсов, что препятствует выполнению произвольной 79 последовательности команд в конвейере без его приостановки. Например, машина может иметь только один порт записи в регистровый файл, но при определенных обстоятельствах конвейеру может потребоваться выполнить две записи в регистровый файл в одном такте. Это также приведет к структурному конфликту. Когда последовательность команд наталкивается на такой конфликт, конвейер приостанавливает выполнение одной из команд до тех пор, пока не станет доступным требуемое устройство. Структурные конфликты возникают, например, и в машинах, в которых имеется единственный конвейер памяти для команд и данных (рисунок 5.2.1). В этом случае, когда одна команда содержит обращение к памяти за данными, оно будет конфликтовать с выборкой более поздней команды из памяти. Чтобы разрешить эту ситуацию, можно просто приостановить конвейер на один такт, когда происходит обращение к памяти за данными. Подобная приостановка часто называются "конвейерным пузырем" (pipeline bubble) или просто пузырем, поскольку пузырь проходит по конвейеру, занимая место, но не выполняя никакой полезной работы. При всех прочих обстоятельствах, машина без структурных конфликтов будет всегда иметь более низкий CPI (среднее число тактов на выдачу команды). Возникает вопрос: почему разработчики допускают наличие структурных конфликтов? Для этого имеются две причины: снижение стоимости и уменьшение задержки устройства. Конвейеризация всех функциональных устройств может оказаться слишком дорогой. Машины, допускающие два обращения к памяти в одном такте, должны иметь удвоенную пропускную способность памяти, например, путем организации раздельных кэшей для команд и данных. Аналогично, полностью конвейерное устройство деления с плавающей точкой требует огромного количества вентилей. Если структурные конфликты не будут возникать слишком часто, то может быть и не стоит платить за то, чтобы их обойти. Как правило, можно разработать неконвейерное, или не полностью конвейерное устройство, имеющее меньшую общую задержку, чем полностью конвейерное. Например, разработчики устройств с плавающей точкой компьютеров CDC7600 и MIPS R2010 предпочли иметь меньшую задержку выполнения операций вместо полной их конвейеризации. Номер команды Номер такта 1 2 3 4 5 6 7 8 9 10 Команда загрузки IF ID EX MEM WB Команда 1 IF ID EX ME M WB Команда 2 IF ID EX ME M WB 80 Команда 3 stall IF ID EX MEM WB Команда 4 IF ID EX MEM WB Команда 5 IF ID EX ME M Команда 6 IF ID EX Рис. 5.2.1 Диаграмма работы конвейера при структурном конфликте Конфликты по данным, остановы конвейера и реализация механизма обходов Одним из факторов, который оказывает существенное влияние на производительность конвейерных систем, являются межкомандные логические зависимости. Такие зависимости в большой степени ограничивают потенциальный параллелизм смежных операций, обеспечиваемый соответствующими аппаратными средствами обработки. Степень влияния этих зависимостей определяется как архитектурой процессора (в основном, структурой управления конвейером команд и параметрами функциональных устройств), так и характеристиками программ. Конфликты по данным возникают в том случае, когда применение конвейерной обработки может изменить порядок обращений за операндами так, что этот порядок будет отличаться от порядка, который наблюдается при последовательном выполнении команд на неконвейерной машине. Рассмотрим конвейерное выполнение последовательности команд на рисунке 5.2.2 ADD R1,R2,R3 IF ID EX ME M WB SUB R4,R1,R5 IF ID EX ME M WB AND R6,R1,R7 IF ID EX ME M WB OR R8,R1,R9 IF ID EX ME M WB XOR R10,R1,R 11 IF ID EX ME M WB Рис. 5.2.2, а. Последовательность команд в конвейере и ускоренная пересылка данных 81 ADD R1,R2,R3 IF ID EX ME M WB R W SUB R4,R1,R5 IF ID EX ME M WB R W AND R6,R1,R7 IF ID EX ME M WB R W OR R8,R1,R9 IF ID EX ME M WB R W XOR R10,R1,R 11 IF ID EX ME M WB R W Рис. 5.2.2, б. Совмещение чтения и записи регистров в одном такте В этом примере все команды, следующие за командой ADD, используют результат ее выполнения. Команда ADD записывает результат в регистр R1, а команда SUB читает это значение. Если не предпринять никаких мер для того, чтобы предотвратить этот конфликт, команда SUB прочитает неправильное значение и попытается его использовать. На самом деле значение, используемое командой SUB, является даже неопределенным: хотя логично предположить, что SUB всегда будет использовать значение R1, которое было присвоено какой-либо командой, предшествовавшей ADD, это не всегда так. Если произойдет прерывание между командами ADD и SUB, то команда ADD завершится, и значение R1 в этой точке будет соответствовать результату ADD. Такое непрогнозируемое поведение очевидно неприемлемо. Проблема, поставленная в этом примере, может быть разрешена с помощью достаточно простой аппаратной техники, которая называется пересылкой или продвижением данных (data forwarding), обходом (data bypassing), иногда закороткой (short-circuiting). Эта аппаратура работает следующим образом. Результат операции АЛУ с его выходного регистра всегда снова подается назад на входы АЛУ. Если аппаратура обнаруживает, что предыдущая операция АЛУ записывает результат в регистр, соответствующий источнику операнда для следующей операции АЛУ, то логические схемы управления выбирают в качестве входа для АЛУ результат, поступающий по цепи "обхода" , а не значение, прочитанное из регистрового файла (рисунок 5.2.3). 82 Рис. 5.2.3. АЛУ с цепями обхода и ускоренной пересылки Эта техника "обходов" может быть обобщена для того, чтобы включить передачу результата прямо в то функциональное устройство, которое в нем нуждается: результат с выхода одного устройства "пересылается" на вход другого, а не с выхода некоторого устройства только на его вход. |