Глоссарий

1 Временна́я локальность

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

2 Вычислительная мощность

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

3 Вычислительная сложность

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

4 Вычислительное ядро

Вычислительное ядро (computational kernel) алгоритма - это часть алгоритма, на которую приходится основное время его работы.

5 Граф алгоритма

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

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

См. также: Граф алгоритма

6 Детерминированность

Детерминированность (determinacy) алгоритма - постоянство структуры вычислительного процесса. Алгоритм выдаёт уникальный и предопределённый результат для заданных входных данных.

7 Избыточные вычисления

Избыточные вычисления (Redundant computation) - понятие, которое используют для обозначения разных явлений в параллельных вычислениях.

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

8 Конечный параллелизм

Конечный параллелизм (finite parallelism) - параллелизм, определяемый информационной независимостью некоторых фрагментов в тексте программы.

9 Координатный параллелизм

Координатный параллелизм (coordinate parallelism) - частный случай скошенного параллелизма, определяемый циклами ParDO, при котором информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей.

10 Локальность (обращений в память)

Локальность (обращений в память) — общее предположение о свойстве работы программ с данными. Заключается в том, что при обращении к некоторым данным велика вероятность, что в скором времени произойдет повторное обращение к тем же или расположенным рядом данным. В частности, на основе данного предположения построена работа кэш-памяти. Различают локальность команд и локальность использования данных, а также пространственную и временну́ю локальность.

11 Локальность вычислений

Локальность вычислений — проекция идеи локальности на конкретный класс данных в памяти – команды, из которых состоят программы.

12 Локальность использования данных

Локальность использования данных — проекция идеи локальности на конкретный класс данных в памяти – все данные, с которыми оперируют программы во время выполнения.

13 Массовый параллелизм

Массовый параллелизм (mass parallelism) - параллелизм, определяемый информационной независимостью итераций циклов программы.

14 Масштабируемость

Масштабируемость (scalability) - способность системы увеличивать свою производительность при добавлении ресурсов (обычно аппаратных). Система называется масштабируемой, если она способна увеличивать производительность пропорционально дополнительным ресурсам. Масштабируемость можно оценить через отношение прироста производительности системы к приросту используемых ей ресурсов. Чем ближе это отношение к единице, тем масштабируемость лучше.

15 Масштабируемость параллельной программы

Масштабируемость параллельной программы (scalability of parallel program) определяется относительно конкретного компьютера и показывает, как изменяются динамические характеристики данной программы при использовании бóльших вычислительных ресурсов.

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

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

16 Масштабируемость вширь

Масштабируемость вширь (wide scaling) - зависимость производительности R от вычислительной сложности задачи W при фиксированном числе процессоров p (p=const).

17 Оценка daps

Оценка daps — предлагаемая нами оценка производительности работы с памятью в программе, равна числу выполненных обращений в память в секунду. Построена по аналогии с распространенной оценкой производительности программ — flop/s (floating point operations per second), которая оценивает число операций с плавающей запятой в секунду. Оценка flop/s показывает производительность всей программы с точки зрения производимых вычислений; в то время как daps оценивает производительность программы с точки зрения работы с памятью.

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

18 Оценка cvg

Оценка cvg — предлагаемая нами машинно-независимая оценка локальности обращений в памяти в программе. Рассмотрим первые N обращений в потоке («окно»), и затем разобьем ось ординат (виртуальный адрес обращений) на отрезки длины K – [X .. X+K], [X+K .. X+2K], …, [Y-K .. Y], где [X, Y] — диапазон выделенной под рассматриваемые массивы виртуальной памяти. Таким образом, область построения профиля делится на прямоугольники размером KxN.

