Basic - Paralelismo

Basic for Experts
Paralelismo

Você está em: MarMSX >> Cursos >> BASIC Os computadores que possuem apenas um processador, como o MSX, normalmente executam uma tarefa, programa, sub-rotina etc por vez.
Hoje em dia, é inimaginável termos um computador que rode só uma aplicação por vez, como por exemplo, um browser ativo e um editor de texto aguardando o término da execução do browser. Até mesmo o mouse não pode esperar a execução completa de um aplicativo qualquer, sob pena de perdermos o controle sobre o sistema.
A computação paralela visa o estudo e implementação de sistemas, que são capazes de gerenciar e executar vários programas "ao mesmo tempo". Entretanto, executar dois ou mais programas realmente "ao mesmo tempo" não é possível, quando se tem somente um processador.
A solução então é dividir a execução de cada programa em "fatias", e alternar a execução de cada um no processador. Como os dois (ou mais) caminham sempre, dão a impressão de estar rodando "ao mesmo tempo".
Para atingir tal fim, é necessário dispor de um terceiro programa, responsável por gerenciar e dividir o processador para cada um dos programas que se deseje rodar em paralelo.

O esquema a seguir apresenta como dois programas P1 e P2 rodam sequencialmente e em paralelo.

 Sequencial     Paralelo

  +------+      +------+   
  |      |      |  P1  |   ↓ Tempo
  |  P1  |      +------+
  |      |      |  P2  |
  |      |      +------+
  +------+      |  P1  |
  |      |      +------+
  |  P2  |      |  P2  |
  |      |      +------+
  +------+      |  P1  |
                +------+

O MSX ativa uma interrupção a cada 1/60 segundos, conforme visto no capítulo do temporizador. Essa interrupção será utilizada de tempo em tempo para chamar o gerenciador e trocar a sub-rotina em execução para a outra sub-rotina, e assim, ficar alternando entre elas.

Paralelismo simples

O objetivo é fazer com que duas sub-rotinas funcionem de forma paralela.

Código Sequencial

O seguinte código possui duas sub-rotinas independentes, onde cada uma traça uma linha em diferentes posições.

10 SCREEN 2
100 '
110 ' Linha 1
120 '
130 X=0
140 PSET(X,80),15
150 X=X+1
160 IF X<=255 THEN 140
200 '
210' Linha 2
220 '
230 X=0
240 PSET(X,100),15
250 X=X+1
260 IF X<=255 THEN 240
270 END

Código Paralelo

Será necessária a construção de uma sub-rotina auxiliar, que gerenciará as trocas.
Essa rotina deverá armazenar a última linha executada por cada sub-rotina, para retornar exatamente no mesmo ponto. Para isso, devemos consultar a pilha da instrução GOSUB.
Enquanto esta sub-rotina executa, a interrupção deverá estar desabilitada.

10 SCREEN 2
20 R=0
30 DIM CG(2,4)
40 DIM VX(2)
50 R=1:GOTO 200
60 R=0
70 ON INTERVAL=10 GOSUB 330
80 INTERVAL ON
100 '
110 ' Linha 1
120 '
130 X=0 : VX(0)=0
140 PSET(X,80),15
150 X=X+1
160 IF X1<=255 THEN 140
170 GOTO 170
200 '
210' Linha 2
220 '
225 GOSUB 500
230 X=0 : VX(1)=0
240 PSET(X,100),15
250 X=X+1
260 IF X<=255 THEN 240
270 END
300 '
310 ' Tratamento Int
320 '
330 INTERVAL OFF
340 T=PEEK(&HF6B1)+PEEK(&HF6B2)*256
350 NR = (R+1) MOD 2
360 FOR I=3 TO 6
370 CG(R,I-3)=PEEK(T+I)
380 POKE T+I,CG(NR,I-3)
390 NEXT I
400 VX(R)=X:X=VX(NR)
410 R=NR
420 INTERVAL ON
430 RETURN
500 '
510 ' Salva contexto
520 '
530 T=PEEK(&HF6B1)+PEEK(&HF6B2)*256
540 FOR I=3 TO 6
550 CG(R,I-3)=PEEK(T+I)
560 NEXT I
570 RETURN 60

As linhas 340-390 armazenam em uma tabela os valores da pilha do GOSUB para cada sub-rotina chamada, ao mesmo tempo que já substitui a pilha com os valores da outra sub-rotina.
A primeira interrupção é feita pela sub-rotina 1, onde obtemos os dados referentes à pilha diretamente. Entretanto, os valores da pilha da sub-rotina 2 são desconhecidos. Para resolver esse problema, criamos um desvio com o GOSUB no inicio dessa sub-rotina, para armazenar o contexto inicial da pilha dessa rotina (linhas 530-570), antes de começar o paralelismo.
O contexto da variável "X" é armazenado na tabela VX, que contém o valor corrente de "X" de cada sub-rotina.

