Lezione  V                       FRAMES  NOFRAMES

Il linguaggio macchina: Parte 3

Riassumiamo cosa abbiamo visto a proposito dei programmi per risolvere i problemi.

a) Dati  e  Istruzioni  devono stare in memoria centrale MC per poter essere usati/eseguite

b) Le Istruzioni sono espresse come sequenze di bit esprimenti CODICI <---> CIRCUITI della CPU ed indirizzi di operandi.

c)  Un programma eseguibile fatto di una sequenza di     istruzioni macchina.

d)  Il programma viene eseguito sequenzialmente.

e)  Il linguaggio macchina LM ha poche istruzioni e con queste poche noi scriviamo il programma.

Adesso facciamo qualche aggiunta al linguaggio macchina per "arricchirlo" introducendo altre istruzioni:             

1)  L' istruzione  STOP  per interrompere il "flusso sequenziale" ossia arresta l'esecuzione del programma.

2)  L'istruzione di  salto " Alterazione incondizionata" , o Salto incondizionato, modifica l' ordine sequenziale di esecuzione delle istruzioni: " invece di eseguire la prossima istruzione il cui indirizzo contenuto nel PC esegui quella di un' altra cella"; per cui questa istruzione modifica il valore contenuto nel registro PC, inserendovi l' indirizzo della cella a cui vogliamo saltare.

3)  L'istruzione di   salto " Alterazione condizionata" , o Salto condizionato del flusso di esecuzione. Talvolta si preferisce che la sequenza di esecuzione non sia quella normale n quella di saltare in assoluto ad una cella prestabilita, ma di saltare ad una certa cella   se vale una certa condizione ad esempio vi sono delle istruzioni che realizzano il salto soltanto se il contenuto del registro ACC positivo.

Le istruzioni di salto agiscono modificando il contenuto del PC e cancellando gli effetti dell' incremento automatico ossia la
( PC ) <---- ( PC ) + 1, eseguito dopo il FETCH.

 

vediamo nella tabella altre istruzioni del linguaggio macchina

 

Tabella 5.1

Sintassi

                     Semantica

Codice operativo

Operando

 

8

IND

se (ACC) >=0

( PC ) <--- IND

(altrimenti nulla)

cambia il contenuto del PC solo se il   ( ACC) >= 0

salto condizionato

7

IND

( PC ) <--- IND

salto incondizionato

Consideriamo adesso un   esempio di programma   che:
dati due numeri,   stampi il maggiore  fra i due.

Analisi

E'  semplice. Abbiamo bisogno di due locazioni di memoria per contenere i due numeri letti da Ingresso; dobbiamo confrontare il  primo con il secondo numero e stampare il maggiore. Il confronto diretto tra due numeri contenuti in celle di memoria centrale impossibile.

Algoritmo

Se il  primo numero maggiore del   secondo  stampare il primo altrimenti stampare il secondo.

Raffinamento

Per vedere se   primo>=secondo   verifichiamo se  primo-secondo>=0    

a)  leggi il primo numero e memorizzalo

b)  leggi il secondo numero e memorizzalo

c)  copia il primo in ACC

d)  sottrazione ( ACC ) - secondo ed il risultato va in ACC

e)  se il   ( ACC ) >= 0  continua  l'esecuzione con l'istruzione di stampa poich vuol dire che   primo >= secondo , altrimenti esegui l'istruzione successiva a questa

f)  stampa il secondo numero

g)  prosegui verso la fine senza stampare il primo

h)  stampa il primo numero

i)  STOP

L'esecuzione sequenziale ma in alcuni punti non lo infatti f) ed h) sono alternative. Se vale la condizione in e) viene eseguita l'istruzione h) e poi i), se non vale la condizione e) viene eseguita f) poi g) poi i).

Programmazione

Vogliamo inserire il primo e secondo numero nelle celle di memoria di indirizzo        201 202  rispettivamente per cui il programma sar :

0) ( 201 ) <---- ( UL )

1) ( 202 ) <---- ( UL )

2) ( ACC ) <---- ( 201)

3) ( ACC ) <---- ( ACC ) - ( 202 )   (ACC) <--- {primo-secondo}

4) se ( ACC ) >= 0 

prosegui a stampare il primo numero vai in 7) cio ( PC ) <--- 7, altrimenti continua in sequenza.

5) ( US ) <---- ( 202 )   { stampa del secondo numero }

6) ( PC ) <---- 8

7) ( US ) <---- ( 201 )   { stampa primo numero}

8) STOP

