Глоссарий
Содержание
1 Временная локальность
Временная локальность показывает среднее число обращений по одному адресу в память за время исполнения всей программы.
2 Граф алгоритма
Граф алгоритма (ГА) — это ориентированный ациклический мультиграф, вершины которого соответствуют операциям алгоритма, а дуги — передаче данных между ними. Вершины ГА могут соединяться несколькими дугами, в частности когда в качестве разных аргументов одной и той же операции используется одна и та же величина. ГА почти всегда является параметризованным графом. В частности, его вид часто зависит от входных данных.
ГА используется как удобное представление алгоритма при исследовании его структуры, ресурса параллелизма, а также других свойств. Его можно рассматривать как параметризованную информационную историю. Он сохраняет её информативность, при это обладая компактностью за счёт параметризации. Разработана методика построения ГА по исходному тексту программ.
См. также: Граф алгоритма
3 Локальность (обращений в память)
Локальность (обращений в память) — общее предположение о свойстве работы программ с данными. Заключается в том, что при обращении к некоторым данным велика вероятность, что в скором времени произойдет повторное обращение к тем же или расположенным рядом данным. В частности, на основе данного предположения построена работа кэш-памяти. Различают локальность команд и использования данных, а также пространственную и временную локальность.
4 Локальность команд
Локальность команд — проекция идеи локальности на конкретный класс данных в памяти – команды, из которых состоят программы.
5 Локальность использования данных
Локальность использования данных — проекция идеи локальности на конкретный класс данных в памяти – все данные, с которыми оперируют программы во время выполнения.
6 Оценка daps
Оценка daps — предлагаемая нами оценка производительности работы с памятью в программе, равна числу выполненных обращений в память в секунду. Построена по аналогии с распространенной оценкой производительности программ — flop/s (floating point operations per second), которая оценивает число операций с плавающей запятой в секунду. Оценка flop/s показывает производительность всей программы с точки зрения производимых вычислений; в то время как daps оценивает производительность программы с точки зрения работы с памятью.
Данная оценка является машинно-зависимой — вычисляется на основе данных аппаратных датчиков. Служит для проверки точности результатов разрабатываемых нами машинно-независимых оценок локальности, таких как cvg.
7 Оценка cvg
Оценка cvg — предлагаемая нами машинно-независимая оценка локальности обращений в памяти в программе.
8 Пространственная локальность
Пространственная локальность отражает среднее расстояние между несколькими последовательными обращениями в память.
9 Профиль обращений в память
10 Ярусно-параллельная форма графа алгоритма
Ярусно-параллельная форма (ЯПФ) — это представление графа алгоритма, в котором:
- все вершины разбиты на перенумерованные подмножества ярусов,
- начальная вершина каждой дуги расположена на ярусе с номером меньшим, чем номер яруса конечной вершины,
- между вершинами, расположенными на одном ярусе, не может быть дуг.
Высота ЯПФ – это число ярусов. Ширина яруса – число вершин, расположенных на ярусе. Ширина ЯПФ – это максимальная ширина ярусов в ЯПФ. Высота ЯПФ ∼ сложность параллельной реализации алгоритма/программы.
Канонической ярусно-параллельной формой называется ЯПФ, высота которой равна длине критического пути + 1, а все входные вершины расположены на первом ярусе. Для заданного графа его каноническая ЯПФ единственна.
См. также:
