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

  • 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 '14 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$ – Gerenuk Sep 28 '14 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 '14 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$ – Gerenuk Oct 14 '14 at 7:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.