Questi appunti sono ricavati dagli Appunti del corso di ARCHITETTURA DEI CALCOLATORI, Corso di Laurea in Informatica, del prof. Giovanni Chiola, tagliando alcune parti che mi sono sembrate troppo complicate, aggiungendo qualche spiegazione ulteriore e facendo qualche modifica per permettere di leggere le note senza aver letto quanto le precedeva. La versione originale si trova QUI.
Gli appunti del prof. Chiola sono protetti dalle condizioni di "Copyleft" che seguono. In base a queste condizioni, mi assumo la piena responsabilità del prodotto finale.
Questo documento é protetto dalla legge sul diritto di autore, e di proprietà esclusiva dell'autore che se ne riserva tutti i diritti.
L'autore concede a chiunque il permesso di copiare gratuitamente qualunque sottoinsieme dei files che compongono questi appunti per qualsiasi uso e su qualsiasi supporto, purchè la copia di ciascun file sia integrale, senza alcuna modifica ad eccezione di un eventuale cambiamento di formato di rappresentazione per necessità di stampa o memorizzazione su sistemi diversi, e purchè ogni copia sia sempre accompagnata dalla presente clausola completa di Copyright.
Le informazioni presenti in questo documento distribuito dall'autore in forma gratuita vengono fornite in quanto tali, senza nessuna garanzia di correttezza, consistenza o assenza di errori da parte dell'autore stesso, il quale per altro declina ogni responsabilità per qualsiasi danno o inconveniente che potesse derivare dall'uso del documento stesso, anche se si dovesse verificare il caso che talune informazioni qui contenute non fossero corrette.
É permessa anche la riutilizzazione parziale o totale del testo e delle figure per la produzione di lavori derivati, purchè i lavori derivati siano soggetti alle condizioni di diffusione ed uso di questo documento originale, con particolare riferimento alla possibilità per chiunque di copiare liberamente e senza restrizione alcuna il documento in forma integrale e di usarne parti per la creazione di lavori derivati soggetti alle medesime condizioni di diffusione ed uso. Nel caso di creazione di lavori derivati mediante inclusione e/o modifica sostanziale del testo originale, l'autore delle modifiche si assumerà la paternità delle aggiunte e delle modifiche, ed il nome dell'autore del testo originale non potrà essere utilizzato senza il suo preventivo ed esplicito consenso per patrocinare l'opera derivata.
Le condizioni di questo Copyright sono liberamente ispirate al
"copyleft"
originariamente introdotto da Richard Stallman, e dovrebbero essere
una versione semplificata ma sostanzialmente equivalente alla
"Free Documentation
License" raccomandata dalla
"Free Software Foundation.
La macchina é realizzata mediante l'interconnessione di quattro dispositivi complessi: memoria, unità operativa, ingresso e uscita, come illustrato in figura:
Nota. Per semplicità ignoriamo i dettagli che riguardano la codifica dei numeri interi e i limiti sui valori interi rappresentabili.
L'unità di controllo é realizzata in modo da poter eseguire (direttamente oppure comandando parte dell'esecuzione alle altre unità della macchina) un insieme finito di istruzioni. Sempre a titolo esemplificativo potremmo individuare un insieme di nove istruzioni base.
L'idea fondamentale di Von Neumann, che viene ancora oggi seguita nella realizzazione dei sistemi di calcolo fu quella di codificare le istruzioni in forma numerica, e di inserirle, insieme agli eventuali dati, nella unità RAM della macchina. Un modo molto semplice per ottenere una codifica numerica per l'identificazione delle istruzioni é quella di elencarle in una lista ordinata, e di usare il numero d'ordine all'interno della lista per individuare l'istruzione. Proviamo a considerare il seguente esempio:
Supponendo di saper codificare qualsiaso istruzione (compresi i suoi eventuali operandi) sotto forma numerica in una singola cella di RAM, allora possiamo individuare una modalità di funzionamento sequenziale per la nostra macchina facendo uso del registro PC, esprimibile con il seguente algoritmo:
Il caricamento di programmi sequenziali nella RAM (codificati in forma numerica) costituisce quindi un mezzo semplice ma molto efficace per definire sequenze di istruzioni (anche molto lunghe) che la macchina dovrà eseguire una volta attivata (per esempio attraverso la pressione di un apposito pulsante).
Le istruzioni 6, 7 e 8 servono per alterare l'esecuzione sequenziale di programmi codificati in memoria. L'istruzione 6 viene chiamata normalmente salto di programma, in quanto determina una interruzione nella continuità della scansione della RAM in forma sequenziale: fa si che la prossima istruzione da eseguire venga decodificata a partire dal contenuto della cella RAM[N] anziché dal contenuto della cella di indirizzo successivo rispetto a quella che contiene la codifica dell'istruzione di salto. L'istruzione 7 viene chiamata (per ovvie ragioni) salto condizionale. Notare che anche le istruzioni 6 e 7 richiedono la codifica di un parametro numerico oltre all'individuazione della istruzione, mentre l'istruzione 8 é priva di parametri.
Un algoritmo semplice per ottenere la codifica numerica di tutte le istruzioni, comprese quelle con un operando, consiste nel moltiplicare per 1000 il numero d'ordine dell'istruzione e sommare il valore dell'eventuale operando (sempre compreso tra 0 e 999 a causa della limitazione sulla dimensione della RAM). La decodifica verra' effettuata prendendo la parte intera della divisione del valore numerico diviso 1000 per ottenere il numero d'ordine dell'istruzione, ed il resto di questa stessa divisione come valore dell'indirizzo della cella di memoria da usare come operando.
Il nostro programma per la stampa della somma di due numeri corrisponderà quindi a caricare in memoria i seguenti valori prima di attivare l'esecuzione della macchina:
Notare che il programma potrebbe funzionare altrettanto bene se sostituissimo i valori contenuti nelle celle RAM[1] con 4000 e RAM[3] con 0. Notare anche che con tale sostituzione la stessa cella RAM[0] verrebbe utilizzata (in tempi diversi) per contenere prima la codifica della prima istruzione del programma e poi (dopo che tale istruzione é stata eseguita) il valore del primo addendo letto dal dispositivo di ingresso. Una tale variazione potrebbe aver senso in questo caso per "risparmiare" l'uso di una cella di memoria, tuttavia riduce la capacità del programmatore di comprendere il funzionamento del programma e garantirne la correttezza. In effetti, per garantire la correttezza di una tale utilizzazione ottimizzata della memoria bisogna essere certi che l'istruzione di cui si perde memoria non dovrà mai più essere eseguita nel prosieguo dell'interpretazione del programma. Per esempio l'utilizzazione della cella RAM[2] (ottenuta sostituendo i valori 4002 nella cella RAM[1] e 2 nella cella RAM[3]) porterebbe ad un programma errato (a meno che, per pura coincidenza, l'utente non decida di specificare il valore 2000 come primo addendo).
Per verificare il livello di comprensione circa la possibilità di programmare una macchina di questo genere proviamo ad organizzare una modifica dell'esempio proposto in modo da poter ripetere indefinitamente l'operazione di somma tra due numeri e stampa del risultato, fin quando non si incontra un addendo uguale a zero (nel qual caso il programma deve terminare). In altre parole, in input diamo una successione di numeri: a_1, a_2, a_3, a_4, ..... ed in output vogliamo: a_1 + a_2, a_3 + a_4, .....; il programma si ferma appena legge un a_k che è zero. Per realizzare questa modifica occorre prevedere l'aggiunta di istruzioni di tipo 6 (per ripetere indefinitamente la sequenza delle istruzioni dall'inizio) e di tipo 7 (per distinguere il caso di addendo uguale a zero da quello di addendo diverso da zero). Una possibile realizzazione sotto forma di programma é la seguente:
In effetti, l'unità di controllo applica l'algoritmo di fetch e decodifica delle istruzioni in modo indiscriminato, sulla base del valore assunto dal registro PC, senza aver alcun modo per sapere se il valore inserito nel registro IR fosse stato effettivamente memorizzato nella cella RAM[PC] con lo scopo di codificare una istruzione oppure di mantenere un valore numerico. É responsabilità del programmatore far si che la cella da cui viene fatto il fetch contenga effettivamente un numero che rappresenta l'istruzione che si vuol eseguire in quel momento e non un qualsiasi altro numero.
Un programma che prima inserisce un dato in una cella di memoria e poi successivamente passa ad interpretare il contenuto di quella stessa cella di memoria come la codifica di una istruzione (accedendovi in fase di fetch) viene detto automodificante. Un programma automodificante non é necessariamente errato, anzi nella macchina di von Neumann alcuni problemi possono essere risolti solo mediante l'uso di programmi automodificanti. Oggi nessun programmatore concepisce programmi automodificanti, anche grazie ai progressi fatti nella organizzazione delle macchine: al contrario, nei moderni sistemi di calcolo la memoria viene partizionata in aree specializzato per contenere i dati distinte da quelle destinate a contenere il codice del programma da eseguire, ed il tentativo di cambiare il contenuto delle celle contenenti il programma provoca normalmente la terminazione del programma stesso con un messaggio di errore.
Fin'ora abbiamo considerato il caso in cui il programma desiderato dall'utente sia stato in qualche modo (magicamente?) inserito nella RAM sotto forma di codifica numerica delle istruzioni. Da un punto di vista pratico si pone però il problema di inserire questi numeri all'interno della RAM prima di far partire l'unità di controllo col fetch della prima istruzione. Per risolvere questo problema la macchina viene normalmente fornita dal costruttore provvista di un insieme di programmi predefiniti, comunemente indicati col termine Sistema Operativo, che hanno lo scopo di facilitare l'uso della macchina stessa fornendo all'utente delle modalità semplici di caricamento dei programmi in memoria e lancio della loro esecuzione.
In particolare nel nostro caso possiamo pensare di risolvere il problema con un semplice programma di " bootstrap "; per brevità chiamiamolo BOOT.
L'input per BOOT è
una successione di numeri : a_1, a_2, a_3,...., a_n, 0 ;
a_1, a_2, a_3,...., a_n costituiscono il nostro programma, lo zero finale
non è parte del programma, serve a capire che l'input è
finito. Notare che 0 è, nella nostra macchina, una istruzione
(somma con indirizzo 0), quindi dobbiamo supporre che i nostri programmi
non la usino mai; questo è ragionevole, visto che in RAM[0] ci
sarà la prima istruzione di BOOT. Complicando un
poco BOOT, si può prevedere un terminatore non ambiguo, ad
esempio 9999.
L'effetto di BOOT è quello di memorizzare, successivamente: a_1 in RAM[15], a_2 in RAM[16], a_3 in RAM[17],..., a_n in RAM[15+n-1] e poi di " lanciare " il programma memorizzato (eseguendo un salto a RAM[15]). La scelta di 15 non è casuale: è appena un po' sotto la fine di BOOT.
Lo schema di BOOT è semplice:
Il problema del punto SALVA si risolve notando che per salvare in RAM di 15, l'istruzione è 4015, per salvare in RAM[16], l'istruzione è 4016, cioè 4015+1 ..... Quindi la soluzione è: esegui l'istruzione 40xy e poi incrementala di 1. Quindi, BOOT modifica se stesso mentre viene eseguito. Questa soluzione però crea un problema: supponiamo che n sia 10; quando siamo arrivati a FINE, l'istruzione è diventata 4024 (= 4015 + 10 - 1). Quindi, se vogliamo riutilizzare BOOT una seconda volta (dopo aver eseguito il primo programma), il caricamento del secondo programma sarà a partire da RAM[24], e cosi' via, fino a " uscire dalla RAM ". Per risolvere questo problema, bisogna inserire, al punto FINE, prima del salto, una fase di ripristino: riportare l'istruzione di memorizzazione al valore originale: 4015.
Una delle tecniche classiche di programmazione é l'estensione procedurale. L'idea consiste nel definire una volta per tutte dei "sottoprogrammi" di utilità generale, che possano essere richiamati da altri programmi per portare a termine parte del compito prefisso. L'esigenza di questi sottoprogrammi nasce dalla limitatezza dell'insieme delle istruzioni base della macchina: la mancanza di una istruzione macchina capace di risolvere immediatamente un sottoproblema stimola l'introduzione di una estensione procedurale che permetta la soluzione di tale sottoproblema una volta per tutte.
Tuttavia la realizzazione di estensioni procedurali è resa difficile dalla rigidità del meccanismo di indirizzamento (solo diretto) e con l'assenza di istruzioni di chiamata e ritorno da sottoprogramma. Per risolvere entrambi i problemi occorre in questo caso sfruttare appropriatamente la possibilità di definire programmi automodificanti.
Consideriamo il caso di una istruzione di moltiplicazione tra due numeri. Tale istruzione non é presente nel repertorio della nostra macchina di Von Neumann, tuttavia possiamo individuare una sequenza di istruzioni macchina esistenti equivalente a tale istruzione mancante. Per semplicità assumiamo che uno dei due operando sia non-negativo. Per esempio, potremmo pensare di caricare una volta per tutte in memoria il sottoprogramma che segue.
L'algoritmo si basa sulla seguente definizione (induttiva) della moltiplicazione, nell'ipotesi y non-negativo:
Inoltre: supponiamo che prima di eseguire le istruzioni che seguono, x sia stato caricato in RAM[999] e y sia stato caricato nel registro ACC; alla fine della esecuzione, il sottoprogramma lscia il risultato della moltiplicazione nel registro ACC.
Questa condizione relativa al "salto indietro" verso il programma principale può essere garantita dalla seguente variante di programma principale, che prima di attivare il sottoprogramma provvede a modificarne il codice inserendo l'indirizzo di ritorno corretto:
Questo modo di organizzare il passaggio dal programma principale al sottoprogramma e viceversa, non é particolarmente comodo da usare, in quanto costringe a conoscere (oltre all'indirizzo della 1a istruzione del sottoprogramma) anche l'indirizzo della cella di memoria dove inserire il valore x e l'indirizzo della cella contenente l'istruzione di ritorno del sottoprogramma (995, nel nostro caso). Tuttavia permette di richiamare lo stesso sottoprogramma da punti diversi del programma principale, consentendo comunque il ritorno alla esecuzione della istruzione seguente del programma principale.
Esempio: stampa del cubo di un numero letto dall'ingresso
Un modo piu' elegante e pulito di organizzare la comunicazione tra programmi e sottoprogrammi 7egrave; il seguente : se la prima istruzione della procedura e` all'indirizzo K, allora in K-1 si carica l'istruzione di ritorno 6abc, in K-2 si carica il primo argomento, x, in K-3 si carica il secondo argomento, y, il sottoprogramma deposita il risultato, x*y, in K-4. Questo si generalizza in modo ovvio e sistematico al caso di p argomenti e q risultati e fornisce un protocollo standard di comunicazione tra programmi e sottoprogrammi.
Per esercizio: provare a modificare l'esempio della moltiplicazione seguendo il nuovo schema.