Структуры ЭВМ с одиночным потоком команд

Конвейерные процессоры для скалярной обработки

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

В любом процессоре машинная команда проходит ряд этапов обработки, например: выборку команды из оперативной памяти (ВК), вычисление абсолютного адреса операнда в оперативной памяти (ВА), выборку операнда из памяти (ВО), операцию в АЛУ.

В процессоре последовательной ЭВМ для выполнения этих функций используется единственное устройство, поэтому время выполнения команды

tк = tВК + tВА + tВО + tАЛУ.

Чтобы уменьшить tк, можно для каждой функции ввести собственное оборудование (рис. 2.1). В таком процессоре любая команда последовательно проходит через все устройства, находясь на каждом этапе время Δt. Так, команда с номером i поступает в УВК, через время Δt она переходит в УВА, а в УВК поступает команда с номером i + 1, затем через время Dt команда i поступает в УВО, i + 1 - в УВА, i + 2 - в УВК и т. д. Наконец, команда i поступает в АЛУ и через время Δt вырабатывается результат. После этого через время Δt будет получен результат команды i + 1. Таким образом, несмотря на то, что общее время выполнения любой команды сохранилось, результаты вырабатываются через время Δt = tк/n, где n - число этапов этого конвейера команд.

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

Рис.2.1. Схема и функционирование конвейера команд: ПК - память команд; ПО - память операндов; УВК, УВА, УВО - устройства выборки команд, вычисление адреса, выборки операндов соответственно

Конвейерные процессоры применяются во всех без исключения старших моделях семейств ЭВМ.

Временная диаграмма на рис. 2.1 строилась при следующих упрощениях: в потоке выбираемых из ПК команд отсутствуют команды условных переходов; все команды имеют одинаковое время нахождения на разных этапах.

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

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

В дальнейшем будет рассмотрена конвейеризация устройств процессора в таком порядке: АЛУ, УВК, УВА, УВО.

Арифметический конвейер можно построить для любых арифметико-логических операций: сложения, умножения, логических операций. В частности, на рис. 2.2, а, показан конвейер для выполнения операции сложения двух чисел с плавающей запятой. Каждое число представлено в форме A*Rp где A - мантисса; R - основание системы счисления, p - порядок. Конвейер для умножения целых чисел изображен на рис. 2.2, б. Здесь каждым входом сумматора Σ первого каскада управляет один разряд множителя. В зависимости от его значения на вход сумматора Σ подаются два смежных сдвинутых частичных произведения. Число каскадов такого конвейерного умножителя равно log2r, где r - разрядность чисел Ai,Bi .

Рис. 2.2 Арифметические конвейеры для сложения (а) и умножения (б)

Как и в случае конвейера команд, числа поступают на вход конвейеризованного АЛУ вплотную друг за другом, поэтому результаты на выходе получаются с интервалом Δt. Для современных ЭВМ величина Δt стала меньше 10 нс, что соответствует бы-стродействию больше 100 млн оп/с, и цикл конвейера имеет тенденцию к дальнейшему уменьшению. Но при этом Δt не может стать меньше времени передачи данных с каскада на каскад.

Впервые арифметические конвейеры были использованы для целей обработки числовых векторов в ЭВМ STAR-100, запущенной в США в 1973 г.

Если ставится задача построить быстродействующий конвейерный процессор с V = 100 млн оп/с, то цикл всех его устройств не должен превышать Δt = 10 нс. Выше было показано, как обеспечить данный цикл в АЛУ.

Рассмотрим, как обеспечить такую производительность в УВК. Поскольку на каждый полученный в АЛУ результат приходится одна выборка команды из ПК, то время выборки этой команды не должно превышать 10 нс. Но современные полупроводниковые запоминающие устройства большой емкости имеют цикл обращения tпк = 100...300 нс, что во много раз больше требуемого цикла конвейера (10 нс). Выходом здесь является использование множества автономных по функционированию блоков памяти. Число этих блоков N = tпк /Δt и может достигать величины 8...64 (обычно кратно степени 2).

