NTL：基本线程池

NTL：基本线程池

在坑了很久之后，今日琪琪子继续更新NTL技术文档。

从今天开始介绍NTL库的基本模块，首先介绍基本线程池。原始文档链接如下：https://shoup.net/ntl/doc/BasicThreadPool.cpp.html。
原文是以注释的形式将模块介绍了一下。

/******************************************************
模块名：基本线程池
简介：一个基本线程池类BasicThreadPool，以及某些更高级别的宏，这些宏可以支持简单的循环并行
*******************************************************/

/*******************************************************
基本的循环并行：
我们首先描述更高级别的宏，我们可以使用这些宏来写一些简单的并行化的循环。仅当我们设置了NTL_THREAD_BOOST=on的时候才有效（此时意味着NTL_THREADS=on）。 不过即便我们设置了NTL_THREAD_BOOST=off，使用这里介绍的工具进行编码也是能够正确的编译并且运行的， 所以这里是在所有的在编译时间和运行时环境下最简单的写并行循环的方式。我们得注意一下，如果NTL_THREADS=on， 要求C++11风格的代码，不过如果NTL_THREADS=off的话，就不需要这种编码风格了，所以C++11以下的编译器也能编译。

下面是一个简单的写并行循环的小例子。

在程序运行开始的时候，程序首先运行

SetNumThreads(nt)

我们可以选择nt为任意的正整数，但是为了达到最好的效果，nt取值应该对应于您的机器可用的核的数量。注意：如果已经设定了NTL_THREAD_BOOST=off，那么函数虽然被定义了， 但是不会起到任何作用。

现在我们考虑下面的循环。

void mul(ZZ* x,ZZ* a,zz* b,long n){
	for(int i=0;i<n;i++){
  		mul(x[i],a[i],b[i]);
  		}
}

如果写成并行循环格式，可以这么写：

void mul(ZZ* x,const ZZ* a,const ZZ* b,const ZZ* c){
	NTL_EXEC_RANGE(n,first,last){
  		for(long i=first;i<last;i++){
			mul(x[i],a[i],b[i]);
		}
	NTL_EXEC_RANGE_END
	}
}

NTL_EXEC_RANGE 以及 NTL_EXEC_RANGE_END都是宏，这两个宏会“做该做的事”。如果有nt个可用的线程，那么区间[0,n)就会最多被分割为nt个小区间，不同的线程会分别处理不同的子区间。人们仍然需要自己去写for循环，因为在宏里面仅仅声明并初始化循环中的第一个和最后一个long类型的变量，这些变量代表了第一个和最后一个在该线程中被处理的子区间的值。

我们得注意一下，当前的线程作为nt个可用的线程中的一个，当前线程会等待直到全部的线程结束任务之后再继续工作。当前线程可以被看做初始值为first==0的线程。

在该构造的构造内，我们可以自由的引用在当前点可见的变量。这是使用C++的lambda特征完成的（使用引用来捕获全部的变量）。

我们得注意到在EXEC_RANGE范围内的代码可以调用其他尝试执行EXEC_RANGE的过程：如果这一点出现了，那么后边的EXEC_RANGE可以检测到这一点，并且在这种情况下，切换到单线程运行。

你可能会希望在EXEC_RANGE内部做一些除了循环之外其他的事情，比如声明变量这种。另外一个你可能想要做的事情就是为ZZ_p模块设置本地环境（或者为另外一个模块设置本地环境），下面就给出其中一个例子。

void mul(ZZ_p* x,const ZZ_p* a,const ZZ_p *b,long n){
	ZZ_pContext context;
	context.save();

	NTL_EXEC_RANGE(n,first,last)

		context.restore()
		for(long i=first;i<last;i++){
			mul(x[i],a[i],b[i]);
		}
	NTL_EXEC_RANGE_END
	}

另外一个非常有用的函数是AvalableThreads（）,该函数会返回可用的线程的个数，如果线程或者多线程不可用，那么该函数就会返回1,不过即便是当多线程（thread boost）可用的情况下，如果处于某些原因导致线程池不可用（比如并未调用SetNumThreads，或者线程池已经被激活），那么AvailableThreads（）还是会返回1。

人们可以使用一个较为底层的工具集，我们可以利用该底层工具集来运行特定数量的线程，假定满足nt<=AvalableThreads(),则下面的代码

NTL_EXEC_INDEX(nt,index)
...code...
NTL_EXEC_INDEX_END

上述代码会在nt个不同的线程上运行代码块，每个线程都拥有一个在范围[0…nt)上不同的索引。被命名为“index”的long类型的变量（或者你随意给一个名字）中存储着这个索引。和EXEC_RANGE一样，当前的线程实际上会作为nt个线程中的一个，并且会被赋值为index=0.

ZZ InnerProd(const ZZ *a,const ZZ *b,long n){
	long cnt = pinfo.NumIntervals(); 
	vec<ZZ> acc;
	acc.setLength(cnt);
	NTL_EXEC_INDEX(cnt,index)
	long first,last;
 	pinfo.interval(first,last,index); 
 	ZZ &sum = acc[index];
 	sum = 0;
 	for(long i=first;i<last;i++){
 		MulAddTo(sum,a[i],b[i]);
 	}
 	NTL_EXEC_INDEX_END 
 	ZZ sum;
 	sum =0;
 	for(long i=0;i<cnt;i++)	
 		sum+=acc[i]; 
 	return sum
 	}

上面的例子介绍了一个叫做PartitionInfo的类，该类对于将较大区间分割为较小区间非常管用（该函数在EXEC_RANGE）内部使用。构造函数取单个argument（在该例子中，参数为n，并且将[0,n)近似等分成相同大小的自取件，并且函数interval(first,last,index)会根据给定的index，将子区间的两个端点分别赋值为first…last）。 从而在该例子中，会运行cnt个线程，其中每一个线程都会将计算结果累加到向量acc的对应位置的元素上，并在最后，acc中的向量会求和。

我们得注意到如果这些线程不可用，或者不可访问，上面的代码也会正确的编译运行，只要使用一个线程即可。

最后，我们介绍一个受保护的NTL_EXEC_RANGE（guarded version），该版本允许并行计算的动态保护。距离来说，在非常小的问题上，循环的并行运算可能根本不值得，或者在另外的一些情况下，并行计算可能会导致不正确的结果，下面我们详细的介绍这一点。

********************************************************/