1
$\begingroup$

Given $ n $ numbers and an infinite number of processors can the min or max be found in constant time? Assume a shared memory architecture (all processors can write to a common shared memory) and the ability to perform concurrent writes

I have tried dividing up the numbers into groups of 2 each and then using $n/2$ processors at the first step and then $n/4$ processors on the output of the first step etc. I can't see how to make use of more than $n/2$ processors given that I have $\infty$ of them

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$
    – Raphael
    Jul 2, 2016 at 11:33
  • $\begingroup$ Added what I've tried/come up till now. Would appreciate any hint from the community to get me beyond this. $\endgroup$
    – wabbit
    Jul 2, 2016 at 13:51
  • 1
    $\begingroup$ Have you tried proving a lower bound? You may want to look at circuit lower bounds. One word to google for is depth (and work) of problems. $\endgroup$
    – Raphael
    Jul 2, 2016 at 13:58

3 Answers 3

Reset to default
4
$\begingroup$

I managed to solve this so hoping it's alright to answer your own question. Initialize to all elements off, an $n$ bit vector $A$ having a 1:1 mapping with the $n $ numbers. Compare each number against every other number on $n \choose 2$ processors. Each processor switches the bit corresponding to the smaller of its two elements to 1. Assumption is that the processors can do concurrent writes to $A$. The bit in $A$ remaining off denotes the maximum element.

This is $\Theta(1)$ (constant time) as the depth of the computational graph is independent of the number of elements. The work required is however $\mathcal {O(n^{2})}$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Nice idea! However: 1) How do you initialize $n$ bits in $O(1)$ time? 2) How do you deal with conflicting writes? Many processors try to write the same bits at the same time! (That is to say, this will only work on some very specific machine models, and not at all on others.) 3) How do you find the 0-bit(s) in constant time? $\endgroup$
    – Raphael
    Jul 3, 2016 at 16:42
  • $\begingroup$ Can you not use $n$ processors each writing to a different location in the array to initialize it? For finding the 0 bit also can't we again use $ n$ processors each reading a different bit of $A$ and writing the index concurrently to a single location only if the corresponding bit is 0? Assumption is that there is no tie for the max element. $\endgroup$
    – wabbit
    Jul 4, 2016 at 15:55
  • $\begingroup$ Yup, that might work. $\endgroup$
    – Raphael
    Jul 4, 2016 at 16:44
0
$\begingroup$

You can get constant time if you use n^2 processors. Basically, every processor makes 1 comparison and writes a 0 to a shared memory array of size n if their comparison is smaller. The index in the array with a 1 left in it at the end is the max.

Improve this answer
$\endgroup$
-1
$\begingroup$

If you find max and min using recursion, then the best case complexity is O(log n). So, I think you can get constant time, by dividing the work into n parts and assigning each of that partition to a processor. Infinite processors can be used only when n is too large.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Did you mean "can get constont time" or "can't get constant time"? $\endgroup$
    – gnasher729
    Jul 3, 2016 at 15:03
  • 2
    $\begingroup$ How do you divide this work into $n$ parts that can be executed simultaneously? $\endgroup$
    – Raphael
    Jul 3, 2016 at 15:13
  • $\begingroup$ Use divide and conquer to divide work just like merge sort! And I meant that the problem would require O(1) time! $\endgroup$
    – kiner_shah
    Jul 4, 2016 at 12:39
  • $\begingroup$ I very much doubt O (1), that's why I asked. We want one answer, so the work done by all the processors needs to be combined into one answer. If you use m processors, that takes O (log m) . $\endgroup$
    – gnasher729
    Jul 5, 2016 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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