Sobre um algoritmo de pipeline
Um algoritmo de pipeline baseia-se no relacionamento que se dá
entre um processo e o processo seguinte, em que o output de um é o input do seu
sucessor.
O input do primeiro processo é o input do algoritmo e
o output do ultimo é o output do algoritmo.
Cada processo consiste numa parte do pipeline e numa
pequena parte do algoritmo
gasta uma unidade de tempo no processo A, outra no B
e outra no C, assim so elabora um item em 3 unidades de tempo.
a maquina é dividida em três pequenas maquinas uma
que faz o passo A, outra o B e outra o C, operando simultaneamente.
Na primeira operação o item so aparece passado três
unidades de tempo,
mas nos passos seguintes apenas demora uma unidade de
tempo a completar um item.
Npassos é o numero de passos.
T
é o tempo para cada passo.
NItens é numero de
itens.
Fórmulas
Gerais
Esta fórmula é para o caso de os tempos de
todos os processos serem diferentes:
Um exemplo de aplicação destas formulas:
No caso de o tempo de todos os processos ser o
mesmo:
Se houver 3 passos A, B e C para construir 7 itens e
se assumirmos que cada passo demora 1 unidade de tempo, ou seja:
T
=1 unidade de tempo
Npassos=3 passos
NItens = 7 itens
Tprimeiro item=3*1*1=3 unidades de tempo
Tsegundo item=3*1*2=6 unidades de tempo
Tsequencial=3*1*7=21 unidades de tempo
Tprimeiro item=(3+1-1)*1= 3 unidades de tempo
Tsegundo item=(3+2-1)*1= 4 unidades de
tempo
TParalelo=(3+7-1)*1=9
unidades de tempo
Para o caso de os tempos de cada processo serem
diferentes:
Se houver 3 passos, para construir 7
itens e se cada passo demorar 3, 2 e 1 unidades de tempo respectivamente:
Tsequencial
= (3+2+1)*7 = 42
Tparalelo=((3+2+1)+(7-1))*3=36
unidades de tempo
Um Algoritmo desenvolvido num sistema pipeline
(paralelo), demora menos unidades de tempo do que num sistema sequencial, isto
devido a num sistema de pipeline os processos serem executados simultaneamente
e num sistema sequencial um processo ter de esperar pelo fim de execução
do seu processo antecessor.
Temos de ter em conta que no primeiro item isto não
acontece, demorando em ambos os sistemas o mesmo tempo de execução.