Esercitazione 5

Esercizio 5.1: esame 2025-02-11

Qui testo e soluzione.

Esercizi con interfacce parallele

Il corretto pilotaggio di interfacce parallele richiede inevitabilmente più stati di quanto è solito usare per esercizi, per esempio, con handshake dav_/rfd o soc/eoc.

Per questo, sono tipicamente gli esercizi che hanno più tempo a disposizione in sede d'esame.

Esercizi senza sintesi di reti combinatorie

Non tutti gli esercizi includono la sintesi di reti combinatorie, così come non tutti i pretest, esercizi di Assembler o domande all'orale coprono un dato argomento del corso.

Nel complesso, ogni esame ambisce a coprire tutti gli argomenti del corso.

Questo esercizio ha due punti fondamentali:

• lavorare con interfacce parallele montate su un bus
• utilizzare (e sintetizzare) microsottoprogrammi

Microprogrammazione con MJR

Cominciamo dal secondo punto. Utilizzare microsottoprogrammi significa codificare una serie di stati a cui si può saltare da diversi altri stati, a cui poi si intende tornare, proprio come i sottoprogrammi nel software. Nella programmazione assembler abbiamo visto l'utilizzo di call e ret, istruzioni che utilizzano lo stack per salvare e poi recuperare l'indirizzo di ritorno, ossia il punto del codice a cui il sottoprogramma deve saltare alla fine della sua esecuzione.

Nella progettazione di reti sincronizzate, costruiamo un meccanismo simile utilizzando un registro MJR (Multiway Jump Register).

La struttura per la descrizione è la seguente. Siano S0...SN gli stati della sequenza principale, e siano Smp0...SmpN gli stati del microsottoprogramma. Uno stato della sequenza principale può saltare a un microsottoprogramma così

    S0: begin
        ...
        MJR <= S1;
        STAR <= Smp0;
    end

Al termine del microsottoprogramma si salterà poi alla sequenza principale così

    SmpN: begin
        ...
        STAR <= MJR;
    end

Si noti che utilizzando un singolo registro è possibile ottenere un solo livello di annidamento delle chiamate: cioè, possiamo avere solo un flusso principale che richiama un microsottoprogramma, ma non un microsottoprogramma che richiama a sua volta un microsottoprogramma. Questo perché abbiamo un singolo stato di ritorno (in MJR) e non una pila come nel software assembler.

All'interno del processore sEP8 visto nel corso si fa un uso massiccio di microsottoprogrammi per separare le varie operazioni del processore in sequenze generiche, atomiche e ben riconoscibili, per l'accesso a locazioni di memoria o interfacce di I/O.

Accedere a interfacce parallele utilizzando microsottoprogrammi

Schema dello spazio di I/O trattato nell'esercizio.

Come nella programmazione di software, il primo passo per introdurre buoni sottoprogrammi è identificare i passaggi eseguiti ripetutamente che ha senso astrarre. In questo esercizio, dobbiamo accedere a due interfacce:

• A, interfaccia di ingresso con handshake
• B, interfaccia di ingresso senza handshake

Interfacce inutilizzate

Lo schema presentato dall'esercizio presenta anche una terza interfaccia, C. Il testo non dice cosa dovremmo farci.

Questo non dovrebbe sorprendere: lo spazio di I/O è pensato per collegare tante interfacce, in questo caso ben $2^{16}$ registri, che non siamo affatto obbligati a utilizzare.

Ricordiamo che per leggere da una interfaccia di ingresso senza handshake è sufficiente accedere in lettura al suo registro RBR. Invece, per leggere correttamente da una interfaccia di ingresso con handshake abbiamo bisogno di leggere ripetutamente il suo registro RSR finché non troviamo l'apposito flag che segnala la validità del dato (flag FI, attivo alto). Dopodiché, possiamo leggere il registro RBR.

Dunque, l'attività che ha più senso astrarre sarà leggere un registro di una interfaccia.