Организация работы такой многоблочной памяти может быть различной. Некоторые варианты памяти этого типа изображены на рис. 2.3.

Если память имеет организацию, предназначенную для чтения со сдвигом (рис. 2.3, а), то в регистры адреса (РА) блоков памяти 1...4 с интервалом Δt подается новый адрес из счетчика адресов команд (СчАК) ПК. С таким же сдвигом по времени на выходе ПК будут появляться команды, которые затем поступают в буфер команд (БК), представляющий собой совокупность быстрых регистров. При поступлении каждой новой команды на вход БК содержимое всех его регистров сдвигается вверх на одну позицию, и верхняя команда (самая старая) удаляется из БК.

В УВК имеется СчАК БК, который указывает положение в БК считываемой из УВА команды. При считывании из БК каждой команды его содержимое уменьшается на единицу, при добавлении в БК новой команды из ПК - увеличивается на единицу. За запросом новых команд в БК постоянно следит УВК, которое определяется величиной l. Если l становится меньше заданного уровня, то запускается СчАК ПК и производится выборка из ПК новых команд.

Рис. 2.3. Организация многоблочной памяти для выборки команд: а - выборка со сдвигом во времени; б - выборка широким словом

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

В схеме на рис. 2.3, б за один цикл памяти в БК заносится несколько команд ("широкое слово"), операции же в БК выполняются, как и ранее. Схемы на рис. 2.3 не имеют явного предпочтения друг перед другом.

Многоблочная структура памяти была впервые применена в ЭВМ STRETCH.

Относительно УВА следует отметить, что оно является простым АЛУ для сложения коротких целых чисел (адресов), поэтому получение малого Δt для этого устройства не составляет труда.

Сократить цикл работы УВО значительно сложнее. Здесь для уменьшения времени чтения операнда необходимо использовать многоблочную память. Однако между выборкой команд и выборкой операндов существует следующее принципиальное различие. Команды в программе и памяти располагаются в порядке линейного нарастания их номеров, поэтому во время исполнения текущей команды всегда можно вычислить адреса и выбрать (исключая команды переходов) любые следующие команды (см. рис. 2.3), что и приводит к уменьшению Δt при выборке команд. Однако строго упорядоченная выборка команд порождает неупорядоченную последовательность адресов для выборки операндов (рис. 2.4). Это означает, что выборка операндов для некоторой команды не может быть произведена заранее, до ее выборки. Следовательно, выборка операндов не может быть конвейеризована, поэтому для построения ПО используется не конвейерный, а поточный принцип организации многоблочной памяти (рис. 2.5).

Поступающие из УВА адреса операндов распределяются по блокам ПО.

Рис. 2.4. Процесс генерации адресов операндов

Рис. 2.5. Поточная организация УВО

Поскольку распределение адресов носит достаточно случайный характер, в отдельных блоках памяти возможны очереди, для размещения которых введены буфера адресов (БА). Выбираемые из памяти операнды должны сразу поступать в АЛУ, однако вследствие неравномерности их появления из ПО и разной длительности исполнения операций в АЛУ вводятся буферные регистры операндов чтения (БОЧ) и записи (БОЗ). С каждой парой операндов связан свой код операции, который хранится также в буфере кода операций (БКОП). Таким образом, в буфере операндов (БО) и БКОП хранятся готовые к исполнению в АЛУ группы информации.

Качественная картина сокращения цикла выборки из многоблочной памяти одного операнда представлена на рис. 2.6. Время цикла одного блока памяти t выражено в относительных единицах.

Рис. 2.6. Зависимость среднего времени выборки операнда из ПО от числа блоков ОП

Для уменьшения числа обращений к ПО, как правило, используются регистры общего назначения (РОН), расположенные в АЛУ (рис. 2.7). Обычно их 8...16. В этом случае АЛУ и УВО работают только с РОН, в результате чего в системе команд ЭВМ происходит дифференциация. Вместо команды с обращением в память за обоими операндами (рис. 2.8, а) появляется команда обмена между памятью и РОН (рис. 2.8, б) и команда для работы АЛУ с РОН (рис. 2.8, в). Качественная картина снижения числа обращений в ПО при увеличении РОН представлена на рис. 2.9.

