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

Question

Я сейчас в ловушке лаборатории оптимизации производительности в книге «Компьютерная система с точки зрения программиста», описанной следующим образом:

В N * N матрице M, где N кратно 32, операция поворота может быть представлена ​​как: Транспонирование: взаимозаменяемость элементов M (i, j) и M (j, i) Обмен строк: строка i заменяется строкой N-1-i

Пример вращения матрицы (для простоты N равно 3 вместо 32):

-------                          -------
|1|2|3|                          |3|6|9|
-------                          -------
|4|5|6|    after rotate is       |2|5|8|
-------                          -------
|7|8|9|                          |1|4|7|
-------                          -------

Наивная реализация:

#define RIDX(i,j,n) ((i)*(n)+(j))

    void naive_rotate(int dim, pixel *src, pixel *dst) 
    {
        int i, j;

        for (i = 0; i < dim; i++)
        for (j = 0; j < dim; j++)
         dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
    }

Я пришёл с идеей по внутреннему циклу - развернуть. Результат:

Code Version          Speed Up
  original                1x
 unrolled by 2           1.33x
 unrolled by 4           1.33x
 unrolled by 8           1.55x
 unrolled by 16          1.67x
 unrolled by 32          1.61x

Я также получил фрагмент кода от pastebin.com, который, похоже, может решить эту проблему:

void rotate(int dim, pixel *src, pixel *dst) 
{
    int stride = 32;
    int count = dim >> 5;
    src += dim - 1; 
    int a1 = count;
    do {
        int a2 = dim;
        do {
            int a3 = stride;
            do {
                *dst++ = *src;
                src += dim;
            } while(--a3);
            src -= dim * stride + 1;
            dst += dim - stride;
        } while(--a2);
        src += dim * (stride + 1);
        dst -= dim * dim - stride;
    } while(--a1);
}

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

Вот вопросы:

1. В версии с внутренним циклом развертывания почему приращение увеличивается при увеличении коэффициента развертывания, особенно при изменении коэффициента развертывания с 8 до 16, что не действует при переключении с 4 на 8? Имеет ли результат какое-то отношение к глубине конвейера ЦП? Если ответ «да», может ли снижение приращения отражать длину конвейера?

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

EDIT:

Моя тестовая среда - архитектура Intel Centrino Duo, версия gcc - 4.4

.

Любой совет будет высоко оценен!

С уважением!

Answer 1

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

Другой код может быть быстрее по причинам купе.

1) Циклы обратного отсчета, а не вверх. Сравнение счетчика цикла с нулем на большинстве архитектур ничего не стоит (флаг устанавливается декрементом автоматически), вы должны явно сравнивать максимальное значение с каждой итерацией.

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

При написании оптимизированного кода вы всегда строите его снизу вверх изнутри. Это означает, что нужно взять самый внутренний цикл и уменьшить его содержимое почти до нуля. В этом случае перемещение данных неизбежно. Увеличение указателя - это минимум для перехода к следующему элементу, другой указатель должен добавить смещение для перехода к следующему элементу. Таким образом, как минимум, у нас есть 4 операции: загрузка, сохранение, приращение, добавление. Если бы архитектура поддерживала «перемещение с постинкрементом», это было бы всего 2 инструкции. На Intel подозреваю, что это 3 или 4 инструкции. Что-то большее, чем вычитание и умножение, добавит значительный код.

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

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

Answer 2

1. Основная цель развертывания цикла состоит в сокращении времени, затрачиваемого на управление циклом (проверка на завершение, увеличение счетчиков и т. Д.). Это случай уменьшения отдачи, поскольку, поскольку цикл развертывается все больше и больше, время, затрачиваемое на управление циклом, становится все менее и менее значительным. Как сказал mmr, развертывание цикла может также помочь компилятору выполнять вещи параллельно, но только до определенного момента.

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

   Алгоритм «data-zone» берет матрицу, к которой вы обращаетесь по столбцу, и выполняет транспонирование только для 32 строк за раз, поэтому объем обрабатываемой памяти равен 32xstride, который, мы надеемся, должен полностью вписаться в кеш. В основном цель состоит в том, чтобы работать с подразделами, которые помещаются в кэш и уменьшают количество скачков в памяти.

Answer 3

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

РЕДАКТИРОВАТЬ : Согласно этого PDF , Centrino Core2 Duo имеет два процессора, каждый из которых способен выполнять 4 одновременных инструкции. Хотя обычно это не так просто. Если ваш компилятор не оптимизирует оба ядра (т. Е. Когда вы запускаете диспетчер задач (если вы работаете в Windows, top, если вы используете Linux), вы увидите, что использование процессора максимально), ваш процесс будет работает на одном ядре за раз. Процессор также имеет 14 этапов выполнения, поэтому, если вы сможете поддерживать конвейер заполненным, вы получите более быстрое выполнение.

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

Для этого последнего, подумайте о том, как работает McDonald's через (я думаю, что это относительно широко распространено?). Автомобиль проезжает мимо, заказывает у одного окна, платит у второго окна и получает еду у третьего окна. Если второй привод входит, когда первый все еще находится в порядке, то к тому моменту, когда оба заканчивают (предполагая, что каждая операция в приводе занимает один «цикл» или единицу времени), то к полному времени, когда 4 цикла пройдут, будут выполнены 2 полные операции. , Если каждая машина выполняет все свои операции в одном окне, то первая машина будет выполнять 3 цикла для заказа, оплаты и получения еды, а затем вторая машина также будет выполнять 3 цикла для заказа, оплаты и получения еды, всего из 6 циклов. Таким образом, время работы за счет конвейеризации уменьшается.

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

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

Обратите внимание, что каждое движение от src к dst не является свободным или отдельной операцией. У вас есть поиск в массивах, и это стоит времени.

Что касается того, почему вторая версия работает так быстро, я рискну предположить, что это связано с оператором []. Каждый раз, когда вызывается, вы выполняете поиск в массивах src и dst, устанавливаете указатели на местоположения и затем извлекаете память. Другой код идет прямо к указателям массивов и напрямую обращается к ним; в основном, для каждого из перемещений из src в dst в перемещении задействовано меньше операций, потому что поиск был обработан явно посредством размещения указателя. Если вы используете [], выполните следующие действия:

• делать любую математику внутри []
• взять указатель на это место (startOfArray + [] в памяти)
• вернуть результат этого места в памяти

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

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