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

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

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

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

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

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

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

Рассмотрим приведенный на рисунке 7.6 ГУЗ для фрагмента программы с пятью базисными блоками А, В, С, D и Е. Одна из возможных динамических последовательностей выполнения базисных блоков имеет вид:

В этой последовательности и верхние, и нижние индексы обозначают итерации внешнего и внутреннего циклов соответственно.

Будем рассматривать итерацию внешнего цикла из ГУЗ, приведенного на рисунке 7.6 как сегмент. То есть статические базисные блоки А, В, С и D (так же, как поток управления через них) входят в состав сегмента. Можно назначить сегмент, соответствующий первой итерации внешнего цикла на первый процессор, соответствующий второй итерации цикла – на следующий процессор и т. д. Процессор, которому назначена в качестве сегмента первая итеративная последовательность, выполняет динамические команды базисных блоков .

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

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

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

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

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

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

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

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

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