Ответы 190 страниц (1184228), страница 24
Текст из файла (страница 24)
При прогоне тестового пакета делаются независимые измерения по каждому отдельному тесту. Обычно такой параметр, как количество запускаемых копий каждого отдельного теста, выбирается исходя из соображений оптимального использования ресурсов, что зависит от архитектурных особенностей конкретной системы. Одной из очевидных возможностей является установка этого параметра равным количеству процессоров в системе. При этом все копии отдельной тестовой программы запускаются одновременно, и фиксируется время завершения последней из всех запущенных программ.
С середины 1994 года SPEC ввела две дополнительные составные оценки: SPECrate_base_int92 и SPECrate_base_fp92, которые накладывает ограничения на используемые компиляторы.
Следует отметить, что SPEC объявила о полном переходе с середины 1996 года на новый (третий) комплект тестов - CINT95, CFP95. Эти тесты удовлетворяют следующим ограничениям и требованиям:
размер кода и данных должен быть достаточно большим, чтобы он гарантированно не размещался целиком в кэш-памяти
время выполнения тестов должно быть увеличено с секунд до минут
используемые фрагменты программ должны быть реалистичными
применение усовершенствованного способа измерения времени
реализация более удобных инструментальных средств
стандартизация требований к компиляторам и методов вызова
Новый комплект тестов состоит из 8 целочисленных программ, написанных на языке Си и 10 программ вещественной арифметики, написанных на Фортране. Новые метрики получили соответствующие названия: SPECint95, SPECfp95, SPECint_base95, SPECfp_base95, SPECrate_int95, SPECrate_fp95, SPECrate_base_int95 и SPECrate_base_fp95.
Закон Амдала.
Предположим, что в вашей программе доля операций, которые нужно выполнять последовательно, равна f, где 0<=f<=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Так вот, для того, чтобы оценить, какое ускорение S может быть получено на компьютере из 'p' процессоров при данном значении f, можно воспользоваться законом Амдала:
Если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (ясно, что 10 получается только в том случае, когда время исполнения параллельной части равно 0).
Посмотрим на проблему с другой стороны: а какую же часть кода надо ускорить (а значит и предварительно исследовать), чтобы получить заданное ускорение? Ответ можно найти в следствии из закона Амдала: для того чтобы ускорить выполнение программы в q раз необходимо ускорить не менее, чем в q раз не менее, чем (1-1/q)-ю часть программы. Следовательно, если есть желание ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение не менее, чем на 99.99% кода, что почти всегда составляет значительную часть программы!
Отсюда первый вывод - прежде, чем основательно переделывать код для перехода на параллельный компьютер (а любой суперкомпьютер, в частности, является таковым) надо основательно подумать. Если оценив заложенный в программе алгоритм вы поняли, что доля последовательных операций велика, то на значительное ускорение рассчитывать явно не приходится и нужно думать о замене отдельных компонент алгоритма.
В ряде случаев последовательный характер алгоритма изменить не так сложно. Допустим, что в программе есть следующий фрагмент для вычисления суммы n чисел:
s = 0
Do i = 1, n
s = s + a(i)
EndDo
(можно тоже самое на любом другом языке)
По своей природе он строго последователен, так как на i-й итерации цикла требуется результат с (i-1)-й и все итерации выполняются одна за одной. Имеем 100% последовательных операций, а значит и никакого эффекта от использования параллельных компьютеров. Вместе с тем, выход очевиден. Поскольку в большинстве реальных программ (вопрос: а почему в большинстве, а не во всех?) нет существенной разницы, в каком порядке складывать числа, выберем иную схему сложения. Сначала найдем сумму пар соседних элементов: a(1)+a(2), a(3)+a(4), a(5)+a(6) и т.д. Заметим, что при такой схеме все пары можно складывать одновременно! На следующих шагах будем действовать абсолютно аналогично, получив вариант параллельного алгоритма.
Казалось бы в данном случае все проблемы удалось разрешить. Но представьте, что доступные вам процессоры разнородны по своей производительности. Значит будет такой момент, когда кто-то из них еще трудится, а кто-то уже все сделал и бесполезно простаивает в ожидании. Если разброс в производительности компьютеров большой, то и эффективность всей системы при равномерной загрузке процессоров будет крайне низкой.
Но пойдем дальше и предположим, что все процессоры одинаковы. Проблемы кончились? Опять нет! Процессоры выполнили свою работу, но результат-то надо передать другому для продолжения процесса суммирования... а на передачу уходит время... и в это время процессоры опять простаивают...
Словом, заставить параллельную вычислительную систему или супер-ЭВМ работать с максимальной эффективность на конкретной программе это, прямо скажем, задача не из простых, поскольку необходимо тщательное согласование структуры программ и алгоритмов с особенностями архитектуры параллельных вычислительных систем.
Нетрадиционные архитектуры: потоковые и нейронные вычислители.
Принципы потоковой обработки информации.
Такая ситуация сохранялась в программировании примерно до начала 80-х годов прошлого века. Далее, однако, обрабатываемые данные непрерывно усложнялись, пока, наконец, для некоторых задач не превзошли по сложности программы, которые обрабатывали эти данные. Рассмотрим в качестве примера большую базу данных, которая хранит текущее состояние дел некоторого крупного предприятия. Можно сказать, что база данных содержит сложно структурированную, изменяющуюся во времени модель этого предприятия. Программы, обрабатывающие информацию из базы данных (БД) называются обычно системой управления базой данных (СУБД) [20]. СУБД позволяет вводить, удалять и модифицировать данные в БД, а также обрабатывать запросы на поиск и выдачу из БД нужных сведений. Так вот, сколько бы программист не исследовал программы, входящие в СУБД, он практически ничего не узнает о самом предприятии, ни что оно выпускает, ни сколько человек на нём работает и т.д. Очевидно, что в нашей модели предприятия (БД+СУБД) данные играют основную роль, а обрабатывающие их программы – уже второстепенную.
Как Вы можете догадаться, примерно в это же время появилась идея коренным образом изменить архитектуру компьютера так, чтобы отказаться от принципа программного управления. Таким образом, если компьютеры традиционной архитектуры управляются потоком (или потоками) команд, то компьютеры новой, нетрадиционной архитектуры должны управляться потоком данных. Можно сказать, что не команды должны определять, когда какие данные надо обрабатывать, а, наоборот, дан-
ные выбирают для себя действия (операторы), которые в определённый момент надо выполнить над этими данными. Компьютеры такой архитектуры принято называть потоковыми ЭВМ (по-английски DFC – Data Flow Computers) [1,16].
Заметим, что сам по себе принцип потоковой обработки данных не представляет собой ничего загадочного или экзотического. Например, отметим, что уже изученные Вами ранее такие алгоритмические системы, как машина Тьюринга и Нормальные алгоритмы Маркова были обработчиками данных именно этого класса. Действительно, например, в машине Тьюринга именно данные (текущий символ, на который указывает головка), определял, какие именно операции необходимо было выполнить на этом шаге работы!
В то же время оказалось, что архитектура потоковых ЭВМ весьма сложна и сильно отличается от архитектуры традиционных ЭВМ. Например, в устройстве управления таких ЭВМ нет никакого счётчика адреса, а в их памяти нет программы (по крайней мере, в нашем традиционном понимании).
Схемы потоковых вычислителей.
Мы рассмотрим функционирование такой ЭВМ на одном очень простом примере.
Пусть нам необходимо вычислить такой оператор присваивания:
x := (x+y)*p + (x+p)/z - p*y/z
Представим этот оператор в виде так называемого графа потока данных, показанного на рис. 16.1. В этом ориентированном графе есть два вида узлов: это сами обрабатываемые данные, изображённые в виде квадратиков (в нашем примере – значения переменных x,y,z и p) и обрабатывающие элементы потоковой ЭВМ, которые мы обозначили просто знаками соответствующих арифметических операций в кружочках.1 Основная идея потоковых вычислений состоит в следующем. Все действия над данными производят обрабатывающие элементы (операторы), в нашем примере эти элемента обозначены арифметическими операциями сложения, вычитания умножения и деления. Можно сказать, что всё арифметико-логическое устройство потоковой ЭВМ – это набор таких обрабатывающих элементов. Каждый обрабатывающий элемент начинает автоматически выполняться, когда есть в наличие (готовы к обработке) требуемые для него данные. Так, в нашем примере автоматически (и параллельно!) начинают выполняться операторы + , + и * во второй строке нашего графа, затем, на втором шаге работы, параллельно выполняются операторы * , / и / в третьей строке и т.д. Здесь просматривается большое сходство со способом работы электронных схем, составленных из вентилей.
Действительно, если граф потока данных "положить на левый бок", то он будет весьма похож на электронную схему двоичного сумматора, как мы показывали её на рис. 2.2а). При этом роль вентилей будут играть обрабатывающие элементы, а входных и выходных сигналов – обрабатываемые Заметим, что обрабатываемые данные в потоковом компьютере вовсе не являются пассивными, как в ЭВМ традиционной архитектуры, наоборот, они "громко заявляют" о своей готовности к обработке (можно сказать, требуют к себе "внимания" со стороны обрабатывающих элементов). Вообще говоря, здесь есть все основания отказаться от принципа Фон Неймана, согласно которому память только хранит данные, но не обрабатывает их. Другими словами, представляется естественным совместить функции хранения и обработки данных, и разместить обрабатывающие элементы не в арифметико-логическом устройстве, а прямо в оперативной памяти. Вообще говоря, граф потока данных и является "программой" для потоковой ЭВМ, а программ в нашем привычном понимании (запись алгоритма на языке машины) здесь не существует. Можно сказать, что здесь сами данные управляют процессом своей обработки. Отсюда можно сделать вывод, что обычные языки программирования плохо подходят для записи алгоритмов обработки данных в потоковых ЭВМ, так как приходится делать сложный компилятор, преобразующий обычную последовательную программу в граф потока данных. Неудивительно поэтому, что вместе с идеей потоковых ЭВМ появились и специальные языки потоков данных (Data Flow Languages),1 ориентированные на прямое описания графа потока данных [1].
Из рассмотренной схемы обработки данных в потоковых ЭВМ можно сделать вывод, что в них может быть реализован принцип максимального параллелизма в обработке данных, так как любые готовые данные тут же могут поступать на выполнение соответствующему обрабатывающему элементу потоковой ЭВМ. Ясно, что быстрее решить задачу просто невозможно. Немного подумав, можно выделить две фундаментальные трудности, которые встают при реализации потоковой ЭВМ. Во-первых, для достаточно сложного алгоритма невозможно полностью построить граф потока данных до начала счёта. Действительно, алгоритм вводит свои входные данные и содержит условные операторы, выполнение которых может, в частности, зависеть и от этих входных данных. Следовательно, компилятор с некоторого традиционного языка программирования может построить только некоторый первоначальный граф потока данных, а устройство управления потоковой ЭВМ должно будет в процессе счёта динамически изменять этот граф. Ясно, что это весьма
сложная задача для аппаратуры центрального процессора потоковой ЭВМ.
Вторая проблема заключается в том, что арифметико-логическое устройство потоковой ЭВМ должно содержать много одинаковых обрабатывающих элементов. Даже для приведённого нами в качестве примера простейшего графа потока данных нужно по два обрабатывающих элемента для выполнения операций сложения и деления. Для реальных алгоритмов число таких одинаковых обрабатывающих элементов должно исчисляться десятками и сотнями, иначе готовые к счёту данные будут долго простаивать в ожидании освобождения нужного им обрабатывающего элемента, и вся выгода от потоковых вычислений будет потеряна (и тогда ни стоило, как говорится, и огород городить).
Другая трудность заключается здесь в том, что выход каждого обрабатывающего элемента (результат его работы) может быть подан на вход любого другого обрабатывающего элемента. Такие вычислительные системы называются полносвязными. При достаточно большом числе обрабатывающих элементов (а выше мы обосновали, что иначе и быть не может), реализовать все связи между ними становится технически неразрешимой задачей.
Ясно, что перед конструкторами потоковой ЭВМ встают очень большие трудности. В настоящее время универсальные потоковые ЭВМ не нашли широкого применения из-за сложности своей архитектуры, пока существуют только экспериментальные образцы таких ЭВМ. Несколько лучше обстоит дело, если обрабатывающие элементы в потоковых ЭВМ, сделать достаточно сложными, т.е. предназначенными для выполнения крупных шагов обработки данных. В этом случае каждый такой обрабатывающий элемент можно реализовать в виде отдельного микропроцессора, снабженного собственной (локальной) памятью и соответствующей программой (программой в традиционном понимании). Все такие обрабатывающие элементы объединены высокоскоростными линиями связи (шинами), причём каждый элемент начинает работать, как только он имеет все необходимые входные данные. Эти данные могут располагаться в локальной памяти или поступать на линии связи данного обрабатывающего элемента от других обрабатывающих элементов. Идея управления обработки информации потоками данных нашла применение и в таком быстроразвивающемся направлении вычислительной техники, как нейрокомпьютеры.
Дополнение
Классическая архитектура потоковой ВС.
Основными компонентами потоковой ВС являются:
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
