# Parallel number systems don't scale well

I'm working on Residue Number System. This is basically a set of relatively coprime integers, let's say $\{3,4,5\}$ and we define its range to be the product of the moduli, i.e. $M=3\cdot4\cdot5=60$. Then we can represent all integers X in $[0,M-1]$ in their RNS format like $$\{X\bmod3,X\bmod 4, X\bmod 5\}$$ and we can add/subtract/multiply them (modulo each modulus) in parallel for all moduli channels. For example, if $X=7=\{1,3,2\}$ and $Y=8=\{2,0,3\}$ then

$$X\cdot Y=\{1\cdot 2 \bmod 5, 3\cdot 0 \bmod 5, 2\cdot 3 \bmod 5\}=\{2,0,1\}.$$ Theoretically, as numbers scale up in real applications like cryptography, there might be significant savings, because instead of multiplying 2 let's say 2048-bit numbers, we can use an RNS with just 32-bit channels and multiply as before. I'm trying to visualize this somehow in Mathematica but my results are not consistent. To start with, my system has 2 cores with hyperthreading, thus 4 logical cores in total.

I defined the following "manual" function for multiplication in RNS, where I assume that my RNS has 4 channels assigned to each logical core

ParallelExecute[X_List, Y_List, Base_List] := {
ParallelEvaluate[Mod[X[[1]]*Y[[1]], Base[[1]]], Kernels[][[1]]],
ParallelEvaluate[Mod[X[[2]]*Y[[2]], Base[[2]]], Kernels[][[2]]],
ParallelEvaluate[Mod[X[[3]]*Y[[3]], Base[[3]]], Kernels[][[3]]],
ParallelEvaluate[Mod[X[[4]]*Y[[4]], Base[[4]]], Kernels[][[4]]]
};

Then I take a simple example of multiplying 2 2048-bit integers and the equivalent of multiplying in parallel their RNS representation over 1024-bit parallel channels. One would expect a significant improvement but:

In[129]:= X*Y // AbsoluteTiming
Out[129]= {7.*10^-6, Huge Number omitted here}

and in RNS

In[143]:= ParallelExecute[XRNS, YRNS, B] // AbsoluteTiming
Out[143]= {0.004377, RNS result omitted here}

I suspect that typical arithmetic operations use the underlying hyperthreading or inherent parallel techniques in Mathematica but I would expect that same thing would happen for RNS but seems not.

What would be an approach that would reveal the speedups in RNS? Perhaps translate operations to bitwise operations? Any advice on manipulating the parallelism techniques offered in Mathematica?

• Your ParallelExecute function evaluates something on kernel 1, waits until it's done, then evaluates something on kernel 2, waits until it's done, and so on. You are slowing down your computation, not speeding it up. Use Parallelize[{eval1, eval2, ...}]. Or use ParallelSubmit (look it up) for asynchronous evaluations. – Szabolcs Mar 26 '17 at 17:44
• Even if you fix this, such fine-grained parallelization is not helpful in Mathematica. The parallelization overhead is high in Mathematica, and inter-kernel communication is slow. Parallelization makes sense only if each individual evaluation takes sufficiently long. I wouldn't bother at all with sub-second evaluation times, though I do not know where the exact limit is (I'm sure it's lower than a second, but it strongly depends on how much data you need to send to subkernels). – Szabolcs Mar 26 '17 at 17:47
• @Szabolcs This is correct, the point is to use this representation in a series of intensive computations to speed them up. – Jimakos Mar 26 '17 at 20:45
• @Szabolcs Regarding your comment on ParallelSubmit , it does perform faster but it doesn't account for executing the expression right? It only corresponds to submitting the data for evaluation, correct? In that case, if I add the AbsoluteTiming for ParallelSubmit plus the time for one of the parallel expressions, will I get a realistic estimate? – Jimakos Mar 26 '17 at 20:51
• The usage is described here, more specifically here. You would need to measure everything, including ParallelSubmit and WaitAll, to get the full timing. In case youare not aware: Keep using AbsouteTiming, as you have been doing so far. Do not use Timing, as it doesn't measure time spent by parallel kernels. – Szabolcs Mar 26 '17 at 21:28