Assumiamo che le informazioni siano caricate in memoria a partire dall'indirizzo 0 ed i dati di input vengano memorizzati nelle celle di indirizzo 201 e 202

Indirizzo

cod. op.

operando

0

 5

 201

1

 5

 202

2

 3

 201

3

 2

 202

4

 8

 7

5

 6

 202

6

 7

 8

7

 6

 201

8

 9

 ...............

9

 

 

10

 

 

Complemento alle lezioni  sul linguaggio macchina.

1) Leggere due numeri da input, sommarli e stampare il risultato.

- Nella tabella di sinistra il programma scritto nelle celle di memoria a partire dalla cella di indirizzo 100. I numeri vengono rappresentati nella forma pi consueta (rappresentazione decimale). Le istruzioni sono composte da un numero per il codice e uno per l'indirizzo dell'operando.

- Il corrispondente programma in linguaggio macchina, scritto usando la rappresentazione binaria dei numeri, nella tabella a destra. Le celle di indirizzo 0 (00000000 binario), 1 (00000001), 2 (00000010) vengono riempite solo durante l'esecuzione del programma. Le istruzioni sono interpretate come segue: i primi tre bit per il codice dell'istruzione, i restanti 8 per l'indirizzo dell'operando.

 

 

rappresentazione decimale di istruzioni e indirizzi rappr. binaria di istruzioni e indirizzi

 

indirizzi

contenuto celle

operazione

indirizzi

contenuto celle

0

(primo numero)

 

00000000

(primo numero)

1