Sappiamo che ciascun registro corrisponde a uno specifico indirizzo dello spazio di I/O, su 16 bit, e contiene 8 bit di dati. Abbiamo quindi bisogno di un microsottoprogramma che prende come argomento un indirizzo di 16 e restituisce come risultato gli 8 bit contenuti dal registro a quell'indirizzo. Mentre in un programma passiamo questi valori tramite variabili - in una RSS non possiamo che usare registri appositi.

Per esempio, prendendo inspirazione dal calcolatore visto a lezione, si potrebbero usare un registro DEST_ADDR su 16 bit e un registro APP0 su 8 bit. Nella soluzione proposta, i due vengono combinati utilizzando due registri a 8 bit, APP1 e APP0: si userà quindi {APP1, APP0} per l'indirizzo e APP0 per il risultato.

Supponiamo quindi che il nostro microsottoprogramma esista già e vediamo come scrivere il flusso principale della RSS. Sia S_in_0 lo stato di ingresso del microsottoprogramma, allora possiamo scrivere:

    reg [7:0] A, B;
    wire [8:0] sum;
    assign #1 sum = A + B;

    always @(reset_ == 0) #1 begin
        ...
        A <= 0;
        B <= 0;
        OUT <= 0;
        STAR <= S0;
    end

    always @(posedge clock) if(reset_ == 1) #3 begin
        casex (STAR)
            // Lettura da RSR di A, aggiornamento OUT a risultato ciclo precedente
            S0: begin
                OUT <= {3'b0, sum};
                APP1 <= 8'h01;
                APP0 <= 8'h00;
                MJR <= S1;
                STAR <= S_in_0;
            end

            // Check di FI
            S1: begin
                STAR <= APP0[0] ? S2 : S0;
            end
            
            // Lettura da RBR di A
            S2: begin
                APP1 <= 8'h01;
                APP0 <= 8'h01;
                MJR <= S3;
                STAR <= S_in_0;
            end

            // Lettura da RBR di B, salvataggio dato A
            S3: begin
                A <= APP0;
                APP1 <= 8'h01;
                APP0 <= 8'h20;
                MJR <= S4;
                STAR <= S_in_0;
            end

            // Salvataggio dato B, nuovo ciclo
            S4: begin
                B <= APP0;
                STAR <= S0;
            end

            ...
        endcase
    end

Il codice qui sopra omette (oltre al solito preambolo di dichiarazione del modulo) tutto ciò che riguarda l'accesso effettivo al bus di I/O: utilizzando microsottoprogrammi, possiamo lavorare a un livello logico più alto senza i dettagli implementativi che vengono nascosti con l'astrazione.

In questo flusso principale non fa che saltare al microsottoprogramma in tre punti, per accedere ai tre diversi registri di interesse.

Microsottoprogramma per leggere da registro I/O

Ovviamente la parte di sopra è incompleta finché non si scrive il microsottoprogramma. Quello che dobbiamo fare in questo microsottoprogramma è:

• Accedere in lettura all'indirizzo in {APP1, APP0}
• Salvare il risultato in APP0
• Saltare allo stato contenuto in MJR

La parte critica, in questo è il corretto pilotaggio del bus, evitando corse critiche e usando porte tri-state per evitare situazioni di corto circuito.

Ricordiamo che le interfacce si attivano alla ricezione di segnali ior_ e iow_. Questi segnali arrivano a tutte le interfacce sul bus, ma è solo quella selezionata tramite addr che si attiva, o leggendo data o assegnandogli un valore. È quindi critico che i fili di uscita addr e data siano stabili prima di portare ior_ o iow_ a 0.

Per data, questo si traduce, per scritture, nel valore assegnato stabile (per esempio, con registro DATA) e la porta tri-state abilitata (solitamente, DIR = 1); per le letture invece si disabilita la porta tri-state (solitamente, DIR = 0) per lasciare che sia l'interfaccia ad assegnargli un valore. Ricordiamo che il problema qui è di tipo elettrico: assegnare un valore logico a un filo equivale a imporre una tensione, e se più dispositivi assegnano tensioni diverse sullo stesso filo la differenza di potenziale porta a un disastroso corto circuito.

Ricordiamo che il problema qui è di tipo elettrico: assegnare un valore logico a un filo equivale a imporre una tensione, e se più dispositivi assegnano tensioni diverse sullo stesso filo la differenza di potenziale porta a un disastroso corto circuito.

In questo caso, però, non abbiamo bisogno di scritture. Possiamo quindi utilizzare data come solo in ingresso, senza bisogno di una porta tri-state, e assegnare iow_ = 1 (ossia, collegare il filo a $V_{cc}$).

Possiamo quindi scrivere il microsottoprogramma così:

    always @(reset_ == 0) #1 begin
        IOR_ <= 1;
        ...
    end

    always @(posedge clock) if(reset_ == 1) #3 begin
        casex (STAR)
            ...

            // Lettura da interfaccia di IO
            // L'indirizzo è passato come argomento tramite { APP1, APP0 }
            // Il dato letto è lasciato in APP0
            S_in_0: begin
                ADDR <= {APP1, APP0};
                STAR <= S_in_1;
            end

            S_in_1: begin
                IOR_ <= 0;
                STAR <= S_in_2;
            end

            S_in_2: begin
                APP0 <= data;
                IOR_ <= 1;
                STAR <= MJR;
            end
        endcase
    end

Sintesi di una RSS con MJR

Un altro aspetto critico è come sintetizzare una rete del genere, cioè come si implementa effettivamente dell'hardware che si comporta in questo modo. L'aspetto chiave è il fatto che quando non si usano microsottoprogrammi, i valori assegnati a STAR sono sempre delle costanti, che come abbiamo visto possono essere sintetizzate usando una ROM. I salti che usano MJR invece no, perché, per l'appunto, usano un registro da cui viene letto il prossimo stato.

Va quindi utilizzata una architettura diversa. Una di quelle viste nel corso è così schematizzata.

In questa architettura notiamo che si aggiunge un nuovo filo in uscita alla ROM per distinguere i salti (in)condizionati dai salti che leggono da MJR. Inoltre, MJR è trattato come un registro operativo, e va quindi sintetizzato come tale (cioè, usando variabili di comando). Possiamo quindi sintetizzare la parte controllo di questo esercizio con una ROM come la seguente.

// Per utilizzare il registro MJR, va esteso il modello di sintesi della parte controllo e la relativa ROM, in modo da distinguere i salti guidati da MJR e non (salti incondizionati o a due vie).

// Per distinguere questi salti da quelli guidati da MJR, introduciamo un altro multiplexer guidato dal campo m-type della ROM
// Questo varrà 0 per i salti incondizionati o a due vie e 1 per i salti guidati da MJR.

// Per i salti incondizionati o a due vie, si utilizzano i campi m-addr T ed m-addr F della ROM, e un multiplexer guidato da una delle variabile di condizionamento prodotte dalla parte operativa.
// Dato che, in questo caso, abbiamo una sola variabile di condizionamento, non c'è bisogno di distinguerle tramite un multiplexer ed il campo c_eff della ROM, che quindi omettiamo.

/* 
m-addr         | m-code | m-addr T     | m-addr F     | m-type
----------------------------------------------------------------
000 (S0)       | ...    | 101 (S_in_0) | 101 (S_in_0) | 0
001 (S1)       | ...    | 010 (S2)     | 000 (S0)     | 0
010 (S2)       | ...    | 101 (S_in_0) | 101 (S_in_0) | 0
011 (S3)       | ...    | 101 (S_in_0) | 101 (S_in_0) | 0
100 (S4)       | ...    | 000 (S0)     | 000 (S0)     | 0
101 (S_in_0)   | ...    | 110 (S_in_1) | 110 (S_in_1) | 0
110 (S_in_1)   | ...    | 111 (S_in_2) | 111 (S_in_2) | 0
111 (S_in_2)   | ...    | XXX          | XXX          | 1

*/

Niente salti condizionati con MJR

L'architettura presentata permette solo

• Salti incondizionati a stato costante, del tipo STAR <= S0;, da sintetizzare con m-type = 0, c_eff = X, m-true = m-false = S0.
• Salti condizionati a stati costanti, del tipo STAR <= c1 ? S0 : S1;, da sintetizzare con m-type = 0, c_eff = c1, m-true = S0, m-false = S1.
• Salti incondizionati a MJR, del tipo STAR <= MJR;, da sintetizzare con m-type = 1, c_eff = X, m-true = X, m-false = X.

Non sono sintetizzabili invece salti del tipo STAR <= c1 ? MJR : S1. Per far questo ci vorrebbe un'altra architettura, diversa da quelle viste in questo corso.

Esercizio 5.1: esame 2024-01-26

Qui testo e soluzione.

Provare da sé

Provare a svolgere da sé l'esercizio, prima di guardare la soluzione o andare oltre per la discussione.

Il testo di questo esercizio è pensato per apparire fuori dalla norma a un occhio poco preparato, ma si rivela molto semplice con le dovute osservazioni.

Tralasciando le curiosità sulla congettura di Collatz, ciò che ci interessa è osservare che il calcolo di $n_{i+1}$ a partire da $n_i$ è di tipo combinatorio. Ciò è anche suggerito dal testo, che ci chiede di sintetizzare proprio questo.

Ciò che non è combinatorio è invece il calcolo di $n_{i+1}$ a partire da $n_0$: questa è infatti una operazione iterativa, che implica una struttura ad anello che svolge più passaggi. Come dovremmo ben sapere, tali anelli non possono essere reti combinatorie, e vanno invece implementate con reti sincronizzate che avanzano a passaggi discreti guidati dal segnale del clock. Anche questa osservazione è suggerita dal testo, visto che il modo più immediato per ottenere $k$ è contare le iterazioni necessarie per arrivare ad 1.

La struttura chiave quindi è la seguente: abbiamo un registro N che conterrà l'attuale $n_i$, inizializzato con $n_0$. Al posedge del clock, campionando l'uscita della rete combinatoria CALCOLO_ITERAZIONE, riceve il nuovo valore $n_{i+1}$. Contemporaneamente, un registro K, inizializzato a 0, conta con K <= K + 1; quanti posedge sono necessari perché N arrivi ad 1. Questo è garantito dall'uso di un cambio di stato che interrompe il conteggio quando la condizione è raggiunta, fatte le solite osservazioni per il corretto conteggio di cicli di clock. Questo ciclo può essere espresso come nel seguente pseudo-codice:

...
CALCOLO_ITERAZIONE ci(
    .n_curr(N), 
    .n_next(n_next)
);
...
always @(posedge clock) if(reset_ == 1) #3 begin
    casex(STAR)
        ...
        S_init: begin
            N <= n_0;
            K <= 0;
            ...
        end
        S_loop: begin
            N <= n_next;
            K <= K + 1;
            STAR <= (n_next == 1) ? S_after : S_loop;
        end
        S_after: ...
    endcase
end
...

Una volta chiarito questo processo, il resto dell'esercizio è molto semplice. Va dimensionato N e la relativa rete combinatoria: il testo ci indica che il massimo raggiungibile è inferiore a 'h4000, implicando che 14 bit sono sufficienti. Va poi sintetizzata la rete combinatoria, che altro non è che un multiplexer, guidato dal bit meno significativo, i cui due ingressi sono uno shift a destra e un moltiplicatore con y = 3 e c = 1. Infine, la rete sincronizzata campiona n_0 e invia k tramite un singolo handshake soc/eoc.