Computational methods: pipelining, visualisation and choosing a method

Overview

Recall questions on pipelining outside the processor and what limits it, visualisation and its limitations, backtracking compared with heuristics, choosing the computational method that fits a problem, and combining methods in a satnav.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is pipelining?

   Model answer

   Splitting a process into a series of stages and keeping every stage busy on a different item at the same time, so that a completed item emerges at the rate of one stage rather than one whole process. In a processor, while one instruction is being executed the next is being decoded and a third is being fetched. The time taken by any single item is not reduced — it still has to pass through every stage — but the throughput, the number completed per unit of time, rises towards one per stage-time instead of one per whole process.

2. 2

   A job passes through four stages, each taking one unit of time, and there are 10 jobs to do. How long does it take without pipelining and with, and what is the general rule?

   Model answer

   Without pipelining each job is finished before the next begins, so the total is 10 x 4 = 40 units. With a four-stage pipeline, the first job still takes 4 units to emerge, but after that one job completes every unit, so the total is 4 + 9 = 13 units — a little over three times faster here, approaching four times as the number of jobs grows. The general rule for n jobs and k equal stages is k + (n - 1) stage times, against n x k without pipelining, so the speed-up tends towards k when n is large and is poor when n is small.

3. 3

   What limits the benefit of pipelining?

   Model answer

   The pipeline runs at the speed of its slowest stage, because all stages must hand on together, so stages of unequal length waste time in the faster ones. A branch or jump means the items already fetched and decoded are the wrong ones, so the pipeline must be flushed and refilled and several stage-times are lost — which is why processors go to such lengths to predict branches. A dependency, where one instruction needs the result of the one immediately before it, stalls the pipeline until that value is available. Deeper pipelines make these penalties worse and cost extra hardware to hold the intermediate results between stages. And pipelining gives nothing at all for a single item run once: the gain only appears with a steady stream of work.

4. 4

   Pipelining is not only a processor technique. Give an example of it applied elsewhere and say what is gained.

   Model answer

   Any repeated multi-stage process can be pipelined. A video-encoding system splits the work into read a frame, convert the colour, compress, package and write out; while frame 5 is being written, frame 6 is being compressed and frame 7 read, so the disc, the processor and the network are all busy at once instead of taking turns. A research data pipeline might extract, clean, analyse and visualise, with each stage working on a different batch. The idea is identical: divide the work into stages with a clean hand-off between them and keep every stage occupied. The gain is throughput and better use of the hardware, not a faster time for any single item.

5. 5

   What is visualisation as a computational method?

   Model answer

   Presenting data, or the problem itself, in a graphical form so that patterns, trends, relationships and outliers become visible that were hidden in rows of figures — exploiting the fact that people read pictures far faster and more reliably than tables of numbers. It is used both to explore data, spotting where something interesting lies before deciding what to analyse in detail, and to communicate findings to people who will never read the raw numbers. It also covers drawing the problem — a network diagram, a graph of connections, a flowchart — to help understand its structure and design a solution.

6. 6

   Give a worked application of visualisation.

   Model answer

   A police force holds several years of individual crime reports, each with a type, a time and a location: millions of rows that nobody can read. Plotted as a heat map of the city, the concentrations of burglary are visible immediately; adding a time control shows a hotspot that appears only on Friday and Saturday nights around one street; a line chart by month shows whether the level is rising or falling. Patrols can then be targeted at the places and times the map identifies, and the effect checked on the same map a month later. A second example: plotting two variables against each other as a scatter chart shows at a glance whether they move together, and exposes the handful of outlying cases that an average would have concealed entirely.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.