ХАРАКТЕРИСТИКИ ТИПОВЫХ АЛГОРИТМИЧЕСКИХ СТРУКТУР*

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 519.683
ХАРАКТЕРИСТИКИ ТИПОВЫХ АЛГОРИТМИЧЕСКИХ СТРУКТУР*
© 2011 г. Вад.В. Воеводин
Московский госуниверситет им. М.В. Ломоносова vadim@paraПel. т
Поступила в редакцию 12.07.2010
Существует предположение, что во многих предметных областях значительное множество задач построено на основе небольшого числа алгоритмических структур. Поняв, какими свойствами обладают эти структуры, можно будет сделать вывод о свойствах и характеристиках самих задач. В данной работе выделяются основные этапы процесса отображения задачи на некоторую аппаратную платформу и на каждом этапе описываются характеристики, которые определяют эффективность отображения.
Ключевые слова: эффективность программ, типовые алгоритмические структуры, характеристики алгоритмов и программ, процесс отображения алгоритма на платформу.
Введение
Существует предположение, основанное как на нашей собственной практике, так и на опыте других, что во многих предметных областях значительное множество задач построено на основе небольшого числа вычислительных структур [1—3]. В этих структурах сосредоточена основная вычислительная часть задачи. Подобные структуры мы будем называть типовыми алгоритмическими структурами. Примерами таких структур могут служить умножение матриц, скалярное произведение, суммирование элементов массива, БПФ или задача N тел. Причем каждая из этих структур является типовой для некоторой определенной предметной области (или набора областей), например БПФ является типовой структурой в области обработки сигналов.
Если многие задачи построены на основе типовых структур, значит, поняв, как устроены типовые структуры, можно понять, как устроены и эти задачи. А это понимание чрезвычайно важно при построении эффективной реализации задачи на некоторой компьютерной платформе. Понимать, как устроена некоторая структура, -
* Статья рекомендована к публикации программным комитетом Международной научной конференции «Параллельные вычислительные технологии 2010».
это значит понимать, какими важными свойствами данные структуры обладают, какие характеристики их описывают, на какие параметры надо обращать внимание.
Задача состоит в нахождении подхода к формализации понятия типовой алгоритмической структуры и после этого - в нахождении подхода к описанию алгоритмической структуры. Необходимо разработать методы исследования и эффективного отображения этих структур на конкретные классы параллельных систем и на конкретные архитектуры. В настоящий момент можно выделить следующие классы архитектур: реконфигурируемые процессоры - FPGA, графические процессоры - GPU, SMP-системы, кластеры и векторные машины. Эти параллельные платформы наиболее распространены на данный момент, однако нет желания ограничиваться только этими архитектурами, а хочется предусмотреть возможность добавления новых платформ, если таковые понадобятся.
Задача отображения
На рис. 1 приведена общая схема отображения алгоритма на некоторую платформу. Сверху расположены типовые структуры, снизу -конкретные платформы. Хочется отработать путь сверху вниз или, если более конкретно,
Конкретные платформы
Рис. 1. Общая схема отображения типовых алгоритмических структур на вычислительные системы
хочется научиться решать, например, такие задачи:
1. Выявление причин неэффективного отображения типовых структур на некоторую платформу.
2. Упрощение процесса отображения при добавлении новых алгоритмических структур или новых платформ.
3. Оценка верхней границы степени эффективности отображения (в некоторой метрике) определенной структуры на определенную платформу.
4. Определение наиболее подходящей платформы для реализации конкретной структуры.
Изучение процесса отображения структур на платформы позволит постепенно определять и фиксировать алгоритм отображения, поэтому в будущем некоторые шаги будут уже заранее
определены и, возможно, даже будут выполняться автоматически.
Этапы процесса отображения типовой структуры на платформу, в общем, совпадают с этапами процесса написания обычной программы. Однако в данной работе важна не сама схема, отражающая последовательность шагов в процессе отображения алгоритма на архитектуру. Ключевым понятием является эффективность отображения. Мы хотим исследовать качество данного процесса, для чего нужно знать свойства и характеристики используемых объектов: алгоритмов, программ и компьютерных платформ. Какие особенности архитектуры компьютера влияют на эффективность выполнения программы? По каким свойствам алгоритма можно судить о возможности его эффективного отображения на конкретную компьютерную платформу? На эти вопросы нам поможет ответить исследование харак-
теристик объектов, присутствующих на схеме отображения.
Исследуемые свойства и характеристики можно разделить на две группы: те, которые мы можем менять, и те, которые мы менять не можем. К первой группе можно отнести такие характеристики, как число процессов или наличие точек синхронизации в программе, а примером из второй может служить характеристика, указывающая объем входных данных. Характеристики из первой группы определяют свободу при выборе отображения, и изменение их значений приводит к различным вариантам реализации алгоритма. Характеристики из второй группы четко фиксированы и определяют потенциал эффективного отображения, который является показателем того, насколько хорошо в принципе можно отобразить алгоритм на выбранную платформу.
Указанную выше схему в более общем виде можно описать так: изначально задан алгоритм, который затем ложится в основу программы, а написанная и готовая к запуску программа затем исполняется на аппаратуре. Таким образом, в схеме можно выделить три основные составляющие - алгоритм, программа и аппаратура. Каждая из этих составляющих обладает набором характеристик, которые могут влиять на эффективность реализации. Очень важным является то, что характеристики алгоритма и аппаратуры принадлежат ко второй группе, то есть не могут быть изменены, в то время как характеристики программы могут меняться. Это означает, что эффективность отображения зависит только от того, насколько удачно будет сделан выбор значений характеристик программы, который должен быть произведен с учетом характеристик двух других составляющих.
На каждом этапе изначально заложенный в алгоритм «потенциал отображения» (насколько хорошо он может быть распараллелен) может только уменьшаться, поэтому нужно выделить те характеристики алгоритма, которые влияют на эффективность отображения, а также научиться их оценивать и изменять для достижения лучших результатов. Невозможность повысить эффективность отображения при переходе от одного этапа к другому объясняется тем, что с каждым этапом происходит уточне-
ние реализации алгоритма, все больше характеристик и параметров алгоритма четко фиксируется, и это накладывает все больше ограничений. Если рассматривать схему отображения, то на верхнем ее этапе задан только алгоритм и ничего более, поэтому и присутствуют только ограничения самого алгоритма. Затем задается технология программирования, в рамках которой необходимо писать программу, однако сама программа пока не зафиксирована. После написания программы становится гораздо меньше возможностей влиять на способ реализации начального алгоритма, поскольку он фиксируется в коде, и так далее. При этом очень часто нет возможности перейти к следующему этапу без потерь эффективности: например, при написании программы приходится заводить временные переменные и работать с ними, что естественно ведет к таким потерям. Поэтому чрезвычайно важно научиться понимать, какие свойства алгоритма на каждом этапе влияют на эффективность его реализации и какие значения этих характеристик позволяют достигнуть наибольшей эффективности. Общей чертой всех этапов является то, что на каждом из них необходимо учитывать характеристики, которые получены не только на данном этапе, но и на всех предыдущих.
Описание характеристик различных этапов отображения
Перейдем к рассмотрению этапов отображения и выделенных в каждом из них характеристик. Общая схема приведена на рис. 2. Стоит отметить сразу, что данный набор характеристик не является окончательным и будет в дальнейшем дополняться.
Анализ информационной структуры алгоритма. Рассмотрим самый верхний уровень, когда известен только алгоритм, а значит, известна и его информационная структура [4]. Для этого будем использовать граф алгоритма, который полностью отражает информационную структуру. Графом алгоритма называется ориентированный граф, в котором вершины - это множество всех операций алгоритма и из одной вершины идет дуга в другую тогда и только тогда, когда результат операции, вычисляемой в
Рис. 2. Основные характеристики различных этапов отображения типовых алгоритмических структур
первой вершине, является аргументом операции, вычисляемой во второй вершине. Данный граф позволяет оценить целое множество полезных свойств, в частности ресурс параллелизма алгоритма, его параллельную и последовательную сложность, длину критического пути ярусно-параллельной формы графа, ширину и однородность ярусов, общее число операций
[4]; объем входных/выходных данных, отношение числа операций к объему входных/выходных данных и другие. Помимо характеристик графа алгоритма, на данном этапе будут учитываться некоторые другие важные характеристики, такие как тип и разрядность данных, с которыми работает алгоритм. Разрядность важна, например, при работе с графическими процессорами, поскольку использование веществен-
ных чисел с двойной точностью вместо одинарной часто существенно снижает скорость выполнения.
Стоит отметить, что большинство характеристик данного этапа относится к первой группе, то есть нельзя менять их значения, поскольку они являются свойствами исходного алгоритма. Однако характеристики графа алгоритма определяют потенциально возможный параллелизм данного алгоритма, верхнюю границу степени эффективности отображения. Они же могут помочь в принятии решения о том, по какому пути двигаться вниз по схеме отображения. К примеру, если мощность вычислений, то есть отношение общего числа операций к объему входных данных, слишком мала, то можно сделать вывод, что данный алгоритм вряд ли полу-
чится эффективно реализовать на графических процессорах, поскольку передача данных извне на графический процессор осуществляется медленно.
После получения и анализа информационной структуры алгоритма желательно определить, на какую архитектуру исходный алгоритм будет отображаться, и на основании этой информации выбрать технологию программирования, поскольку не все технологии могут хорошо подходить для конкретной архитектуры.
Написание и анализ текста программы. После анализа графа алгоритма и последующего выбора технологии программирования наступает этап написания программы. Здесь накладываются новые ограничения на возможности отображения, поскольку необходимо программировать в рамках выбранной технологии.
Следующий этап - анализ текста программы. На данном этапе представляют интерес такие характеристики, как количество условных переходов и циклов в программе, уровень вложенности циклов; число объявленных переменных, и особенно массивов; характеристики параллельности программы - число нитей/процессов, каким образом они порождаются и т.д.; наличие в коде повторяющихся фрагментов программ (это может быть важно для реконфигурируемых процессоров); количество точек барьерной синхронизации. Такие характеристики, как число циклов и уровень их вложенности, важны потому, что цикл является одним из основных источников параллелизма, и, следовательно, эти характеристики позволяют оценить потенциал распараллеливания в рамках написанной программы. В конце данного этапа определяются некоторые технические аспекты отображения, а именно происходит выбор наиболее подходящего компилятора и его опций, а также определение подключаемых библиотек, если таковые требуются.
Компиляция и исполнение. Далее идет уровень, связанный с компиляцией программы и ее выполнением. Здесь анализируются основные характеристики, касающиеся работы с памятью (локальность данных, необходимый объем памяти, общее число обращений в память), а также коммуникационные характеристики, такие как коммуникационный профиль программы,
объем передаваемых данных, неоднородность пересылок между процессами и т.д.
Одной из важных и интересных для рассмотрения характеристик является локальность данных. Локальность данных определяет, насколько близки последующие обращения в память. В зависимости от типа рассматриваемых объектов, выделяют локальность команд и локальность использования данных. Также различают пространственную и временную локальность. Пространственная локальность отражает среднее расстояние между несколькими последовательными обращениями в память; временная локальность показывает среднее число обращений в память по одному адресу за время исполнения всей программы. Анализ данных характеристик будет проводиться как минимум на двух уровнях, поскольку ясно, что большая часть информации о работе с памятью получается при выполнении программы, но часть информации можно извлечь и на этапе компиляции (можно оценить долю и профиль использования статических массивов).
Локальность использования данных является частью более общей характеристики - работы с памятью. Важным ее свойством, как и свойством некоторых других характеристик, является то, что они оказывают влияние почти на всех этапах отображения. Соответственно, оценивать их значение и влияние необходимо комплексно
и, возможно, с применением отдельного, особого подхода.
Описание аппаратуры и оценка эффективности. Рассмотрим последний этап - выполнение программы. На этапе компиляции заканчивается часть процесса отображения, связанная со статикой, то есть с исследованием статических свойств алгоритма или программы, и на данном этапе начинается динамика - изучение программы во время ее исполнения. Здесь для нас важны аппаратные характеристики вычислительных платформ, для которых мы хотим найти эффективное отображение типовой алгоритмической структуры. Сюда входят такие характеристики, как число процессоров/ядер, тактовая частота процессора, объем и структура ОЗУ и кэш-памяти, суперскалярность, характеристики коммуникационной сети и т.д. Важной особенностью подобных характеристик являет-
Таблица
Описание систем, использованных в экспериментах с «триадой»
Название Тип процессора Частота процессора, GHz Степень супер-скалярности ядра Частота FSB, MHz Пиковая производительность, GFlops
Clovertown1 Xeon 5310 1.6 4 1066 6.4
Clovertown2 Xeon 5345 2.33 4 1333 9.32
Clovertown3 Xeon 5355 2.66 4 1333 10.64
Woodcrest1 Xeon 5150 2.66 4 1333 10.64
Woodcrest2 Xeon 5160 3.0 4 1333 12
Opteron1 Opteron 280 2.4 2 1000 4.8
Opteron2 Opteron 265 1.8 2 1000 3.6
Harpertown Xeon E5472 3.02 4 1600 12
ся то, что мы не можем изменять их значения, они только накладывают ограничения на потенциал эффективного отображения, и это приходится учитывать.
С указанными характеристиками тесно связаны критерии для оценки эффективности отображения. На их основе мы будем оценивать, насколько эффективно написана программа для данной платформы. Это такие критерии, как загрузка процессора, работа с кэш-памятью, загрузка сети и т.д. Они будут сигнализировать о том, что эффективность где-то теряется, а для того чтобы определить, в каком именно месте теряется эффективность, необходимо «подниматься» по схеме отображения по уровням вверх, чтобы понять, какую характеристику надо изменить для достижения большей эффективности. Например, некоторый критерий показывает, что происходит много кэш-промахов. Это значит, что в получившейся программе плохая локальность использования данных. Можно ли это исправить и как? Сначала исследуются характеристики на нижнем уровне, связанные с локальностью данных, однако причина не здесь, значит, надо подниматься вверх; на этапе компиляции тоже все нормально; еще на уровень выше, на этапе написания программы, видно, что надо было написать циклы в другом порядке (или использовать другие структуры данных). После внесения изменений в программе необходимо снова провести анализ характеристик эффективности.
Исследование эффективности реализации типовой структуры «триада»
Рассмотрим на конкретном примере влияние характеристик последнего уровня на эффективность реализации. Возьмем несколько вариаций типовой алгоритмической структуры «триада»:
A[i] = B[i]*X+C, (1)
A[i] = B[i]*X[i]+C, (2)
A[i] = B[i]*X+C[i], (3)
A[i] = B[i]*XH+CW. (4)
Соответственно, переменные X и C в одних вариантах являются скалярами, в других - массивами. Также будем рассматривать различные способы адресации массивов в этих вариантах -прямую и два варианта косвенной, с использованием дополнительного массива индексов ind. В первом варианте ind1[i] = i, во втором ind2[i] = = (i*K)/N+(i*K)%N, где N - длина массива. Первый вариант помогает оценить накладные расходы, привносимые косвенной адресацией, а второй моделирует случай с плохой локальностью данных: константа K подбирается так, чтобы обеспечить максимальный процент кэш-промахов. При этом будем рассматривать самый простой, последовательный вариант решения этой задачи, в котором все исполняется только на одном ядре. При кажущейся простоте поставленной задачи ее анализ позволяет увидеть много интересного. Для реализации был выбран язык С (на ассемблере ничего не писалось), однако выбор языка не так важен в данном эксперименте, поскольку эффективность результатов рассматривалась относительно друг друга. В качестве критерия эффективности использовалось отношение реальной производительности к пиковой.
Для изучения влияния аппаратных характеристик и получения реальных значений эффективности был проведен ряд экспериментов на различных системах. Информация о системах приведена в таблице.
Основные аппаратные характеристики, которые могут оказывать влияние на эффективность последовательной реализации, следующие: тактовая частота ядер, скорость шины FSB (системной шины), частота оперативной памяти, объем ОЗУ на процессор, размер кэшпамяти разных уровней, суперскалярность, наличие векторных операций и т.д.
:{и/1_с11)/(ЕРРс11/ЕРР0
Рис. 3. Влияние характеристики Ь на эффективность реализации структуры «триада»
10
о4

64 МБ
с I overtown 1
clovertown2 ПП clovertown3 S woodcrestl H woodcrest2 ЕЯ harpertown
256 МБ 512 МБ
Размер массива
Рис. 4. Эффективность задачи для процессоров линейки Xeon
Первые две характеристики сами по себе напрямую не определяют эффективность, однако их отношение является очень важным параметром, на который, как мы дальше увидим, нужно обращать внимание при рассмотрении эффективности реализаций. И вот почему: эффективность задачи определяется тем, насколько полно загружен процессор, однако скорость подачи данных по системной шине практически всегда меньше скорости обработки этих данных процессором и, значит, данные просто не будут успевать передаваться по шине процессору. Таким образом, узким местом является пропускная способность системной шины.
Взаимосвязь частоты процессора и частоты системной шины. Будем рассматривать следующую характеристику: Ь = (Fcpu*s)/FfsЬ, где Рсри - частота процессора, 5 - степень суперска-лярности, FfsЬ - частота системной шины. Рассмотрим вариант (1) типовой структуры «триада». В этом варианте идеальным является значение Ь =1, поскольку в таком случае системная шина перестает быть узким местом (можно и меньше 1, но к лучшим результатам это не приведет, поскольку узким местом станет процессор и эффективность остановится на уровне эффективности самого процессора). Однако для многих систем
-с1оуег1о\«п1 -- \лгоос!сге512
- с1оуеПо\«п2 -ор1егоп1 -
-с10Уег10У«13“
-ор1егоп2
-улгооскгеБи
Ьагрег1о\л/п
•©
•©
Г)
(1)А[!]= В[!]*Х + С
(2)А[1]=В[1]*ХШ + С
(3)АШ=ВШ*Х+СШ
(4)А[!]= В[!]*Х[!] + СШ
(5) АрпсВД]] = ВПш)1[Ш*Х+С
(6) А[1пс11[1]] = В[1пс11[1]]*Х[1пс11[1]] + С
(7) А[шс11[1]] = В[тс11[П]*Х + С[тс!1П]]
(8) А[1пс11[!]] = В[тс11[|]]*Х[|П(Л[|]] + С[тсП[Ш
(9) А[та2[Ш = В[та2[1]]*Х + С
(10) А[тЬ2[!]] = В[1г^2[Ш*Х[М2[Ш + С
(11) А[таг[1]] = врпйрп*х+ сппсвд]
(12) А[1п<12[1]] = B[ind2[l]]*X[ind2[i]] + С[1пй2[Ш
Рис. 5. Влияние степени локальности данных на эффективность реализации «триады»
данное значение далеко от идеального. Рассмотрим связь характеристики Ь с эффективностью реализации нашей задачи. Для этого сначала посчитаем эффективность для каждой из систем, а затем посмотрим, как соотносятся значения эффективностей для различных систем и их значения характеристики Ь. Для этого мы считаем отношение эффективностей, деленное на обратное отношение характеристик Ь. Соответственно, чем ближе полученное значение к 1, тем ближе зависимость рассмотренных двух систем от параметра Ь друг к другу. Назовем этот отношение Я, а эффективность будем обозначать Ег, где г - название системы. Приведенные отношения показаны на рис. 3: для каждой системы указано значение отношения Я относительно системы с1оуег1:о—п1. Можно видеть, что для всех рассмотренных систем это значение близко к 1, и, значит, для этих систем имеет место практически прямая зависимость эффективности от значения Ь. Это говорит о том, что изменение эффективности на рассматриваемых процессорах определяется практически исключительно изменением характеристики Ь, что показывает ее важ-
ную роль. Конечно, в других задачах эта зависимость может прослеживаться не столь явно, если обращения в память в них происходят не столь часто.
Из полученного вывода можно вывести интересные следствия. Рассмотрим эффективность для систем с процессорами из одной линейки -Хеоп (рис. 4). У процессоров с1оуеГ;о—п2 и с1оуеГ;о—п3, а также у обоих процессоров -оо^ сге81 одинаковая частота системной шины. При этом увеличение тактовой частоты при переходе от одного к другому не приводит к какому-либо реальному ускорению работы программы, однако увеличивает значение пиковой производительности. Это, в свою очередь, приводит к обратно пропорциональному уменьшению эффективности программы. То есть используя более мощный процессор мы получаем уменьшение эффективности! Похожий эффект можно наблюдать и у процессора Ьагрейо—п - у него и тактовая частота выше, и системная шина быстрее, однако отношение Ь не в его пользу: у Ьагрейо—п это значение равно 7.55, а у с1оуег-;о-п2 - 6.99. Наилучшее значение характеристики Ь из рассматриваемых систем у с1оуег-;о-п1 - 6, что и выражается в наибольшей эф-
фективности. При этом отношение эффективностей с точностью до сотых долей совпадает с отношениями их характеристик Ь.
Кэш-промахи. Теперь рассмотрим примеры, когда работа с кэш-памятью происходит по разным сценариям. Для этого прогоним все 4 варианта задачи со всеми способами адресации и посмотрим изменения эффективности. Соответственно, для каждой системы у нас будет 3 группы значений, по 4 в каждой. Динамика изменений для всех систем похожа, поэтому мы будем говорить безотносительно к какой-либо конкретной системе.
В первой и второй группах результатов кэш-попадание происходило часто, поскольку выборка данных идет последовательная. Основным их отличием является наличие дополнительного массива индексов т^, что и видно на рис. 5: эффективности тех экспериментов, в которых используется одинаковое число массивов (например, эксперименты (2), (3) и
(5) или (4), (6), и (7)), практически равны. Однако в третьей группе экспериментов эффективность падает катастрофически, достигая значений менее 0.2%, - кэш-промахи образуются практически при каждом обращении в память. Данный пример говорит о том, насколько важной характеристикой является локальность использования данных для оценки эффективности реализации.
Заключение
В данной статье рассмотрены некоторые теоретические и практические аспекты процесса выделения характеристик типовой алгоритмической структуры и оценки с их помощью эффективности реализации. На простом примере вычислительного ядра «триада» показано влияние этих характеристик. Этот пример также показывает, что эффективность и простой задачи может зависеть от довольно большого числа различных характеристик и эта зависимость будет становиться все только сложнее с рассмотрением реальных больших задач.
Работа проводилась при поддержке Федерального агентства по науке и инновациям (государственный контракт М 02.740.11.0388), гранта РФФИ № 10-07-00586-а и гранта Президента РФ для молодых ученых МК-3040.2009.9.
Список литературы
1. Воеводин В. В. Вычислительная математика и структура алгоритмов. М: Изд-во МГУ, 2006. 112 с.
2. Asanovic K. et al. The Landscape of Parallel Computing Research: A View from Berkeley. Technical Report № UCB/EECS-2006-183, University of California, Berkeley, Dec. 1S, 2006.
3. Asanovic K. et al. A View of the Parallel Computing Landscape // Communications of the ACM. Nov. 2009. 52, 10. P. 56-67.
4. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.
CHARACTERISTICS OF TYPICAL ALGORITHMIC STRUCTURES
Vad. V. Voevodin
There is an assumption that a large set of tasks in many subject areas is based on a small number of algorithmic structures. Having understood what sort of features these structures have, one can make some conclusions regarding the characteristics and properties of the tasks themselves. In this paper, main stages of the process of task mapping onto a certain hardware platform are identified, and characteristics determining the mapping efficiency are described for each stage.
Keywords: program efficiency, typical algorithmic structures, characteristics of algorithms and programs, mapping of algorithms onto hardware.