Физический смысл такого прямоугольника (при правильно подобранных значениях K и N) заключается в том, что любая последовательность точек, попавших в один прямоугольник, всегда обладает хорошей как пространственной, так и временно́й локальностью. Действительно, при достаточно малом значении K в прямоугольник попадает небольшой локальный фрагмент виртуальной памяти, а, значит, соседние обращения по памяти в любом случае будут расположены близко друг относительно друга. А временна́я локальность внутри прямоугольника не может быть больше N, поэтому при достаточно малом N можно обеспечить и хорошую временну́ю локальность. Однако не имеет смысла брать слишком малые значения для K и N, поскольку в этом случае теряется полезная информация о хорошей локальности не попавшего в прямоугольник фрагмента профиля.

Выделим те прямоугольники, в которые попадает хотя бы одно обращение. Чем меньше таких прямоугольников – тем больше точек попало в одни и те же прямоугольники, тем в общем случае лучше локальность. Пример разбиения профиля на прямоугольники приведен на рис. 1. Здесь для иллюстрации выделено три «окна», в каждом по 6 точек. В первом «окне» всего 2 непустых прямоугольника и самая хорошая локальность их трех вариантов. Во втором «окне» задействованы все 4 прямоугольника, при этом в каждый попало лишь по 1-2 обращения. Третье «окно» включает 3 непустых прямоугольника, и в этом варианте локальность лучше, чем у второго «окна», но хуже, чем у первого.

Рисунок 1. Пример разбиения профиля на прямоугольники

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

Далее для каждого «окна» посчитаем число таких непустых прямоугольников (обозначим это число как rects), в результате чего получим последовательность положительных натуральных чисел. Затем посчитаем среднее значение для данной последовательности. Полученное значение назовем оценкой локальности на основе метода покрытий и будем обозначать cvg.

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

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

19 Параллельная сложность

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

20 Параметры запуска

Параметры запуска (startup parameters) параллельной программы — параметры, оказывающие влияние на работу параллельной программы, не влияющие на реализацию алгоритма работы программы (например: размер задачи – a, число процессов – b, размер блока – c, число процессов на узел - d и т.п.) Параметры запуска по типу можно разделить на:

1. Аппаратные – относящиеся к параметрам аппаратуры.
2. Системные – относящиеся к операционной системе, используемым библиотекам и системным приложениям и их настройкам.
3. Программные – влияющие на логику работы программы или вычислительную сложность задачи, различные параметры, предусмотренные разработчиком.

21 Пиковая производительность

Пиковая производительность (peak performance) R_peak — теоретический предел производительности для данного компьютера. Пиковая производительность компьютера вычисляется как сумма пиковых производительностей всех входящих в него вычислительных устройств (процессоров, ускорителей и т.д.). Под пиковой производительностью каждого из вычислительных устройств понимают количество операций в секунду, которые он смог бы теоретически выполнять при полной загрузке всех своих компонент. Надо понимать, что пиковая производительность не только суперкомпьютера, но и, например, любого отдельно взятого процессора является величиной сугубо теоретической, недостижимой на практике.

22 Последовательная сложность

Последовательная сложность (serial complexity) алгоритма - число операций, которые нужно выполнить при его последовательном исполнении.

23 Пространственная локальность

Пространственная локальность отражает среднее расстояние между несколькими последовательными обращениями в память.

24 Производительность

Производительность (performance) R=Op/t определяется количеством операций Op, производимых данным компьютером в единицу времени. Для высокопроизводительных вычислений в расчёт обычно берут количество арифметических операций в секунду над вещественными данными, представленными в форме с плавающей точкой. Эта величина называется Flop/s (от английского Floating point operations per second).

Поскольку современные суперкомпьютеры производят очень много таких операций в секунду, их производительность измеряется кратными величинами, такими как GFlop/s (10⁹ операций в секунду), TFlop/s (10¹²), PFlop/s (10¹⁵). Производительность мощнейших современных суперкомпьютеров уже измеряется десятками PFlop/s, активно идёт обсуждение построения систем экзафлопсного (порядка 10¹⁸ операций в секунду) уровня производительности.

25 Профиль обращений в память

