Принципы организации параллелизма выполнения машинных команд в процессорах

/>/>Министерствообразования и науки Российской Федерации
Федеральное агентство по образованию
Южно-Уральский государственный университет
Кафедра прикладной математики
Курсовая работа
по дисциплине «АрхитектураЭВМ и ВС»
на тему: «Принципыорганизации параллелизма выполнения
машинных команд в процессорах»
Выполнила: студентка группы ММ-392
Соловьева М.Н.
Дата «___» «                               »2007 г.
Проверил:
Никитин Г.А.
Дата «___» «                               »2007 г.
Оценка__________________________
Челябинск
2007

содержание
введение. 3
1 Классификацияпараллельных ВС… 5
1.1 Классификация Флинна. 5
1.2 Системы с общей и распределенной памятью… 7
2 Конвейеры операций. 9
2.1 Конвейеры… 9
2.2 Оценка производительности идеальногоконвейера. 10
2.3 Конфликты в конвейере и способы минимизацииих влияния на производительность процессора. 13
3 Суперскалярныеархитектуры… 18
3.1 Работа суперскалярного конвейера. 18
3.2 Трудности реализации. 21
3.3 Историческая справка. 22
4 VLIW-архитектура. 25
4.1 Аппаратно-программный комплекс VLIW… 25
4.2 Устройство VLIW-процессора. 26
4.3 Принцип действия VLIW-компилятора. 27
4.4 Трудности реализации VLIW… 28
5 Предсказание переходов. 30
6 Матричные процессоры… 35
6.1 Матричные процессоры… 35
6.2 Векторный процессор. 36
6.3 Внутрипроцессорная многопоточность. 37
6.4 Многопоточность в Pentium 4. 39
7 Закон Амдала. ЗаконГустафсона. 42
7.1 Ускорение, эффективность, загрузка икачество. 42
7.2 Закон Амдала. 44
7.3 Закон Густафсона. 47
вывод. 49
список литературы… 50
введение
Спрос на компьютеры, работающие с все болееи более высокой скоростью, не прекращается. Астрономы пытаются воспроизвестивсю историю Вселенной с момента большого взрыва и до сегодняшнего дня.Фармацевты хотели бы разрабатывать новые лекарственные препараты с помощьюкомпьютеров, не принося в жертву легионы крыс. Разработчики летательныхаппаратов могли бы получать лучшие результаты, если бы вместо строительстваогромных аэродинамических труб моделировали свои конструкции на компьютере. Какимибы мощными ни были компьютеры, их возможностей никогда не хватит для решениямногих нетривиальных задач (особенно научных, технических и промышленных).
Быстродействие процессоров растет, но у нихпостоянно возникают проблемы со скоростью передачи информации, посколькускорость распространения электромагнитных волн в медных проводах и света воптико-волоконных кабелях прежнему остается равной 20 см/нс, независимо оттого, насколько умны инженеры компании Intel. Кроме того, чем быстрее работаетпроцессор, тем сильнее он нагревается, поэтому возникает задача защиты его отперегрева.
Разработчики компьютеров стремятся к тому,чтобы повысить производительность своих машин. Один из способов заставить процессорыработать быстрее — повышение их тактовой частоты, однако при этом существуюттехнологические ограничения. Поэтому большинство разработчиков для повышенияпроизводительности при данной тактовой частоте процессора используютпараллелизм (выполнение двух или более операций одновременно).
Существует две основные формы параллелизма:параллелизм на уровне команд и параллелизм на уровне процессоров. В первомслучае параллелизм реализуется за счет запуска большого количества командкаждую секунду. Во втором случае над одним заданием работают одновременнонесколько процессоров. Каждый подход имеет свои преимущества.
Параллелизм можно вводить на разныхуровнях. На самом низком уровне он может быть реализован в процессоре за счетконвейеризации и суперскалярной архитектуры с несколькими функциональнымиблоками.
На следующем уровне возможно внедрение всистему внешних плат ЦП с улучшенными вычислительными возможностями. Какправило, в подключаемых процессорах реализуются специальные функции, такие какобработка сетевых пакетов, обработка мультимедийных данных, криптография.Производительность специализированных приложений за счет этих функций можетбыть повышена в 5-10 раз.
Чтобы повысить производительность в сто,тысячу или миллион раз, необходимо свести воедино многочисленные процессоры иобеспечить их эффективное взаимодействие. Этот принцип реализуется в видебольших мультипроцессорных систем и мультикомпьютеров (кластерных компьютеров).Естественно, объединение тысяч процессоров в единую систему порождает новыепроблемы, которые нужно решать.
Наконец, в последнее время появиласьвозможность интеграции через Интернет целых организаций. В результатеформируются слабо связанные распределенные вычислительные сетки, или решетки.Такие системы только начинают развиваться, но их потенциал весьма высок.
Когда два процессора или обрабатывающихэлемента находятся рядом и обмениваются большими объемами данных с небольшимизадержками, они называются сильно связанными (tightly coupled). Соответственно,когда два процессора или обрабатывающих элемента располагаются далеко друг отдруга и обмениваются небольшими объемами данных с большими задержками, ониназываются слабо связанными (loosely coupled). [2]
1 Классификация параллельных ВС
 
1.1 Классификация Флинна
Даже краткое перечисление типов современныхпараллельных вычислительных систем (ВС) дает понять, что для ориентирования вэтом многообразии необходима четкая система классификации. От ответа на главныйвопрос — что заложить в основу классификации — зависит, насколько конкретнаясистема классификации помогает разобраться с тем, что представляет собойархитектура ВС и насколько успешно данная архитектура позволяет решатьопределенный круг задач.
Общепринята удачная классификация ВС,которую предложил в 1970 г. Г. Флин (США). Основным определяющим архитектурнымпараметром он выбрал взаимодействие потока команд и потока данных (операндов ирезультатов).
ОКОД — «один поток команд — один потокданных» (SISD — «Single Instruction, Single Data»). В ЭВМ классическойархитектуры ведется последовательная обработка команд и данных. Командыпоступают одна за другой (за исключением точек ветвления программы), и для нихиз ОЗУ или регистров также последовательно поступают операнды. Одной команде(операции) соответствует один необходимый ей набор операндов. Представителямиэтого класса являются, прежде всего, классические фоннеймановские ВМ. То, чтодля увеличения скорости обработки команд и скорости выполнения арифметическихопераций может применяться конвейерная обработка, не имеет значения, поэтому вкласс SISD од­новременно попадают как ВМ CDC 6600 со скалярными функциональными устройствами, так и CDC 7600 с конвейерными. Некоторые специалисты считают, что кSISD-системам можно причислить и векторно-конвейерныеВС, если рассматривать вектор как неделимый элемент данных для соответствующейкоманды.
Тип ОКМД— «один поток команд — много потоков данных» (SIMD — «Single Instruction — Multiple Data») охватывает ВС, в которыходной ко­мандой обрабатывается набор данных, множество данных, вектор, и вы­рабатываетсямножество результатов. Это векторные и матричные системы, в которых по однойкоманде выполняется одна и та же операция над всеми элементами массива —вектора или матрицы, распределенными между процессорными (обрабатывающими)элементами ПЭ или процессо­рами. Принцип обработки показан на рисунке 1.2.
Отечественные векторные ВС — ПС-2000, ПС-2100. Допускаюторганизацию матричной обработки. Классический пример матричной архитектуры — ILLIAC-IV (США).
К типу МКОД — «много потоков команд — один поток данных»(MISD — «Multiple Instruction — Single Data») принято относить векторныйконвейер (обычно в составе ВС, чтобы подчеркнуть основной используемый принципвычислений), например, в составе ВС Сгеу-1, «Электроника ССБИС». На векторномконвейере производится последовательная обработка одного потока данных многимиобрабатывающими устройствами (ступенями, станциями) конвейера.
К такому же типу относится ВС, реализующая макроконвейер(ВС «Украина»). В ней задача, решаемая циклически, «разрезается» напоследовательные этапы, закрепляемые за отдельными процессорами. Запускаетсяконвейер многократного выполнения цикла, составляющего задачу.
Тип МКМД — «много потоков команд — много потоков данных»(MIMD — «Multiple Instruction — Multiple Data»). Класс предполагает на­личиев вычислительной системе множества устройств обработки команд, объединенных вединый комплекс и работающих каждое со своим потоком команд и данных. Класс MIMD чрезвычайно широк, поскольку включает в себявсевозможные мультипроцессорные системы. Кроме того, приобщение к классу MIMD зависит от трактовки. Так, ранее упоминавшиесявекторно-конвейерные ВС можно вполне отнести и к классу MIMD,если конвейерную обработку рассматривать как выполнение множества команд(операций ступеней конвейера) над множественным скалярным потоком.
Схема классификации Флинна вплоть до настоящего времениявляется наиболее распространенной при первоначальной оценке той или иной ВС,поскольку позволяет сразу оценить базовый принцип работы системы, чего частобывает достаточно. Однако у классификации Флинна имеются и очевидныенедостатки, например неспособность однозначно отнести некоторые архитектуры ктому или иному классу. Другая слабость — это чрезмерная насыщенность класса MIMD. Все это породило множественные попытки либомодифицировать классификацию Флинна, либо предложить иную системуклассификации.
 
1.2 Системы с общей и распределенной памятью
Системы с общей (разделяемой) оперативной памятью образуютсо­временный класс ВС — многопроцессорных супер-ЭВМ. Одинаковый доступ всехпроцессоров к программам и данным представляет широкие возможности организациипараллельного вычислительного процесса (параллельных вычислений). Отсутствуют потериреальной производи­тельности на межпроцессорный (между задачами, процессами ит. д.) обмен данными).
Системы с распределенной памятью образуют вычислительныеком­плексы (ВК) — коллективы ЭВМ с межмашинным обменом для совместного решениязадач (рис. 1.5б). В ВК объединяются вычислительные средства систем управления,решающие специальные наборы задач, взаимосвязанных по данным. Принято говорить,что такие ВК выполняют распределенные вычисления, а сами ВК называют распределеннымиВК.
Другое, противоположное воплощение принципа МИМД — масспроцессорныеили высокопараллельные архитектуры, объединяющие сотни — тысячи — десятки тысячпроцессоров.
В современных супер-ЭВМ наметилась тенденция объединениядвух принципов: общей (распределяемой) и распределенной (локальной) оперативнойпамяти (ЛОП). Такая структура используется в проекте МВК «Эльбрус-3» и«Эльбрус-ЗМ».
/>/>2 Конвейеры операций
 
2.1 Конвейеры
Уже много лет известно, что главнымпрепятствием высокой скорости выполнения команд является необходимость ихвызова из памяти. Для разрешения этой проблемы можно вызывать команды из памятизаранее и хранить в специальном наборе регистров. Эта идея использовалась еще в1959 году при разработке компьютера Stretch компании IBM, а набор регистров былназван буфером выборки с упреждением. Таким образом, когда требоваласьопределенная команда, она вызывалась прямо из буфера, а обращения к памяти непроисходило.
В действительности при выборке супреждением команда обрабатывается за два шага: сначала происходит вызовкоманды, а затем — ее выполнение. Еще больше продвинула эту стратегию идеяконвейера. При использовании конвейера команда обрабатывается уже не за два, аза большее количество шагов, каждый из которых реализуется определеннымаппаратным компонентом, причем все эти компоненты могут работать параллельно.
На рисунке 2.1 а) изображен конвейер изпяти блоков, которые называются ступенями. Первая ступень (блок С1) вызываеткоманду из памяти и помещает ее в буфер, где она хранится до тех пор, пока непотребуется. Вторая ступень (блок С2) декодирует эту команду, определяя ее типи тип ее операндов. Третья ступень (блок СЗ) определяет местонахождениеоперандов и вызывает их из регистров или из памяти. Четвертая ступень (блок С4)выполняет команду, и, наконец, блок С5 записывает результат обратно в нужныйрегистр.
Чтобы лучше понять принципы работыконвейера, рассмотрим аналогичный пример. Представим себе кондитерскую фабрику,на которой выпечка тортов и их упаковка для отправки производятся раздельно.Предположим, что в отделе отправки находится длинный конвейер, вдоль которогорасполагаются 5 рабочих (или ступеней обработки). Каждые 10 секунд (это времяцикла) первый рабочий ставит пустую коробку для торта на ленту конвейера. Этакоробка отправляется ко второму рабочему, который кладет в нее торт. Послеэтого коробка с тортом доставляется третьему рабочему, который закрывает изапечатывает ее. Затем она поступает к четвертому рабочему, который ставит на нейштамп. Наконец, пятый рабочий снимает коробку с конвейерной ленты и помещает еев большой контейнер для отправки в супермаркет. Примерно таким же образомдействует компьютерный конвейер: каждая команда (в случае с кондитерскойфабрикой — торт) перед окончательным выполнением проходит несколько ступенейобработки.
Возвратимся к нашему конвейеру на рисунке2.1. Предположим, что время цикла у этой машины — 2 нс. Тогда для того, чтобыодна команда прошла через весь конвейер, требуется 10 нс. На первый взглядможет показаться, что такой компьютер будет выполнять 100 млн команд в секунду,в действительности же скорость его работы гораздо выше. В течение каждого цикла(2 нс) завершается выполнение одной новой команды, поэтому машина выполняет не100, а 500 млн команд в секунду! [2]
 
