Оптимальное программирование процессоров EPIC-архитектуры

Сортировка с помощью прямого выбора

Общий принцип алгоритма:

Сложность алгоритма составляет $$O(n{}^2 )$$.

В табл. 8.2 показана по шагам сортировка того же массива. Курсивом выделены меняющиеся на каждом шаге местами первый и минимальный элементы неупорядоченной части массива.

Основная процедура, многократно применяемая в алгоритме — процедура нахождения минимального элемента среди уменьшающегося множества элементов.

Рассмотрим эту процедуру отдельно. В ней реализуется операция преобразования вектора (массива) в скаляр, что также соответствует сложению или умножению всех элементов массива. Эта операция является составной частью скалярного умножения, численного интегрирования и т.д. Возможности распараллеливания ограничены информационной связностью промежуточных результатов. Единственно возможная параллельная схема счета — счет способом "пирамиды", при котором производится попарное сравнение и нахождение меньшего элемента внутри пары, затем попарное сравнение результатов первого сравнения и т.д. — до получения окончательного результата. Длина критического пути при реализации всех возможностей распараллеливания (при достаточном количестве ИУ) не менее ]log2n[t, где t — время элементарной, образующей операции (сравнения и возможной пересылки).

При использовании небольшого числа ИУ возможна их практически полная загрузка на всем протяжении счета при наличии средств синхронизации, "страхующих" опережающее использование несформированных данных.

Представим схему счета "пирамидой" при нахождении минимального элемента массива, на основе которой составим план программы для процессора EPIC -архитектуры. Предварительно расширим данный массив, дополнив его n-1 элементами — промежуточными результатами анализа, а также (последний элемент) результатом поиска.

Для схемы счета "пирамидой" не принципиальна четность или степень "двойки" значения n. На рис. 8.1 представлена схема для n = 7.

(рис 8.1) Схема счёта "пирамидой"

Стрелки указывают на направление движения информации, $$\alpha _{1}$$ — $$\alpha _{6}$$ — значения предикатов — результатов попарного сравнения элементов.

Рисунок иллюстрирует простой цикл сравнения и пересылок меньших элементов. Единственным условием правильного выполнения операции является, как говорилось ранее, синхронизация, исключающая использование результата сравнения до окончания его формирования. При длине массива, значительно превышающей количество ИУ, эффективен механизм ожидания рассчитываемого результата, т.е. задержки выполнения команд при попытке считывания до записи. Задержки начнутся только на последнем этапе выполнения "пирамиды".

Однако отметим преимущества принудительного программного решения проблемы синхронизации с помощью команды закрытия адресов по считыванию до окончания записи по этим адресам. Такая команда позволяет предварительно закрыть адреса данных an+1 - a2n-1. Их открытие при записи в ходе выполнения программы обеспечивает правильное выполнение "пирамиды" во времени.

План программы выполнения данной процедуры представлен на рис. 8.2. Иллюстрируется "развернутый" цикл, где ромбами обозначены операции сравнения $$\alpha _{i} = a_{i} < a_{i+1}$$. Пересылки помечены предикатами или их отрицаниями, в соответствии со значениями которых они производятся. Считаем, что значение предиката может быть использовано через два такта, что определяет взаимное смещение пересылок и сравнений при формировании "длинных" командных слов. При формировании программы необходимо учесть организацию цикла, индексацию и т.д. Однако важно отметить, что все ветвление в данном проекте программы выполнено без остановок конвейера.

(рис 8.2) План программы счёта "пирамидой"

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

Пузырьковая сортировка

Алгоритм этой сортировки заключается в последовательном сравнении и смене мест (если необходимо) пар соседних элементов массива. Процесс продолжается до тех пор, пока обмены не прекратятся. Сложность алгоритма также составляет $$O(n{}^2 )$$.

Легко видеть, что последовательный учет результатов предыдущего сравнения (последовательное всплытие "пузырьков") не допускает распараллеливания. Алгоритм нуждается в модификации.

Для эффективного распараллеливания на процессоре EPIC -архитектуры необходимо при одном обзоре массива отделить процедуру сравнения элементов и формирования значений предикатов от процедуры пересылки, т.е. организовать множественное всплытие "пузырьков".

Для этого при каждом обзоре текущее (частично упорядоченное) множество элементов разбивается на пары. При первом (нечетном) обзоре первая пара включает первый элемент массива. При втором (четном) обзоре группирование начинается со второго элемента и т.д. Внутри пар элементы упорядочиваются, при необходимости меняясь местами так, чтобы слева стоял меньший элемент. Наличие обменов при каждом просмотре фиксируется. Их прекращение свидетельствует об окончании сортировки массива.

Ниже по шагам (обзорам) отражена сортировка ранее рассмотренного массива. Формируемые на каждом шаге пары элементов выделены. При четном n нечетные шаги сортировки требуют анализа k = n/2 пар элементов, четные шаги требуют анализа k = (n/2) - 1. При нечетном n k = [n/2] пар элементов.

План программы (внутренний цикл развернут) представлен на рис. 8.3. Здесь $$\alpha _{i} = a_{i(i+1)} < a_{i+1(i+2)}$$ ; индексация выполнена с учетом попеременного формирования пар соседних элементов и с учетом их переименования после пересылки; k — индекс последней анализируемой пары элементов; $$\beta$$ — предикат, принимающий значение "1", если операция, при которой он указан, выполняется. Предполагается, что при выходе за границу массива операция над элементами не производится. Далее предполагается возможность взаимного обмена данными, инициированная в одном командном слове.

(рис 8.3) План программы пузырьковой сортировки

Программа не предполагает использование условных переходов и соответствует "теоретической" сложности, хотя время выполнения алгоритма при данной комплектации АЛУ сокращается почти в четыре раза по сравнению с применением одного ИУ.

Сортировка Шелла

Данный метод относится к "улучшенным". Он предполагает последовательные этапы разбиения исходного массива на несколько групп и их независимую сортировку.

Однако следует с осторожностью относиться к "улучшенным" методам сортировки, требующим значительных подготовительных работ и ориентированным на человека — вычислителя, для которого логический анализ действий не представляется сложным, а потому выносится за область учета трудоемкости. В компьютерной программе должно быть все учтено посредством формализованных действий.

На ранее выбранном массиве продемонстрируем сортировку Шелла.

Сначала выполняется четверная сортировка: группируются и сортируются элементы массива, отстоящие друг от друга на расстоянии 4. Рассматриваемый массив будет разбит на четыре группы элементов: A1 = {6, 4, 5}, A2 = {2, 7, 8}, A3 = {4, 10, 0}, A4 = {3, 9, 1}. Каждая группа сортируется одним из известных способов. Элементы возвращаются в массив с соблюдением тех же начала и расстояния, с которыми они извлекались. Тогда результатом четверной сортировки будет последовательность 4, 2, 0, 1, 5, 7, 4, 3, 6, 8, 10, 9.

На втором проходе элементы полученной последовательности перегруппировываются — теперь каждый элемент группы отстоит от другого на две позиции. В данном случае сформируются две группы: B1 = {4, 0, 5, 4, 6, 10} и B2 = {2, 1, 7, 3, 8, 9}. Сортировка внутри групп ( двойная сортировка) и возвращение в исходный массив на соответствующие места приводят к последовательности 0, 1, 4, 2, 4, 3, 5, 7, 6, 8, 10, 9.

На третьем проходе окончательно производится обычная ( одинарная ) сортировка всей последовательности, при которой число пересылок сведено до минимума.

Исследования по выбору расстояний привели к теоретическому обоснованию оценки сложности алгоритма, как O(n1,2). Эта сложность основана на минимизации требуемых пересылок.

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

Применение данного метода, очевидно, нецелесообразно на процессоре EPIC -архитектуры.

Сортировка с помощью дерева

Алгоритм сортировки предполагает следующие действия.

На рис. 8.4,а представлено двоичное дерево для нахождения минимального элемента 0 в ранее рассмотренном массиве. После исключения этого элемента находится минимальный элемент 1 из оставшихся, как показано на рис. 8.4,б.

После исключения этого элемента, элемент 5, как результат первого уровня сравнений, продвигается в вершину следующего уровня. Минимальный элемент находится, как показано на рис. 8.4,в.

Следующий шаг демонстрируется на рис 8.4,г и т.д. — до полного опустошения дерева.

Данный алгоритм имеет "теоретическую" сложность O(n log2n), рассчитанную на основе оценок числа сравнений и пересылок и не учитывающую обслуживание древовидной структуры. Известно, что графовые структуры, которые для параллельного компьютера на уровне обработки целесообразно представлять матрицами следования, приводят к оценкам сложности не менее $$O(n{}^2 )$$. Очевидно, что программа анализа графического представления отношений между элементами массива сложна и трудоемка, хотя во многом зависит от изощренности программиста. Учитывая информационную связность процесса, многократно использующего "пирамиду" (требуется использование средств синхронизации) при не регулярном расположении элементов (затруднено нахождение сравниваемых элементов при динамически меняющейся структуре дерева), следует высказать сомнение о целесообразности реализации метода на процессоре EPIC -архитектуры.

Быстрая сортировка

Сложность данного алгоритма, учитывающая лишь операции сравнения и пересылки, но не организацию вычислений, составляет O(n log2 n).

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

Представим модификацию алгоритма быстрой сортировки, обеспечивающую простоту программной реализации.

В табл. 8.3 отображен процесс быстрой сортировки рассмотренного ранее массива. На каждом шаге производится преобразование всех сформированных на предыдущем шаге подмножеств (отмечены фигурными скобками), т.е. всего массива. Курсивом выделены элементы, относительно которых производится разбиение подмножеств.

Программу целесообразно планировать на основе циклически запускаемой процедуры разбиения каждого ранее сформированного подмножества вида A и C на три новых, как указано в модифицированном алгоритме. При этом множества вида B пропускаются, так как для их элементов сортировка закончена.

Однако опытный программист здесь может обнаружить "скрытые" пересылки, обусловленные необходимостью "склеивания" динамически формируемых подмассивов, с их неопределенным, переменным началом. Необходимо учесть, что каждое разбиение на подмножества не меняет их суммарную длину. То есть подмножества формируются "на том же месте", и пересылки носят локальный характер внутри одних подмножеств, не нарушая структуру и расположение других.

При организации программы разбиения массива приходится все же пользоваться значительным объемом дополнительной памяти. Только подмассив A может располагаться (накапливаться) с начала разбиваемого массива. Подмассивы B и C, во избежание многократной коррекции расположения, целесообразно накапливать отдельно. При этом начала подмассивов A и B, а также B и C, должны отстоять друг от друга не менее чем на длину разбиваемого массива.

Экономия памяти достигается лишь тем, что после каждого разбиения производится "склейка" массивов A, B и C на месте разбитого массива.

Следует учесть, что каждое расширение используемой памяти приводит к увеличению числа "промахов" при обращении в кэш, а потому нежелательно.

План выполнения основной процедуры разбиения в применении к исходному массиву,в виде "развернутого" цикла, показан на рис. 8.5.

(рис 8.5) План программы быстрой сортировки

Таким образом, разбиение может производиться с использованием дополнительной памяти и продолжаться до вырождения подмножеств, что в конечном итоге приведет к получению упорядоченного массива.

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

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

В этом отношении модифицированная "пузырьковая" сортировка универсальна, проста в реализации и не требует дополнительных ресурсов памяти.

Сортировка методом прямого включения также дает хорошую загрузку исполнительных устройств. Однако необходимость синхронизации пересылок на последнем этапе выполнения основной процедуры нахождения минимального элемента массива методом "пирамиды" может приводить к "разреженности" в выполнении команд во времени, к появлению пропущенных тактов. Следует учесть и необходимое увеличение вдвое объема используемой памяти.

Другие известные методы сортировки, как правило, ресурсоемки и не реализуют "теоретическую" сложность алгоритмов при программной реализации, включая программы процессора EPIC -архитектуры.

Таким образом, отметим, что EPIC -архитектура наиболее приспособлена к реализации двух модифицированных методов сортировки: "пузырьковой" и быстрой. Сложность первой — $$O(n{}^2 )$$, сложность второй, улучшенной, — O(n log2 n). Программная реализация этих методов достаточно проста, затраты на управление выполнением программы (индексация, циклы) минимальны. Принцип предикатных вычислений и спекулятивного режима выполнения операций дает значительный эффект и исключает применение условных переходов. Он позволяет полностью загружать работой исполнительные устройства процессора, обеспечивая высокую эффективность распараллеливания.

Оптимизация предикатных вычислений при решении задач поиска на процессоре EPIC-архитектуры

Выше указывается на существование задач, для которых основным средством решения является механизм ветвления. В процессорах "традиционной" архитектуры ветвление производится с помощью последовательных логических проверок и условных передач управления. Архитектура процессора EPIC -архитектуры предусматривает предикатный механизм, позволяющий хранить условия ветвления — булевы переменные и производить спекулятивные вычисления, т.е. выполнять операции, если указанное при них логическое переменное имеет значение ИСТИНА (1). Это значительно снижает вес условных переходов в программе (хотя и поддержанных запуском дополнительного конвейера), а то и вовсе исключает их.

Если в задачах сортировки используются анализ и пересылки отдельных элементов массива, то в задачах поиска производится совместный анализ "массив с массивом", что значительно затрудняет решение проблемы минимизации числа условных переходов.

Поиск является одним из наиболее часто встречающихся действий при программировании. Отметим важность таких задач, как текстовый анализ, выделение подструктур генетического кода, нормальные алгоритмы Маркова, кусочная аппроксимация временных рядов и др.

Задача поиска формулируется следующим образом.

Заданы массивы A = {a1, ..., an} (текст) и B = b1, ..., bm (слово, эталон). Необходимо найти первое вхождение (индекс i ) в массив A таких следующих подряд m элементов {ai, ai+1, ..., ai+m-1}, что ai+j-1 = bj, j = 1, ..., m.

Прямой поиск

Самый простой алгоритм поиска заключается в последовательном просмотре текста — элементов множества A и их сравнением с первым элементом B. При положительном результате сравниваются следующие элементы массивов и т.д. В случае появления отрицательного результата сравнения дальнейший анализ массива A продолжается со следующего элемента. Сложность этого поиска составляет O(nm).

В табл. 8.4 представлен пример прямого поиска по шагам. Каждый шаг обусловлен переходом, в случае несовпадения элементов, к анализу, начиная со следующего элемента массива A.

На рис. 8.6 представлен план программы прямого поиска. Каждая явно наблюдаемая строка соответствует параллельно выполняемым командам, отображенным в одном "длинном" командном слове. Столбец соответствует одному исполнительному устройству (ИУ). Внутренний цикл попарного сравнения элементов массивов показан в развернутом виде.

(рис 8.6) План программы прямого поиска

Предусмотрено многократное выполнение команды условного перехода на продолжение циклического перебора элементов массива A. Эти команды выполняются в спекулятивном режиме и требуют единственной подготовительной команды запуска дополнительного конвейера. В случае первого несовпадения элементов массива и эталона единственный раз выполняется условный переход.

Начальное смещение команд сравнения выполнено в предположении о необходимости двух тактов для возможного использования результата.

Следует признать высокую эффективность распараллеливания — высокий коэффициент использования ИУ и достижимость "теоретической" сложности алгоритма.

КМП-поиск

Данный алгоритм предложен Д. Кнутом, Д. Морисом и В. Праттом [10] и основан на соображении, что в процессе сравнения накапливается полезная информация, которую можно использовать в последующем поиске, "перескакивая" по тексту вперед. А именно, если произошло совпадение при сравнении текста с несколькими начальными символами слова, а затем последовал отрицательный результат сравнения, то для продолжения поиска необходимо сместиться по тексту на число совпавших символов.

В табл. 8.5 показан пример поиска по данному алгоритму. Совпавшие символы на каждом шаге выделены курсивом. Показано, что в случае совпадения двух символов сдвиг слова для последующего сравнения производится на две позиции.

Однако иллюстрируется упрощенный подход. Действительный алгоритм значительно сложнее и основан на предварительном исследовании слова B — на составлении таблицы значений, определяющих величину сдвига при частичном совпадении символов. Такая обработка слова оправдана при значительных размерах текста и при многократном поиске вхождения слова.

Авторы утверждают, что сложность метода составляет O(n+m).

На рис. 8.7 представлен план программы для упрощенного варианта КМП-поиска. Анализ этого плана показывает, что, несмотря на усложнившуюся логику, возможно получение компактной программы при некоторых допущениях относительно особенностей выполнения операций. Например, считаем, что условный переход, обозначенный в "длинной" команде, выполняется после окончания выполнения всех операций, предусмотренных в этой же команде.

(рис 8.7) План программы КМП-поиска

Структура программы подтверждает принципиальную достижимость "теоретической" сложности упрощенного алгоритма КМП-поиска (она, конечно, выше той, что объявлена авторами). Однако общий случай, требующий расчета специальных таблиц сдвига слова-эталона вдоль текста, приводит к высокой трудоемкости и к сложной логике программы. При существовании других методов полиномиальной сложности использование такого метода нецелесообразно.

О применении БМ-поиска

КМП-поиск дает выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. В этом случае искомое слово (эталон, образ) сдвигается по тексту более чем на одну позицию.

Однако совпадение символов встречается гораздо реже, чем несовпадение. В связи с этим, Р. Буер и Д. Мур предложили [10] метод, где сравнение символов начинается не с начала, а с конца слова. При обнаружении расхождения между словом и текстом слово сдвигается вправо. Для определения длины сдвига, как и в общем случае КМП-поиска, используется ранее построенная таблица. Иногда слово сдвигается вправо на всю свою длину.

Сложность метода имеет порядок O(n).

Для КМП-поиска удается построить упрощенный вариант, допускающий эффективное программирование. Однако указанная сложность БМ-поиска, по-видимому, носит рекламный характер и не учитывает затрат трудоемкости как на предварительную подготовку таблиц, так и на развившуюся логику программы. Реализация противоположных направлений анализа слова и текста, переменной длины их относительного смещения при наличии многих альтернатив порождает программу весьма большого объема и значительного времени выполнения.

Очевидно, что объявленная "теоретическая" сложность алгоритма недостижима даже на параллельном процессоре EPIC -архитектуры.

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

Учитывая высокое быстродействие при развитом параллелизме, а также полиномиальную сложность методов, целесообразно применение таких методов поиска, как прямой поиск и упрощенный КМП-поиск.