3 ms·

> We view disentanglement as generalizing the notion of “time” as it relates to memory for parallel programs: in both sequential and disentangled parallel progr

> We view disentanglement as generalizing the notion of “time” as it relates to memory for parallel programs: in both sequential and disentangled parallel programs, an instruction can only access objects that are allocated before it. > Disentanglement opens a new perspective on parallel memory management: rather than viewing memory as a global shared resource, we can instead organize memory as a distributed structure that mirrors (i.e., corresponds with) the structure of parallelism in the program. Parallel, concurrent, and distributed systems are moving closer and closer to a relativistic model of the world. If we consider memory as roughly equivalent to space (N bits of memory take O(sqrt(N)) physical space http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html ) then this approach is essentially scheduling the work across spacetime (rather than just time); or, from a different perspective, the interactions defined within the program can be interpreted as a spatial layout of the problem/solution, which this compiler is utilising when deciding how to arrange the allocations. See also https://en.wikipedia.org/wiki/Relativistic_programming https://en.wikipedia.org/wiki/Relativistic_programming

linspace 5y ago
I know nothing about distributed programming, but Leslie Lamport's paper [1] from 1978 about distributed systems already reads very close to the typical intro in special relativity about clock synchronization. I would be surprised if there is not already a body of research about whether: 1) Relativity in the physical world arises if we consider some distributed model of computation 2) Physical laws, in particular speed of light, affecting algorithm complexity limits [1] http://lamport.azurewebsites.net/pubs/time-clocks.pdf http://lamport.azurewebsites.net/pubs/time-clocks.pdf
aristus 5y ago
It's not Einsteinian, though. Simple Gallilean relativity is enough to model what's going on.
- chriswarbo 5y ago
  I disagree. Concurrency (including parallelism) only defines a partial order on events, not a total/global order. This leads to one of the following: - We assume there's a total order anyway. This lets us use Gallilean relativity, but is an incorrect model, which manifests as race conditions. - We impose a total order, by introducing causality between every event (e.g. synchronisation, or data dependencies like counters, etc.). This lets us use Gallilean relativity and maintain correctness, but it is no longer concurrent/parallel. - We only assume a partial order. This avoids race conditions, but allows races between independent results (which can therefore be calculated in parallel). This is inherently relativistic, since independent events can occur in a different order for different observers (in the case of this article, the observers are CPU cores). See also https://en.wikipedia.org/wiki/Relativity_of_simultaneity https://en.wikipedia.org/wiki/Relativity_of_simultaneity

linspace 5y ago

I know nothing about distributed programming, but Leslie Lamport's paper [1] from 1978 about distributed systems already reads very close to the typical intro in special relativity about clock synchronization. I would be surprised if there is not already a body of research about whether: 1) Relativity in the physical world arises if we consider some distributed model of computation 2) Physical laws, in particular speed of light, affecting algorithm complexity limits [1] http://lamport.azurewebsites.net/pubs/time-clocks.pdf http://lamport.azurewebsites.net/pubs/time-clocks.pdf

aristus 5y ago

It's not Einsteinian, though. Simple Gallilean relativity is enough to model what's going on.

chriswarbo 5y ago
I disagree. Concurrency (including parallelism) only defines a partial order on events, not a total/global order. This leads to one of the following: - We assume there's a total order anyway. This lets us use Gallilean relativity, but is an incorrect model, which manifests as race conditions. - We impose a total order, by introducing causality between every event (e.g. synchronisation, or data dependencies like counters, etc.). This lets us use Gallilean relativity and maintain correctness, but it is no longer concurrent/parallel. - We only assume a partial order. This avoids race conditions, but allows races between independent results (which can therefore be calculated in parallel). This is inherently relativistic, since independent events can occur in a different order for different observers (in the case of this article, the observers are CPU cores). See also https://en.wikipedia.org/wiki/Relativity_of_simultaneity https://en.wikipedia.org/wiki/Relativity_of_simultaneity