2.2 Оценка производительности идеального конвейера
Пусть задана операция, выполнение которойразбито на n последо­вательных этапов. Пусть ti — время выполнения i-го этапа. Припоследо­вательном их выполнении операция выполняется за время
/>
а быстродействие ЭВМ или одного процессораВС, выполняющего только эту операцию, составит
/>
Выберем время такта — величину tT = max{ti}и потребуем при раз­биении на этапы, чтобы для любого i = 1,..., n выполнялосьусловие ti + t(i+1) mod n= tT. То есть чтобы никакие двапоследовательных этапа (включая конец и новое начало операции) не могли бытьвыполнены за время одного такта.
Максимальное быстродействие процессора приполной загрузке конвейера составляет
/>
Число n — количество уровней конвейера, или глубина перекрытия, таккак каждый такт на конвейере параллельно выполняются n операций. Чем больше число уровней (станций), тем большийвыигрыш в быстродействии может быть получен.
Известна оценка
/>
то есть выигрыш в быстродействии получаетсяот /> до n раз.
Реальный выигрыш в быстродействииоказывается всегда меньше, чем указанный выше, поскольку:
1) некоторые операции, например, надцелыми, могут выполняться за меньшее количество этапов, чем другиеарифметические операции. Тогда отдельные станции конвейера будут простаивать.
2)  при выполнении некоторых операций наопределённых этапах могут требоваться результаты более поздних, ещё невыполненных эта­пов предыдущих операций. Приходится приостанавливать конвейер.
3) поток команд порождает недостаточноеколичество операций для полной загрузки конвейера [3].
Рассмотрим принципы конвейерной обработкиинформации на примере пятиступенчатого конвейера, вкотором выполнение команды складывается из следующих этапов:
IF (InstructionFetch) — считывание команды в процессор;
ID (Instruction Decoding) — декодирование команды;
OR (OperandReading) — считывание операндов;
EX (Executing)- выполнение команды;
WB (Write Back)- запись результата.
Выполнение команд в таком конвейере представлено в таблице 2.1.
Так как в каждом тактемогут выполняться различные стадии обработки команд, то длительность такта выбирается исходя из максимального временивыполнения всех стадий. Кроме того, следует учитывать, что для передачи командыс одной стадии на другую требуется определенное дополнительное время (Дt),связанное с записью промежуточных результатов обработки в буферные регистры.
/>Таблица 2.1 Команда Такт 1 2 3 4 5 6 7 8 9 i IF ID OR EX WB i+1 IF ID OR EX WB i+2 IF ID OR EX WB i+3 IF ID OR EX WB i+4 IF ID OR EX WB
Пусть для выполнения отдельных стадийобработки требуются следующие затраты времени (в некоторых условных единицах):
TIF =20, TID = 15, TOR = 20, TEX = 25, TWB = 20.
Тогда, предполагая, что дополнительныерасходы времени составляют Дt = 5 единиц, получим время такта:
T =max {TIF, TID, TOR, TEX, TWB} + Дt = 30.
Оценим время выполнения одной команды инекоторой группы команд при последовательной и конвейерной обработке.
При последовательной обработке времявыполнения N команд составит:
Tпосл = N*(TIF + TID + TOR + TEX + TWB) = 100N.
Анализ таблицы 2.1 показывает, что при конвейернойобработке после того, как получен результат выполнения первой команды,результат очередной команды появляется в следующем тактеработы процессора. Следовательно,
Tконв = 5T + (N-1) *T.
Примеры длительности выполнения некоторогоколичества команд при последовательной и конвейерной обработке приведены втаблица 2.2.
/>Таблица 2.2 Количество команд Время при последовательном выполнении при конвейерном выполнении 1 100 150 2 200 240 10 1000 420 100 10000 3120
Очевидно, что при достаточно длительнойработе конвейера его быстродействие будетсущественно превышать быстродействие, достигаемое при последовательнойобработке команд. Это увеличение будет тем больше, чем меньше длительность такта конвейера и чем большеколичество выполненных команд. Сокращение длительности тактадостигается, в частности, разбиением выполнения команды на большое числоэтапов, каждый из которых включает в себя относительно простые операции ипоэтому может выполняться за короткий промежуток времени. Так, если впроцессоре Pentium длина конвейера составляла 5ступеней (при максимальной тактовой частоте 200 МГц), то в Pentium-4 — уже 20ступеней (при максимальной тактовой частоте на сегодняшний день 3,4 ГГц).
 
2.3 Конфликты в конвейере и способы минимизации их влияния напроизводительность процессора
Значительное преимущество конвейернойобработки перед последовательной имеет место в идеальномконвейере, в котором отсутствуют конфликты и все команды выполняютсядруг за другом без перезагрузки конвейера. Наличиеконфликтов снижает реальную производительность конвейерапо сравнению с идеальным случаем.
Конфликты — это такие ситуации вконвейерной обработке, которые препятствуют выполнению очередной команды впредназначенном для нее такте.
Конфликты делятся на три группы:
-     структурные,
-     по управлению,
-     по данным.
/>Структурные конфликты возникают в том случае, когдааппаратные средства процессора не могут поддерживать все возможные комбинациикоманд в режиме одновременного выполнения с совмещением.
Причины структурныхконфликтов.
1. Не полностью конвейерная структурапроцессора, при которой некоторые ступени отдельных команд выполняются болееодного такта.
Пусть этап выполнения команды i+1 занимает 3 такта. Тогдадиаграмма работы конвейера будет иметь вид,представленный в таблица 2.3.
/>Таблица 2.3 Команда Такт 1 2 3 4 5 6 7 8 9 i IF ID OR EX WB i+1 IF ID OR EX EX EX WB i+2 IF ID OR O O EX WB i+3 IF ID OR O O EX i+4 IF ID OR O O
При этом в работе конвейеравозникают так называемые «пузыри» (обработка команд i+2 и следующих за ней, начиная с такта6), которые снижают производительность процессора.
Эту ситуацию можно было бы ликвидироватьдвумя способами. Первый предполагает увеличение времени тактадо такой величины, которая позволила бы все этапы любой команды выполнять заодин такт. Однако при этом существенно снижаетсяэффект конвейерной обработки, так как все этапы всех команд будут выполнятьсязначительно дольше, в то время как обычно нескольких тактовтребует выполнение лишь отдельных этапов очень небольшого количества команд.Второй способ предполагает использование таких аппаратных решений, которыепозволили бы значительно снизить затраты времени на выполнение данного этапа(например, использовать матричные схемы умножения). Но это приведет кусложнению схемы процессора и невозможности реализации на этой БИС другихфункционально более важных узлов. Так как представленная в таблице 2.3 ситуациявозникает при реализации команд, относительно редко встречающихся в программе,то обычно разработчики процессоров ищут компромисс между увеличениемдлительности такта и усложнением того или иногоустройства процессора.
2. Недостаточное дублирование некоторыхресурсов.
Одним из типичных примеров служит конфликтиз-за доступа к запоминающим устройствам. Из таблицы 2.1 видно, что в случае,когда операнды и команды находятся в одном запоминающем устройстве, начиная с такта 3, работу конвейерапридется постоянно приостанавливать, поскольку различные команды в одном и томже такте обращаются к памяти на считывание команды,выборку операнда, запись результата.
Борьба с конфликтами такого рода проводитсяпутем увеличения количества однотипных функциональных устройств, которые могутодновременно выполнять одни и те же или схожие функции. Например, обычноразделяют кэш-память для хранения команд и кэш-память данных, а такжеиспользуют многопортовую схему доступа к регистровой памяти, при которой крегистрам можно одновременно обращаться по одному каналу для записи, а подругому — для считывания информации. Конфликты из-за исполнительных устройствобычно сглаживаются введением в состав процессора дополнительных блоков.
В суперскалярных процессорах реализованаконвейерная обработка и параллельное выполнение команд. Несколько командодновременно могут выполниться в течение одного такта. В таблице 2.4представлена последовательность выполнения команд в процессоре, имеющем два конвейера, при условии, что команде К1 требуется 3 такта на этапе EX.
/>Таблица 2.4 Этап Такт 1 2 3 4 5 6 7 IF K1 K2 K3 K4 K5 K6 K7 K8 K7 K9 K7 K10 K11 K12 ID K1 K2 K3 K4 K5 K6 K5 K8 K5 K9 K7 K10 OR K1 K2 K3 K4 K3 K6 K3 K8 K5 K9 EX K1 K2 K1 K4 K1 K6 K3 K8 WB K2 K4 K1 K6
При этом команды будут завершаться впоследовательности К2-К4-К1-К6-...
Следовательно, может нарушиться исходныйпорядок завершения команд программы. Недостатком суперскалярных процессоровявляется необходимость синхронного продвижения команд в каждом из конвейеров. При возникновении затора в одном из конвейеров должны приостанавливать свою работу и другие. Нотакие приостановки существенно снижают быстродействие процессора. Разрешениеэтой ситуации состоит в том, чтобы дать возможность выполняться командам водном конвейере вне зависимости от ситуации в другихконвейерах. Это приводит к неупорядоченномувыполнению команд. При этом команды, стоящие в программе позже, могутзавершиться ранее команд, стоящих впереди. Аппаратные средства процессора должныгарантировать, что результаты выполненных команд будут записаны в приемник втом порядке, в котором команды записаны в программе. Для этого в процессоререзультаты этапа выполнения команды обычно сохраняются в специальном буферевосстановления последовательности команд. Запись результата очередной командыиз этого буфера в приемник результата проводится лишь после того, как выполненывсе предшествующие команды и записаны их результаты.
Конфликты по управлениювозникают при конвейеризации команд переходов и других команд, изменяющихзначение счетчика команд.
Суть конфликтов этой группы наиболее удобнопроиллюстрировать на примере команд условного перехода. Пусть в программе,представленной в таблице 2.1, команда i+1 являетсякомандой условного перехода, формирующей адрес следующей команды в зависимостиот результата выполнения команды i. Команда i завершит свое выполнение в такте5. В то же время команда условного перехода уже в такте3 должна прочитать необходимые ей признаки, чтобы правильно сформировать адресследующей команды. Если конвейер имеет большуюглубину (например, 20 ступеней), то промежуток времени между формированиемпризнака результата и тактом, где он анализируется,может быть еще большим. В инженерных задачах примерно каждая шестая команда являетсякомандой условного перехода, поэтому приостановки конвейера при выполнениикоманд переходов до определения истинного направления перехода существенноскажутся на производительности процессора.
Наиболее эффективным методом сниженияпотерь от конфликтов по управлению служитпредсказание переходов. Суть данного метода заключается в том, что привыполнении команды условного перехода специальный блок процессора определяетнаиболее вероятное направление перехода, не дожидаясь формирования признаков,на основании анализа которых этот переход реализуется. Процессор начинаетвыбирать из памяти и выполнять команды по предсказанной ветви программы (такназываемое исполнение по предположению, или «спекулятивное»исполнение). Однако так как направление перехода может быть предсказаноневерно, то получаемые результаты с целью обеспечения возможности иханнулирования не записываются в память или регистры (то есть для них невыполняется этап WB), а накапливаются в специальномбуфере результатов.
В современных процессорах вероятностьправильного предсказания направления переходов достигает 90% [6,11].
Конфликты по даннымвозникают в случаях, когда выполнение одной команды зависит от результатавыполнения предыдущей команды. При обсуждении этих конфликтов будем предполагать,что команда i предшествует команде j[11].
Все виды зависимостей по данным могут бытьклассифицированы по типу ассо­циаций: RAR — «чтениепосле чтения», WAR — «запись после чтения» и WAW — «запись после записи», RAW —«чтение после записи».
Некоторые из зависимостей по данным могутбыть устранены. RAR, по сути дела, соответствуетотсутствию зависимости, поскольку в данном случае порядок выполнения команд неимеет значения. Действительной зависимостью является только «чтение послезаписи» (RAW), так как необходимо прочитатьпредварительно записанные новые данные, а не старые.
Лишние зависимости по данным появляются врезультате «записи после чтения» (WAR) и «записи послезаписи» (WAW). Лишние зависимости появляются понескольким при­чинам: не оптимизированный программный код, ограничениеколичества регистров, стремление к экономии памяти, наличие программных циклов.Важно отметить, что запись может быть произведена в любой свободный ресурс, ане только тот, который указан в программе[1].
1. Конфликты типа RAW(Read After Write): команда j пытается прочитатьоперанд прежде, чем команда i запишет на это местосвой результат. При этом команда j может получитьнекорректное старое значение операнда.
Проиллюстрируем этот тип конфликта напримере выполнения команд, представленных в таблице 2.1. Пусть выполняемыекоманды имеют следующий вид:
i
ADD R1,R2  
R1 = R1+R2
i+1=j 
SUB R3,R1
R3 = R3-R1
Команда iизменит состояние регистра R1 в такте 5. Но команда i+1 должнапрочитать значение операнда R1 в такте 4. Если не приняты специальные меры, то из регистра R1 будет прочитано значение, которое было в нем довыполнения команды i.
Уменьшение влияния конфликта типа RAW обеспечивается методом обхода (продвижения) данных. Вэтом случае результаты, полученные на выходах исполнительных устройств, помимовходов приемника результата передаются также на входы всех исполнительныхустройств процессора. Если устройство управления обнаруживает, что данныйрезультат требуется одной из последующих команд в качестве операнда, то онсразу же, параллельно с записью в приемник результата, передается на входисполнительного устройства для использования следующей командой.
Конфликты типа RAWобусловлены именно конвейерной организацией обработки команд.
Главной причиной двух других типов конфликтов по данным является возможность неупорядоченноговыполнения команд в современных роцессорах, то есть выполнение команд не в томпорядке, в котором они записаны в программе.
2. Конфликты типа WAR(Write After Read): команда j пытается записать результатв приемник, прежде чем он считается оттуда командой i,При этом команда i может получить некорректноеновое значение операнда:      
Этот конфликт возникнет в случае, есликоманда j вследствие неупорядоченного выполнениязавершится раньше, чем команда i прочитает староесодержимое регистра R2.
3. Конфликты типа WAW(Write After Write): команда j пытается записатьрезультат в приемник, прежде чем в этот же приемник будет записан результатвыполнения команды i, то есть запись заканчиваетсяв неверном порядке, оставляя в приемнике результата значение, записанноекомандой i:
Устранение конфликтовпо данным типов WAR и WAWдостигается путем отказа от неупорядоченного исполнения команд, но чаще всегопутем введения буфера восстановления последовательности команд.
Как отмечалось выше, наличие конфликтовприводит к значительному снижению производительности процессора. Определенныетипы конфликтов требуют приостановки конвейера. Приэтом останавливается выполнение всех команд, находящихся на различных стадияхобработки. Другие конфликты при неверном предсказанном направлении перехода,ведут к необходимости полной перезагрузки конвейера.Потери будут тем больше, чем более длинный конвейериспользуется в процессоре. Такая ситуация явилась одной из причин сокращениячисла ступеней в процессорах последних моделей [11].
3 Суперскалярные архитектуры
 
3.1 Работа суперскалярного конвейера
Одна из возможных схем процессора с двумяконвейерами показана на рисунке 3.1. В ее основе лежит конвейер, изображенныйна рисунке 2.1. Здесь общий блок выборки команд вызывает из памяти сразу по двекоманды и помещает каждую из них в один из конвейеров. Каждый конвейер содержитАЛУ для параллельных операций. Чтобы выполняться параллельно, две команды недолжны конфликтовать из-за ресурсов (например, регистров), и ни одна из них недолжна зависеть от результата выполнения другой. Как и в случае с однимконвейером, либо компилятор должен гарантировать отсутствие нештатных ситуаций(когда, например, аппаратура не обеспечивает проверку команд на несовместимостьи при обработке таких команд выдает некорректный результат), либо за счетдополнительной аппаратуры конфликты должны выявляться и устранятьсянепосредственно в ходе выполнения команд.
Сначала конвейеры (как сдвоенные, так иобычные) использовались только в RISC-компьютерах. У процессора 386 и егопредшественников их не было. Конвейеры в процессорах компании Intel появились,только начиная с модели 486. Процессор 486 имел один пятиступенчатый конвейер,a Pentium — два таких конвейера. Похожая схема изображена на рисунке 3.1, норазделение функций между второй и третьей ступенями (они назывались декодер 1 идекодер 2) было другим. Главный конвейер (u-конвейер) мог выполнять произвольныекоманды. Второй конвейер (v-конвейер) мог выполнять только простые команды сцелыми числами, а также одну простую команду с плавающей точкой (FXCH) [2,5].
Имеются сложные правила определения,является ли пара команд совместимой в отношении возможности параллельноговыполнения. Если команды, входящие в пару, были сложными или несовместимыми,выполнялась только одна из них (в u-конвейере). Оставшаяся вторая командасоставляла затем пару со следующей командой. Команды всегда выполнялись попорядку. Таким образом, процессор Pentium содержал особые компиляторы, которыеобъединяли совместимые команды в пары и могли порождать программы,выполняющиеся быстрее, чем в предыдущих версиях. Измерения показали, чтопрограммы, в которых применяются операции с целыми числами, при той же тактовойчастоте на Pentium выполняются почти в два раза быстрее, чем на 486. Вне всякихсомнений, преимущество в скорости было достигнуто благодаря второму конвейеру.
Стоит отметить, что переход к четыремконвейерам возможен, но требует громоздкого аппаратного обеспечения. Вместоэтого используется другой подход. Основная идея — один конвейер с большимколичеством функциональных блоков, как показано на рисунке 3.2. Pentium II, кпримеру, имеет сходную структуру. В 1987 году для обозначения этого подхода былвведен термин суперскалярная архитектура. Однако подобная идея нашла воплощениееще тридцатью годами ранее в компьютере CDC 6600. Этот компьютер вызывалкоманду из памяти каждые 100 не и помещал ее в один из 10 функциональных блоковдля параллельного выполнения. Пока команды выполнялись, центральный процессорвызывал следующую команду.
Со временем значение понятия«суперскалярный» несколько изменилось. Теперь суперскалярныминазывают процессоры, способные запускать несколько команд зачастую от четырехдо шести) за один тактовый цикл. Естественно, чтобы передавать все эти команды,в суперскалярном процессоре должно быть несколько функциональных блоков.Поскольку в процессорах этого типа, как правило, предусматривается одинконвейер, его устройство обычно соответствует рисунку 3.2.
В свете такой терминологической динамики насегодняшний день можно утверждать, что компьютер 6600 не был суперскалярным стехнической точки зрения — ведь за один тактовый цикл в нем запускалось небольше одной команды. Однако при этом был достигнут аналогичный результат — команды запускались быстрее, чем выполнялись. На самом деле разница впроизводительности между ЦП с циклом в 100 не, передающим за этот период поодной команде четырем функциональным блокам, и ЦП с циклом в 400 не,запускающим за это время четыре команды, трудноуловима. В обоих процессорахсоблюдается принцип превышения скорости запуска над скоростью управления; приэтом рабочая нагрузка распределяется между несколькими функциональными блоками.
Отметим, что на выходе ступени 3 командыпоявляются значительно быстрее, чем ступень 4 способна их обрабатывать. Если бына выходе ступени 3 команды появлялись каждые 10 не, а все функциональные блокиделали свою работу также за 10 не, то на ступени 4 всегда функционировал бытолько один блок, что сделало бы саму идею конвейера бессмысленной. Как видноиз рисунка 3.2, на ступени 4 может быть несколько АЛУ.
Суперскалярные процессоры имеют:  
-     многоуровневую иерархическую память, включая до трех уровнейкэш-памя­ти;
-     раздельные кэш-памяти команд и данных;
-     устройство выборки команд, обеспечивающее выборку на исполнениесово­купности команд;
-     таблицы предсказания переходов;
-     переименование регистров;
-     поддержку внеочередного исполнения команд;
-     набор функциональных устройств для преобразования данных вформатах с фиксированной и плавающей точкой.
Суперскалярные машины используютпараллелизм на уровне команд путем посылки нескольких команд из обычного потокакоманд в несколько функциональных устройств. Дополнительно, чтобы снятьограничения последовательного выполнения команд, эти машины используютмеханизмы внеочередной выдачи и внеочередного завершения команд,прогнозирование переходов, кэши целевых адресов переходов и условное (попредположению) выполнение команд. Возросшая сложность, реализуемая этимимеханизмами, создает также проблемы реализации точного прерывания.
В типичной суперскалярной машине аппаратураможет осуществлять выдачу от одной до шести команд в одном такте. Обычно этикоманды должны быть независимыми и удовлетворять некоторым ограничениям,например таким, что в каждом такте не может выдаваться более одной командыобращения к памяти. Если какая-либо команда в потоке команд является логическизависимой или не удовлетворяет критериям выдачи, на выполнение будут выданытолько команды, предшествующие данной. Поэтому скорость выдачи команд всуперскалярных машинах является переменной. Это отличает их от VLIW-машин, вкоторых полную ответственность за формирование пакета команд, которые могутвыдаваться одновременно, несет компилятор, а аппаратура в динамике не принимаетникаких решений относительно выдачи нескольких команд.
Предположим, что машина может выдавать навыполнение две команды в одном такте. Одной из таких команд может быть командазагрузки регистров из памяти, записи регистров в память, команда переходов,операции целочисленного АЛУ, а другой может быть любая операция плавающей точки(ПТ). Параллельная выдача целочисленной операции и операции с плавающей точкойнамного проще, чем выдача двух произвольных команд. В реальных системах(например, в процессорах PA7100, hyperSPARC, Pentium и др.) применяется именнотакой подход. В более мощных процессорах (например, MIPS R10000, UltraSPARC,PowerPC 620 и др.) реализована выдача до четырех команд в одном такте.
Выдача двух команд в каждом такте требуетодновременной выборки и декодирования по крайней мере 64 бит. Чтобы упроститьдекодирование можно потребовать, чтобы команды располагались в памяти парами ибыли выровнены по 64-битовым границам. В противном случае необходимоанализировать команды в процессе выборки и, возможно, менять их местами вмомент пересылки в целочисленное устройство и в устройство ПТ. При этомвозникают дополнительные требования к схемам обнаружения конфликтов. В любомслучае вторая команда может выдаваться, только если может быть выдана навыполнение первая команда. Аппаратура принимает такие решения в динамике,обеспечивая выдачу только первой команды, если условия для одновременной выдачидвух команд не соблюдаются. В таблице 3.1 представлена диаграмма работыподобного конвейера в идеальном случае, когда в каждом такте на выполнениевыдается пара команд.
Такой конвейер позволяет существенноувеличить скорость выдачи команд. Однако чтобы он смог так работать, необходимоиметь либо полностью конвейеризованные устройства плавающей точки, либосоответствующее число независимых функциональных устройств. В противном случаеустройство плавающей точки станет узким горлом и эффект, достигнутый за счетвыдачи в каждом такте пары команд, сведется к минимуму.
Рассмотрим следующие этапы выполнениякоманды:
-     выборка команды — IF;
-     декодирование команды — ID;
-     выполнение операции — EX;
-     обращение к памяти — MEM;
-     запоминание результата — WB. Тип команды Ступень конвейера Целочисленная команда IF ID EX MEM WB Команда ПТ IF ID EX MEM WB Целочисленная команда IF ID EX MEM WB КомандаПТ IF ID EX MEM WB Целочисленная команда IF ID EX MEM WB Команда ПТ IF ID EX MEM WB Целочисленная команда IF ID EX MEM WB Команда ПТ IF ID EX MEM WB
Таблица 3.1 Работа суперскалярного конвейера
 
