2.1.11. Специфика мультитредовых моделей распараллеливания

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

Базисный блок – это основной элемент микропроцессора Kin. В нём находится последовательность команд преобразования данных в регистрах и памяти, которая извлекается и декодируется устройством выборки команд. Далее в блоках переименования регистров устраняются лишние зависимости по данным, потом команды направляются в блок организации внеочередного исполнения. Затем команды поступают в резервирующие станции, в которых они находятся пока не будут готовы операнды для начала исполнения в функциональных блоках. В них происходит интерпретация арифметических и логических команд, выполнение команд обращения к памяти. Результаты исполнения отправляются в резервирующие станции, в блок внеочередного исполнения команд или в блок предвыборки команд.

Блок предвыборки команд используется для предсказания переходов. Он использует «жадную предвыборку команд»: после извлечения команды из кэш-памяти декодированных команд он приписывает им динамический тег, обозначающий трассу, которой принадлежит команда, при этом он может доставать команды из разных кэш-строк памяти как по направлению перехода, так и по направлению отсутствия перехода. Поэтому при определении значения предиката команды перехода нужно удалить результаты неверно предвыбранных команд и сами эти команды. Для этого используется динамический тег, генерируемый в ходе исполнения команд перехода. Например, если команда имела в теге трассу v, то предвыбранные команды одного направления получат трассу v1, а другого – v8. Поэтому при каждом определении направления перехода можно найти все ошибочные команды.

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

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

Выполняемая программа разбивается на программные модули. Используются при этом различные критерии, например, функциональную законченность модуля и т. д. Наиболее приемлемым для рассматриваемого случая является обеспечение минимума обмена информацией между модулями. Это связано с тем, что изучаемая в данном курсе лекций ВС является критичной к объёмам передаваемой или получаемой информации. Задача разбиения программы на модули является достаточно сложной, и обычно решается разработчиком программ на интуитивном уровне в соответствии с возникающими требованиями.

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