Locality methodology: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(Новая страница: «# <span style="color:red">Описание локальности алгоритма</span> # Описание локальности реализации алг…»)
 
Строка 12: Строка 12:
 
## Построить графики со сравнением каждой из оценок с реализациями других, типовых алгоритмов (например, Линпак, БПФ, перемножение матриц и т.д.)
 
## Построить графики со сравнением каждой из оценок с реализациями других, типовых алгоритмов (например, Линпак, БПФ, перемножение матриц и т.д.)
 
### По возможности проанализировать положение изучаемой реализации в ранжировании относительно типовых программ. Особенно интересно анализ результатов по сравнению со схожими реализациями (например, сравнение классического и блочного перемножения матриц; рекурсивной и нерекурсивной реализаций; двух реализаций, среди которых одна является значительной частью другого).
 
### По возможности проанализировать положение изучаемой реализации в ранжировании относительно типовых программ. Особенно интересно анализ результатов по сравнению со схожими реализациями (например, сравнение классического и блочного перемножения матриц; рекурсивной и нерекурсивной реализаций; двух реализаций, среди которых одна является значительной частью другого).
 +
 +
 +
== Условия запуска утилиты для сбора профиля и оценок локальности ==
 +
# Описание программно-аппаратной среды
 +
## Платформа: процессор Intel Xeon X5650 @ 2.67GHz
 +
## Размер кэш-памяти (L1/L2/L3): 32K/256K/12M
 +
## Компилятор: gcc version 4.4.7
 +
## Строка компиляции: g++ -O2 -Wall -Wextra -Werror
 +
# Описания параметров запусков
 +
## Размер "окна": 512
 +
## Размер профиля для визуального анализа: < 1 млн. обращений (часто < 100.000)
 +
## Размер профиля для анализа на основе оценок daps и cvg: ~ 30 млн. обращений

Версия 16:08, 22 января 2015

  1. Описание локальности алгоритма
  2. Описание локальности реализации алгоритма
    1. Качественное (словесное) описание пространственной и временной локальности
      1. Построить график профиля обращений в память.
      2. Выполнить визуальный анализ структур профиля обращений (при необходимости масштабировать график для проведения более подробного анализа). На различных шагах масштабирования привести выводы/предположения о пространственной и временной локальности, которые можно сделать на данном шаге.
        1. В результате должно сложиться понимание о структуре профиля с точностью до отдельных обращений.
        2. Особое внимание стоит обратить на выделение характерных фрагментов профиля: итераций, циклов, переборов элементов массивов, случайному доступу и т.д.
        3. При масштабировании необходимо на предыдущем графике профиля отобразить его фрагмент, который будет масштабироваться.
      3. После проведения визуального анализа сделать общие выводы о пространственной/временной локальности (если он не были сделаны ранее).
  3. Количественная оценка локальности
    1. Посчитать daps и cvg.
    2. Построить графики со сравнением каждой из оценок с реализациями других, типовых алгоритмов (например, Линпак, БПФ, перемножение матриц и т.д.)
      1. По возможности проанализировать положение изучаемой реализации в ранжировании относительно типовых программ. Особенно интересно анализ результатов по сравнению со схожими реализациями (например, сравнение классического и блочного перемножения матриц; рекурсивной и нерекурсивной реализаций; двух реализаций, среди которых одна является значительной частью другого).


Условия запуска утилиты для сбора профиля и оценок локальности

  1. Описание программно-аппаратной среды
    1. Платформа: процессор Intel Xeon X5650 @ 2.67GHz
    2. Размер кэш-памяти (L1/L2/L3): 32K/256K/12M
    3. Компилятор: gcc version 4.4.7
    4. Строка компиляции: g++ -O2 -Wall -Wextra -Werror
  2. Описания параметров запусков
    1. Размер "окна": 512
    2. Размер профиля для визуального анализа: < 1 млн. обращений (часто < 100.000)
    3. Размер профиля для анализа на основе оценок daps и cvg: ~ 30 млн. обращений
Источник — https://algowiki-project.org/w/ru/index.php?title=Locality_methodology&oldid=879