3.2 Трудности реализации
При параллельной выдаче двух операций(одной целочисленной команды и одной команды ПТ) потребность в дополнительнойаппаратуре, помимо обычной логики обнаружения конфликтов, минимальна:целочисленные операции и операции ПТ используют разные наборы регистров иразные функциональные устройства. Единственная сложность возникает, только есликоманды представляют собой команды загрузки, записи и пересылки чисел сплавающей точкой. Эти команды создают конфликты по портам регистров ПТ, а такжемогут приводить к новым конфликтам типа RAW, когда операция ПТ, которая моглабы быть выдана в том же такте, является зависимой от первой команды в паре.
Если пара команд состоит из одной командызагрузки с ПТ и одной операции с ПТ, которая от нее зависит, необходимообнаруживать подобный конфликт и блокировать выдачу операции с ПТ. Заисключением этого случая, все другие конфликты естественно могут возникать, каки в обычной машине, обеспечивающей выдачу одной команды в каждом такте. Дляпредотвращения ненужных приостановок могут, правда, потребоватьсядополнительные цепи обхода.
Другой проблемой, которая может ограничитьэффективность суперскалярной обработки, является задержка загрузки данных изпамяти. В нашем примере простого конвейера команды загрузки имели задержку водин такт, что не позволяло следующей команде воспользоваться результатомкоманды загрузки без приостановки. В суперскалярном конвейере результат командызагрузки не может быть использован в том же самом и в следующем такте. Этоозначает, что следующие три команды не могут использовать результат командызагрузки без приостановки. Задержка перехода также становится длиною в трикоманды, поскольку команда перехода должна быть первой в паре команд. Чтобыэффективно использовать параллелизм, доступный на суперскалярной машине, нужныболее сложные методы планирования потока команд, используемые компилятором илиаппаратными средствами, а также более сложные схемы декодирования команд.
В общем случае в суперскалярной системекоманды могут выполняться параллельно и возможно не в порядке, предписанномпрограммой. Если не предпринимать никаких мер, такое неупорядоченное выполнениекоманд и наличие множества функциональных устройств с разными временамивыполнения операций могут приводить к дополнительным трудностям. Например, привыполнении некоторой длинной команды с плавающей точкой (команды деления иливычисления квадратного корня) может возникнуть исключительная ситуация ужепосле того, как завершилось выполнение более быстрой операции, выданной послеэтой длинной команды. Для того, чтобы поддерживать модель точных прерываний,аппаратура должна гарантировать корректное состояние процессора при прерываниидля организации последующего возврата.
Обычно в машинах с неупорядоченнымвыполнением команд предусматриваются дополнительные буферные схемы,гарантирующие завершение выполнения команд в строгом порядке, предписанномпрограммой. Такие схемы представляют собой некоторый буфер «истории»,то есть аппаратную очередь, в которую при выдаче попадают команды и текущиезначения регистров результата этих команд в заданном программой порядке. />
3.3 Историческая справка
В 1993 году корпорация Intel внедрила вмассовое производство параллелизм на уровне команд, выпустив процессор IntelPentium, обладавший способностью декодировать и выполнять командывычислительного потока параллельно. Годом позже специалисты Intel реализовалидвухпроцессорную обработку (два полноценных процессора помещались в два разъемана одной системной плате), создав аппаратную многопоточную среду для серверов ирабочих станций. В 1995 году был представлен процессор Intel Pentium Pro, поддерживавшийэффективное объединение четырех процессоров на одной системной плате, чтопозволило обеспечить более высокую скорость обработки данных в многопоточныхприложениях, ориентированных на серверные платформы и рабочие станции.
Появление в 2002 году технологииHyper-Threading (HT) ознаменовало приход многопоточного параллелизма, то естьвозможности выполнять разные потоки приложений одновременно на одноядерномпроцессоре. Тестирование производительности, проведенное корпорацией Intel,показало, что на процессорах с технологией HT скорость работы некоторыхприложений возрастает в среднем на 30%.
Ныне, взяв курс на многоядерные платформы,корпорация Intel стала лидером в процессе перехода на многопоточные ипараллельные вычисления на массовых ПК, обеспечив обработку данных нанескольких вычислительных ядрах одного процессора.
Большинство приложений, уже сегодняоптимизированных для параллельного исполнения вычислительных потоков, например,программ, поддерживающих технологию Hyper-Threading или предназначенных кисполнению на рабочих станциях или серверах с двухпроцессорной конфигурацией,при выполнении на многоядерном процессоре демонстрируют прекраснуюмасштабируемость производительности. К этой категории относятся мультимедийныеприложения, научные приложения и системы CAD/CAM [7,9].
Первый суперскалярный МП i960 был выпущенфирмой Intel в 1987 году. Затем были разработаны МП SPARC (1987-1989 годы),MIPS (1988-1989 годы), МПi860 (1989 год)и ряд других суперскалярных МП, вчастности:
1.        Процессор Pentium был впервые поставлен фирмой Intel в 1993 году какпродолжение семейства МП 80x86. Цель его создания — получение быстродействияRISC-МП и полная совместимость на уровне двоичных кодов с программнымобеспечением, созданным для всех МП 80x86.
2.        Группа фирм AIM (APPLE + IBM + MOTOROLA) совместно разработали семействоМП POWER PC и выпустили его первый образец МП 661 в 1993 году.
3.        Фирма DEC в 1992 году для создания мощных рабочих станций выпустила МП21064 с тактовой частотой 250 Мгц, а затем более мощный МП — 21164.
4.        В 1994 году фирма MIPS Computer, известная разработкой суперконвейерныхМП, выпустила первый суперскалярный МП MIPS R8000 (MIPS — MicroprocessorWithout Interlocked Pipeline Stages), а затем МП R10000.
5.        В 1994 году фирма Sun Microsystem Inc. в продолжение развития своейсерии SPARC (Scalable Processor Architecture) выпустила мощный МП UltraSPARC.
6.        В 1994-1995 годах фирмой Hewlett-Packard был выпущен МП PA7200 свысокими показателями быстродействия, предполагается к выпуску МП РА8000.
Все указанные МП являются суперскалярными и поэтому характеризуются рядомобщих свойств, в частности:
1.        Формирование группы команд для загрузки конвейеров производитсядинамически в каждом такте. Для этого аппаратно на этапе предвыборки идешифрации производится анализ зависимости по данным смежных команд. Вконвейеры для параллельного исполнения подбираются независимые команды, приэтом допускается изменение порядка выполнения команд.
2.        Все МП используют динамическое прогнозирование ветвлений на основебуфера истории переходов. Иногда используется одновременное выполнениеальтернативных ветвей.
3.        Некоторые МП строятся таким образом, что число физических регистровпревышает число РОН, определенных архитектурно (РРС620, Mips R10000, P6). Этонеобходимо для реализации альтернативных ветвей при переходах и для устранениязависимостей по данным, вызванных недостатком РОН. В процессе выполнения команднеобходимо производить переименование физических регистров, то есть онивыступают в качестве виртуальных.
Большинство указанных МП выпускается в однокристальном исполнении, однаков целях получения более высокого быстродействия для МП PPC 620 использовано 10кристаллов пяти типов, а для МП R8000 — 4 кристалла трех типов.
Архитектура описанных выше суперскалярных МП приобретает традиционныйхарактер, поэтому предпринимаются попытки освоить новые архитектуры. Одной изнаиболее перспективных является разработка МП РА9000, производимая совместнофирмами Hewlett-Packard и Intel. Главная особенность РА9000 состоит в том, чтогенерация набора команд для одного такта полностью переносится в компилятор,что позволяет достичь высокого уровня оптимальности программы и значительноразгрузить кристалл от схем планирования и упаковки. Тем самым совершаетсяпереход к VLIW (Very Long Instruction Word) архитектуре [8,10].
4 VLIW-архитектура
В 1970 г. многие вычислительные системы оснащались дополнительнымивекторными сигнальными процессорами (VSP — Vector Signal Processor),использующими VLIW-подобные длинные инструкции, прошитые в ПЗУ. Эти процессорыприменялись для выполнения быстрого преобразования Фурье (БПФ) и другихвычислительных алгоритмов.
Первыми настоящими VLIW-компьютерами стали мини-суперкомпьютеры,выпущенные в начале 1980 года компаниями MultiFlow, Culler и Cydrome, но они неимели коммерческого успеха. Планировщик вычислений и программная конвейеризациябыли предложены Фишером и Рау (Cydrome). Сегодня это является основойтехнологии VLIW-компилятора.
Первый VLIW-компилятор компании Multi-Flow 7/300 использовал два АЛУ дляцелых чисел, два АЛУ для чисел с плавающей точкой и блок логического ветвления.Все это было собрано на нескольких микросхемах. Его 256-битное слово инструкциисодержало семь 32-битных кодов операций. Модули для обработки целых чисел могливыполнять 2 операции за один такт длиной 130 нс (то есть всего 4 при двух АЛУ),что при обработке целых чисел обеспечивало быстродействие около 30MIPS (MillionInstruction Per Second). Первый VLIW-компьютер Cydrome Cydra-5 использовал 256-битнуюинструкцию и специальный режим, обеспечивающий выполнение инструкций какпоследовательности из шести 40-битных операций. Поэтому его компиляторы моглигенерировать смесь параллельного кода и обычного последовательного. Существуетмнение, что в то время, как эти VLIW-машины использовали несколько микросхем,процессор Intel i860 стал первым VLIW-процессором на одной микросхеме. Приустановке правильной последовательности операций этот процессор в большейстепени зависит от компилятора, нежели от аппаратуры.
Несмотря на то, что архитектура VLIW появилась еще на заре компьютернойиндустрии (Тьюринг разработал VLIW-компьютер еще в 1946 году), она до сих порне имела коммерческого успеха. Однако значительного повышенияпроизводительности и скорости вычислений можно добиться лишь путем переносаинтеллектуальных функций из аппаратного обеспечения в программное (вкомпилятор). В целом успех этого мероприятия будет определяться в основномпрограммными средствами, именно в этом и состоит проблема.
 
4.1 Аппаратно-программный комплекс VLIW
Архитектура VLIW представляет собой одну из последних реализацийконцепции внутреннего параллелизма в процессорах. Их быстродействие можноповысить двумя способами: увеличив либо тактовую частоту, либо количествоопераций, выполняемых за один такт. В первом случае требуется изобретение«быстрых» технологий (например, использование арсенида галлия иликремния на сапфире) и применение таких архитектурных решений, как глубинная конвейеризация(конвейеризация в пределах одного такта, когда в каждый момент временизадействован весь кристалл, а не отдельные его части). Для увеличенияколичества выполняемых за один цикл операций необходимо на одной микросхемеразместить множество функциональных модулей обработки и обеспечить надежноепараллельное исполнение машинных инструкций, что дает возможность включить вработу все модули одновременно. Надежность в таком контексте означает, чторезультаты вычислений будут правильными. Для примера рассмотрим два выражения,которые связаны друг с другом следующим образом: А=В+С и В=D+Е. Значениепеременной А будет разным в зависимости от порядка, в котором вычисляются этивыражения (сначала А, а потом В, или наоборот), но в программе подразумеваетсятолько одно определенное значение.
Планирование порядка вычислений довольно трудная задача, которуюприходится решать при проектировании современного процессора. В суперскалярныхпроцессорах (процессор с двумя и более конвейерами, что позволяет выполнятьболее одной команды за один такт в идеальных условиях) для распознаваниязависимостей между машинными инструкциями применяется специальное довольносложное аппаратное решение (в процессоре Pentium Pro, например, для этогоиспользуется буфер переупорядочивания инструкций). Однако размеры такогоаппаратного планировщика при увеличении количества функциональных модулейобработки возрастают в геометрической прогрессии, что, в конце концов, может«съесть» весь кристалл процессора. Поэтому суперскалярные проекты остановилисьна отметке пять-шесть управляемых за цикл инструкций. При другом подходе можнопередать все планирование программному обеспечению, как это делается вконструкциях с VLIW. «Умный» компилятор должен выискать в программевсе инструкции, которые являются совершенно независимыми, собрать их вместе вочень длинные строки (длинные инструкции) и затем отправить на одновременноеисполнение функциональными модулями, количество которых строго равно количествуопераций в такой длинной инструкции. Очень длинные инструкции обычно имеютразмер от 256 бит до 1024 бит. Размер полей, кодирующих операции для каждогофункционального модуля, в такой метаинструкции намного меньше.
 
4.2 Устройство VLIW-процессора
Процессор VLIW, имеющий такую схему, может выполнять восемь операций заодин такт и работать при аналогичной тактовой частоте на 80-100% быстреесуществующих суперскалярных чипов. Добавочные функциональные блоки могутповысить производительность (за счет уменьшения конфликтов), не слишком усложняячип. Однако это расширение ограничивается физическими возможностями:количеством портов чтения-записи, необходимым для обеспечения одновременногодоступа функциональных блоков к файлу, регистров и взаимосвязей, котороегеометрически растет при увеличении количества функциональных блоков. К тому жекомпилятор должен распараллелить программу до необходимого уровня, чтобыобеспечить загрузку каждому блоку. Процессор выполняет 8 операций за один цикл.
Эта гипотетическая инструкция длиной в 256 бит имеет восемь операционныхполей, каждое из которых выполняет традиционную трехоперандную инструкцию ( ). Каждоеоперационное поле может непосредственно управлять специфическим функциональнымблоком при минимальном декодировании.
Аппаратная реализация VLIW-процессора очень проста: несколько небольшихфункциональных модулей (сложения, умножения, ветвления и т.д.), подключенных кшине процессора, и несколько регистров и блоков кэш-памяти. VLIW-архитектурапредставляет интерес для полупроводниковой промышленности по двум причинам.Первая причина — теперь на кристалле больше места может быть отведено дляблоков обработки, а не, скажем, для блока предсказания переходов. Втораяпричина — VLIW-процессор может быть высокоскоростным, так как предельнаяскорость обработки определяется только внутренними особенностями самихфункциональных модулей.
VLIW изымает  микрокод из процессора и переносит его в компилятор, врезультате чего эмуляция инструкций процессора 8086, таких, как STOS, осуществляетсяочень эффективно, поскольку процессор получает для исполнения уже готовыемакросы. Но вместе с тем это порождает и некоторые трудности, ведь написаниемикрокода — невероятно трудоемкий и длительный процесс. Архитектуре VLIW можетобеспечить жизнеспособность только «умный» компилятор, которыйвозьмет эту работу на себя. Именно это ограничивает использованиевычислительных машин с архитектурой VLIW: пока она нашла свое применение тольков векторных (для научных расчетов) и сигнальных процессорах.
 
4.3 Принцип действия VLIW-компилятора
Вновь вспыхнувший в последнее время интерес к VLIW, как к архитектуре,которую можно использовать для реализации вычислений общего назначения, далсущественный толчок развитию техники компиляции для VLIW. VLIW-компиляторупаковывает группы независимых операций в очень длинные слова инструкций такимспособом, чтобы обеспечить эффективное их исполнение функциональными модулямиза один машинный такт. Компилятор сначала обнаруживает все зависимости междуданными, а затем определяет, как их развязать. Чаще всего это делается путемпереупорядочивания всей программы, разные ее блоки перемещаются с одного местав другое. Этот подход отличается от применяемого в суперскалярном процессоре,который для определения зависимостей использует специальное аппаратное решениепрямо во время выполнения программы (оптимизирующие компиляторы, безусловно,улучшают работу суперскалярного процессора, но не делают его«привязанным» к ним). Большинство суперскалярных процессоров можетобнаружить зависимости и планировать параллельное исполнение только внутрибазовых программных блоков (группа последовательных операторов программы, несодержащих внутри себя останова или логического ветвления, допустимых только вконце).
Для обеспечения большего параллелизма VLIW-компьютеры должны наблюдать заоперациями из разных базовых блоков, чтобы поместить эти операции в одну и туже длинную инструкцию, их «область обзора» должна быть шире, чем усуперскалярных процессоров. Это обеспечивается путем прокладки«маршрута» по всей программе (трассировка). Трассировка — наиболееоптимальный для некоторого набора исходных данных маршрут по программе дляобеспечения правильного результата, гарантирует непересечение этих данных. Тоесть маршрут, который «проходит» по участкам, пригодным дляпараллельного выполнения (эти участки формируются, кроме всего прочего, и путемпереноса кода из других мест программы), после чего остается упаковать этиучастки в длинные инструкции и передать на выполнение. Планировщик вычисленийосуществляет оптимизацию на уровне всей программы, а не ее отдельных базовыхблоков. Для VLIW, так же, как и для RISC, ветвления в программе являются«врагом», препятствующим эффективному ее выполнению: типичный программныйкод (тот, что не используется в научных расчетах) содержит около шестиветвлений на инструкцию. В то время как RISC для прогнозирования ветвленийиспользует аппаратное решение, VLIW оставляет это за компилятором. Компиляториспользует информацию, собранную им путем профилирования программы, хотя убудущих VLIW-процессоров предполагается небольшое аппаратное расширение,обеспечивающее сбор для компилятора статистической информации непосредственново время выполнения программы. Компилятор прогнозирует наиболее подходящиймаршрут и планирует его прохождение, рассматривая его как один большой базовыйблок, а затем повторяет этот процесс для всех других возникших после этогопрограммных веток, и так до самого конца программы. Он также умеет делать прианализе кода и другие «умные шаги», такие, как развертываниепрограммного цикла и IF-преобразование, в процессе которого временно удаляютсявсе логические переходы из секции, подвергающейся трассировке. Там, где RISCможет только просмотреть код вперед на предмет ветвлений, VLIW-компиляторперемещает его с одного места в другое до обнаруженного ветвления (согласнотрассировке), но предусматривает при необходимости возможность отката назад, кпредыдущему программному состоянию. Соответствующее аппаратное обеспечение, добавленноек VLIW-процессору, может оказать определенную поддержку компилятору. Например,операции, имеющие по несколько ветвлений, могут входить в одну длиннуюинструкцию и, следовательно, выполняться за один машинный такт. Поэтомувыполнение условных операций, которые зависят от результатов предыдущих, можетбыть реализовано программным способом, а не аппаратным. Цена, которуюприходится платить за увеличение быстродействия VLIW-процессора, намного меньшестоимости компиляции. Именно поэтому основные расходы приходятся накомпиляторы.
 