Рис. 2.7. Организация АЛУ с регистровой памятью: К - коммутатор

Рис. 2.8. Структура команды конвейерной ЭВМ а - оба операнда размещены в памяти; б - один операнд размещен в памяти, другой в РОН; в - оба операнда раз-мещены в РОН; КОП - код операции; А1, А2, А3 - абсолютные адреса перво-го, второго операндов и результата; R1, R2 - поля для указания номеров РОН, где размещены операнды; Xi, Bi - поля для указания номеров РОН, где хранят-ся индексный и базовый адреса; Di - смещение

Довольно сложную структуру памяти для выборки команд и операндов, содержащую множество блоков памяти, ряд буферов и других регистровых файлов, иногда заменяют единой, достаточно большой сверхоперативной памятью, называемой КЭШ-памятью (CACHE) или просто КЭШ. КЭШ-память имеет малый цикл обращения (десятки наносекунд) и большой (до 16...32 кбайт) объем (рис. 2.10). Основная память M разделена на N страниц (обычно объемом 1024 байт). КЭШ содержит n страниц такого же объема, причем N>>n. Любая страница КЭШ может заполняться информацией из M всего за несколько тактов. В каждой странице КЭШ расположены данные со смежными адресами, разные же страницы КЭШ могут не стыковаться по адресам.

При всяком обращении к M из УВК или УВО с помощью ассоциативной памяти производится проверка наличия искомой информации в КЭШ. Если информация имеется, производится обращение к КЭШ. При этом надо различать операции чтения и записи. В случае записи одновременно корректируется соответствующая ячейка памяти в M. Если нужный адрес обращения в КЭШ отсутствует, то из M в КЭШ производится запись новой страницы.

Рис. 2.9. Снижение числа обращения в ПО в зависимости от количества РОН: r - число обращений за операндами в ПО в пересчете на одну выполненную команду

Рассмотрим два процесса: обращение к КЭШ и смену страницы в КЭШ.

При всяком обращении к M с помощью ассоциативной памяти делается проверка наличия данной страницы в КЭШ. Если она есть, то адрес в КЭШ будет таким:

A=N3 (из ассоциативной памяти)+N2 (из команды обращения).

В поле Z периодически заносится некоторое число. При каждом обращении к странице КЭШ из занесенного числа вычитается единица. Когда в КЭШ не оказывается нужного слова, требуется заменить страницу. Для этого просматриваются поля Z. Там, где число наибольшее, страница считается редко используемой. Вместо нее из M вводится новая страница, и ассоциатив-ная память корректируется. От обычного буфера КЭШ отличается большими размерами, что не позволяет добавлять новую информацию путем сдвига файла регистров, а также наличием несмежных страниц, так как приводит к специальной схеме обмена и обращения, обязательно использующей ассоциативную память для доступа к таблице. Кроме того, эффективность КЭШ зависит от характера распределения данных в M. Плохое распределение данных приводит к частой смене страниц.

Рис. 2.10. Структура КЭШ-памяти: N1 и N2 - номера страниц и слова, указанные в запросе на обращение к ОП; N3 - номер страницы КЭШ; N4 - номер страницы, размещенной в КЭШ

Итак, мы изучили структуру отдельных устройств конвейерного процессора.

Теперь рассмотрим структуру и функционирование скалярного конвейерного процессора в целом (рис. 2.11).

Рис. 2.11. Организация скалярного конвейерного процессора: ЦМП - центральная многоблочная память; БАО - буфер адресов операндов; АЛУ - конвейеризованные арифметико-логические устройства для сложения, умножения и деления чисел с плавающей запятой; K', K''- коммутаторы памяти и АЛУ соответственно; БС РОН - блок состояния РОН; УПК - указатель номе-ра пропущенной команды; СчК - счетчик команд; 1 - шина адреса команд; 2 - шина управления выполнением команд обращения к памяти; 3 - шина заполне-ния БК; 4 - шина смены состояний РОН; 5 - шина управления выполнением регистровых команд

