Parallelism, Pipelining, and Graph Folding
Parallelism, Pipelining, and Graph Folding
m Parallelism: Multiple functional units at the same level in the graph active at the same time.
m Pipelining: Functional units on multiple levels of the graph being active at the same time.
m Widthwise Graph Folding: restricts parallelism with the addition of symbolic dependencies.
Ô Limiting case: Multi-stage pipelined processor with feedback and memories between the stages.
m Lengthwise Graph Folding: decreases the number of levels in the graph with the addition of symbolic multiplexers.
Ô Similar to colored tokens in dataflow computer systems (Arvind, 1978).Ô Implementation of the folded graph need not use actual multiplexers.Ô Limiting Case: Parallel processor with an interconnection network to switch values between processors and memories.
EE290H, Fall 87