4.4 Трудности реализации VLIW
При реализации архитектуры VLIW возникают и другие серьезные проблемы:VLIW-компилятор должен в деталях «знать» внутренние особенностиархитектуры процессора, опускаясь до внутреннего устройства самихфункциональных модулей. Как следствие, при выпуске новой версии VLIW-процессорас большим количеством обрабатывающих модулей (или даже с тем же количеством, нодругим быстродействием) все старое программное обеспечение, скорее всего,потребует полной перекомпиляции. Надо ли было при переходе, скажем, напроцессор 486 избавляться от имеющегося ПО для процессора 386? Конечно, нет, авот при переходе от одного VLIW-процессора к другому придется, и эторазработчик должен учесть при планировании своих затрат — потребуютсядополнительные средства на перекомпиляцию. Сторонники VLIW-архитектуры воправдание предлагают разделить процесс компиляции на две стадии. Всепрограммное обеспечение должно готовиться в аппаратно-независимом формате сиспользованием промежуточного кода, который окончательно транслируется вмашинно-зависимый код только после установки на машине пользователя. Примертакого подхода демонстрирует фонд OSF со своим стандартом ANDF(Architecture-Neutral Distribution Format). Но кросс-платформенное программноеобеспечение пока еще только желаемое, а в действительности разработчики ПО дляПК зачастую весьма инертны по отношению к принятию радикально новых технологий.Другая трудность — это по своей сути статическая природа оптимизации, которуюобеспечивает VLIW-компилятор. Как поведет себя программа, когда столкнется вовремя компиляции с непредусмотренными динамическими ситуациями, такими как,например, ожидание ввода-вывода? Архитектура VLIW возникла в ответ на требованиясо стороны научно-технических организаций, где при вычислениях особеннонеобходимо большое быстродействие процессора, но для объектно-ориентированных иуправляемых по событиям программ она менее подходит, а ведь именно такиепрограммы составляют сейчас большинство в мире ПК. Но и это еще не все: а какможно проверить, что компилятор выполняет такие сложные преобразования надежнои правильно? Пока никак. Вот почему VLIW-компиляторы называют «вещью всебе». Однако решение сложной задачи обеспечения взаимодействияаппаратного и программного обеспечения в архитектуре VLIW требует серьезныхпредварительных исследований.
Таким образом, достоинства VLIWзаключаются в следующем. Во-первых, компилятор может более эффективноисследовать зависимости между командами и выбирать параллельно исполняемыекоманды, чем это делает аппаратура суперскалярного процессора, ограниченнаяразмером окна исполнения.
Во-вторых, VLIW процессор имеетболее простое устройство управления и по­тенциально может иметь более высокуютактовую частоту.
Однако у VLIW процессоров естьсерьезный фактор, снижающий их произво­дительность. Это команды ветвления,зависящие от данных, значения которых ста­новятся известны только в динамикевычислений. Окно исполнения VLIW-процессора не можетбыть очень большим ввиду отсутствия у компилятора информации о зависимостях,формируемых динамически, в процессе выполнения. Этот недостаток препятствуетвозможности переупорядочивания операций в VLIWпроцессор. Кроме того, VLIW реализация требует большогоразмера памяти имен, многовходовых регистровых файлов, большого числаперекрестных связей. Возможен также останов, когда во время выполнения возникласитуация, отличающаяся от состояния в момент генерации плана выполнения(например, во время выполнения произошло неудачное обращение в кэш-память).
5 Предсказание переходов
Команды, помещенные в окно исполнения, могут бытьзависимы по данным. Эти зависимости обусловлены использованием одних и тех жересурсов памяти (регистров, ячеек памяти) в разных командах. Поэтому дляправильного исполнения программы необходимо использование этих ресурсов впредписываемом программой порядке.
Поскольку при суперскалярной обработке необходимоизвлекать из памяти не­сколько команд за один такт для загрузки параллельноработающих функциональных устройств, повышенные требования предъявляются кпропускной способности интерфейса «процессор-память». В современных процессорахприменяются многоуровневые раздельные кэш-памяти данных и команд.
Для уменьшения потерь процессорных тактов, связанных спромахами при обра­щении к кэш-памяти в случае выполнения команд ветвления, всостав системы кэширования вводятся средства предсказания переходов, основноеназначение которых — повысить вероятность наличия в кэшпамяти требуемой команды.
Исполнение условных ветвлений состоит из следующихэтапов:
-       распознавание команды условного ветвления;
-       проверка выполнения условия перехода;
-       вычисление адреса перехода;
-       передача управления в случае перехода.
На каждом этапе используются специальные приемыповышения производи­тельности [1].
1. Для быстрого декодирования применяются либодополнительные биты в поле команды, либо преддекодирование команд при ихвыборке из кэш-памяти команд.
2. Часто, когда команда уже выбрана изкэш-памяти команд, условие перехода еще не вычислено. Чтобы не задерживатьпоток команд, в данном случае используется предсказание перехода по одной изнескольких возможных схем.
Механизм предсказания переходов выполняетдве основные функции — предсказание программного адреса инструкции, на которуюпроизводится переход (для всех инструкций перехода), и предсказание направленияветвления (для инструкций условного перехода). Оба предсказания должны бытьвыполнены заблаговременно — раньше, чем начнётся декодирование и обработкаинструкции перехода — для того, чтобы выборка нового блока инструкций былапроизведена без потерь лишних тактов либо с минимальными потерями.
Необходимость предсказания адреса «целевой»инструкции вызвана тем, что этот адрес может быть извлечён из x86-инструкцииперехода и вычислен только на финальной стадии декодирования, с большойзадержкой. Более того, даже простое выделение инструкций переменной длины изсчитанного блока и поиск среди них инструкций перехода займёт какое-то время.Поэтому в процессорах архитектуры x86 предсказание производят по целому блоку,без разбиения его на составляющие инструкции.
В современных процессорах для предсказанияадреса перехода обычно используют специальную таблицу адресов переходов BTB(Branch Target Buffer). Эта таблица устроена подобно кэшу и содержит адресаинструкций, на которые ранее производились переходы. Например, в процессореP-III таблица BTB имеет размер 512 элементов и организована в виде 128 наборовс ассоциативностью 4. Для адресации набора используются младшие разряды адреса16-байтового блока инструкций. Если в этом блоке есть инструкции перехода, иесли эти инструкции отрабатывали ранее, то алгоритм предсказания может оченьбыстро найти адрес целевой инструкции в таблице BTB и начать считывание блока,содержащего эту инструкцию. Адреса целевых инструкций помещаются в BTB в моментотставки соответствующих инструкций перехода.
В других современных процессорах размертаблицы BTB достигает 2048 элементов (K8) и 4096 элементов (P-4). Организацияданной подсистемы в процессоре K8 несколько отличается от классической иосновывается на предварительной разметке блоков инструкций в так называемыхмассивах селекторов перед помещением их в I-кэш. Эти селекторы привязаны кположению инструкций в I-кэше и при их вытеснении оттуда сохраняются в L2-кэше(в так называемых ECC-битах, предназначающихся для коррекции ошибок). Элементытаблицы BTB также привязаны к положению инструкций в I-кэше и теряются при ихвытеснении. Это несколько снижает эффективность предсказания адресов переходовв процессоре K8.
Для предсказания направления условногоперехода используется другой механизм, основанный на изучении поведенияпереходов в программе в процессе её выполнения (своего рода «сбор статистики»).Этот механизм учитывает как локальное поведение конкретной инструкции перехода(например, «как правило, переходит», «как правило, не переходит»), так иглобальные закономерности («чередуется по определённому закону» и т.п.).История поведения инструкций условного перехода записывается в специальныхструктурах, обычно называемых «таблицами истории переходов» (Branch HistoryTable, BHT). Современные механизмы предсказания переходов обеспечиваютправильное предсказание более чем в 90 процентах случаев.
Перечислим некоторые механизмы,используемые в новом процессоре P8, имеющем наиболее совершенную системупредсказания переходов:
-     сочетание локального и глобального механизмов для предсказания«обычных» инструкций перехода с учётом истории их поведения;
-     статический предсказатель для инструкций, совершающих переход впервый раз, основанный на эмпирических закономерностях (например, «переходназад» обычно предсказывается как совершённый, так как может означать переходпо циклу, а «переход вперёд» — как несовершённый);
-     предсказатель коротких циклов, распознающий такие переходы иопределяющий число итераций цикла (позволяет правильно предсказать моментвыхода из цикла);
-     предсказатель косвенных переходов, определяющий целевые адресадля различных исполнений инструкции перехода (с учётом возможного чередованияэтих адресов);
предсказатель целевых адресов дляинструкций выхода из подпрограммы, использующий небольшой аппаратный стек длязапоминания адресов возврата (Return Address Stack) для эффективной отработкиинструкций Call — Return.
В других процессорах компании Intelиспользуется только часть перечисленных механизмов. Эти механизмысовершенствуются с каждым новым поколением процессоров.
В процессорах AMD K8 и IBM PPC970используются более простые механизмы предсказания обычных переходов, иотсутствуют механизмы предсказания циклов и чередующихся косвенных переходов.
Если после формирования анализируемыхпризнаков оказалось, что направление перехода выбрано верно, все полученныерезультаты переписываются из буфера по месту назначения, а выполнение программыпродолжается в обычном порядке. Если направление перехода предсказано неверно,то буфер результатов очищается. Также очищается и конвейер,содержащий команды, находящиеся на разных этапах обработки, следующие закомандой условного перехода. При этом аннулируются результаты всех ужевыполненных этапов этих команд. Конвейер начинаетзагружаться с первой команды другой ветви программы. Так как конвейернаяобработка эффективна при большом числе последовательно выполненных команд, то перезагрузкаконвейера приводит к значительным потерям производительности. Поэтому вопросамэффективного предсказания направления ветвления разработчики всех процессоровуделяют большое внимание.
Методы предсказания переходов делятся настатические и динамические. При использовании статических методов до выполненияпрограммы для каждой команды условного перехода указывается направлениенаиболее вероятного ветвления. Это указание делается или программистом спомощью специальных средств, имеющихся в некоторых языках программирования, поопыту выполнения аналогичных программ либо результатам тестового выполненияпрограммы, или программой-компилятором по заложенным в ней алгоритмам.Статические методы предсказания ветвлений слишком упрощены; они предписывают всегдавыполнять или не выполнять определенные типы переходов. В некоторых процессорах(не принадлежащих к семейству x86) команды содержат «намек» на направлениепредполагаемого перехода, который компилятор может сделать на основе ожидаемогоим поведения программы.
Но в целом более эффективное решение —динамический алгоритм предсказания ветвлений, который учитывает направленияпереходов, реализовывавшиеся этой командой при выполнении программы. Например,подсчитывается количество переходов, выполненных ранее по тому или иномунаправлению, и на основании этого определяется направление перехода приследующем выполнении данной команды. Динамический алгоритм предсказанияветвлений на самом деле оценивает поведение команд перехода за предшествующийпериод времени (поскольку один и тот же переход часто выполняется более чемодин раз, например, в цикле). Благодаря информации о предыстории предсказаниябудущих ветвлений могут делаться гораздо более точно. Таблица предсказанияветвлений организуется по ассоциативному принципу, подобно кэш-памяти, ееэлементы доступны по адресу команды, ветвление которой предсказывается. Внекоторых реализациях элемент таблицы предсказания ветвления являетсясчетчиком, значение которого увеличивается при правильном предсказании иуменьшается при неправильном. При этом значение счетчика определяетпреобладающее направление ветвлений. Если требуется осуществить смену значениясчетчика команд, то необходим, по крайней мере, один такт для распознаваниякоманды ветвления, модификации счет­чика команд и выборки команды по заданномузначению счетчика команд. Эти за­держки вызывают пустые такты в конвейерахпроцессора. Более сложные решения используют буферы, содержащие наборы команддля двух возможных результатов ветвлений.
Возможно также использование «отложенныхпереходов», когда одна или не­сколько команд после команды ветвлениявыполняются безусловно.
В момент определения действительногозначения условия ветвления вносится изменение в историю ветвления. Еслипредсказание было неверным, то должна ини­циироваться выборка правильныхкоманд. Результаты команд, которые были услов­но выполнены, должны бытьаннулированы.
Механизм предсказания переходов работаетодновременно с декодером инструкций и независимо от него. Благодаря эффективнойреализации предсказания адреса перехода в процессорах P-III, P-M, P-M2, P8 и K8при правильном предсказании теряется всего 1 такт. Это означает, чтоминимальное время, затрачиваемое на итерацию цикла (либо на один переход вцепочке переходов) составляет 2 такта. По существу, предсказатель переходов втаком цикле (или цепочке) работает в своём независимом цикле, состоящем из двухстадий — предсказания и считывания нового блока кэша — а декодер и прочиеподсистемы процессора обрабатывают инструкции из вновь считываемых блоков.Поскольку предсказатель переходов «просматривает» целый блок, который можетсодержать большое число инструкций, то он может «опережать» декодер в своёмпросмотре. Благодаря этому переход может быть совершён раньше, чем исчерпаютсяинструкции в текущем блоке, и указанной потери такта не произойдёт — этот тактбудет скрыт на фоне бесперебойной работы декодера.
В процессоре PPC970 предсказатель переходовработает менее эффективно — при правильном предсказании теряется 2 такта, аминимальное время итерации цикла составляет 3 такта. Хотя предсказательпросматривает инструкции с некоторым опережением, это может лишь частичноскрыть потерю указанных двух тактов, и в результате эффективность исполненияперехода окажется ниже, чем в других процессорах.
Когда инструкция перехода попадёт вфункциональное устройство для исполнения, будет выяснено, правильно предсказанэтот переход, или нет. В момент её отставки при неправильном предсказанииперехода все последующие инструкции будут отменены, и начнётся считывание инструкцийиз I-кэша по правильному адресу. Такую процедуру называют сбросом конвейера, авремя (в тактах), которое было потрачено на выполнение инструкции перехода смомента её считывания из кэша, называют длиной конвейера непредсказанногоперехода. Это время характеризует чистую потерю в идеальных условиях, когдаинструкция проходила через все этапы «гладко» и нигде не задерживалась повнешним причинам. В реальных условиях потеря на неправильно предсказанныйпереход может оказаться выше.
Длина конвейера непредсказанного переходане всегда указывается в документации и известна весьма приблизительно. Еёдовольно трудно замерить, так как современные предсказатели переходов работаютдостаточно эффективно и не позволяют добиться гарантированной доли неправильныхпредсказаний в тестах. Можно дать следующие примерные оценки длины конвейера:P-III — 11, P-M — 12, P-4 — 20, P-4E — 30, P8 — 14, K8 — 11, PPC970 — 13. Нужноучесть, что в процессорах P-4 и P-4E длина такта меньше, чем в другихпроцессорах, и потеря на непредсказанный переход, выраженная в«нормализованных» тактах с учётом соотношения 1:1.4, составит соответственно 15и 22.
6 Матричные процессоры
Конвейеры и суперскалярная архитектураобычно повышают скорость работы всего лишь в 5-10 раз. Чтобы увеличитьпроизводительность в 50, 100 и более раз, нужно создавать компьютеры снесколькими процессорами.
В любой параллельной компьютерной системепроцессоры, выполняющие разные части единого задания, должны как-товзаимодействовать друг с другом, чтобы обмениваться информацией. Как именнодолжен происходить обмен? Для этого было предложено и реализовано двестратегии: мультипроцессоры и мультикомпьютеры. Ключевое различие междустратегиями состоит в наличии или отсутствии общей памяти. Это различиесказывается как на конструкции, устройстве и программировании таких систем, таки на их стоимости и размерах.
 
6.1 Матричные процессоры
Многие задачи в физических и техническихнауках предполагают использование массивов или других упорядоченных структур.Часто одни и те же вычисления могут производиться над разными наборами данных водно и то же время. Упорядоченность и структурированность программ,предназначенных для выполнения такого рода вычислений, очень удобны в планеускорения вычислений за счет параллельной обработки команд.
Матричный процессор (array processor)состоит из большого числа сходных процессоров, которые выполняют одну и ту жепоследовательность команд применительно к разным наборам данных. Первым в миретаким процессором был ILLIAC IV (Университет Иллинойс). Схематически онизображен на рисунке 6.1. Первоначально предполагалось сконструировать машину,состоящую из четырех квадрантов, каждый из которых содержал матрицу размером 8х 8 из блоков процессор/память. Для каждого квадранта имелся один блокконтроля. Он рассылал команды, которые выполнялись всеми процессорамиодновременно, при этом каждый процессор использовал собственные данные изсобственной памяти (загрузка данных происходила при инициализации). Эторешение, значительно отличающееся от стандартной фон-неймановской машины,иногда называют архитектурой SIMD (Single Instruction-stream MultipleData-stream — один поток команд с несколькими потоками данных). Из-за оченьвысокой стоимости был построен только один такой квадрант, но он мог выполнять50 млн операций с плавающей точкой в секунду. Если бы при создании машиныиспользовалось четыре квадранта, она могла бы выполнять 1 млрд операций сплавающей точкой в секунду, и вычислительные возможности такой машины в двараза превышали бы возможности компьютеров всего мира.
 
6.2 Векторный процессор
С точки зрения программиста, векторныйпроцессор (vector processor) очень похож на матричный. Как и матричный, ончрезвычайно эффективен при выполнении последовательности операций над парамиэлементов данных. Однако в отличие от матричного процессора, все операциисложения выполняются в одном блоке суммирования, который имеет конвейернуюструктуру. Компания Cray Research, основателем которой был Сеймур Крей,выпустила множество моделей векторных процессоров, начиная с модели Сгау-1A974.
Оба типа процессоров работают с массивамиданных. Оба они выполняют одни и те же команды, которые, например, попарноскладывают элементы двух векторов. Однако если у матричного процессора столькоже суммирующих устройств, сколько элементов в массиве, векторный процессорсодержит векторный регистр, состоящий из набора условных регистров. Этирегистры загружаются из памяти единственной командой, которая фактически делаетэто последовательно. Команда сложения попарно складывает элементы двух такихвекторов, загружая их из двух векторных регистров в суммирующее устройство сконвейерной структурой. В результате из суммирующего устройства выходит другойвектор, который либо помещается в векторный регистр, либо сразу используется вкачестве операнда при выполнении другой операции с векторами.
Матричные процессоры в настоящее время невыпускаются, но принцип, на котором они основаны, по-прежнему актуален.Аналогичная идея применяется в наборах ММХ- и SSE-команд процессоров Pentium 4,и она успешно решает задачу ускоренного выполнения мультимедийных программ. Вэтом отношении компьютер ILLIAC IV можно считать одним из прародителейпроцессора
Pentium 4.
 