Процессор содержит несколько конвейерных АЛУ. Это позволяет одновременно исполнять смежные арифметико-логические операции, что соответствует реализации не только паралле-лизма служебных операций, но и локального параллелизма. Для разных операций АЛУ имеют различную длину конвейера (на рис. 2.11 она равна 6, 7 и 14 позициям). В процессоре используются команды двух классов: команды обращения в память (см. рис. 2.8, б) и регистровые команды для работы с РОН (см. рис. 2.8, в). Буфер команд имеет многостраничную структуру, что позволяет во время работы УУ с одной страницей производить заранее смену других страниц.

Для изучения работы процессора (см. рис. 2.11) использован отрезок программы, соответствующий вычислению выражения

Z = A - (B * C + D) - E.

В программе: LD - команда загрузки операнда из памяти в регистр; MP, SUB, ADD - команды умножения, вычитания и сложения соответственно; ST - команда записи операнда из регистра в память.

Состояние некоторых регистров при выполнении программы показано в табл. 2.1. В последней колонке таблицы приведен порядок запуска команд на исполнение. В частности, видно, что некоторые команды могут опережать по запуску команды, находящиеся в программе выше запущенной. Например, команды 4 и 5 выполняются ранее команды 3. Это возможно благодаря наличию в программе локального параллелизма и нескольких АЛУ в структуре процессора. Однако подобные "обгоны" не должны нарушать логики исполнения программы, задаваемой ее ИГ (рис. 2.12). Любая операция согласно рисунку может быть запущена только после того, как подготовлены соответствующие операнды. Это достигается путем запрета доступа в определенные РОН до окончания операции, в которой участвуют данные РОН. Состояния РОН отражены в специальном БС РОН.

Рис. 2.12. Информационный граф программы: Ri - регистр общего назначения

В табл. 2.1 приведено также описание нескольких тактов работы процессора. Принято, что выборка операнда из ЦМП занимает четыре такта. Кроме того, считается, что за один такт процессора устройство управления запускает на исполнение одну команду или просматривает в программе до четырех команд.

Таблица 2.1.

Порядок исполнения программы в скалярном конвейере

Сделаем пояснения к таблице.

Такт 1. Анализ БС РОН показывает, что все РОН свободны, поэтому команда 1 запускается для исполнения в ЦМП. В столбец R0 записывается 4, что означает: R0 будет занят четыре такта. После исполнения каждого такта эта величина уменьшается на единицу. В структуре процессора занятость R0 описывается установкой разряда R0 БС РОН в 1, а затем сброс R0 в 0 по сигналу с шины 4, который появляется в такте 4 после получения операнда из памяти.

Такт 2. Запускается команда 2 и блокируется регистр R1.

Такт 3. Просматривается команда 3, она не может быть выполнена, так как после анализа БС РОН нужные для ее исполнения регистры R0 и R1 заблокированы. Команда 3 пропускается, а ее номер записывается в УПК. Производится анализ условий запуска следующей (по состоянию СчК) команды. Команда 4 может быть запущена и запускается.

Такт 4. Просмотр БК начинается с номера команды, записанной в УПК. Команда 3 не может быть запущена, поэтому запускается команда 5.

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

Такт 6. Запускается команда 3.

В дальнейшем процесс происходит аналогично. Можно заметить, что за 10 тактов, описанных в табл. 2.1, в процессоре запущено семь команд, что соответствует 10/7 " 1,5 такта на команду. Предположим, что такт процессора равен 10 нс. Тогда на выполнение одной команды тратится 15 нс, что соответствует быстродействию V = 70 млн оп/с.

Составлено по материалам книги Г.И. Шпаковский. Организация параллельных ЭВМ и суперскалярных процессоров