Graph architectures

History / Edit / PDF / EPUB / BIB
Created: August 12, 2015 / Updated: June 23, 2018 / Status: in progress / 4 min read (~797 words)

  • Study the difference with the current analysis of graphs as programs when we include start/end nodes
    • Should while-true loop programs have to terminate?
  • In a conditional statement such as while(X) or if(X), should the evaluation of the statement and the branch jump be considered as two steps?

  • Stability

  • Easy to do forward/backward propagation

For this study, we will analyze simple control structures (programs) in order to identify increase order of complexity. To simplify the study, we'll assume that these structures will run on a single thread (in other words, no parallel processing will be done). Do note that some of the graphs below may make sense if executed in a parallel environment: each disjoint graph may be executed by a single thread.

Statement

graph TD
1["statement 1"]
1

While-true loop
Program never terminates

graph TD
1["while (true) {}"]
1 --> 1

Not valid (could be considered valid in a parallel architecture as long as statement 1 and statement 2 are independent)

graph TD
1["statement 1"]
2["statement 2"]

Sequential statements

graph TD
1["statement 1"]
2["statement 2"]
1-->2

Not valid

graph TD
1["while (true) {}"]
2["statement 2"]
1-->1

Not valid

graph TD
1["statement 1"]
2["while (true) {}"]
2-->2

While-true loop - Statement
Program never terminates
Statement 1 is never executed

graph TD
1["while (true) {}"]
2["statement 1"]
1-->1
1-->2

Statement - while-true loop
Program never terminates

graph TD
1["statement 1"]
2["while (true) {}"]
1-->2
2-->2

Do-while-true
Program never terminates

graph TD
1["do { statement 1 }"]
2["while (true);"]
1-->2
2-->1

Not valid

graph TD
1["statement 1"]
2["statement 2"]
1-->1
2-->2

graph TD
1["statement 1"]
2["statement 2"]
1-->1
1-->2
2-->1
graph TD
1["statement 1"]
2["statement 2"]
1-->2
2-->1
2-->2

Sequential double while-true loop
Program never terminates

graph TD
1["statement 1"]
2["statement 2"]
1-->1
1-->2
2-->2