1. What is the problem being solved?
- To develop Dataflow that works with C-like languages.
- Scalable low complexity architecture
Dataflow Architecture
It is the collection of operation with their operand identified. Dataflow have firing rule which will execute when tokens are available.
Why is memory ordering important?
Dataflow do not have program counter and would execute when operands for a given operation are ready. Hence, for data dependent operands we need to maintain memory order for correct execution of dataflow graph.
Dataflow graph and Dependency
- Anti Dependency - occurs when an instruction requires a value that is later updated(WAR)
- False Dependency
- True Dependency-occurs when an instruction depends on the result of a previous instruction (RAW).
- Memory Dependency
- Control Flow Dependency
- Structural Dependency
1) and 2) do not exist in Dataflow graph. These exist in out-of-order machine due to finite register space. 3) in Dataflow graph can be resolved by memory ordering. 4) is difficult to handle as we do know the address of memory until load/store is executed.
Functional Language Vs Imperative Language
- The basic flow in Imperative Languages is to declare variable and arrays and modify them to produce output, whereas, in Functional Language, we do not declare variable but everything is a function call. A program is written by nesting function calls.
- In functional language, we can very clearly identify dependencies and can have very parallel programs. But, the main problem is the difficulty in accessing memory.
- Example :
Imperative Language Functional Language
Declare array merge_sort(read_input())
Merge_sort(*array)
2. Who are the intended users?
Users
- General Purpose Processor.
- High Parallel Application
Readers
- Architects
- Designer
Why did they did not transform from high language to Dataflow graph to have better scheduling scheme?
It is easy to translate Registers into Dataflow nodes. It may be not the best way but it is easier to translate. Moreover, they were able to generate good results from binary translation.
3. What is unique about the suggested solution?
- Decentralized execution using tag management
Why Tag Management is important?
Tagging instructions are important to have loop parallelism and remove name dependencies. In backward branch, the same instruction is executed again and again. So, if we tag them we can unroll the loop and track them.
Waves are group of instructions or chunk of control flow. It helps us to have a decentralized execution.
Decentralized execution is important to solve the problem of wire delays.
Some Definition of Blocks
Basic Block – Starts and end with a branch.
Hyper block – Single entry and multiple exit points treats as a basic block
Super block – Multiple basic blocks but single entry and exit points treated as basic blocks.
Waves
- Control Flow split/merge
- No loops within waves
- Maintain memory ordering
- Limits the number of instructions by cluster size
Memory ordering can be maintain by maintaining a single chain for all memory. A simple way is to number all load/store and enforce that a instruction(load/store) X can be executed when all load or store with number less than number of X is executed.
The above algorithm would work well only for sequential logic but when 2 load/store depends on a previous load/store, then they can be executed in parallel.
Hence, we do chaining by a simple rule <P,C,N>. Each memory instruction would store the number of previous memory instruction<P>, its number<C> and the number of next memory instruction.
The following rule has a problem when an instruction has 2 or more instruction as previous instruction. This problem is solved by adding a NOP instruction in one of the path and now each instruction has only one previous instruction.
