PIPE Buffer

Lezione del 2019-01-10.

Mantenendo le specifiche illustrate nel fifo buffer, consideriamo una implementazione a PIPE, con la seguente architettura.

PIPE buffer: software architecture

Un buffer PIPE è formato da una serie di celle, ognuna con la capacità di memorizzare una informazione, concatenate tra loro.

L’informazione fluisce, usando i canali \(\sigma_i\) da una cella all’altra, come illustrato qui di seguito:

Quando una cella è vuota, utilizzamo il simbolo \(\bot\) (bottom) per rimarcare che non contiene alcun dato.

Quindi la stringa s é: \(s \in (V \cup \{ \bot \})^+\). E la sua lunghezza è \(\lvert s \rvert = N+2\).

Specifichiamo una singola generica cellula c, considerandola come un buffer di capacità 1.

Se la cella è vuota abbiamo solo la possibilità di inserire un dato \(e \in V = \{ 0, 1 \}\):

\[c(\bot) = \sum_{e \in V} in(e) \cdot c(e)\]

Se la cella contiene un dato, è piena. Quindi possiamo solo ricevere:

\[c(e) = out(e) \cdot c(\bot)\]

Ora, nel considerare il buffer con \(N+2\) celle, abbiamo i seguenti casi.

Con l’indice della cella che varia tra 0 e N+1: \(0 \leqslant i \leqslant N+1\), l’estremo sinistro sarà per \(i = 0\), come segue:

Ora definiamo una funzione di relabeling come segue:

\[\begin{split}\phi_0(a) = \begin{cases} \sigma_0 \quad & if \, a = in \\ out \quad & if \, a = out \end{cases}\end{split}\]

ovvero, se l’azione è un input, diviene \(\sigma_0\), se invece è un output, l’azione rimane inalterata.

In questo modo possiamo ridefinire \(c_0 = c[\phi_0]\), utilizzando la definizione di c(e).

Consideriamo ora l’estremo destro: \(i = N+1\), avremo:

Usando la funzione di relabeling:

\[\begin{split}\phi_{N+1}(a) = \begin{cases} in \quad & if \, a = in \\ \sigma_N \quad & if \, a = out \end{cases}\end{split}\]

potremo definire \(c_{N+1} = c[\phi_{N+1}]\).

Per l’indice generico \(0 < i < N+1\) avremo:

Usando la precednte funzione di relabeling:

\[\begin{split}\phi_i(a) = \begin{cases} \sigma_i \quad & if \, a = in \\ \sigma_{i-1} \quad & if \, a = out \end{cases}\end{split}\]

potremo definire \(c_i = c[\phi_i]\).

Ora componiamo in parallelo le diverse celle:

\[pipe(s) = [(c_0[\phi_0] \parallel_{\sigma_0} \cdots \parallel_{\sigma_{i-1}} c_i[\phi_i] \parallel_{\sigma_i} \cdots \parallel_{\sigma_N} c_{N+1}[\phi_{N+1}])] \setminus \{ \sigma_0 \cdots \sigma_{N} \}\]

facendo attenzione che vi sia il vincolo della sincronizzazione rispetto i canali \(\sigma_i, 0 \leqslant i \leqslant N\). Questa condizione permette il flusso ordinato dei dati dalla prima all’ultima cella.

Lezione del 2019-01-17

Osserviamo che con questa architettura un dato in input deve attraversare tutte le celle prima di essere ricevuto in output. Con l’architettura parallela esposta, questo avviene subito. Ricordando che tutte le celle sono vuote, quando la prima cella (\(c_{N+1}\)) riceve un dato, visto che a sx \(c_N\) è vuota, si sincronizza con lei (azione \(\sigma_N\)), passando il dato e svuotandosi. Ciò capita a catena sino ad arrivare a \(c_0\), dove il dato sarà a disposizione del destinatario con l’azione out(e).

Se un secondo dato \(e_2\) viene immesso nel buffer prima che il precedente sia stato ricevuto dal destinatario, allora si fermerà nell’ultima cella vuota disponibile: \(c_1\); e così via; eventualmente sino al riempimento del buffer.

Quindi per una generica stringa s il buffer avrà lo stato:

\[pipe(s) = (c_0(s_0) \parallel_{\sigma_0} c_1(s_1) \parallel_{\sigma_1} \cdots \parallel_{\sigma_N} c_{N+1}(s_{N+1})\]

ottenendo \(s = s_0 \, s_1 \cdots s_{N+1}, \; s_i \in \{ \bot, 0, 1 \}\).

Osserviamo inoltre, che l’architettura indicata può nascondere i dettagli di comportamento della PIPE rispetto l’osservatore esterno: le azioni \(\sigma_i, 0 \leqslant i \leqslant N\) non saranno visibili all’esterno.

Per formalizzare questa osservazione, definiamo la funzione di relabeling:

\[\begin{split}\phi(a) = \begin{cases} in \quad & if \, a = in \\ out \quad & if \, a = in \\ \tau \quad & if \, a = \sigma_0, \sigma_1, \cdots \sigma_N \end{cases}\end{split}\]

con \(\tau\) azione nascosta, invisibile all’osseratore esterno.

Applicando questa funzione di relabeling alla pipe, le azioni \(\sigma_i\) saranno trasformate in \(\tau\). Solo input e output non sono rietichettate. Quindi un osservatore esterno che guarda le azioni, vedrà solo le sequenze di input e output intervallate con una serie di \(\tau\).

Nello stato iniziale avremo N+2 volte \(\bot\) (prima inizializzazione del sistema)

\[pipe(\bot \bot \cdots \bot)[\phi]\]