В начало

Мультискалярные процессоры (Лекция)

 

ПЛАН ЛЕКЦИИ

– Мультискалярная модель выполнения программы

– Мультискалярные программы

– Мультискалярные аппаратные средства

– Преимущества мультискалярной архитектуры

 

Мультискалярная модель выполнения программы

Мультискалярные процессоры используют агрессивную парадигму выполнения кода с целью извлечения параллелизма уровня команд из последовательной программы, представленной на языке высокого уровня. В соответствии с данной парадигмой программа разбивается на совокупность задач с помощью программных и аппаратных средств. Задача - часть программы, выполнению которой соответствует непрерывная область динамической последовательности команд (например, часть базисного блока, базисный блок, множество базисных блоков, одиночная итерация цикла, полный цикл, обращение к функции, и т.д.). Задачи программы статически разграничиваются аннотациями. Зависимости между операторами программы по управлению представляются как граф управляющих зависимостей (ГУЗ), в котором вершинами являются задачи, а дугами задается порядок их выполнения. Динамика выполнения программы может рассматриваться как обход ГУЗ программы. На каждом шаге обхода мультискалярный процессор назначает одну задачу на один из процессорных элементов (ПЭ) для выполнения, без учета фактического содержания задачи, и продолжает обход ГУЗ от рассматриваемой вершины до следующей.

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

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

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

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

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

Рис. 1. Микроархитектура мультискалярного процессора

 

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

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

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

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

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

Из-за спекулятивного характера мультискалярное выполнение должно иметь как средства подтверждения правильности выполнения, так и средства исправления в случае неправильного выполнения. Выполнение команд внутри задач может рассматриваться как спекулятивное с двух точек зрения:

• спекулятивное по управлению;

• спекулятивное по данным.

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

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

 

Мультискалярные программы

Мультискалярная программа должна обеспечить возможность быстрого обхода ее ГУЗ, в результате которого производится распределение множества задач по множеству процессоров.

Спецификация кода для каждой задачи стандартна. Задача определяется как фрагмент программы для последовательной машины. Хотя система команд, в которой представляется код, оказывает влияние на конструкцию каждого индивидуального процессора, это не оказывает влияния на остальную часть конструкции мультискалярного процессора.

Для ускорения обхода ГУЗ планировщику мультискалярного процессора требуется информация о структуре потока управления программы. В частности, требуется знать, какие задачи являются возможными преемниками любой данной задачи в ГУЗ. Планировщик мультискалярного процессора использует эту информацию для предсказания одной из возможных задач-преемников и продолжения обхода ГУЗ, начиная с текущей отметки. Такая информация может быть определена статически и помещена в описатель задачи. Описатели задачи могут быть расположены внутри текста программы (например, перед кодом задачи) или помещены отдельно, рядом с текстом программы (например, в конце).

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

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

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

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

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

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

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

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

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

Разделение исполнительного кода и описателей позволяет упростить процедуру перенесения программы на другие аппаратные средства.

 

Мультискалярные аппаратные средства

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

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

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

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

 

Преимущества мультискалярной архитектуры

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

При стандартном подходе точность предсказания ветвлений ограничивает степень параллелизма. Если средняя вероятность правильного предсказания перехода - 0,9, то вероятность правильного предсказание на пять ветвлений вперед только 0,6.

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

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

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

Для одновременной выдачи n результатов в процессоре должна использоваться логика со сложностью n², чтобы выполнить перекрестную про­верку зависимостей среди команд. В суперскалярном процессоре, это ограничивает пропускную способность логики выдачи. В мультискалярном процессоре каждый ПЭ выдает команды независимо, т.е. используется сложность логики порядка n.

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

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

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

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

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

Изложенный выше подход не является единственно возможным при реализации этой плодотворной идеи - привлечения компилятора к распределению заданий по ПЭ и балансировке загрузки процессоров в многопроцессорных системах.