You will be able to
- Count radix-2 stages and approximate byte traffic.
- Separate analytical traffic estimates from runtime measurements.
The staged computation
For N=2ᵖ, a radix-2 FFT has p stages and N/2 butterflies per stage. Arithmetic structure reduces the DFT cost, but runtime also depends on memory movement, layout, occupancy, launch costs and numerical precision. Operation count alone does not capture these constraints.
A model with disclosed assumptions
The lab assumes each stage reads and writes the full complex-FP32 buffer in global memory. Complex FP32 uses 8 bytes per value, so traffic is 16N bytes per stage per batch. An ideal one-read/one-write I/O floor is 16N bytes per batch. Real implementations reuse data and may move workspace, twiddles and intermediate results; neither column is a runtime prediction.
Worked example
N=1024 has 10 stages and 5120 butterflies per transform. For one batch, model traffic is 163840 bytes versus an ideal 16384-byte floor. Their ratio is 10, not an observed 10× speedup.
A common trap
An analytical byte ratio is not a speedup claim. Hardware measurements need validated outputs and a disclosed environment.
Predict, then experiment
Will doubling batch change the byte ratio, the absolute traffic, or both? Before touching the controls, say or write your prediction.
Interactive experiment
Count traffic before timing it
How much data could a stage-by-stage FFT move?
Radix-2 complex FP32 model: each stage reads and writes the whole buffer once. The ideal column counts only one input read and output write. Neither is a measured runtime or a complete convolution pipeline.
Your experiment
Use log₂ length 10. Compare batches 1 and 8, then transform powers 8 and 12. Read MB labels as well as relative bar heights.
Change one parameter at a time. Compare what you observed with your prediction and record an explanation in your notes.
Check your understanding
Try from memory first. Hints and feedback are part of learning, not a penalty. These checks are for self-study, not a graded qualification.
Reference answers (after your attempt)
- an analytical byte ratio under stated assumptions — Correct: the model explicitly counts bytes.
- 11stages — 2048=2¹¹.
Apply it: Write a traffic budget
Use paper, your notes, or a local notebook/editor. Code examples are Python 3 starting points to run yourself; this page does not execute code or automatically assess the practical task.
- For N=256 and batch 4, calculate stage count.
- Calculate complex FP32 ideal bytes and model stage bytes.
- List at least two real costs omitted by the model.
Reference solution & review criteria
8 stages; ideal bytes=16×256×4=16384; stage model=131072. Omitted costs include twiddle/workspace traffic, cache reuse, launches, transfers and layout conversions.
Your notebook
Notes and progress stay in this browser. They are not sent to the server; ordinary web-server request logs still operate. Export a backup from the course page.
Completion requires both correct checks and your practical-task acknowledgement.
Go deeper
Sources support further study; the worked examples and questions here are original. Browser experiments are small, disclosed models—not evidence of production-model quality or hardware performance.