Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


543 users

0 votes

Question 2 of sheet #2 states: 

We could admit one student to the room, let him or her finish all registration steps, and then admit the next student. A better solution to increase the throughput would be to pipeline the registration procedure into 5 stages.

Does pipelining mean that as soon as student 1 has finished his first stage, the next student immediately enters the room and starts working? Or can we definie a interval, in which students enter the room? For example: Student 2 enters after X minutes or Student 2 enters after student 1 has finished stage 3 for example (and not stage 2)?

in * TF "Emb. Sys. and Rob." by (350 points)

1 Answer

+1 vote
Best answer

Pipelining simply means to overlap an repeated sequential execution. For instance, assume that the steps S[1]; S[2]; S[3]; S[4] were executed in an infinite loop. Then, the simplest form of pipelining would mean to start the next loop iteration after the first step of the previous iteration has terminated, i.e.,  we have the following execution where each row corresponds to one loop iteration and the columns are the steps in that iteration:

time 1     2     3     4     5     6     7
    S[1]; S[2]; S[3]; S[4];
          S[1]; S[2]; S[3]; S[4];
                S[1]; S[2]; S[3]; S[4];
                      S[1]; S[2]; S[3]; S[4];
As can be seen, after the first 3 steps, the pipeline is filled, and now we execute  S[1]; S[2]; S[3]; S[4] in parallel (instead of a sequence). However, note that the steps  S[1]; S[2]; S[3]; S[4] in the pipeline refer to different loop iterations.
PIpelining is not only used in hardware designs (where it is frequently used), but also in software, where it is sometimes called software pipelining. That is an important compiler technique that statically scheduled processor architectures are using to find more parallelism for the execution of loops.
The filling phase is often called the prolog, and the phase where the pipeline may terminate is called then the epilog.

It is however not required that the next iteration starts one step later. In particular, it is even sometimes required that the next iteration has to start later than that to avoid conflicts. Then, you may have instead a picture like the following below which is still pipelining:

time 1     2     3     4     5     6     7

    S[1]; S[2]; S[3]; S[4];
                S[1]; S[2]; S[3]; S[4];
                            S[1]; S[2]; S[3]; S[4];
                                        S[1]; S[2]; S[3]; S[4];

Clearly, there is less parallel execution in this case, so the initiation interval (which is the time gap between two starting iterations) should be as small as possible. 

by (166k points)
selected by
Imprint | Privacy Policy