0
$\begingroup$

In parallel computations I frequently use the following distribution of data to processors: having a sequence of $n$ elements $x_1,\ldots,x_n$ and $P$ processors $p_1,\ldots,p_P$, processor $p_k$ handles the elements $x_{\mathit{first}(k)},\ldots,x_{\mathit{last}(k)}$, where

$$ \mathit{first}(k)=\left\lceil (k-1)\frac{n}{P}+\frac{1}{2} \right\rceil, \quad \mathit{last}(k)=\left\lceil k\frac{n}{P}-\frac{1}{2} \right\rceil. $$

This provide a balanced distribution such that each processor handles the same amortized number of elements. The element $x_i$ is then located in a local array of processor $p_{\mathit{proc}(i)}$ at position $\mathit{pos}(i)$, where

$$ \mathit{proc}(i)=\left\lfloor \left(i-\frac{1}{2}\right) \frac{P}{n} \right\rfloor + 1, \quad \mathit{pos}(i)=i-\mathit{first}(\mathit{proc}(i)). $$

My problem is that I am not sure whether the values of $\mathit{proc}$ and $\mathit{pos}$ functions calculated by floor/ceil functions within a computer program and thus containing rounding errors may not differ from their actual values? And also, I wonder how to provide an analysis of this problem. Is there any mathematical approach for such kind of analyses/proves?

$\endgroup$
  • $\begingroup$ This depends on $n$. If it's too large you might want to use a different assignent algorithm. $\endgroup$ – AlexR Feb 1 '15 at 13:52
  • $\begingroup$ I can imagine $n$ going up to $10^{13}$ nowadays, $10^{16}$ in the near future. Which different assignment algorithm would you suggest? $\endgroup$ – Daniel Langr Feb 1 '15 at 13:58
  • $\begingroup$ That's definately going to become an issue then. You should use an integer-based assignment algorithm. Let me write something up. $\endgroup$ – AlexR Feb 1 '15 at 13:58
  • $\begingroup$ You might consider using big integers instead of floating point in your computation. For example, in C there is a "bignum" library, and Python has built-in support for big integers. $\endgroup$ – awkward Feb 1 '15 at 14:42
1
$\begingroup$

Basically what you are trying to do is separate $(x_n)$ into chunks of size $n/P$ (your assignment seems faulty as-is actually, the chunks will have length $P/n \to 0$ as $n\to\infty$. I suggest doing a high-precision computation of $$l := \lfloor n/P \rfloor$$ using a non floating-point algorithm of your choice and doing the same for $$r := n\ \mathrm{mod}\ P$$ Now you have two integers with $n = P\cdot l + r$ so the load can be determined by

globalIdx = 0;
for (i = 0; i < P; i++)
    l[i] = i < r ? l : l + 1;
    pStart[i] = globalIdx;
    pEnd[i] = globalIdx + l[i] - 1;
    globalIdx += l[i];
end

If $P$ also grows, we can run the algorithm in parallel on each processor in $\mathcal O(1)$. Only $l$ and $r$ need to be precomputed (feasible in $\mathcal O(\log n)$):

l[i] = i < r ? l : l + 1; // Determine my load
pStart[i] = i * l;
if (i > r) pStart[i] += i - r;
pEnd[i] = pStart[i] + l[i] - 1;
$\endgroup$
  • $\begingroup$ My fault, I swapped the parts of the fractions in $\mathit{first}$ and $\mathit{last}$ when rewriting from my papers. Edited a while ago to become correct. $\endgroup$ – Daniel Langr Feb 1 '15 at 14:34
  • $\begingroup$ I suggest long-division to get $l$ and $r$ simultaneously btw. $\endgroup$ – AlexR Feb 1 '15 at 14:40
  • $\begingroup$ True, nice solution. But I am more concerned about calculation of processor number and the local position for $i$th element, in $\mathcal{O}(1)$ at best. $\endgroup$ – Daniel Langr Feb 1 '15 at 14:40
  • $\begingroup$ @DanielLangr My algorithm can be parallelised to get $\mathcal O(1)$ as well, I'll line out how. $\endgroup$ – AlexR Feb 1 '15 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.