Ускорение большого модульного умножения в базе 2 ^ 8 без множителя - PullRequest
Новая
       74

Ускорение большого модульного умножения в базе 2 ^ 8 без множителя

5 голосов
/ 01 ноября 2019

В настоящее время я конвертирую библиотеку nacl в risc-v. У меня уже работает поли1305. Я пытаюсь сделать это, используя основной набор команд risc-v, поэтому у меня нет множителя. Алгоритм для Pol1305 использует в настоящий момент ceil (m / 16) * 17 * 17 8-битных умножений, где m - длина сообщения в байтах (умножение двух 2 ^ 130 целых чисел на основание 2 ^ 8 по модулю 2 ^ 130-5),Поэтому я хочу использовать быстрый алгоритм умножения, чтобы сохранить его быстрым.

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

    andi  t2, t0, 1     //t0 is the multiplier
    sub   t2, zero, t2  //creating a mask
    and   t3, t1, t2    //applying the mask to the multiplicand
    add   a0, a0, t3    //doing the add
    srli  t0, t0, 1     //shifting the multiplier
    slli  t1, t1, 1     //shifting the multiplicand

Это дает мне действительные результаты при 63 циклах на умножение. Проблема заключается в том, что общее время выполнения программы составляет 175 219 циклов для сообщения длиной 131 байт. Из этого времени 9 * 17 * 17 * 63 = 163863 циклов используются для умножения. Что я хотел бы улучшить.

1 Ответ

2 голосов
/ 07 ноября 2019

Вот немного улучшенный код. Это основано на алгоритме, показанном в учебнике Паттерсона и Хеннесси. 

    // initialization
    add   a0, zero, t0  //copy multiplier to the product
    slli  t1, t1, 8     //shift the multiplicand to the left half of a 16bit register

    // repeat 8 times from here
    andi  t2, a0, 1     //the right half of a0 is the multiplier
    sub   t2, zero, t2  //creating a mask
    and   t3, t1, t2    //applying the mask to the multiplicand
    add   a0, a0, t3    //doing the add to the left half of the product
    srli  a0, a0, 1     //shifting the product
    // to here

Кроме того, вы можете применить метод разворачивания цикла, повторяя приведенный выше код 8 раз вместо циклического перехода / перехода.

На уровне алгоритма алгоритм Карацубы может уменьшить число 8-битных умножений в арифметике с высокой точностью.

...