<p>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 <em>huge array of processors</em> which - however - can only <em>communicate locally</em> 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?</p>

<p>Let's assume the <em>number of processors is allowed to scale up as O(N)</em>. 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?</p>

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

CC BY-SA 3.0
2014-09-28T05:25:08.637Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2014-09-28T09:27:20.400Z
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?
Gere
CC BY-SA 3.0
2014-10-14T04:06:58.963Z
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).
Jukka Suomela
CC BY-SA 3.0
2014-10-14T07:41:55.567Z
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 http://en.wikipedia.org/wiki/NC_%28complexity%29 on the internet. But I want to additionally assume that there is no global RAM - just local.
Gere
<time-complexity><dc.parallel-comp>
Limits of parallel computing with local connections?
Gere
# Limits of parallel computing with local connections?

(Asked by: username_0 on 2014-09-24)

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 :)

**Tags:** time-complexity, dc.parallel-comp
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_2**: 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).  
> **username_0**: 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 http://en.wikipedia.org/wiki/NC_%28complexity%29 on the internet. But I want to additionally assume that there is no global RAM - just local.  

---

## 0 answers