O programa a seguir adiciona mais uma sub-rotina e desenha três linhas na tela "ao mesmo tempo".

10 SCREEN 2
20 R=0
30 DIM CG(3,4)
40 DIM VX(3)
50 R=1:GOTO 200
60 R=2:GOTO 300
65 R=0
70 ON INTERVAL=10 GOSUB 530
80 INTERVAL ON
100 '
110 ' Linha 1
120 '
130 X=0 : VX(0)=0
140 PSET(X,80),15
150 X=X+1
160 IF X1<=255 THEN 140
170 GOTO 170
200 '
210' Linha 2
220 '
225 GOSUB 700
230 X=255 : VX(1)=255
240 PSET(X,100),15
250 X=X-1
260 IF X>=0 THEN 240
270 END
280 GOTO 280
300 '
310' Linha 3
320 '
325 GOSUB 700
330 X=0 : VX(2)=0
340 PSET(X,120),15
350 X=X+1
360 IF X<=255 THEN 340
370 END
380 GOTO 380
500 '
510 ' Tratamento Int
520 '
530 INTERVAL OFF
540 T=PEEK(&HF6B1)+PEEK(&HF6B2)*256
550 NR = (R+1) MOD 3
560 FOR I=3 TO 6
570 CG(R,I-3)=PEEK(T+I)
580 POKE T+I,CG(NR,I-3)
590 NEXT I
600 VX(R)=X:X=VX(NR)
610 R=NR
620 INTERVAL ON
630 RETURN
700 '
710 ' Salva contexto
720 '
730 T=PEEK(&HF6B1)+PEEK(&HF6B2)*256
740 FOR I=3 TO 6
750 CG(R,I-3)=PEEK(T+I)
760 NEXT I
770 IF R=1 THEN RETURN 60 ELSE RETURN 65

Nos dois programas apresentados, quanto menor o tempo de interrupção para a troca de sub-rotinas, maior será o tempo de execução total. Isto acontece porque cada troca de contexto consome um tempo considerável e, quanto menor o tempo, maior o número de trocas.
No MSX Turbo-R, experimente trocar o intervalo da linha 70 de 10 para 1. A impressão é de que as três linhas estão sendo desenhadas "ao mesmo tempo".

Paralelismo com o laço FOR

O paralelismo para sub-rotinas que possuem o laço FOR é um desafio maior, pois a pilha do FOR deverá ser gerenciada na troca de sub-rotinas.

O capítulo do temporizador possui um programa que desenha um círculo na tela, ponto a ponto. Deste modo, vamos aproveitar esse programa para testar o paralelismo. A idéia aqui é criar uma nova sub-rotina de desenho de círculo, que desenha outro círculo em posição diferente do primeiro.

Código Sequencial

O código sequencial irá desenhar os dois círculos, sendo que um de cada vez.

10 SCREEN 2
100 ' Desenho 1
110 P1=90 : P2=60
120 FOR AA=0 TO 6.4 STEP 0.2
130 P3=60+COS(AA)*30 : P4=60-SIN(AA)*30
140 LINE(P1,P2)-(P3,P4),15
150 P1=P3 : P2=P4
160 NEXT AA
200 ' Desenho 2
210 Q1=150 : Q2=120
220 FOR AB=0 TO 6.4 STEP 0.2
230 Q3=120+COS(AB)*30 : Q4=120-SIN(AB)*30
240 LINE(Q1,Q2)-(Q3,Q4),15
250 Q1=Q3 : Q2=Q4
260 NEXT AB
270 GOTO 270

É importante ter o nome das variáveis diferentes nas duas sub-rotinas, para que não haja confusão quando houver o paralelismo.

Código em Paralelo

O objetivo agora é modificar o programa anterior, de forma que as sub-rotinas "Desenho 1" e "Desenho 2" sejam alternadas durante uma determinada fração de tempo.
A instrução INTERVAL-GOSUB será utilizada para chamar a sub-rotina que faz o gerenciamento de troca de sub-rotinas, a cada 2 segundos.
Foi visto no capítulo extra de pilhas que o GOSUB-RETURN e o FOR-NEXT escrevem dados na pilha, e que estes servem para o interpretador Basic se orientar. Então, não basta somente trocar a sub-rotina em execução. Há a necessidade de modificar a pilha, de forma que a informação de cada sub-rotina seja a correta.
Desse modo, temos que salvar o contexto da pilha tanto para o GOSUB, como para o FOR, e modificá-los na pilha, quando houver a troca de sub-rotina.

O programa que desenha os círculos "ao mesmo tempo" é apresentado a seguir. Rode-o em um MSX 1, 2 ou 2+.

