Быстрая реализация двоичной экспансионизации реализации в OpenCL

Я пытаюсь разработать быструю двоичную реализацию экспоненции в OpenCL. Моя текущая реализация очень похожа на мою в this book about pi.Быстрая реализация двоичной экспансионизации реализации в OpenCL

// Returns 16^n mod ak 
inline double expm (long n, double ak) 
{ 
    double r = 16.0; 
    long nt; 

    if (ak == 1) return 0.; 
    if (n == 0) return 1; 
    if (n == 1) return fmod(16.0, ak); 

    for (nt=1; nt <= n; nt <<=1); 

    nt >>= 2; 

    do 
    { 
     r = fmod(r*r, ak); 
     if ((n & nt) != 0) 
      r = fmod(16.0*r, ak); 
     nt >>= 1; 
    } while (nt != 0); 
    return r; 
}

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

источник

2014-01-20 AnimatedRNG

Любая идея, что представляет собой общий диапазон ввода? – cactus1

n может варьироваться до миллиона или около того. Итак, довольно большой диапазон ввода. – AnimatedRNG

Действительно ли 'ak' удваивает или целое число? Что это за диапазон? –

Моя первая мысль - векторизовать его, для потенциальной скорости ~ 1.6x. Это использует 5 умножений за цикл по сравнению с 2 умножениями в оригинале, но с примерно четвертью числа циклов для достаточно больших N. Преобразование всех double s в long с, а замена fmod с на % с может обеспечить некоторую скорость в зависимости от конкретного используемого GPU и любого другого.

inline double expm(long n, double ak) { 

    double4 r = (1.0, 1.0, 1.0, 1.0); 
    long4 ns = n & (0x1111111111111111, 0x2222222222222222, 0x4444444444444444, 
      0x8888888888888888); 
    long nt; 

    if(ak == 1) return 0.; 

    for(nt=15; nt<n; nt<<=4); //This can probably be vectorized somehow as well. 

    do { 
     double4 tmp = r*r; 
     tmp = tmp*tmp; 
     tmp = tmp*tmp; 
     r = fmod(tmp*tmp, ak); //Raise it to the 16th power, 
             //same as multiplying the exponent 
             //(of the result) by 16, same as 
             //bitshifting the exponent to the right 4 bits. 

     r = select(fmod(r*(16.0,256.0,65536.0, 4294967296.0), ak), r, (ns & nt) - 1); 
     nt >>= 4; 
    } while(nt != 0); //Process n four bits at a time. 

    return fmod(r.x*r.y*r.z*r.w, ak); //And then combine all of them. 
}

Редактировать: Я уверен, что теперь это работает.

источник

2014-01-21 13:03:37 cactus1

Это выглядит потрясающе! К сожалению, сегодня у меня не так много времени, чтобы точно определить, что делает ваш код; Завтра я посмотрю. – AnimatedRNG

Спасибо! Думаю, теперь у меня это работает. Суть в том, что он использует векторные типы для обработки входных 4 бит за раз. – cactus1

Я проверю это сегодня. Благодаря! – AnimatedRNG

Петля для извлечения nt = log2(n); может быть заменен
if (n & 1) ...; n >>= 1;
в то время как делать-цикл.
Учитывая, что изначально r = 16;, FMOD (г * г, ак) против FMOD (16 * г, ак) может быть легко с задержкой, чтобы вычислить по модулю только каждый N-й итерации или так - петля разворачивая?
Также почему fmod?

источник

2014-01-21 05:10:06

Быстрая реализация двоичной экспансионизации реализации в OpenCL

ответ

Смежные вопросы