ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2021
Просмотров: 223
Скачиваний: 2
В каждом поле может содержаться число, начиная с нуля. Поле «Уровень итерации» хранит порядковый номер текущей итерации цикла; поле «Имя функции» идентифицирует вызов функции; поле «Индекс» указывает на определенный элемент массива. Первые два поля могут быть объединены в одно.
Индивидуальные поля тега трактуются как числовые значения, пересылаемые от одной вершины к другой. Минимальным требованием к динамической потоковой ВС является наличие операций, позволяющих извлечь значение, содержащееся в каждом поле, или установить в любом поле иное значение. Например, операция «Прочитать поле токена» берет токен и формирует из него другой токен, где определенное поле заполнено содержимым аналогичного поля из входного токена. Операция «Установить поле токена» формирует выходной токен, совпадающий с входным, за исключением указанного поля, куда заносится значение, заданное в данной операции в виде литерала. Применительно к полю «Уровень итерации» могут быть предусмотрены операции инкремента и декремента.
Основное преимущество динамических потоковых систем – это более высокая производительность, достигаемая за счет допуска присутствия на дуге множества токенов. При этом, однако, основной проблемой становится эффективная реализация блока, который собирает токены с совпадающим цветом (токены с одинаковыми тегами). В плане производительности этой цели наилучшим образом отвечает ассоциативная память. К сожалению, такое решение является слишком дорогостоящим, поскольку число токенов, ожидающих совпадения тегов, как правило, достаточно велико. По этой причине в большинстве вычислительных систем вместо ассоциативных запоминающих устройств (ЗУ) используются обычные адресные ЗУ.
В последнее время все более популярной становится другая организация динамической потоковой ВС, позволяющая освободиться от ассоциативной памяти и известная как архитектура с явно адресуемыми токенами.
Значительным шагом в архитектуре потоковых ВС стало изобретение механизма явной адресации токенов (explicit token-store), имеющего и другое название – непосредственное согласование (direct matching). В основе этого механизма лежит то, что все токены в одной и той же итерации цикла и в одном и том же вхождении в реентерабельную процедуру имеют идентичный тег (цвет). При инициализации очередной итерации цикла или очередном обращении к процедуре формируется так называемый кадр токенов, содержащий токены, относящиеся к данной итерации или данному обращению, то есть с одинаковыми тегами. Использование конкретных ячеек внутри кадра задается на этапе компиляции. Каждому кадру выделяется отдельная область в специальной памяти кадров (frame memory), причем раздача памяти под каждый кадр происходит уже на этапе выполнения программы.
В схеме с явной адресацией токенов любое вычисление полностью описывается указателем команды (IP, Instruction Pointer) и указателем кадра (FP, Frame Pointer). Этот кортеж <FP, IP> входит в тег токена.
Команды, реализующие потоковый граф, хранятся в памяти команд и имеют формат: Код операции • Индекс в памяти кадров • Адресат.
Здесь «Индекс в памяти кадров» определяет положение ячейки с нужным токеном внутри кадра, то есть какое число нужно добавить к FP, чтобы получить адрес интересующего токена. Поле «Адресат» указывает на местоположение команды, которой должен быть передан результат обработки данного токена. Адрес в этом поле также задан в виде смещения – числа, которое следует прибавить к текущему значению IP, чтобы получить исполнительный адрес команды назначения в памяти команд. Если потребителей токена несколько, в поле «Адресат» заносится несколько значений смещения.
Типовая архитектура системы с явной адресацией токенов показана на рис. 9.
Рис. 9. Архитектура системы с явной адресацией токенов
При этом функция согласования токенов является достаточно короткой операцией, что позволяет внедрить ее в виде нескольких ступеней процессорного конвейера.
Макропотоковые вычислительные системы
Механизм обработки с управлением от потока данных функционирует на уровне команд поэтому данному подходу сопутствуют большие издержки при пересылке операндов. Для уменьшения коммуникационных издержек применяется потоковая обработка на процедурном уровне или макропотоковая обработка (multithreading).
Макропотоковая модель совмещает локальность программы, характерную для фон-неймановской модели, с толерантностью к задержкам на переключение задач, свойственной потоковой архитектуре. Это достигается за счет того, что вершина графа представляет собой не одну команду, а последовательность из нескольких команд, называемых нитью (thread). По этой причине макропотоковую организацию часто именуют крупнозернистой потоковой обработкой (coarsegrained dataflow). Макропотоковая обработка сводится к потоковому выполнению нитей, в то время как внутри отдельной нити характер выполнения фон-неймановский. Порядок обработки нитей меняется динамически в процессе вычислений, а последовательность команд в пределах нити определена при компиляции статически. Структура макропотоковой ВС представлена на рис. 10.
Рис. 10. Структура ПЭ макропотоковой системы
Существенное отличие макропотоковой системы от обычной потоковой ВС состоит в организации внутреннего управляющего конвейера, где последовательность выполнения команд задается счетчиком команд, как в фон-неймановских машинах. Иными словами, этот конвейер идентичен обычному конвейеру команд.
В макропотоковой архитектуре каждый узел графа представляет команду, состоящую из нитей. Если команда приостанавливается, останавливается и соответствующая нить, в то время как выполнение других нитей может продолжаться.
Существуют две формы макропотоковой обработки: без блокирования и с блокированием. В модели без блокирования выполнение нити не может быть начато, пока не получены все необходимые данные. Будучи запущенной, нить выполняется до конца без приостановки. В варианте с блокированием запуск нити может быть произведен до получения всех операндов. Когда требуется отсутствующий операнд, нить приостанавливается (блокируется), а возобновление выполнения откладывается на некоторое время. Процессор запоминает всю необходимую информацию о состоянии и загружает на выполнение другую готовую нить. Модель с блокированием обеспечивает более мягкий подход к формированию нитей (часто это выражается в возможности использования более длинных нитей) за счет дополнительной аппаратуры для хранения блокированных нитей. Возможна также и потоковая обработка переменного уровня, когда узлы соответствуют как простым операциям, так и сложным последовательным процедурам. Последний случай иногда называют комбинированной обработкой с потоками данных и потоками управления (combined dataflow/control flow).
Гиперпотоковая обработка
В основе гиперпотоковой технологии (hyperthreading), разработанной фирмой Intel и впервые реализованной в микропроцессоре Pentium 4, лежит то, что современные процессоры в большинстве своем являются суперскалярными и многоконвейерными, то есть выполнение команд в них идет параллельно, по этапам и на нескольких конвейерах сразу. Гиперпотоковая обработка призвана раскрыть этот потенциал таким образом, чтобы функциональные блоки процессора были бы максимально загружены. Поставленная цель достигается за счет сочетания соответствующих аппаратных и программных средств.
Выполняемая программа разбивается на два параллельных потока (threads). Задача компилятора (на стадии подготовки программы) и операционной системы (на этапе выполнения программы) заключается в формировании таких последовательностей независимых команд, которые процессор мог бы обрабатывать параллельно, по возможности заполняя функциональные блоки, не занятые одним из потоков, подходящими командами из другого, независимого потока.
Операционная система, поддерживающая гиперпотоковую технологию, воспринимает физический суперскалярный процессор как два логических процессора и организует поступление на эти два процессора двух независимых потоков команд.
Процессор с поддержкой технологии hyperthreading эмулирует работу двух одинаковых логических процессоров, принимая команды, направленные для каждого из них. Это не означает, что в процессоре имеются два вычислительных ядра – оба логических процессора конкурируют за ресурсы единственного вычислительного ядра. Следствием конкуренции является более эффективная загрузка всех ресурсов процессора.
В процессе вычислений физический процессор рассматривает оба потока команд и по очереди запускает на выполнение команды то из одного, то из другого, или сразу их двух, если есть свободные вычислительные ресурсы. Ни один из потоков не считается приоритетным. При остановке одного из потоков (в ожидании какого-либо события или в результате зацикливания) процессор полностью переключается на второй поток. Возможность чередования команд из разных потоков составляет принципиальное отличие между гиперпотоковой и макропотоковой обработкой.
Эффективность технологии hyperthreading зависит от работы операционной системы, поскольку разделение команд на потоки осуществляет именно она.
В настоящий момент аппаратная поддержка технологии заложена в микропроцессоры Pentium 4, причем, по информации Intel, в процессоре Pentium 4 Хеоn это потребовало 5% дополнительной площади на кристалле. Программная поддержка технологии предусмотрена в операционных системах Windows 2000, Windows XP и Windows .NET Server (в предшествующих ОС Windows такая возможность отсутствует).
3. ВС с управлением вычислениями по запросу
В системах с управлением от потока данных каждая команда, для которой имеются все необходимые операнды, немедленно выполняется. Однако для получения окончательного результата многие из этих вычислений оказываются ненужными. Отсюда прагматичным представляется иной подход, когда вычисления инициируются не по готовности данных, а на основе запроса на данные. Такая организация вычислительного процесса носит название управления вычислениями по запросу (demand-driven control). В ее основе, как и в потоковой модели (data-driven control), лежит представление вычислительного процесса в виде графа. В потоковой модели узлы вверху графа запускаются раньше, чем нижние. Это – нисходящая обработка. Механизм управления по запросу состоит в обработке вершин потокового графа снизу вверх путем разрешения запуска узла, лишь когда требуется его результат. Данный процесс получил название редукции графа, а ВС, оперирующая в режиме снизу вверх, называется редукционной вычислительной системой.
Математическую основу редукционных ВС составляют лямбда-исчисления, а для написания программ под такие системы нужны так называемые функциональные языки программирования (FP, Haskell и др.). На функциональном языке все программы представляются в виде выражений, а процесс выполнения программы заключается в определении значений последних (это называется оценкой выражения). Оценка выражения производится посредством повторения операции выбора и упрощения тех частей выражения, которые можно свести от сложного к простому (такая часть выражения называется редексом, причем сам редекс также является отдельным выражением). Операция упрощения называется редукцией. Процесс редукции завершается, когда преобразованное редукцией выражение больше не содержит редекса. Выражение, не содержащее редекса, называется нормальной формой.
В редукционной ВС вычисления производятся по запросу на результат операции. Предположим, что вычисляется выражение: a=(b+1) c - d/c. В случае потоковых моделей процесс начинается с самых внутренних операций, а именно с параллельного вычисления (b + 1) и d/c. Затем выполняется операция умножения (b + 1) с и, наконец, самая внешняя операция – вычитание.
При вычислениях, управляемых запросами, все начинается с запроса на результат а, который включает в себя запрос на вычисление выражений (b+1) с и d/c, а те, в свою очередь, формируют запрос на вычисление b+ 1, то есть на операцию самого внутреннего уровня. Результат возвращается в порядке, обратном поступлению запросов.
Редукционные вычисления, естественно, согласуются с концепцией функционального программирования, упрощающей распараллеливание программ.
На рис. 11 показан процесс вычисления с помощью редукционной ВС значения выражения а = b - c(b = d + e, с = fg) для d =1, e = 3, f= 5, g = 7. Программа редукции состоит из распознавания редексов с последующей заменой их вычисленными значениями. Таким образом, вся программа в конечном итоге редуцируется до результата.
Рис. 11. Пример вычисления выражения на редукционной ВС
Известны два типа моделей редукционных систем: строчная и графовая, отличающиеся тем, что именно передается в функцию – скопированные значения данных или же только указатели, указывающие на места хранения данных.
В строчной редукционной модели каждый запросивший узел получает отдельную копию выражения для собственной оценки. Длинное строковое выражение рекурсивным образом сокращается (редуцируется) до единственного значения. Каждый шаг редукции содержит оператор, сопровождаемый ссылкой на требуемые входные операнды. Оператор приостанавливается, пока оцениваются входные параметры.
На рис. 12 показан процесс вычислений с помощью строчной редукции.
Рис. 12. Процесс вычислений в модели со строчной редукцией
Если требуется значение а = (b + с) (b - с) (рис. 12, а), то копируется граф программы, определяющий вычисление а (рис. 12, б). При этом запускается операция умножения. Поскольку это вычисление невозможно без предварительного расчета двух параметров, то запускаются вычисления «+» и «-», в результате чего образуется редуцированный граф (с ветвями «6» и «2») (рис. 12, в). Результат получается путем дальнейшей редукции (рис. 12, г).
В графовой редукционной модели выражение представлено как ориентированный граф. Граф сокращается по результатам оценки ветвей и подграфов. В зависимости от запросов возможно параллельное оценивание и редукция различных частей графа или подграфов. Запросившему узлу, который управляет всеми ссылками на граф, возвращается указатель на результат редукции. «Обход» графа и изменение ссылок продолжаются, пока не будет получено значение результата, копия которого возвращается запросившей команде.