6.3 Внутрипроцессорная многопоточность
Для всех современных конвейеризованныхпроцессоров характерна одна и та же проблема — если при запросе к памяти словоне обнаруживается в кэшах первого и второго уровней, на загрузку этого слова вкэш уходит длительное время, в течение которого конвейер простаивает. Одна изметодик решения этой проблемы называется внутрипроцессорной многопоточностью(on-chip multithreading). Она позволяет процессору одновременно управлятьнесколькими программными потоками и тем самым маскировать простои. Вкратцепринцип можно изложить так: если программный поток 1 блокируется, процессорможет обеспечить полную загрузку аппаратуры, запустив программный поток 2.
Основополагающая идея проста, реализуетсяона разными способами. Первый из них, называемый мелкомодульноймногопоточностью (fine-grained multithreading), применительно к процессору,способному вызывать одну команду за такт, иллюстрирует рисунок 6.2. На рисунке6.2 а-в изображено три программных потока (А, В, С), соответствующих 12машинным циклам. В ходе первого цикла поток А выполняет команду A1. Посколькуэта команда завершается за один цикл, при наступлении второго цикла запускаетсякоманда А2. Ее обращение в кэш первого уровня оказывается неудачным, поэтому доизвлечения нужного слова из кэша второго уровня проходит два цикла. Исполнениепотока продолжается в цикле 5. Как показано на рисунке, потоки В и С такжерегулярно простаивают. В рамках такого решения вызов последующей команды дозавершения предыдущей не осуществляется. Точнее, при наличии сложного счетчикаобращений в некоторых случаях это допустимо, но такую возможность мы дляпростоты исключаем.
При мелкомодульной многопоточности простоймаскируется путем исполнения потоков «по кругу», то есть в смежныхциклах запускаются разные потоки (рисунок 6.2 г). К моменту наступления цикла 4обращение к памяти, инициированное командой A1, завершается, поэтому даже есликоманде A2 нужен результат команды A1, она запускается. В таком случаемаксимальная продолжительность простоя составляет два цикла, то есть приналичии трех программных потоков простаивающая операция все равно завершаетсявовремя. При простое в 4 цикла для беспрерывной работы понадобилось бы 4программных потока, и т. д.
Поскольку разные программные потоки никакдруг с другом не связаны, каждому из них нужен свой набор регистров. Он долженбыть указан для каждой вызываемой команды, и тогда аппаратное обеспечение будетзнать, к какому набору регистров при необходимости нужно обращаться. Следовательно,максимальное число одновременно исполняемых программных потоков определяется впериод разработки микросхемы.
Обращениями к памяти причины простоя неограничиваются. Иногда для исполнения следующей команды требуется результатпредыдущей команды, который еще не вычислен. В других случаях команда вызванабыть не может, так как она следует за условным переходом, направление которогоеще неизвестно. Общее правило формулируется так: если в конвейере k ступеней,но по кругу можно запустить, по меньшей мере, k программных потоков, то в одномпотоке в любой отдельно взятый момент не может выполняться более одной команды,поэтому конфликты между ними исключены. В такой ситуации процессор можетработать на полной скорости, без простоя.
Естественно, далеко не всегда числодоступных потоков равно числу ступеней конвейера, поэтому некоторыеразработчики предпочитают методику, называемую крупномодульной многопоточностью(coarse-grained multithreading), которую иллюстрирует рисунок 6.2, д. В данномслучае программный поток А продолжает выполняться последовательно, вплоть допростоя. При этом теряется один цикл. Далее происходит переключение на первуюкоманду программного потока B (B1). Так как эта команда сразу переходит всостояние простоя, в цикле 6 выполняется уже команда C1. Так как каждый раз припростое команды теряется один цикл, по своей эффективности крупномодульнаямногопоточность, казалось бы, уступает мелкомодульной, однако у нее есть односущественное преимущество — за счет меньшего числа программных потоковзначительно сокращается расход ресурсов процессора. При недостаточномколичестве активных потоков эта методика оптимальна.
Судя по нашему описанию, прикрупномодульной многопоточности просто выполняется переключение между потоками,однако это — не единственный предусматриваемый данной методикой вариантдействий. Есть возможность немедленного переключения с команд, которыепотенциально способны вызвать простой (например, загрузка, сохранение ипереходы), без выяснения, действительно ли намечается простой. Эта стратегияпозволяет переключаться раньше обычного (сразу после декодирования команды) иисключает бесконечные циклы. Иными словами, исполнение продолжается до тогомомента, пока не обнаружится возможность возникновения проблемы, после чего следуетпереключение. Такие частые переключения роднят крупномодульную многопоточностьс мелкомодульной.
Вне зависимости от используемого вариантамногопоточности, необходимо как-то отслеживать принадлежность каждой операции ктому или иному программному потоку. В рамках мелкомодульной многопоточностикаждой операции присваивается идентификатор потока, поэтому при перемещениях поконвейеру ее принадлежность не вызывает сомнений. Крупномодульнаямногопоточность предусматривает возможность очистки конвейера перед запускомкаждого последующего потока. В таком случае четко определяется идентичностьпотока, исполняемого в данный момент. Естественно, данная методика эффективнатолько в том случае, если паузы между переключениями значительно большевремени, необходимого для очистки конвейера.
Все сказанное относится к процессорам,способным вызывать не более одной команды за тактовый цикл. Однако мы знаем,что для современных процессоров это ограничение не актуально. Применительно кизображению на рисунке 6.3 мы допускаем, что процессор может вызывать по 2команды за цикл, однако утверждение о невозможности запуска последующих командв случае простоя предыдущей остается в силе. Рисунок 6.3, а иллюстрируетмеханизм мелкомодульной многопоточности в сдвоенном суперскалярном процессоре.Как видно, в потоке А первые две команды запускаются во время первого цикла,однако в потоке В во втором цикле запускается только одна команда.
В суперскалярных процессорах есть еще одинспособ организации многопоточности — так называемая синхронная многопоточность(simultaneous multithreading), которую иллюстрирует рисунок 6.3, в. Этаметодика представляет собой усовершенствованный вариант крупномодульноймногопоточности, где каждый программный поток может запускать по две команды затакт, однако в случае простоя с целью обеспечения полной загрузки процессоразапускаются команды следующего потока. При синхронной многопоточности полностьюзагружаются все функциональные блоки. В случае невозможности запуска командыиз-за занятости функционального блока выбирается команда из другого потока. Нарисунке предполагается, что в цикле 11 простаивает команда B8, поэтому в цикле12 запускается команда С7.
 
6.4 Многопоточность в Pentium 4
Разобравшись с теорией многопоточности,рассмотрим практический пример — Pentium 4. Уже на этапе разработки этогопроцессора инженеры Intel продолжали работу над повышением его быстродействиябез внесения изменений в программный интерфейс. Рассматривалось пять простейшихспособов:
-     повышение тактовой частоты;
-     размещение на одной микросхеме двух процессоров;
-     введение новых функциональных блоков;
-     удлинение конвейера;
-     использование многопоточности.
Самый очевидный способ повышениябыстродействия заключается в том, чтобы повысить тактовую частоту, не меняядругие параметры. Как правило, каждая последующая модель процессора имеетнесколько более высокую тактовую частоту, чем предыдущая. К сожалению, припрямолинейном повышении тактовой частоты разработчики сталкиваются с двумяпроблемами: увеличением энергопотребления (что актуально для портативныхкомпьютеров и других вычислительных устройств, работающих на аккумуляторах) иперегревом (что требует создания более эффективных теплоотводов).
Второй способ — размещение на микросхемедвух процессоров — сравнительно прост, но он сопряжен с удвоением площади,занимаемой микросхемой. Если каждый процессор снабжается собственнойкэш-памятью, количество микросхем на пластине уменьшается вдвое, но это такжеозначает удвоение затрат на производство. Если для обоих процессоровпредусматривается общая кэш-память, значительного увеличения занимаемой площадиудается избежать, однако в этом случае возникает другая проблема — объемкэш-памяти в пересчете на каждый процессор уменьшается вдвое, а это неизбежносказывается на производительности. Кроме того, если профессиональные серверныеприложения способны полностью задействовать ресурсы нескольких процессоров, тов обычных настольных программах внутренний параллелизм развит в значительноменьшей степени.
Введение новых функциональных блоков такжене представляет сложности, но здесь важно соблюсти баланс. Какой смысл вдесятке блоков АЛУ, если микросхема не может выдавать команды на конвейер стакой скоростью, которая позволяет загрузить все эти блоки?
Конвейер с увеличенным числом ступеней,способный разделять задачи на более мелкие сегменты и обрабатывать их закороткие периоды времени, с одной стороны, повышает производительность, сдругой, усиливает негативные последствия неверного прогнозирования переходов,кэш-промахов, прерываний и других событий, нарушающих нормальный ход обработкикоманд в процессоре. Кроме того, чтобы полностью реализовать возможностирасширенного конвейера, необходимо повысить тактовую частоту, а это, как мызнаем, приводит к повышенным энергопотреблению и теплоотдаче.
Наконец, можно реализовать многопоточность.Преимущество этой технологии состоит во введении дополнительного программногопотока, позволяющего ввести в действие те аппаратные ресурсы, которые впротивном случае простаивали бы. По результатам экспериментальных исследованийразработчики Intel выяснили, что увеличение площади микросхемы на 5 % приреализации многопоточности для многих приложений дает приростпроизводительности на 25 %. Первым процессором Intel с поддержкоймногопоточности стал Хеоn 2002 года. Впоследствии, начиная с частоты 3,06 ГГц,многопоточность была внедрена в линейку Pentium 4. Intel называет реализациюмногопоточности в Pentium 4 гиперпоточностью (hyperthreading).
7 Закон Амдала. Закон Густафсона
 
