0

这是我第一次在这里提问，如果有问题，请见谅。
我正在尝试使用 cpp 线程并行化 NTT，但我只是迷路了。我将代码基于一篇解释 NTT 的 CUDA 并行化的文章并对其进行了调整，以便它对处理器更有意义（更少的线程），但我碰壁了，无法进步。基本上，创建了一个类来映射每个线程与数组中的哪对元素需要使蝴蝶打开，结果是错误的，并且 psis 似乎被正确计算（位反转顺序）。
我是并行计算和 NTT 的新手，不胜感激。

class threadInfo {
    public:
        std::vector<long long *> psi, u, v;
        void clear(){
            psi.clear();
            u.clear();
            v.clear();
        }
};

void threadButterfly(threadInfo info, long long mod, bool invert){
    for (long long i = 0; i < info.u.size(); i++)
    {
        long long u = * info.u[i], v = * info.v[i];
        if(!invert)     v = modulo(v* * info.psi[i],mod);
        * info.u[i] = modulo(u+v,mod);
        * info.v[i] = modulo(u-v,mod);
        if(invert)      * info.v[i] = modulo((u-v)* * info.psi[i],mod);
        else            * info.v[i] = modulo(u-v,mod);
    }
}

void threadSched(vector<long long> &a, long long mod, long long len, std::vector<long long> &psi, vector<threadInfo> info, bool invert){
    vector<thread> threads(THREAD_NUM);
    long long n = a.size();
    for (long long id = 0; id < n>>1; id++)                                 //puts each u and v pairs in each thread object
    {
        long long step = (a.size()/len)/2;                                  // step counts the distance between u and v
        long long psi_step = id/step;                                       // what k in psi**k to use relative to the first in the group
        long long target = (psi_step * step * 2) + (id % step);             // what u and v we want
        long long group = len + psi_step;                                   // what k in psi**k to use relative to all psis
        long long arrayid = floor((2*id*THREAD_NUM)/n);                     // what thread will the par go to
        info[arrayid].psi.push_back( & psi[group]);
        info[arrayid].u.push_back( & a[target]);
        info[arrayid].v.push_back( & a[target+step]);
    }
    for ( size_t id=0; id<THREAD_NUM; id++ )        threads[id] = thread(threadButterfly,info[id],mod,invert);
    for ( size_t id=0; id<THREAD_NUM; id++ )        threads[id].join(); 
    for ( long long i = 0; i<info.size(); i++ )     info[i].clear();
    if(invert)  for ( long long j = 0; j < n; j++ ) a[j]=modulo(a[j]*mod_in(n,mod),mod);
}

void ntt(vector<long long> &a, long long mod, vector<long long> &psi){
    vector<threadInfo> fwd(THREAD_NUM);
    for (long long len = 1; len < a.size(); len = 2 * len)
    {
        threadSched(a,mod,len,psi,fwd,false);
    }
}

void intt(vector<long long> &a, long long mod, vector<long long> &psi){
    vector<threadInfo> rev(THREAD_NUM);
    for (long long len = 1; len < a.size(); len = 2 * len)
    {
        threadSched(a,mod,len,psi,rev,true);
    }
}

感谢您的关注。
EDIT1：
解释得更好一点，数论变换基本上是傅里叶变换，在以模为界的字段中具有整数，它从 x-power=index 更改多项式的表示（例如：6x^2 + 5x +9） ([9,5,6]) 到 {x,y}={index, variable}([9,20,26]) 以便我们可以更快地乘以多项式。为此，我们需要原始根（代码中的 psis）及其幂，它们基于多项式的大小及其模数。
Ntt里面是一个蝶形操作，论文把这个操作里面的数组元素分给了gpu的各个线程，所以为了cpus的修改，我创建了一个类来符号化各个线程，给各个线程传递SIZEOFPOLYNOMIAL/TH​​READNUMBER元素. 当线程被调用时，它会为其给定的元素数组计算蝶形。
我正在使用gcc -O3 -std=c++17 -pthread -march=native -lm并且我正在使用各种实现测试 NTT，唯一不起作用的是这个，所以主要功能（是巨大的）在这种情况下并不重要，只会使这篇文章膨胀。
论文：https ://eprint.iacr.org/2021/124.pdf

4

0 回答 0