WaveScalar
Part I: Lecture 4
1. What is the problem being solved?
1.1 Big picture
- Complexity
- Scalable performance (single chip)
- Superscaler does not scale well because of high complexity.
- Reduce wire delay and area of control logic
What’s preventing it?
- Centralized structures with sequential semantics
- Cost (latency and bandwidth) of wires
- Constrained by technology
- Global communication doesn’t scale well.
- Improve locality
- Defect tolerance (The paper doesn’t evaluate on this.)
1.2 Specifics
- Memory ordering semantics
- Convert C to dataflow (Source-level compatibility with superscalar code)
- Exceptions, interrupts (mentioned, not discussed)
- Cache coherence (not discussed)
- Finite storage/tag management (not evaluated)
- Indirect jumps
- Locality
2. Who are the intended users?
- GPP style programs
- Single thread of control
- Von Neumann semantics at programming level
- Aiming for high-end
- Not low-power (Power wasn’t an issue at the time.)
3. Solution
3.1 Dataflow
- Different way of doing program execution
- An instruction fires as input operands are available.
- Example 1: Simple DFG (dataflow graph)
a = b + c
a = a + d
f = 2 * a
jmp L
…
L: e = a + 1
- Example 2: DFG with branch
a = b + c
a = a + d
f = 2 * a
if (f > s)
e = b + 1
else
e = a + 1
g = e * 2
- How do you deal with merged nodes in a DFG? What happens if only one branch fires?
- This is basically illegal. No merge is allowed.
- How do we solve this?
- Replication (DFG may become very large in size.)
- JOIN instruction
- How do you deal with merged nodes in a DFG? What happens if only one branch fires?
- Example 3: DFG with branch and loop
a = b + c
a = a + d
f = 2 * a
if (f > s)
e = b + 1
else
e = a + 1
b = e * 2
- Potential problem: deadlock
- Solution: use tagged data (i.e., dynamically unroll loops) to break the loop causing deadlock.
3.2 Architecture
- Clusters
- To exploit locality
- Interconnect Network
- Mesh topology
- Hierarchy of communication
WaveCache
- An implementation of the WaveScalar ISA
- Clusters arranged in mesh topology
- PEs are grouped into clusters (16 PEs/cluster in paper)
- PEs(Processing Elements) connected through a bus, within each cluster
- Each PE contains storage for 8 instructions, input/output queues, ALU, control logic, and interconnect
- Instructions are bound to PE, and fire when operands are ready
- No traditional fetch/decode/writeback stages, no program counter
- Caches operations (i.e., data, instructions, and state) similar to context switches in OS but loading/eviction is done rather at finer granularity
- When no more space in WaveCache (cache overflow), instructions must be thrown out to bring in new instructions
- Entire states of execution must be evicted, thus slow and heavyweight
- Mapping dataflow to hardware
- Instruction format: opcode, memory address, tag
- Execution
- Handling of multiple outputs
- Broadcast values
- problem: loss of locality, i.e., every PE attempts to output.
- Solutions: unbalance tree or communication through memory loads/stores (trade-offs for space)
- Handling of multiple outputs
- What if a producer outputs data to two consumers at the same time and one of the consumers is missing?
- Bring in and out cacheline but thrashing can be a problem if cache size is small.
- Memory ordering semantics
- Waves?
- {$\equiv$} tags
- {$\equiv$} hyperblock : one entry, multiple exists
- Acyclic
- Memory sequentiality with wave
- Resource constraints (finite store buffers)
- Tradeoff inter/intra wave parallelism
- Waves?
- Assigning wave numbers done dynamically but creating waves done statically by compiler
- Sequential waves, sequential instructions
- Interrupts/Exceptions not supported
4. What about in the context of class?
- Transmeta: dynamic compilation
- WaveScalar: static compilation
Part II: Lecture 5
1. Uniqueness
- Traditional dataflow → Sequential memory semantics in dataflow
- Problems with dataflow
- Interrupts
- Need new programs that play nicely with memory synchronization mechanisms (e.g., full/empty, functional languages)
- Indirect branches (not needed)
- WaveScalar uses distributed tag management.
2. Waves
- CFG portion
- Single entry
- Acyclic
- Resource constraints in hardware
- With large waves, parallelism can be lost.
- Dependency between different waves (i.e., Waves cannot be skipped.)
- Instructions from different waves can execute simultaneously if there are no dependencies, but must complete in-order
- If wave has load/store, the ordering must be maintained, so cannot advance to next wave until everything before is done
- Monotonically increasing wave numbers (assigned by the WAVE-ADVANCE instruction)
- Instruction queues store instructions not in order.
- Instruction consists of
- Inputs (value, pending)
- Output destinations (which one/two instructions depend on it)
- Memory ops have ordering
- Wave number
- Example:
- Each instruction waits for a wave number greater than its current wave number.
| In1 | In2 | Out1 | Out2 | Wave# | ||
| 0 | + | 1 | 0 | 1 | 0 | |
| 1 | + | 1 | 10 | 2 | 0 | |
| 2 | + | 1 | 20 | 0 | 0 | |
| 3 |
3. Memory within a wave
- Traverse CGF in breadth-first order (to make sure of partial orders)
- Create memory ordering dependence
- <pred, mem op #, succ>
- Illegal condition: <2,3,?><?,4,5>
- New rule: No path through the program may contain a pair of memory operations in which the first operation’s successor value and the second operation’s predecessor value are both ‘?’. In such cases, NOP instructions are inserted.
- <2, 3, ?><3, 4, 5><?, 5,6>
- New rule: No path through the program may contain a pair of memory operations in which the first operation’s successor value and the second operation’s predecessor value are both ‘?’. In such cases, NOP instructions are inserted.
- How about the following case? Can WaveCache exploit parallelism among such memory operations?
- No, WaveCache does not support this because the fourth operation can proceed as soon as any one of the first three operations completes, which can violate the actual program order. In the paper, they say it is part of the future work and can be done by relying on memory aliasing information from the compiler.
- <None, 1, ?><None, 1, ?><None, 1, ?><1, 5, ?><5, 7, 8><?, 8, 9>
- No, WaveCache does not support this because the fourth operation can proceed as soon as any one of the first three operations completes, which can violate the actual program order. In the paper, they say it is part of the future work and can be done by relying on memory aliasing information from the compiler.
4. Evaluation
- Used subset of SPEC benchmarks
- Used architectural simulators to measure normalized, Alpha-equivalent IPC
- Used Alpha processor’s binary to avoid writing a new compiler
- Generated waves from the same binary as what Superscalar processors normally use (good for fair comparison)
- IPCs are comparable. Relying on the same binary which ran on alpha hardware
- Presumably, cycle time should be reasonably good because of the light-weight hardware (i.e., not too unconvincing), although they did not do evaluation.
- Used aggressive 16-wide Superscalar OOO core with 16-pipeline stages for comparison
- DID NOT evaluate their operating systems including file I/O, interrupts/exceptions, and virtual memory
- Worst part neglected in evaluation
- No memory systems
- The paper claims locality is important for scalability; however, it neglected performance implications of incorporating memory system in the WaveCache architecture.