7.1 Ускорение, эффективность, загрузка и качество
Параллелизм достигается за счет того, что в составевычислительной системы отдельные устройства присутствуют в нескольких копиях.Так, в состав процессора может входить несколько АЛУ, и высокая произ­водительностьобеспечивается за счет одновременной работы всех этих АЛУ. Второй подход былописан ранее.
Рассмотрим параллельное выполнение программы соследующими характеристиками:
О(n) — общее число операций(команд), выполненных на n-процессорной системе;
Т(n) — время выполнения О(n) операций на n-процессорной системев виде числа квантов времени.
В общем случае Т(n) 2. Примем, что в однопроцессорной системе T(1)= О(1).
Ускорение (speedup), или точнее,среднее ускорение за счет параллельного выполнения программы — это отношениевремени, требуемого для выполнения наилучшего из последовательных алгоритмов наодном процессоре, и времени параллельного вычисления на n процессорах. Без учета коммуникационных издержек ускорение S(n) определяется как
/>
Как правило, ускорение удовлетворяет условию S(n) />n.Эффективность (efficiency) n-процессорнойсистемы — это ускорение на один процессор, определяемое выражением
/>
Эффективность обычно отвечает условию 1/n /> Е(n) /> n. Для более реалис­тичного описания производительностипараллельных вычислений необходимо промоделировать ситуацию, когда параллельныйалгоритм может потребовать больше операций, чем его последовательный аналог.
Довольно часто организация вычислений на n процессорах связана с существеннымииздержками. Поэтому имеет смысл ввести понятие избыточности (redun­dancy) в виде
/>
Это отношение отражает степень соответствия междупрограммным и аппаратным параллелизмом. Очевидно, что 1 /> R(n) /> n.
Определим еще одно понятие, коэффициент полезногоиспользования или утилизации (utilization), как   
/>
Тогда можно утверждать, что
/>
Рассмотрим пример. Пусть наилучший из известныхпоследовательных алгоритмов занимает 8 с, а параллельный алгоритм занимает напяти процессорах 2 с. Тогда:
S(n) =8/2 = 4;    
Е(n) = 4/5 = 0,8;
R(n) =1/0,8 — 1 = 0,25.
Собственное ускорение определяется путем реализациипараллельного алгоритма на одном процессоре.
Если ускорение, достигнутое на n процессорах, равно n, то говорят,что алгоритм показывает линейное ускорение.
В исключительных ситуациях ускорение S(n) может быть больше, чем n. В этихслучаях иногда применяют термин суперлинейное ускорение. Данное явление имеетшансы на возникновение в двух следующих случаях:
Последовательная программа может выполняться в оченьмаленькой памяти, вызывая свопинги (подкачки), или, что менее очевидно, можетприводить к большему числу кэш-промахов, чем параллельная версия, где обычнокаждая параллельная часть кода выполняется с использованием много меньшего наб­раданных.
Другая причина повышенного ускорения иллюстрируетсяпримером. Пусть нам нужно выполнить логическую операцию A1v A2, гдекак A1 так и А2 имеют значение «Истина» с вероятностью50%, причем среднее время вычисления Ai, обозначенноекак T(Ai), существенноразличается в зависимости от того, является ли результат истинным или ложным.
Пусть
/>
Теперь получаем четыре равновероятных случая (Т —«истина», F — «ложь»):
/>
Таким образом, параллельные вычисления на двухпроцессорах ведут к среднему ускорению:
/>
Отметим, что суперлинейное ускорение вызвано жесткостьюпоследователь­ной обработки, так как после вычисления еще нужно проверить А2. Кфакторам, ограничивающим ускорение, следует отнести:
-     Программные издержки. Даже если последовательные и параллельныеалгоритмы выполняют одни и те же вычисления, параллельным алгоритмам присущидобавочные программные издержки — дополнительные индексные вычисления,неизбежно возникающие из-за декомпозиции данных и распределения их по процессорам;различные виды учетных операций, требуемые в параллельных алгоритмах, ноотсутствующие в алгоритмах последовательных.
-     Издержки из-за дисбаланса загрузки процессоров. Между точкамисинхронизации каждый из процессоров должен быть загружен одинаковым объемомработы, иначе часть процессоров будет ожидать, пока остальные завершат своиоперации. Эта ситуация известна как дисбаланс загрузки. Таким образом,ускорение ограничивается наиболее медленным из процессоров.
-     Коммуникационные издержки. Если принять, что обмен информацией ивычисления могут перекрываться, то любые коммуникации между процессорамиснижают ускорение. В плане коммуникационных затрат важен уровень гранулярности,определяющий объем вычислительной работы, выполняемой между коммуникационнымифазами алгоритма. Для уменьшения коммуникационных издержек выгоднее, чтобывычислительные гранулы были достаточно крупными, и доля коммуникаций быламеньше.
Еще одним показателем параллельных вычислений служит качествопараллель­ного выполнения программ — характеристика, объединяющая ускорение,эффективность и избыточность. Качество определяется следующим образом:
/>
Поскольку как эффективность, так и величина, обратнаяизбыточности, представляют собой дроби, то Q(n) /> S(n). Поскольку Е(n) — это всегдадробь, a R(n) -число между 1 и n, качество Q(n) при любых условиях ограниченосверху величиной ускорения S(n)[4].
 
7.2 Закон Амдала
В идеальном случае система из n процессоров могла бы ускорить вычисления в n раз. В реальности достичь такого показателя по ряду причинне удается. Главная из этих причин заключается в невозможности полногораспараллеливания ни одной из задач. Как правило, в каждой программе имеетсяфрагмент кода, который принципиально должен выполняться последовательно итолько одним из процессоров. Это может быть часть программы, отвечающая зазапуск задачи и распределение распараллеленного кода по процессорам, либофрагмент программы, обеспечивающий операции ввода/вывода. Можно привести идругие примеры, но главное состоит в том, что о полном распараллеливании задачигово­рить не приходится. Известные проблемы возникают и с той частью задачи,кото­рая поддается распараллеливанию. Здесь идеальным был бы вариант, когдапараллельные ветви программы постоянно загружали бы все процессоры системы,причем так, чтобы нагрузка на каждый процессор была одинакова. К сожалению, обаэтих условия на практике трудно реализуемы. Таким образом, ориентируясь напараллельную ВС, необходимо четко сознавать, что добиться прямопропорционального числу процессоров увеличения производительности не удастся,и, естественно, встает вопрос о том, на какое реальное ускорение можнорассчитывать. Ответ на этот вопрос в какой-то мере дает закон Амдала.
Джин Амдал (Gene Amdahl) — один из разработчиковвсемирно известной системы IBM 360, в своей работе,опубликованной в 1967 году, предложил формулу, отражающую зависимость ускорениявычислений, достигаемого на многопроцессорной ВС, от числа процессоров исоотношения между последовательной и параллельной частями программы.Показателем сокращения времени вычислений служит такая метрика, как «ускорение».Напомним, что ускорение S— это отношение времени Ts, затрачиваемого на проведение вычислений наоднопроцессорной ВС (в варианте наилучшего последовательного алгоритма), ковремени Тр решения той же задачи на параллельной системе (при использовании наилучшегопараллельного алгоритма):
/>
Оговорки относительно алгоритмов решения задачи сделаны,чтобы подчеркнуть тот факт, что для последовательного и параллельного решениялучшими могут оказаться разные реализации, а при оценке ускорения необходимоисходить именно из наилучших алгоритмов.
Проблема рассматривалась Амдалом в следующей постановке(рисунок 7.1). Прежде всего, объем решаемой задачи с изменением числапроцессоров, участвующих в ее решении, остается неизменным. Программный кодрешаемой задачи состоит из двух частей: последовательной и распараллеливаемой.Обозначим долю операций, которые должны выполняться последовательно одним изпроцессоров, через f, где 0/>f/>1 (здесь доляпонимается не по числу строк кода, а по числу реально выполняемых операций).Отсюда доля, приходящаяся на распараллеливаемую часть программы, составит 1-f. Крайние случаи в значениях fсоответствуют полностью параллельным (f=0) и полностьюпоследовательным (f=1) программам. Распараллеливаемаячасть программы равномерно распределяется по всем процессорам.
С учетом приведенной формулировки имеем:
/>
В результате получаем формулу Амдала, выражающуюускорение, которое мо­жет быть достигнуто на системе из n процессоров:
/>
Формула выражает простую и обладающую большой общностьюзависимость. Характер зависимости ускорения от числа процессоров и долипоследовательной части программы показан на рисунке 7.2.
Если устремить число процессоров к бесконечности, то впределе получаем:
/>
Это означает, что если в программе 10% последовательныхопераций (то есть f=0,1), то, сколько бы процессоров нииспользовалось, убыстрения работы программы более чем в десять раз никак ниполучить, да и то, 10 — это теоретическая верхняя оценка самого лучшего случая,когда никаких других отрицательных факторов нет. Следует отметить, чтораспараллеливание ведет к определенным издержкам, которых нет припоследовательном выполнении программы. В качестве примера таких издержек можноупомянуть дополнительные операции, связанные с распределением программ попроцессорам, обмен информацией между процессорами [4].

7.3 Закон Густафсона
Решая на вычислительной системе из 1024 процессоров трибольших задачи, для которых доля последовательного кода fлежала в пределах от 0,4 до 0,8%, Джон Густафсон из NASA Ames Research получил значения ускоренияпо сравнению с однопроцессорным вариантом, равные соответственно 1021,1020 и1016. Согласно закону Амдала для данного числа процессоров и диапазона f, ускорение не должно было превысить величины порядка 201.Пытаясь объяснить это явление, Густафсон пришел к выводу, что причина кроется висходной предпосылке, лежащей в основе закона Амдала: увеличение числапроцессоров не сопровождается увеличением объема решаемой задачи. Реальное жеповедение пользователей существенно отличается от такого представления. Обычно,получая в свое распоряжение более мощную систему, пользователь не стремитсясократить время вычислений, а, сохраняя его практически неизменным, стараетсяпропорционально мощности ВС увеличить объем решаемой задачи. И тут оказывается,что наращивание общего объема программы касается главным образомраспараллеливаемой части программы. Это ведет к сокращению значения f. Примером может служить решение дифференциального уравненияв частных производных. Если доля последовательного кода составляет 10% для 1000узловых точек, то для 100 000 точек доля последовательного кода снизится до0,1%. Сказанное иллюстрирует рисунок 7.3, который отражает тот факт, что,оставаясь практически неизменной, последовательная часть в общем объемеувеличенной программы имеет уже меньший удельный вес.
Было отмечено, что в первом приближении объем работы,которая может быть произведена параллельно, возрастает линейно с ростом числапроцессоров в системе. Для того чтобы оценить возможность ускорения вычислений,когда объем последних увеличивается с ростом количества процессоров в системе(при посто­янстве общего времени вычислений), Густафсон рекомендуетиспользовать выра­жение, предложенное Е. Барсисом (Е. Barsis):
/>
Данное выражение известно как закон масштабируемогоускорения или закон Густафсона (иногда его называют также закономГустафсона-Барсиса). В заключение отметим, что закон Густафсона не противоречитзакону Амдала. Различие состоит лишь в форме утилизации дополнительной мощностиВС, возникающей при увеличении числа процессоров [4].
вывод
Развитие вычислительной техникихарактеризуется тем, что на каждом этапе новых разработок требования кпроизводительности значительно превышают возможности элементной базы.
Это обусловлено задачами сложных системуправления в реальном времени, централизованным решением задач в сетях,имитационным моделированием сложных процессов (например, в ядерной физике),оперативным планированием и управлением. Такие задачи требуют концентрациивычислительных мощностей, постоянно поддерживая высокую актуальность проблемысоздания супер-ЭВМ.
Добиваться повышения производительностикомпьютеров только за счет увеличения тактовой частоты становится все сложнее,так как появляется проблема отвода тепла. Поэтому разработчики обратили своевнимание на параллелизм как на средство ускорения вычислений. Параллелизм можетвводиться на разных уровнях, как на самых нижних, где элементы очень жесткосвязаны друг с другом, так и на верхних, где связи весьма слабые.
Параллелизм на уровне команд имеет место,когда обработка нескольких команд или выполнение различных этапов одной и тойже команды может перекрываться во времени. Разработчики вычислительной техники прибегаютк методам, известным под общим названием «совмещения операций», при которомаппарату­ра ВМ в любой момент времени выполняет одновременно более однойоперации.
В работе мы рассмотрели принципыорганизации параллелизма на уровне команд, ознакомились с работой конвейера, суперскалярногоконвейера, матричного процессора, убедились в том, что параллелизм –эффективный способ повышения производительности при неизменной тактовой частотепроцессора.
список литературы
1.        Корнеев В.В. Вычислительные системы.-М.: Гелиос APB,  2004.-512с., ил.- с.34-46
2.        Таненбаум, Э. Архитектура компьютера/Пер. с англ.- 4-е изд.  Учебникдля вузов.-СПб.: Питер, 2003 698 с.: ил.
3.        Барский А.Б. Параллельные информационные технологии: Учебноепособие/А.Б. Барский.-М.: Интернет-университет информационных технологий;БИНОМ. Лаборатория знаний, 2007.-503 с.: ил., таб.-(серия «Основы информационныхтехнологий»)- с.20-28, с.56-58.
4.        Цилькер, Б. Я. Организация ЭВМ и систем: Учебник для вузов.-СПб.:Питер, 2007.-668с.: ил- с. 481-492
5.        Куприянов М.С., Петров Г.А., Пузанков Д.В. Процессор Pentium:Архитектура и программирование. /ГЭТУ-СПб., 1995.-277с -с. 11-17
6.        Гук М, Юров В. Процессоры Pentium 4, Atlon и Duron.-СПб.: Питер, 2001.-512с.: ил- с. 42-46
7.        Головкин Б.А. Параллельные вычислительные системы. — М.: Наука, 1980. — 518 с.
8.        Шпаковский Г.И. Архитектура параллельных ЭВМ: Учеб. пособие для вузов. — Мн.: Университетское, 1989. — 192 с.
9.        Коуги П.М. Архитектура конвейерных ЭВМ / Пер. с англ. — М.: Радио исвязь, 1985. — 360 с.
10.     Хокни З., Джессхоуп К. Параллельные ЭВМ. — М.: Радио и связь, 1986. — 389 с.
11.     http://www.tver.mesi.ru/e-lib/res/628/11/2.html — Интернет-университет информационных технологий — дистанционное образование