cudadl

cudadl-0.9

21 Mar 2012 Ryan Henry and Ian Goldberg {rhenry,iang}@cs.uwaterloo.ca http://crysp.uwaterloo.ca/software/

This package contains the source code to our CUDA implementation of van Oorschot and Wiener's parallel version of the Pollard rho discrete log algorithm. It is intended for use on 1536-bit moduli that are RSA numbers with smooth totient; that is, the modulus N=pq, where p and q are 768-bit primes, and the prime factors of p-1 and q-1 are all distinct and less then B, for a parameter B. [The value 1536 is hardcoded as "WORDS = 24" (24*32*2 = 1536) in the Makefile; it is easy to change this value and recompile if desired.] Note that this means the totient of N = \phi(N) = (p-1)(q-1) has all prime factors less than B; that is, \phi(n) is "B-smooth".

There are two versions of this program: a 2-GPU version and a multi-GPU distributed version. The first uses only 2 GPUs on a single computer, but is much simpler and doesn't require Libevent or MPI. The second version can run across many computers and GPUs.

This software is described in "Solving Discrete Logarithms in Smooth-Order Groups with CUDA", CACR technical report 2012-02, http://www.cacr.math.uwaterloo.ca/techreports/2012/cacr2012-02.pdf

This program is covered under version 3 of the GNU General Public Licence; see the file COPYING for more information.

Building

1. Download and install:

   • NTL (>= 7.0, but != 11.2.0)
   • GMP
   • NVIDIA CUDA Toolkit 9.0

2. If you wish to run the distributed version, you will also need:

   • Libevent
   • OpenMPI

3. Make a new Makefile.local file. An example:

   MACROS = -DVERBOSE
   CUDA_ARCH ?= sm_60
   
   GMP ?=
   CUDA ?=
   MPI ?= /usr/local
   

   Most variables have default values. If you set any of the library paths to an empty value, they will not be set to the default value. This is useful on systems like SHARCNET which loads libraries automatically, and where you should not choose any path.

4. To build the 2-GPU version, run make nompi. To build the distributed version, run make all.

Requirements

