3
$\begingroup$

There are successes with an increasing numbers of individual computational units in GPUs or as processor cores. Given someone made the effort to build a huge array of processors which - however - can only communicate locally with their neighbors (let's say on a hex grid in 2D - not arbitrary distance connections), how will time complexities of algorithms change and which algorithms will profit and which will never be fast enough?

Let's assume the number of processors is allowed to scale up as O(N). Probably many physics simulation can get a significant boost, however, some problems might require complex interaction between all parts of the data such that the time complexity cannot get below some limit. Are there results for this kind of problem?

PS: I have general math and computation knowledge, but I will try to understand technical details as much as possible :)

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I am not sure what exactly you are looking for, but does the following example answer your question? Suppose we have N machines each of which has one integer, and we want to compute their sum S (say, every machine has to know S by the end of a protocol). In each round, each machine can communicate with at most one machine. We want to minimize the number of rounds. If there is no locality constraint, there is an easy procedure with O(log N) rounds. If the machines are connected as a 2D (square or hexagonal) grid, clearly Ω(√N) rounds are necessary. $\endgroup$
    – Tsuyoshi Ito
    Sep 28, 2014 at 5:25
  • $\begingroup$ Basically I wonder which problems will still be hard if you have an unlimited number of locally connected processors. Surely some problem have data dependencies such that you gain nothing from parallelizing? $\endgroup$
    – Gere
    Sep 28, 2014 at 9:27
  • $\begingroup$ Where is your input stored? And where do you need to write the output? It makes a big difference if e.g. your input is given in a distributed manner (e.g., each processor knows one part of the input) vs. input is stored in a central location (e.g., in a shared read-only random-access memory). $\endgroup$
    – Jukka Suomela
    Oct 14, 2014 at 4:06
  • $\begingroup$ In fact that's the main concern in my question. All the data is restricted to be local only. The units can communicate, but that - of course - takes time. I've found en.wikipedia.org/wiki/NC_%28complexity%29 on the internet. But I want to additionally assume that there is no global RAM - just local. $\endgroup$
    – Gere
    Oct 14, 2014 at 7:41

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.