10 SCREEN 2
20 R=0
30 DEFINT C
40 DIM CG(2,4)
50 DIM CF(2,25)
60 GOTO 200
70 ON INTERVAL=120 GOSUB 310
80 INTERVAL ON
100 ' Desenho 1 (R=0)
110 P1=90 : P2=60
120 FOR AA=0 TO 6.4 STEP 0.2
125 CF(0,0)=&H82
130 P3=60+COS(AA)*30 : P4=60-SIN(AA)*30
140 LINE(P1,P2)-(P3,P4),15
150 P1=P3 : P2=P4
160 NEXT AA
165 CF(0,0)=0
170 GOTO 170
200 ' Desenho 2 (R=1)
205 GOSUB 500
210 Q1=150 : Q2=120
220 FOR AB=0 TO 6.4 STEP 0.2
225 CF(1,0)=&H82
230 Q3=120+COS(AB)*30 : Q4=120-SIN(AB)*30
240 LINE(Q1,Q2)-(Q3,Q4),15
250 Q1=Q3 : Q2=Q4
260 NEXT AB
265 CF(1,0)=0
270 GOTO 270
300 ' Tratamento de interrupção
310 INTERVAL OFF
320 T=PEEK(&HF6B1)+PEEK(&HF6B2)*256
330 NR = (R + 1) MOD 2
340 FOR I=3 TO 6
350 CG(R,I-3)=PEEK(T+I)
360 POKE T+I, CG(NR,I-3)
370 NEXT I
380 FOR I=7 TO 31
390 IF CF(R,0)<>0 THEN CF(R,I-7) = PEEK(T+I)
400 IF CF(NR,0)<>0 THEN POKE T+I,CF(NR,I-7)
410 NEXT I
420 R=NR
430 INTERVAL ON
440 RETURN
500 ' Pega contexto de Desenho 2
510 T=PEEK(&HF6B1)+PEEK(&HF6B2)*256
520 FOR I=3 TO 6
530 CG(1,I-3) = PEEK(T+I)
540 NEXT I
550 RETURN 70

Os dois círculos não desenham exatamente ao mesmo tempo, mas uma parte de cada um vai sendo desenhada na tela alternadamente.
Ao executar o programa, observa-se que o tempo de desenho para os dois círculos aumentou em relação ao desenho seqüencial. Este tempo extra é conseqüẽncia do tratamento da interrupção e da troca de contexto, necessária ao funcionamento do programa.

Os principais passos do programa são:

Criar variáveis para o gerenciador de troca de sub-rotinas.
- A variável "R" indica sub-rotina atual.
- CG é a matriz de contexto do GOSUB na pilha, para cada uma das sub-rotinas.
- CF é a matriz de contexto do FOR na pilha, para cada uma das sub-rotinas.
Salvar o contexto do GOSUB para a sub-rotina "Desenho 2".
- A primeira troca irá necessitar do contexto do "Desenho 2", que ainda não existe.
- Desviamos da linha 60 para a linha 205, para criar um contexto nessa linha.
- Utilizamos o "GOSUB 500" na linha 205 para criar o contexto do GOSUB na memória e salvá-lo na matriz CG, através da sub-rotina "Pega contexto de Desenho2".
- O retorno é forçado para a linha 70.
- O contexto de "Desenho 1" será salvo na primeira interrupção do sistema.
Determinar o intervalo da interrupção e ativá-la.
Sinalizar a entrada e saída dos laços FOR em cada sub-rotina.
- Isto facilita a identificação ser o FOR está ou não ativo em uma sub-rotina.
Começar a sub-rotina "Desenho 1".
Quando o programa é interrompido, desviar para a sub-rotina de gerenciamento.
- Desabilitar a interrupção antes de qualquer coisa.
- Trocar o contexto na pilha do GOSUB de um "Desenho" para o outro.
- Trocar o contexto na pilha do FOR de um "Desenho" para o outro, caso o FOR tenha sido atingido.
- Indicar a nova rotina em execução.
- Ao final, habilitar novamente a interrupção e retornar.

Dicas:

Experimente alterar o intervalo na linha 70 para 80, e depois para 40.
Rode o programa em um MSX Turbo-R e mude o intervalo na linha 70 para 6. Repare que o desenho dos círculos parece bem mais "ao mesmo tempo" que nos outros casos.

Considerações Finais

O paralelismo demonstrado nesse capítulo tem somente objetivo de apresentar o conceito, visto que ele é muito pesado para rodar uma linguagem interpretada como o Basic do MSX.
Entretanto, ele foi brilhantemente implementado em linguagem de máquina Z-80 no sistema operacional SymbOS, por Jörn Mika. Como prova disso, podemos observar várias aplicações rodando ao mesmo tempo em diferentes janelas.

Obviamente, para desenhar dois círculos ao mesmo tempo na tela como efeito de animação, basta colocar o comando de desenho de cada círculo no mesmo laço FOR.

<< Anterior

Basic

Próxima >>