Профиль обращений в память — последовательность выполняемых в программе обращений к данным в памяти, расположенных в том порядке, в котором обращения происходят в программе.

Обозначим профиль обращений A = {A₁,A₂,…,A_N}, где N – общее число всех обращений при выполнении программы. Номер i элемента A_i в профиле указывает, каким по счету является данное обращение от начала выполнения программы. Любой элемент А_i будем называть элементом профиля. Запись А_i означает, что данный элемент имеет i-й порядковый номер; данная запись не содержит никакой информации о том, к какой переменной в программе происходит данное обращение.

На данный момент рассматриваются в основном обращения к массивам, поскольку они являются самыми распространенными структурами данных. Каждое обращение представлено в профиле некоторым числом. Таким образом, профиль обращений представляет собой последовательность чисел, которыми могут являться: 1) индексы элементов массива (если профиль строится только для одного массива); 2) виртуальные адреса, к которым происходят обращения; 3) физические адреса. Естественно, в рамках одного профиля используются числа только одного типа.

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

Рисунок 2. Визуализация профиля обращений в память

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

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

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

26 Реальная производительность

Реальная производительность (real performance) R_max — производительность данного компьютера на конкретном приложении.

27 Сильная масштабируемость

Сильная масштабируемость (strong scaling) - зависимость производительности R от количества процессоров p при фиксированной вычислительной сложности задачи (W=const).

28 Скошенный параллелизм

Скошенный параллелизм (skewed parallelism) - параллелизм в пространстве итераций, определяемый поверхностями уровней разверток.

29 Слабая масштабируемость

Слабая масштабируемость (weak scaling) - зависимость производительности R от количества процессоров p при фиксированной вычислительной сложности задачи в пересчёте на один процессор (W/p=const).

30 Степень исхода

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

31 Суперлинейное ускорение

Суперлинейное ускорение (super linear speedup) или сверхлинейное ускорение программы - это ускорение, превосходящие число используемых процессоров p. Чаще всего объясняется эффектом от использования кэш-памяти.

32 Ускорение

Ускорение (speedup) работы программы S = T₁/T_p - отношение времени работы некоторой программы на одном процессоре T₁ ко времени работы распараллеленной программы при использовании p процессоров T_p.

33 Устойчивость

Устойчивость (stability) алгоритма - свойство алгоритма не увеличивать или увеличивать в незначительной степени погрешности, допущенной в начальных данных или допускаемой при вычислениях.

34 Эквивалентное возмущение

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

35 Эквивалентное преобразование

Эквивалентное преобразование (equivalent transformaion) программы - такое преобразование, при котором в точности сохраняется результат выполнения программы.

36 Эффективность распараллеливания

Эффективность распараллеливания (parallel efficiency) E = S/p (где S - полученное ускорение работы программы, а p - число используемых процессоров) определяет среднюю долю времени выполнения параллельного алгоритма, в течение которого процессоры реально используются для решения задачи. Получение большого ускорения за счёт использования большого числа процессоров зачастую приводит к снижению эффективности.

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

37 Эффективность реализации

Эффективность реализации (implementation efficiency) программы R_max/R_peak определяется как отношение реальной производительности R_max к пиковой производительности R_peak.

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

38 Ярусно-параллельная форма графа алгоритма

Ярусно-параллельная форма (ЯПФ) — это представление графа алгоритма, в котором:

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

Высота ЯПФ – это число ярусов. Ширина яруса – число вершин, расположенных на ярусе. Ширина ЯПФ – это максимальная ширина ярусов в ЯПФ. Высота ЯПФ ∼ сложность параллельной реализации алгоритма/программы.

Канонической ярусно-параллельной формой называется ЯПФ, высота которой равна длине критического пути + 1, а все входные вершины расположены на первом ярусе. Для заданного графа его каноническая ЯПФ единственна.

См. также:

• Ярусно-параллельная форма графа
• Критический путь графа