Структура описания свойств алгоритмов

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

Общая схема описания алгоритмов имеет следующий вид:

1 ЧАСТЬ I. Описание свойств и структуры алгоритмов: общая часть

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

1.1 Словесное описание алгоритма

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

1.2 Математическое описание

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

1.3 Вычислительное ядро алгоритма

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

1.4 Макроструктура алгоритма

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

1.5 Описание схемы реализации последовательного алгоритма

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

1.6 Последовательная сложность алгоритма

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

1.7 Информационный граф

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

1.8 Описание ресурса параллелизма алгоритма

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

1.9 Описание входных и выходных данных

В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма. Векторы, матрицы, скаляры, множества… Плотные или разреженные. Объем. Предположения относительно диапазона значений (например, нули на диагонали, близость к машинному нулю, к максимально представимому числу, характер разреженности и т.п.).

1.10 Свойства алгоритма

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

• соотношение последовательной и параллельной сложности данного алгоритма,
• вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных,
• сбалансированность типов операций,
• детерминированность алгоритма, которая может определяться:
• * числом итераций,
• * структурами данных (например, структура разреженности матриц),
• * использование датчиков случайных чисел,
• * использование другого порядка выполнения ассоциативных операций, что может привести к накоплению ошибок округления.
• особенности семейств дуг информационного графа, регулярность, наличие "длинных" дуг в информационном графе,
• интенсивность работы с данными, степень исхода вершин информационного графа,
• известные компактные укладки графа (что важно, например, для проектирования специализированных процессоров или реализации алгоритма на ПЛИС).

2 ЧАСТЬ II. Описание свойств и структуры алгоритмов: программная реализация

Данная часть рассматривает все составные части процесса реализации описанного выше алгоритма. Реализация последовательная и параллельная. Свойства программы и особенности архитектуры компьютера. Работа с памятью, локальность данных и вычислений. Особенности реализации параллелизма. Свойства параллельных программ: масштабируемость, эффективность. Привязка к классам архитектур.

2.1 Особенности реализации последовательного алгоритма

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

2.2 Описание локальности данных и вычислений

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

2.3 Возможные способы и особенности реализации параллельного алгоритма

Раздел довольно обширный, в котором, в частности, предполагается описывать:

• представленный иерархически ресурс параллелизма, опирающийся на структуру вхождения циклических конструкций и на структуру графа вызовов программы,
• комбинацию (иерархию) массового параллелизма и параллелизма конечного,
• возможные способы распределения операций между процессами/нитями,
• возможные способы распределения данных,
• оценку количества операций, объёма и количества пересылок данных (общего и в пересчёте на процесс).

В дальнейшей работе данный раздел будет дополняться.

2.4 Масштабируемость алгоритма и его реализации

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

2.5 Динамические характеристики и эффективность реализации алгоритма

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

2.6 Выводы для классов архитектур

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

2.7 Существующие реализации алгоритма

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