(secondo ")

 

00000001

(secondo ")

2

(risultato)

 

00000010

(risultato)

3

 

 

00000011

 

 

 

 

 

 

 

 

 

 

 

99

 

 

01100011

 

100

5  0

lettura primo numero

01100100

10100000000

101

5  1

lettura sec. numero

01100101

10100000001

102

3  0

caricamento

01100110

01100000000

103

1  1

somma

01100111

00100000001

104

4  2

memorizzazione

01101000

10000000010

105

6  2

stampa

01101001

11000000010

106

 

 

01101010

 

Il programma precedente fatto per usare le celle 0, 1, 2 per i dati di input/output. Nelle tabelle seguenti, il programma riscritto per funzionare usando le celle di indirizzi 10 (00001010 binario), 11 (00001011) e 12 (00001100) per i dati di inp/out.

rappr. decimale di istruzioni e indirizzi rappr. binaria di istruzioni e indirizzi

 

indirizzi

contenuto celle

operazione

indirizzi

contenuto celle

0
 
(cella inutilizzata)
00000000
 
1
 
(cella inutilizzata
00000001
 
...
   
...
 
...
   
...
 
10
(primo numero)
 
00001010
(primo numero)
11
(secondo ")
 
00001011
(secondo ")
12
(risultato)
 
00001100
(risultato)
13
   
00001101
 
     
...
 
     
...
 
99
   
01100011
 
100
5 10
lettura primo num.
01100100
10100001010
101
5 11
lettura sec. num.
01100101
10100001011
102
3 10
caricamento
01100110
01100001010
103
1 11
somma
01100111
00100001011
104
4 12
memorizzazione
01101000
10000001100
105
6 12
stampa
01101001
11000001100
106
   
01101010
 

Un p di numeri (a sinistra) scritti in formato binario (a destra)
 

0

0

 

5

101

 

10

1010

 

15

1111

 

20

10100

 

100

1100100

1

1

 

6

110

 

11

1011

 

16

10000

 

30

11110

 

1000

1111101000

2

10

 

7

111

 

12

1100

 

17

10001

 

32

100000

 

1024

10000000000

3

11

 

8

1000

 

13

1101

 

18

10010

 

50

110010

 

2048

100000000000

4

100

 

9

1001

 

14

1110

 

19

10011

 

60

111100

 

4096

1000000000000


  

2) Dati due numeri, stampare il maggiore.

Analisi  : ci servono due locazioni di memoria (celle), per contenere i due numeri letti da input.

Dovremo confrontare il 1 con il 2 numero e stampare quello maggiore.

Il confronto diretto tra due numeri contenuti in celle di memoria centrale impossibile;

osserviamo che 1 >= 2 se e solo se 1 - 2  >= 0. Se facciamo in modo che il numero 1-2 sia messo nell'accumulatore, potremo usare l'istruzione di codice 8 (che l'unica che permette un qualche tipo di test.

Sintesi dell'Algoritmo:

  1. leggere il 1 numero e memorizzarlo
  2. leggere il 2 numero e memorizzarlo
  3. copiare il 1 in ACC
  4. sottrazione: (ACC) <-- (ACC) - 1
  5. se (ACC) >= 0 allora proseguire dalla istruzione h (altrimenti la prossima istruzione la f)
  6. stampare il 2 numero
  7. saltare all'istruzione i
  8. stampare il 1 numero
  9. STOP
Programmazione (Codifica dell'algoritmo usando il linguaggio di programmazione): assumiamo che le   istruzioni  siano caricate in memoria centrale   a partire dall'indirizzo 0  e i  dati di input vengano memorizzati nelle   celle di indirizzo 201 e 202.   (Nella figura si vede un pezzo della memoria centrale, in cui stato caricato il programma: i numeri in corsivo indicano indirizzi di celle).

 


 

0 5 201 (201) <-- (UL)  
1 5 202 (202) <-- (UL)  
2 3 201 (ACC) <-- (201)  
3 2 202 (ACC)<--(ACC)-(202) 200  
4 8 7 se (ACC) >= 0 (PC)<--7 201  
5 6 202 (US)<--(202) 202  
6 7 8 (PC)<-- 8  
7 6 201 (US)<-- (201)  
8 9 … STOP  
9        
     

Esecuzione simulata, supponendo INPUT = 12 seguito da 7
Inizialmente (quando il programma deve essere eseguito) l'indirizzo della prima istruzione viene posto nel registro PC della CPU. PC=0
Fetch: (IR) <-- (0) e incremento di (PC) IR=<5 201> PC=1
Execute Viene recepito il 12 da UL e copiato in (201) (201)=12
Fetch: (IR) <-- (1) e incremento di (PC) IR=<5 202> PC=2
Execute Viene recepito il 7 da UL e copiato in (202) (202)=7
Fetch: (IR) <-- (2) e incremento di (PC) IR=<3 201> PC=3
Execute Viene caricato in ACC il contenuto della cella 201 (ACC)=12
Fetch: (IR) <-- (3) e incremento di (PC) IR=<2 202> PC=4
Execute Viene sottratto il cont. Della cella 202 da ACC. Ris. In (ACC). (ACC)=5
Fetch: (IR) <-- (4) e incremento di (PC) IR=<8 7> PC=5
Execute (ACC) maggiore di 0, quindi (PC) <-- 7
Fetch: (IR) <-- (7) e incremento di (PC) IR=<6 201> PC=8
Execute stampa di (201) sull'unit di OUTPUT
Fetch: (IR) <-- (8) e incremento di (PC) IR=<9 > PC=9
Execute STOP (fine programma)
Notiamo che le istruzioni nelle celle 5 e 6 non sono state eseguite (sono state saltate).

Esecuzione simulata, supponendo INPUT = 4 seguito da 16
Inizialmente (quando il programma deve essere eseguito) l'indirizzo della prima istruzione viene posto nel registro PC della CPU. PC=0
Fetch:   (IR) <-- (0)  e incremento di (PC) IR=<5 201> PC=1
Execute Viene recepito il 4 da UL e copiato in (201) (201)=4
Fetch:   (IR) <-- (1)  e incremento di (PC) IR=<5 202> PC=2
Execute Viene recepito il 16 da UL e copiato in (202) (202)=16
Fetch:   (IR) <-- (2)  e incremento di (PC) IR=<3 201> PC=3
Execute Viene caricato in ACC il contenuto della cella 201 (ACC)= 4
Fetch:   (IR) <-- (3)  e incremento di (PC) IR=<2 202> PC=4
Execute Viene sottratto il cont. Della cella 202 da ACC. Ris. In (ACC) (ACC)= -12
Fetch:   (IR) <-- (4)  e incremento di (PC) IR=<8 7> PC=5
Execute (ACC) minore di 0, quindi NESSUNA MODIFICA DI PC
Fetch:   (IR) <-- (5)  e incremento di (PC) IR=<6 202> PC=6
Execute stampa di (202) sull'unit di OUTPUT
Fetch:   (IR) <-- (6)  e incremento di (PC) IR=<7 8> PC=7
Execute Viene modificato PC, in modo che la prossima istruzione sia quella in cella 8 PC=8
Fetch:   (IR) <-- (8)  e incremento di (PC) IR=<9 > PC=9
Execute STOP (fine programma)
Notiamo che le istruzioni nella cella 7 non stata eseguita ( stata saltata).
 
 

3) Leggere TRE numeri da input e stampare il pi grande.

Algoritmo

1) leggere i tre numeri e memorizzarli in tre celle, di indirizzo DATO1, DATO2, DATO3

2) mettere il maggiore tra il 1o e il 2o nella cella di indirizzo PARZ12;

3) stampare il maggiore tra i numeri in PARZ12 e DATO3

Assumiamo che il programma sia caricato in memoria centrale a partire dall'indirizzo 0, e che DATO1=201, DATO2=202, DATO3=203, PARZ12=204.

Sia il punto 2) che il 3) possono essere risolti sfruttando l'esempio "Stampare il maggiore tra due numeri". Infatti il punto 2) dell'algoritmo molto simile a quell'esercizio: invece di "stampare il maggiore tra 1 e 2 numero" bisogna "memorizzare in PARZ12 il maggiore tra 1 e 2 numero).
2) mettere il maggiore tra il 1o e il 2o nella cella di indirizzo PARZ12;

