Scopo di questa esercitazione è il progetto e la realizzazione
completa di un'architettura di processore attraverso strumenti di emulazione
circuitale. L'architettura in questione dovrà supportare un insieme
minimale di istruzioni assembler, utilizzando le quali dovrà essere
implementato un algoritmo per la ricerca e il conteggio del numero di occorrenze
di una stringa di valori interi in un vettore dati in memoria.
Tale programma di ricerca (Pattern Search) dovrà essere ideato e memorizzato
dai componenti del gruppo, e risulterà essere il test funzionale principale
dell'architettura realizzata.
Il tool utilizzato per l'emulazione circuitale è RETRO, per il quale
trovate tutte le informazioni (originali) su
http://www.ee.uwa.edu.au/~braunl/retro/
e per il quale potete scaricare la versione completa (e patch di correzione per la funzione SAVE) alla URL
http://www.cs.unibo.it/~bononi/ARCH2002/
Retro è stato realizzato da B. "Toy" Chansavat e Thomas Braunl, ed è distribuito sotto GNU public license.
La progettazione dell'architettura del processore (di seguito
CPU) deve essere mirata all'implementazione di un insieme di istruzioni del
linguaggio assembler previsto per la CPU stessa. L'insieme di tali istruzioni
è ovviamente ridotto e non significativo in termini di utilizzo pratico,
in quanto la finalità del progetto è unicamente didattica, e
in quanto esistono limiti pratici alla complessità di realizzazione
dell'architettura finale.
Per la realizzazione dell'architettura della CPU ci si avvale della libreria
Standard di componenti messi a disposizione da RETRO.
Tra questi componenti architetturali, esistono componenti di basso livello
(es. porte logiche, collegamenti, bus) ed esistono componenti più complessi
(es. multiplexer, decoder, flip-flop, registri, ROM, RAM, sommatori...) che
possono essere utilizzati senza limiti (se non quelli fisici legati alla dimensione
della "basetta" virtuale di RETRO).
Il requisito fondamentale riguardo all'esigenza di avere una progettazione
completa dell'architettura richiede che ogni componente complesso utilizzato
almeno una volta nell'architettura realizzata debba essere progettato e realizzato
in emulazione, usando una "basetta" separata di RETRO. Di fatto,
quindi, ogni componente registro, multiplexer, sommatore, ecc. deve essere
progettato e realizzato (in forma prototipale) almeno una volta a partire
dalla sintesi circuitale basata sulle sole porte logiche AND, OR, NOT. A tale
scopo, dovranno essere descritte le fasi di progetto e sintesi, mostrando
i dettagli dei metodi di sintesi utilizzati (mappe di Karnaugh, metodo Quine-MkCluskey,
ecc.). La dimostrazione di funzionamento dei singoli componenti complessi
dovrà essere possibile, prevista e supportata dall'implementazione
attraverso RETRO (ad esempio predisponendo opportunamente led e display per
semplici funzioni di test).
Nella realizzazione finale della CPU non si utilizzeranno di fatto i componenti
progettati (in quanto non importabili come macro-oggetti), ma si utilizzeranno
i componenti della libreria standard di RETRO.
Gli unici componenti complessi che non devono essere realizzati malgrado risultino
utilizzati sono: clock, generatori di impulsi, RAM, ROM, e tutti i dispositivi
di visualizzazione (display, led, ecc).
Tutta la fase di progetto e sintesi dei costituenti della CPU deve essere opportunamente documentata in una relazione finale alla quale saranno allegati i file di RETRO per il test di funzionamento. La relazione dovrà essere consegnata in formato elettronico (.pdf, .ps o .html) entro le date che saranno definite in seguito.
L'architettura della CPU è a 8 bit e deve necessariamente prevedere i seguenti elementi costituenti l'architettura stessa:
ALU: unità aritmetico-logica per supportare l'insieme delle operazioni sui dati richieste dall'architettura
ACC: registro accumulatore a 8 bit, utilizzato per memorizzare i dati/risultati della ALU o i dati da/verso la memoria
CodeRegister: registro per il mantenimento e gestione del codice operativo dell'istruzione in esecuzione
AddressRegister: registro di indirizzamento a 8 bit, utilizzato per mantenere l'indirizzo di memoria dell'eventuale operando di un'istruzione assembler della CPU.
PC: (program counter) registro a 8 bit che punta alla prossima istruzione assembler da eseguire durante l'esecuzione di un programma memorizzato in RAM.
RAM: memoria costituita da 256 locazioni da un byte, indirizzate da 00hex a FFhex, sulle quali potranno essere memorizzati programmi e dati
Clock di sistema: segnale che governa l'evoluzione dell'architettura.
Generatore di Impulsi (pulse pattern generator): meccanismo di astrazione del concetto di microprogramma, che determina la temporizzazione delle fasi di esecuzione delle microistruzioni, e delle componenti architetturali coinvolte, secondo il classico schema di un'architettura CISC. Su questo oggetto saranno definite in seguito le assunzioni che permettono di semplificare l'architettura stessa.
Rete di controllo: agisce sulla base dei segnali ottenuti dal generatore di impulsi, e attraverso la codifica del codice operativo della istruzione in esecuzione, per determinare la effettiva sequenza dei segnali di controllo che governano l'evoluzione della elaborazione della CPU (dipendente dal tipo di istruzione in esecuzione).
Per maggiore chiarezza, verranno forniti esempi di architetture simili che possano risultare di ausilio nella comprensione e progettazione dell'architettura richiesta (es. scaricate da qui cpu2.toy e CPU2.mem, poi analizzate cpu2.toy con RETRO).
Si definisce ora l'insieme delle istruzioni assembler che devono
essere supportate dall'architettura realizzata.
Tutte le operazioni aritmetiche si intendono realizzate su valori binari interi
a 8 bit, espressi in complemento a due.
Fanno eccezione i valori degli indirizzi di RAM che si assumono espressi su
8 bit in binario naturale (256 Byte indirizzabili).
Le uniche istruzioni con operando e gli operandi leciti sono espressamente citati.
Elenco delle istruzioni assembler da implementare per la CPU:
ACC := ACC ; questa istruzione impegna l'architettura senza causare nessuna modifica allo stato del sistema (NOP)
ACC := mem(Address) ; il registro ACC viene caricato con il valore (Byte) contenuto alla locazione di RAM di indirizzo Address. Si noti che il tipo di indirizzamento è immediato, e non sono possibili indirizzamenti indiretti (non potete modificare Address a runtime, in quanto non è legale usare codice auto-modificante). Address è l'operando di questa istruzione. Es. ACC = mem(F7hex).
ACC := mem(ACC) ; il registro ACC viene caricato con il valore (Byte) contenuto alla locazione di RAM di indirizzo contenuto nell'accumulatore stesso. Questa è l'unica forma di indirizzamento riconducibile a un indirizzamento indiretto. (Notare che in questo modo il codice non è auto-modificante).
ACC := ACC + mem(Address) ; il registro ACC viene ad assumere il valore ottenuto dal valore attuale al quale si somma in binario il valore contenuto in RAM all'indirizzo Address (indirizzo immediato). Non devono essere gestiti i casi di overflow. Address è l'operando di questa istruzione.
ACC++; questa istruzione causa l'incremento di un'unità del valore in ACC
ACC := OPP(ACC); questa istruzione causa il "complemento a due" del valore contenuto nel registro accumulatore.
mem(Address) := ACC ; questa operazione scrive in RAM alla locazione Address (indirizzo immediato) il valore contenuto nel registro ACC. Address è l'operando di questa istruzione. Es. mem(87hex) := ACC.
if (ACC >= 0) then PC :=PC + Offset ; questa istruzione causa l'aggiornamento condizionale (se ACC >= 0) del program counter (PC), eventualmente sommandogli il valore immediato Offset (8 bit in complemento a due). Offset è l'operando di questa istruzione.
PC :=PC + Offset ; questa istruzione causa l'aggiornamento incondizionato del program counter (PC), sommando il valore immediato Offset (8 bit in complemento a due). Offset è l'operando di questa istruzione.
Il ciclo generico di esecuzione di un'istruzione assembler per l'architettura in esame risulta genericamente definito attraverso le fasi di:
fetch del codice operativo dell'istruzione da eseguire (nel Code Register) e aggiornamento PC
decodifica del codice operativo dell'istruzione da eseguire
caricamento dell'indirizzo dell'eventuale operando dell'istruzione sull'Address Register
fetch dell'eventuale operando dell'istruzione (direttamente alla ALU) e eventuale aggiornamento PC
esecuzione dell'operazione da parte della ALU, che coinvolge ACC e l'eventuale operando
store del risultato sul registro ACC
Si noti come la sequenza di queste fasi possa essere considerata uno (statico)
schema del microprogramma per ognuna delle istruzioni richieste. Questa assunzione
semplifica la fase di progetto e realizzazione, in quanto permette di definire
un pattern statico di temporizzazione dell'architettura nelle sue micro-costituenti.
Ognuna delle fasi descritte deve essere realizzata attraverso la definizione
di un insieme statico di pattern di temporizzazione, utilizzando il pattern
generator, i cui segnali possono essere dinamicamente mascherati attraverso
la rete di controllo (che risulta molto semplice) basata sull'interpretazione
del codice operativo della istruzione in esecuzione. Si rimanda all'analisi
della rete di esempio (cpu2.toy) per maggiori dettagli. Sono da privilegiare
le scelte architetturali volte all'ottimizzazione dell'architettura stessa.
Non è ammessa la semplificazione data dal considerare tutte le istruzioni
seguite da operando fittizio (non si devono quindi sprecare i Byte di RAM per
semplificare l'aggiornamento del PC quando si eseguono istruzioni senza operando).
Per quello che riguarda il progetto di alto livello dell'architettura, la relazione dovrà documentare le scelte, i criteri, e gli accorgimenti usati per ottenere un'architettura che soddisfi al meglio i requisiti minimi definiti. In particolare si ponga attenzione alle diverse modalità di implementazione delle istruzioni richieste, selezionando quelle che si ritengono migliori o meno complesse.
In questa fase del progetto, i costituenti del gruppo dovranno
progettare il programma assembler per la ricerca, in una porzione di area dati
della RAM, di un pattern (vettore di min:1, max:10 valori interi in complemento
a due) memorizzato in un'altra area di RAM (memoria dati). Si possono utilizzare
unicamente le istruzioni implementate per l'architettura realizzata. In seguito
il codice assembler dovrà essere tradotto (assemblato) nell'equivalente
linguaggio macchina e memorizzato nella RAM dell'architettura progettata, al
fine di essere eseguito.
N.B. Si richiede di scrivere un programma rilocato staticamente che effettui
quanto richiesto secondo lo schema di algoritmo che segue (i dettagli sono lasciati
alla fantasia dei costituenti dei gruppi, e lo schema presentato non è
in alcun modo vincolante).
Si assuma di avere l'area del codice in RAM a partire dagli indirizzi 00hex
fino all'indirizzo AFhex.
Si assuma di avere l'area dei dati in RAM a partire dall'indirizzo B0hex fino
all'indirizzo FFhex.
La locazione B0hex contiene un valore intero positivo Size (min:01, max:0A)
che rappresenta la dimensione in Bytes del pattern da ricercare in RAM. Nei
Bytes immediatamente successivi si trova memorizzato il pattern composto da
Size Bytes.
In seguito possono essere fissate locazioni che contengono i puntatori attuali
per la scansione del pattern (PattInd) e della RAM (ScanInd). Altre locazioni
da fissare riguardano un contatore del numero di interi consecutivi del pattern
trovati (Found) e il contatore del numero di occorrenze del pattern trovate
(Cnt). Infine, devono essere individuati gli indirizzi assoluti di inizio e
fine dell'area dati di RAM soggetta alla scansione per la ricerca delle occorrenze
del pattern (il che dipende dall'implementazione).
N.B. siccome sono state proposte varie versioni, contenenti errori, dello pseudo-codice da realizzare, vi propongo di sviluppare insieme sul newsgroup la versione finale. (Io non ho il tempo di seguire le vostre indicazioni e suggerimenti, inoltre sarò assente fino al 17 Giugno, per cui proponete le modifiche e le correzioni sullo spazio del ng... vince chi scrive lo pseudocodice più semplice e corretto. La sfida prosegue poi in fase di assembly: vince chi riesce a generare il sorgente assembly che si traduce nella linguaggio macchina più compatto... il premio è il titolo simbolico di GURU del codice compatto ;-)))).
N.B. per semplificare assumiamo che il pattern da ricercare sia composto da n valori distinti (altrimenti occorre considerare un algoritmo di riconoscimento multi-livello o ricorsivo, se il pattern contiene più volte la sottosequenza iniziale... es. pattern=ABCAA cosa succede se trovo ABCABCAA? quando trovo la seconda B mi accorgo di non avere trovato il pattern, ma la A precedente potrebbe essere l'inizio del pattern e ormai l'ho già scandita...)
Una volta realizzato l'algoritmo, questo dovrà essere "assemblato"
dagli autori ottenendo il linguaggio macchina equivalente (a questo livello
entrano in gioco le scelte soggettive di definizione delle istruzioni, ecc.).
Il linguaggio macchina ottenuto dovrà essere memorizzato sulla parte
iniziale della RAM (assumendo una rilocazione statica), e quindi eseguito. Eventuali
dati temporanei utili all'implementazione dell'algoritmo dovranno essere allocati
staticamente nella porzione dati della RAM.
Per eventuali domande, errori riscontrati o segnalazioni in genere si prega di fare uso dello spazio discussione unibo.cs.arch sul quale mi impegno a rispondere (quasi) giornalmente.