1. Two compute capability level 3.0 CUDA cards to run the 2-GPU version (if you have more or just 1, you'll need to modify dlrho.cc, unfortunately). If running the distributed version, you can use any number of GPUs.

2. If running the MPI version, passwordless ssh is highly recommended. Make sure to also ssh from every node to every other node in order to accept the host key.

Usage

1. Create the modulus N as, for example, a 1536-bit RSA number whose totient is 2^50-smooth:

   ./gen_N 1536 50 > N
   

2. Generate a DL problem mod N and solve it:

   1. 2-GPU version:

      ./dlrho < N
      

   2. Distributed version:

      mpirun --bind-to none --mca plm_rsh_no_tree_spawn 1 -n 4 --host grunt3,grunt4,grunt5,grunt6 bash -c "./mpi 8 1 \$HOME/data -w 32 -n 4 -m 100 N 1"
      

      The --bind-to none is important to prevent binding to CPU cores, which doesn't play nicely with cudadl which forks.

   3. Distributed version with Slurm (not using MPI; you must be running on a network file system):

      Update the job parameters in slurm-jobscript.sh.

      sbatch slurm-jobscript.sh N data_output_dir cudadl_path
      

Macros

• VERBOSE: Print extra debugging information.

• DERANDOMIZE (f627a022): Deterministically generate the same problem for a given N file. Will choose a deterministic problem (base and target), and Pollard's rho parameters (a, b, astep, and bstep). The distinguished points will also be arranged deterministically after each kernel launch.

• SAVE_DPS (1da839f0): Save the distinguished points to a file. By setting the SAVEDPS macro, you can save the distinguished points. The points discovered during each subproblem are saved in individual files (or multiple files in the case of multiple dpnodes). The file name format is 'dplist{subproblemid}.out' for the dlrho version, or 'dplist{dpnodeid}{subproblemid}.out' for the controller/worker version. This can generate a large amount of data, so it's best to use it on small problems (B < 2^60). When run with the DERANDOMIZE macro, it should produce the same points each time, except in the case of small subproblems where dpfreq is large and the device dp buffer is filled. In this case the points will not be the same, and this can be detected by the line "Warning: The device dp buffer was filled, so some points were not recorded." in the worker's stderr.

• MAKE_VERSIONS_COMPARABLE (f496ab2b): Make the output from the two versions (dlrho and controller/worker) comparable. This forces the controller/worker version to use one worker per subproblem and one dpnode per subproblem. This should make the saved distinguished points comparable between the two, but the number of kernel launches will be slightly higher in the controller/worker version since the worker will usually run an extra kernel launch before it receives the stop message from the dpnode.

• RIPPLE (d8d46482): Add the suffix '-data0' to the hostname in order to use the 4*40Gbps bonded interface on the University of Waterloo's RIPPLE facility.

• GRAHAM (d8d46482): Add the prefix 'ic-' to the hostname in order to use the Infinband interface on SHARCNET's Graham cluster.

• DPFREQ_DIVISOR (563cc16a): Reduce the dp frequency by this number. This is useful when the desired resources calculations provide a dpfreq that is too large and fills the device dp buffers.

Tips and Example Makefiles

For these example makefiles, copy them into a Makefile.local file.

• RIPPLE: The NTL package installed on RIPPLE is too old for the current version of cudadl, so you must compile a newer version manually. The number of threads/blocks in the makefile below work well, but could be optimized further.

  MACROS = -DRIPPLE -DNTHREADS=16384 -DNBLOCKS=32
  CUDA_ARCH = sm_30
  
  NTL ?= <fill this in>
  

• Graham: The Graham module system will automatically load the CUDA and GMP packages. You will need to build NTL and Libevent manually. You cannot run the MPI version on Graham since the MPI version forks (which isn't compatible with Infiniband). Instead, you must use the non-MPI version designed for Slurm. The number of threads/blocks in the makefile below work well, but could be optimized further.

  Before running make, run module load cuda/9.0.176.

  MACROS = -DGRAHAM -DNTHREADS=71680 -DNBLOCKS=112 -DDPFREQ_DIVISOR=4
  CUDA_ARCH = sm_60
  
  GMP ?= <leave this blank>
  NTL ?= <fill this in>
  CUDA ?= <leave this blank>
  LIBEVENT ?= <fill this in>
  MPI ?= <leave this blank>
  

• Cedar: The Cedar module system will automatically load the CUDA and GMP packages. You will need to build NTL and Libevent manually. You cannot run the MPI version on Cedar since the MPI version forks (which isn't compatible with Infiniband). Instead, you must use the non-MPI version designed for Slurm. The number of threads/blocks in the makefile below work well, but could be optimized further.

  Before running make, run module load cuda/9.0.176.

  MACROS = -DNTHREADS=71680 -DNBLOCKS=112 -DDPFREQ_DIVISOR=4
  CUDA_ARCH = sm_60
  
  GMP ?= <leave this blank>
  NTL ?= <fill this in>
  CUDA ?= <leave this blank>
  LIBEVENT ?= <fill this in>
  MPI ?= <leave this blank>
  

Notes for compiling required libraries

1. GMP

   tar --lzip -xvf gmp-*.tar.lz
   cd gmp-*
   ./configure --prefix="$HOME/libraries/gmp"
   make
   make check
   make install
   

2. NTL

   tar -xzf ntl-*.tar.gz
   cd ntl-*/src
   ./configure PREFIX="$HOME/libraries/ntl"
   make
   make check
   make install
   # make sure it used GMP (look for "GMP version check" in make output)
   

3. Libevent

   tar -xzf libevent-*-stable.tar.gz
   cd libevent-*-stable
   ./configure --prefix="$HOME/libraries/libevent"
   make
   make check # may not be able to run due to many 'Nameserver
   #            127.0.0.1:42868 has failed: request timed out.'
   #            messages, which cause it to be very slow
   make install
   

Changelog

• 0.9 (21 Mar 2012)

  Extend the code to handle smoothness levels (B) larger than 2^60. Now we can handle up to 2^92. We have successfully run a test with B = 2^80.

• 0.8 (23 Jan 2012)

  Initial public release