2.1) mettere il primo in ACC

2.2) mettere in ACC la differenza tra (ACC) e secondo numero

2.3) se (ACC) >= 0 allora il primo era maggiore del secondo,

quindi eseguire solo le istruzioni 2.7 e 2.8, che mettono il 1 nella cella PARZ12

altrimenti   eseguire le istruzioni successive 2.4, 2.5 per mettere il 2 in PARZ12

(ma poi dovremo saltare le 2.7 e 2.8).
2.4) mettere il contenuto della cella DATO2 nell'ACC

2.5) mettere il contenuto dell'ACC nella cella PARZ12 (ora DATO2 in PARZ12)

2.6) proseguire oltre le due istruzioni successive

2.7) mettere il contenuto della cella DATO1 nell'ACC

2.8) mettere il contenuto dell'ACC nella cella PARZ12 (ora DATO1 in PARZ12)

Il punto 3 proprio la stessa cosa dell'esercizio "Stampare il maggiore tra due numeri". Solo che i due numeri da confrontare sono quelli in PARZ12 e in DATO3.
3) mettere il maggiore tra il 1o e il 2o nella cella di indirizzo PARZ12;

3.1) mettere (PARZ12) nell'accumulatore

3.2) mettere in ACC la differenza tra (ACC) e (DATO3)

3.3) se (ACC) >= 0 allora (PARZ12) era maggiore di (DATO3), Cio (PARZ12) era il numero pi grande tra i tre dati in INPUT. In tal caso bisogna saltare ad un'istruzione che stampi (PARZ12) e poi fermarsi.   Altrimenti  stampare (DATO3) e poi procedere verso lo STOP.
DA QUI: PROSEGUIRE DA SOLI e poi controllare il programma scritto con quello che segue!

Raffinamento dell'Algoritmo Programmazione

 

indirizzi           

semantica

commenti

istruzioni

0
(DATO1) <- (UL)
lettura primo dato e memorizzazione nella cella di indirizzo DATO1
5 201
1
(DATO2) <- (UL)
...
5 202
2
(DATO3) <- (UL)
...
5 203
3
(ACC) <- (DATO1)
per mettere il maggiore tra DATO1 e DATO2 in PARZ12, prima il primo numero in ACC
3 201
4
(ACC) <- (ACC) - (DATO2)
diff tra 1o e 2o in ACC
2 202
5
se (ACC)>=0 vai a 9
se (ACC)>=0 vai a mettere il 1o in PARZ12, senn prosegui mettendo 

il 2o in PARZ12

8 9
6
(ACC) <- (DATO2)
caricamento
3 202
7
(PARZ12) <- (ACC)
memorizzazione 
4 204
8
(PC) <- 11
vai a 11
7 11
9
(ACC) <- (DATO1)
primo in ACC e poi in PARZ12
3 201
10
(PARZ12) <- (ACC)
memorizza primo in PARZ12
4 204
11
(ACC) <- (PARZ12)
ora il confronto tra PARZ12 e DATO3.
NB. questo caricamento sarebbe superfluo (perch?)
3 204
12
(ACC) <-(ACC) - (DATO3)
diff tra max parziale e terzo in ACC
2 203
13
se (ACC)>=0, (PC)<-16
se (ACC)>=0 vai a stampare PARZ12, senn prosegui stampando DATO3
8 16
14
(US) <- (DATO3)
stampa il contenuto della cella DATO3
6 203
15
(PC) <- 17
vai verso la fine
7 17
16
(US) <- (PARZ12) 
stampa il contenuto della cella PARZ12
6 204
17
STOP 
interrompere l'esecuzione
9
... 
     
201
 
primo numero
 
202
 
secondo numero
 
203
 
terzo numero
 
204
 
massimo parziale tra il 1o e il 2o
 

Eseguire il programma tre volte, con dati: {12, 3, 20},{19, 13, 2},{32, 33, 1}

tabella linguaggio macchina simbolico