OpenCL accellerated lattice siever

pstach · 2014-05-16, 20:42

Hi folks,

A colleague of mine and I have been working on an OpenCL based lattice siever. The code can be found at https://github.com/pstach/gls/.

The current status of the various pieces are:

1) Small prime sieve/resieve is just stub code "that does the job". There are obviously far faster methods for performing this task.
2) Larger primes are currently only translated onto the (q,r) lattice using the GPU. The expensive portion, expansion of these sub-lattices, is still done on the CPU. We've been modeling a method of doing both tasks inclusive of "bucket" fill in and resieving using a merge sort like algorithm.
3) Some minor routines need to be implemented in the OpenCL MP code
4) Cofactorization is fast. The scheduling of kernels could be a bit better to take advantage of overlapping copies and kernel executions.
5) Code doesn't work on AMD/ATI. This is due to an odd bug regarding lowering of constants for integer division and a heap overflow in the register planner.

The README and code has more details.

-Patrick

jasonp · 2014-05-23, 01:03

Very cool; looking over the source now.

Do you have any timing comparisons between CPU and GPU for the cofactorization stage?

2014-05-16, 20:42	#1
pstach Aug 2008 19 Posts	OpenCL accellerated lattice siever Hi folks, A colleague of mine and I have been working on an OpenCL based lattice siever. The code can be found at https://github.com/pstach/gls/. The current status of the various pieces are: 1) Small prime sieve/resieve is just stub code "that does the job". There are obviously far faster methods for performing this task. 2) Larger primes are currently only translated onto the (q,r) lattice using the GPU. The expensive portion, expansion of these sub-lattices, is still done on the CPU. We've been modeling a method of doing both tasks inclusive of "bucket" fill in and resieving using a merge sort like algorithm. 3) Some minor routines need to be implemented in the OpenCL MP code 4) Cofactorization is fast. The scheduling of kernels could be a bit better to take advantage of overlapping copies and kernel executions. 5) Code doesn't work on AMD/ATI. This is due to an odd bug regarding lowering of constants for integer division and a heap overflow in the register planner. The README and code has more details. -Patrick

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
QS Lattice Siever	R.D. Silverman	Factoring	31	2018-10-08 17:17
Compiling 64 bit lattice siever on gcc 4.8.5	chris2be8	Factoring	6	2018-02-06 17:22
Shape of a CUDA lattice siever	fivemack	Programming	2	2012-12-16 01:07
Msieve / lattice siever with degree 7/8 poly	Batalov	Msieve	54	2010-01-13 19:45
ggnfs lattice siever misses some primes	fivemack	Factoring	1	2008-01-18 13:47

2014-05-23, 01:03	#2
jasonp Tribal Bullet Oct 2004 3²·5·79 Posts	Very cool; looking over the source now. Do you have any timing comparisons between CPU and GPU for the cofactorization stage?