ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.12.2021
Просмотров: 2459
Скачиваний: 7
Вычислительные системы с управлением вычислениями от потока данных 6 3 1
положенные между основными ступенями конвейера. Применяемое здесь разде-
ление ресурсов можно условно назвать статическим: каждая буферная память (оче-
дедь) разбивается пополам, и за каждым логическим процессором закрепляется
своя половина очереди.
Применительно к другому виду очередей — очередям диспетчеризации команд
(их в процессоре три) — можно говорить о динамическом разделении. Вместо того
чтобы из предусмотренных в каждой очереди двенадцати входов фиксировано на-
значить входы 0-5 логическому процессору (ЛП) 0, а входы 6-11 — логическому
процессору 1, каждому ЛП разрешается использовать любые входы очереди, лишь
бы их общее число не превысило шести.
С позиций логического процессора и потока между статическим и динамичес-
ким разделением нет никакой разницы — в обоих случаях каждому ЛП выделяет-
ся своя половина ресурса. Различие становится существенным, если в качестве
отправной точки взять физический процессор. Отсутствие привязки потоков к кон-
кретным входам очереди позволяет не принимать во внимание, что имеются два
потока, и расценивать обе половины как единую очередь. Очередь диспетчериза-
ции команд просто просматривает каждую команду в общей очереди, оценивает
зависимости между командами, проверяет доступность ресурсов, необходимых для
выполнения команды, и планирует команду к исполнению. Таким образом, выда-
ча команд на исполнение не зависит от того, какому потоку они принадлежат. Ди-
намическое разделение очередей диспетчеризации команд предотвращает моно-
полизацию очередей каким-либо одним из логических процессоров.
Завершая обсуждение разделяемых ресурсов, отметим, что если процессор Хеоп
обрабатывает только один поток, то для обеспечения максимальной производи-
тельности этому потоку предоставляются все ресурсы процессора. В динамически
разделяемых очередях снимаются ограничения на количество входов, доступных
одному потоку, а в статических разделяемых очередях отменяется их разбиение на
две половины.
Совместно используемые ресурсы.
Этот вид ресурсов в гиперпотоковой тех-
нологии считается определяющим. Чем больше ресурсов могут совместно исполь-
зовать логические процессоры, тем большую вычислительную мощность можно
«снять» с единицы площади кристалла процессора. Первую группу общих ресур-
сов образуют функциональные (исполнительные) блоки: целочисленные опера-
ционные устройства, блоки операций с плавающей запятой и блоки обращения
(чтения/записи) к памяти. Эти ресурсы "не знают", из какого ЛП поступила ко-
манда. То же самое можно сказать и о регистровом файле — втором виде совмест-
но используемых ресурсов.
Сила гиперпотоковой технологии — общие ресурсы — одновременно является
и ее слабостью. Проблема возникает, когда один поток монополизирует ключевой
ресурс (такой, например, как блок операций с плавающей запятой), чем блокирует
другой поток, вызывая его остановку. Задача предотвращения таких ситуаций воз-
лагается на компилятор и операционную систему, которые должны образовать
потоки, состоящие из команд с максимально различающимися требованиями к сов-
местно используемым ресурсам. Так, один поток может содержать команды, нуж-
дающиеся главным образом в блоке для операций с плавающей запятой, а дру-
6 3 2 Глава 15. Потоковые и редукционные вычислительные системы
гой — состоять преимущественно из команд целочисленной арифметики и обра-
щения к памяти,
В заключение необходимо остановиться на третьем виде общих ресурсов — кэш-
памяти. Процессор Хеоп предполагает работу с кэш-памятью трех уровней (LI, L2
и L3) и так называемой кэш-памятью трассировки. Оба логических процессора
совместно используют одну и ту же кэш-память и хранящиеся в ней данные. Если
поток, обрабатываемый логическим процессором 0, хочет прочитать некоторые
данные, кэшированные логическим процессором 1, он может взять их из общего
кэша. Из-за того, что в гиперпотоковом процессоре одну и ту же кэш-память ис-
пользуют сразу два логических процессора, вероятность конфликтов и, следова-
тельно, вероятность снижения производительности возрастает.
Любой вид кэш-памяти одинаково трактует все обращения для чтения или за-
писи, вне зависимости от того, какой из логических процессоров данное обраще-
ние производит. Это позволяет любому потоку монополизировать любой из кэ-
шей, причем никакой защитой от монополизации, как это имеет место в случае
очередей диспетчеризации команд, процессор не обладает. Иными словами, физи-
ческий процессор не в состоянии заставить логические процессоры сотрудничать
при их обращении к кэшам.
В целом, среди совместно используемых ресурсов в технологии hyperthreading
кэш-память оказывается наиболее критичным местом, и конфликты за обладание
этим ресурсом сказываются на общей производительности процессора наиболее
ощутимо.
По оценке Intel, прирост скорости вычислений в некоторых случаях может до-
стигать 25-35%. В приложениях, ориентированных на многозадачность, програм-
мы ускоряются на 15-20%. Возможны, однако, ситуации, когда прирост в быстро-
действии может быть незаметен и даже быть отрицательным. Таким образом,
эффективность технологии находится в прямой зависимости от характера реали-
зуемого программного приложения. Максимальная отдача достигается при работе
серверных приложений за счет разнообразия процессорных операций.
В настоящий момент аппаратная поддержка технологии заложена в микропро-
цессоры Pentium 4, причем, по информации Intel, в процессоре Pentium 4 Хеоп это
потребовало 5% дополнительной площади на кристалле. Программная поддержка
технологии предусмотрена в операционных системах Windows 2000, Windows XP
и Windows .NET Server (в предшествующих ОС Windows такая возможность от-
сутствует).
Вычислительные системы с управлением
вычислениями по запросу
В системах с управлением от потока данных каждая команда, для которой имеют-
ся все необходимые операнды, немедленно выполняется. Однако для получения
окончательного результата многие из этих вычислений оказываются ненужными.
Отсюда прагматичным представляется иной подход, когда вычисления иници-
ируются не по готовности данных, а на основе запроса на данные. Такая организа-
ция вычислительного процесса носит название
управления вычислениями по запросу
Вычислительные системы с управлением вычислениями по запросу 6 3 3
(demand-driven control). В ее основе, как и в потоковой модели (data-driven control),
лежит представление вычислительного процесса в виде графа. В потоковой моде-
ли узлы вверху графа запускаются раньше, чем нижние. Это — нисходящая обра-
ботка. Механизм управления по запросу состоит в обработке вершин потокового
графа снизу вверх путем разрешения запуска узла, лишь когда требуется его ре-
зультат. Данный процесс получил название
редукции графа,
а ВС, оперирующая в
режиме снизу вверх (см, рис. 15.1, г), называется
редукционной вычислительной
системой.
Математическую основу редукционных ВС составляют
лямбда-исчисления
[2,
57,202], а для написания программ под такие системы нужны так называемые функ-
циональные языки программирования (FP, Haskell и др.). На функциональном
языке все программы представляются в виде выражений, а процесс выполнения
программы заключается в определении значений последних (это называется
оцен-
кой выражения).
Оценка выражения производится посредством повторения опе-
рации выбора и упрощения тех частей выражения, которые можно свести от слож-
ного к простому (такая часть выражения называется
редексом,
причем сам редекс
также является отдельным выражением). Операция упрощения называется
редук-
цией.
Процесс редукции завершается, когда преобразованное редукцией выраже-
ние больше не содержит редекса. Выражение, не содержащее редекса, называется
нормальной формой.
В редукционной ВС вычисления производятся по запросу на результат опера-
ции. Предположим, что вычисляется выражение а = (b +1) х с — .В случае пото-
ковых моделей процесс начинается с самых внутренних операций, а именно с па-
раллельного вычисления (b + 1) и
d/c.
Затем выполняется операция умножения
(b
+ 1) х с и, наконец, самая внешняя операция — вычитание. Такой род вычисле-
ний часто называют
энергичными вычислениями
(eager evaluation).
При вычислениях, управляемых запросами, все начинается с запроса на резуль-
тат
а,
который включает в себя запрос на вычисление выражений
(b +
1) х с и
d/c,
а те, в свою очередь, формируют запрос на вычисление b
+
1, то есть на операцию
самого внутреннего уровня. Результат возвращается в порядке, обратном поступ-
лению запросов. Отсюда название
ленивые вычисления
(lazy evaluation), поскольку
операции выполняются только тогда, когда их результат требуется другой команде.
Редукционные вычисления, естественно, согласуются с концепцией функциональ-
ного программирования, упрощающей распараллеливание программ.
На рис. 15.16 показан процесс вычисления с помощью редукционной ВС зна-
чентвырзжешя а =b - с(b =d + е,с=fxg) для d =
1,е = 3,f=5,g=7.Программа
редукции состоит из распознавания редексов с последующей заменой их вычис-
ленными значениями. Таким образом, вся программа в конечном итоге редуциру-
ется до результата.
Известны два типа моделей редукционных систем: строчная и графовая, отли-
чающиеся тем, что именно передается в функцию — скопированные значения дан-
ных или же только указатели, указывающие на места хранения данных.
В
строчной редукционной модели
каждый запросивший узел получает отдель-
ную копию выражения для собственной оценки. Длинное строковое выражение
6 3 4 Глава 15. Потоковые и редукционные вычислительные системы
Рис. 15.16. Пример вычисления выражения на редукционной вычислительной системе:
а
— исходное положение;
б —
после первого шага редукции
рекурсивным образом сокращается (редуцируется) до единственного значения.
Каждый шаг редукции содержит оператор, сопровождаемый ссылкой на требуе-
мые входные операнды. Оператор приостанавливается, пока оцениваются вход-
ные параметры.
На рис. 15.17 показан процесс вычислений с помощью строчной редукции. Если
требуется значение
a=(b + с)
х
(b - с)
(рис. 15.17, я), то копируется граф програм-
мы, определяющий вычисление
а
(рис. 15.17,
6).
При этом запускается операция
умножения. Поскольку это вычисление невозможно без предварительного расче-
та двух параметров, то запускаются вычисления «+» и «-», в результате чего обра-
зуется редуцированный граф (с ветвями «6» и «2»), показанный на рис, 15.17,
в.
Результат получается путем дальнейшей редукции (рис. 15.17, г),
В
графовой редукционной модели
выражение представлено как ориентирован-
ный граф. Граф сокращается по результатам оценки ветвей и подграфов. В зависи-
мости от запросов возможно параллельное оценивание и редукция различных ча-
стей графа или подграфов. Запросившему узлу, который управляет всеми ссылками
на граф, возвращается указатель на результат редукции. «Обход» графа и измене-
ние ссылок продолжаются, пока не будет получено значение результата, копия
которого возвращается запросившей команде.
Рисунок 15.18 иллюстрирует пример вычислений с помощью графовой редук-
ции. В этой модели, когда требуется найти значение
а,
определение вычисления
а
не копируется, а передается указатель определяющей программы. При достиже-
Контрольные вопросы 6 3 5
Рис. 15.17. Процесс вычислений в модели со строчной редукцией:
в
— исходный граф;
б, в
— последовательно редуцированные графы; г— результат редукции
Рис. 15.18. Процесс вычислений в модели с графовой редукцией:
а —
исходный граф;
б, в, г— последовательная редукция со сменой направления указателей;
Л — результат редукции
нии узла «Ч» направление переданного указателя меняется на противоположное,
чтобы запомнить место, из которого будет выдаваться результат вычисления (рису-
нок 15.18,
б).
Далее путем повторения операции смены направления указате-
ля (текущего указателя) на обратное получается граф, показанный на рис. 15.18,
в.
Теперь операции
*+*
и «-» можно выполнять, граф редуцируется сначала до изоб-
раженного на рис. 15.18, г, а затем — на рис. 15.18,5.
Контрольные вопросы
1. Перечислите и охарактеризуйте возможные механизмы управления вычисли-
тельным процессом.
2. В чем состоит идея управления от потока данных?
3. Какие элементарные операторы могут быть взяты в качестве вершин потоко-
вого графа?
4. Каким образом осуществляется передача данных между узлами потокового
графа?