BU/CLA CS-551
Parallel Computing: Models, Languages, and Architectures
Nonlinear pipeline design [problem 6.6 in textbook]
Consider the following pipeline reservation table.
Cycle
.-----------------------.
| | 1 2 3 4 5 6 |
|----+------------------|
| S1 | X X |
Stage | S2 | X X |
| S3 | X |
| S4 | X X |
`-----------------------'
In other words, to complete the execution of the function at hand, we
need to use stage 1 for one cycle, then stage 2 for one cycle, then
stage 3 for one cycle, then stage 4 and stage 2 for one cycle, then
stage 4 for one cycle, then stage 1 for one cycle.
- What are the forbidden latencies for this pipeline?
- Draw the state transition diagram.
- List all the simple latency cycles and all the greedy cycles.
- Determine the optimal latency cycle and the minimal average latency.
- Let the pipeline clock period be 20 nanoseconds. What is the throughput?
This document has been prepared by Professor Azer Bestavros
<best@cs.bu.edu> as the WWW Home Page for
CS-551, which is
part of the NSF-funded
undergraduate curriculum on parallel
computing at BU.
Date of last update: October 19, 1994.