Pipelining as a Computational Method (OCR A Level Computer Science): Revision Note

Pipelining as a Computational Method

• Before revising pipelining as a computational method, it is important to revise the concept of pipelining within the CPU first.

What is Pipelining?

• Pipelining is the process of carrying out multiple instructions concurrently 

• It improves the overall efficiency and performance of a task or instruction

• In order to utilise pipelining it can be broken down into the following stages:

  1. Break down the task - analyse the process carefully to identify the individual tasks that make up the overall job

  2. Arrange in sequential order - organise the tasks into a logical sequence, where the output of one task becomes the input for the next

  3. Allow multiple tasks to operate at the same time - instead of waiting for one task to fully complete before starting the next one, allow multiple tasks to operate concurrently

Pipelining in Programming

• In languages such as Python and Java pipelining is chaining multiple instructions together

• Pipelining is a similar concept to an assembly line which is used to make the overall process more efficient

• Here is an example program written in Python that generates squared values of numbers from a list and then filters them to find only the even values

01 list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

02 squared = [x**2 for x in list]

03 filtered = [x for x in squared if x % 2 == 0]

04 print(filtered)

• Line 01 creates a list of ten numbers

• Line 02 uses iteration to square each value in the list one by one and generate a new list called ‘squared’

• Line 3 filters the new list, searching for each even number and adding them to a separate list called "filtered"

• On line 04 we print the filtered list, the final output would be:

[4, 16, 36, 64, 100]

• In the first example commands are separated by being on their own individual numbered lines, in other languages such as Unix the ‘|’ symbol is used to separate commands

• Each command in the ‘pipeline’ is separated and data flows left to right

• An example of the ‘|’ symbol used in Unix:

grep “hello” docs | grep “world”

• Here two grep commands (search) are chained together to perform a specific task

• The first grep command grep “hello” docs searches for lines that contain the word “hello” in a list of files contained in a file named ‘docs’

• The pipe symbol ‘|’ connects the output of the first command to the input of the second command meaning only lines containing the word “hello” are passed to the second command

• The second grep command grep “world” searches for lines in the filtered results from command 1 that contain the word “world”

Evaluating pipelining

When is pipelining most effective?

• Pipelining gives the biggest gain when there are many instructions or tasks to process, because every stage is kept busy

• It works best when:

  • The stages each take a similar amount of time, so no stage holds up the others

  • The tasks run in sequence, so the next task can safely start before the current one finishes

What limits pipelining?

• In a processor, a branch (jump) instruction means the instructions already fetched and decoded behind it may be the wrong ones

• The pipeline has to be flushed (reset) and refilled, which costs time

• A task that depends on the result of the task before it cannot start until that result is ready

• For more detail on how the processor flushes its pipeline, see Pipelining