patternMinor
In what sense are dataflow architectures non-deterministic?
Viewed 0 times
whatnonaredataflowarchitecturessensedeterministic
Problem
The Wikipedia article mentions non-determinism in the context of dataflow architectures. Arthur Veen's paper mentions non-determinism when it elaborates on MERGE nodes as conditional constructs.
Are dataflow architectures non-deterministic in the sense of Non-Deterministic Turing Machine?
For any program which deterministically runs on a von Neumann architecture, can we guarantee that it runs deterministically on a data flow architecture?
Are dataflow architectures non-deterministic in the sense of Non-Deterministic Turing Machine?
For any program which deterministically runs on a von Neumann architecture, can we guarantee that it runs deterministically on a data flow architecture?
Solution
Are dataflow architectures non-deterministic in the sense of Non-Deterministic Turing Machine?
In principle one could create a non-deterministic dataflow architecture, but that would be a bit odd. There is nothing about dataflow that fundamentally requires determinism or non-determinism.
Normally I'd expect that a dataflow architecture would be deterministic in the sense that the result of the computation is a deterministic function of the inputs (in principle it doesn't have to be that way, but that's probably the common case for a dataflow architecture). Of course, the order in which intermediate values are computed might not be deterministic, even though the result is. See Why doesn't parallelism necessarily imply non-determinism? for a detailed explanation of that point.
Beware that there are multiple meanings of the word "non-determinism". One meaning is non-determinism in the sense of a non-deterministic Turing machine, i.e., there can be a choice of transitions and the machine magically makes the best choice at every step; this is not implementable directly in real-world machines, so is purely a theoretical nothing. Another meaning is that the system is not deterministic, e.g., there are aspects of its behavior that are not specified or random; those are resolved somehow but not necessarily by choosing the best choice. Occasionally I've seen people use the word "indeterminism" for the latter notion, but that seems to be pretty rare. See also Differences and relationships between randomized and nondeterministic algorithms?, https://cs.stackexchange.com/a/38158/755, https://en.wikipedia.org/wiki/Nondeterministic_algorithm, https://en.wikipedia.org/wiki/Indeterminacy_in_computation.
In principle one could create a non-deterministic dataflow architecture, but that would be a bit odd. There is nothing about dataflow that fundamentally requires determinism or non-determinism.
Normally I'd expect that a dataflow architecture would be deterministic in the sense that the result of the computation is a deterministic function of the inputs (in principle it doesn't have to be that way, but that's probably the common case for a dataflow architecture). Of course, the order in which intermediate values are computed might not be deterministic, even though the result is. See Why doesn't parallelism necessarily imply non-determinism? for a detailed explanation of that point.
Beware that there are multiple meanings of the word "non-determinism". One meaning is non-determinism in the sense of a non-deterministic Turing machine, i.e., there can be a choice of transitions and the machine magically makes the best choice at every step; this is not implementable directly in real-world machines, so is purely a theoretical nothing. Another meaning is that the system is not deterministic, e.g., there are aspects of its behavior that are not specified or random; those are resolved somehow but not necessarily by choosing the best choice. Occasionally I've seen people use the word "indeterminism" for the latter notion, but that seems to be pretty rare. See also Differences and relationships between randomized and nondeterministic algorithms?, https://cs.stackexchange.com/a/38158/755, https://en.wikipedia.org/wiki/Nondeterministic_algorithm, https://en.wikipedia.org/wiki/Indeterminacy_in_computation.
Context
StackExchange Computer Science Q#109011, answer score: 2
Revisions (0)
No revisions yet.