Reference : Introduction to Parallel Computing, Edition Second by Vipin Kumar et al
Pipelinig
- There are three types of pipelining;
- Adding numbers (type 1)
- Insertion Sort (type 2)
- Linear System back substitution (type 3)
- Prblems that can be divided into a series of seq tasks that can be completed one after another.
- Typical Scenario
- 독립된 문제가 한 개 이상 계산 될 예정일때 (Instruction)
- 각각 여러 계산을 필요로 하는 연결된 데이터들을 계산되어야 할때 (Graphics)
- 다른 계산에 필요한 작업이 그 계산이 필요로 하기전에 작업을 마칠수 있을때 (Software)
Type 1 - Adding number
- Single Intance:
- Multiple Instance:
Type 2 - Insertion Sort
Type 3 - Linear Equations
Back substitution —> passes calculated value to solve the other ones (like fibonacci).
Process i performs i sends and receives, i multiply/adds, one division/subtract and one final send
t_comm = (2i + 1) * (t_s +t_w) and t_comp = 2i + 2
