Architetture Parallele e Distribuite, 2008-09
Note sul supporto alle comunicazioni con processore di comunicazione
contributo di Massimiliano Meneghin
Queste note riportano una versione alternativa (più semplice) del supporto alla comunicazione tra
processi rispetto a quella presente nella Dispensa nel Cap. VI (multiprocessor) e nel Cap. VII
(multicomputer)
1. Architettura a memoria condivisa
Quanto segue vale sia per architetture SMP che NUMA.
Nelle sez. 3.2 e 3.3 del Cap. VI è riportata una versione basata sul seguente principio: il processo
mittente su IP delega completamente l’esecuzione della send a KP e si mette in condizione di
ricevere l’esito dell’esecuzione stessa (conoscere se è stato riempito completamente il buffer o
meno). A questo scopo, viene modificato l’algoritmo di scheduling a basso livello e vengono posti
dei vincoli sul numero di primitive che possono essere lanciate contemporaneamente a KP prima di
ricevere un esito; nella versione presentata è mostrato il caso più semplice in cui il processo si
blocca se, dopo aver delegato una send a KP e non aver ricevuto ancora l’esito, incontra un’altra
primitiva di comunicazione.
Questa versione ha il vantaggio di non impegnare IP nelle fasi dell’algoritmo della send, ma ha lo
svantaggio di non permettere di sovrapporre più di una comunicazione al calcolo.
È possibile pensare ad una soluzione che abbia caratteristiche complementari: impegnare
maggiormente IP nel supporto della send, e quindi ridurre un po’ il tempo di comunicazione
sovrapposto al calcolo, ma, al tempo stesso, poter delegare a KP un numero qualsiasi di primitive
contemporaneamente, sullo stesso canale o su canali diversi. In altre parole, se il programma
parallelo ha la possibilità di sovrapporre più comunicazioni al calcolo, questo viene reso possibile,
ma al prezzo di una minore sovrapposizione di ogni singola comunicazione al calcolo.
La seconda soluzione è più semplice dal punto di vista algoritmico, con poche varianti rispetto al
caso senza KP: non fa uso di un esito esplicitamente trasmesso da KP e non ha implicazioni sullo
scheduling a basso livello.
Incontrando una send con grado di asincronia k, IP accede al descrittore di canale per controllare se
il buffer (di messaggi o di capability a variabili targa) contiene attualmente k elementi. Se sì, viene
messa la variabile sender_wait a true, viene delegato il proseguimento della send a KP, e il processo
mittente si sospende. Altrimenti (meno di k elementi presenti) viene delegato il proseguimento della
send a KP e IP prosegue in esecuzione. Le azioni sul descrittore di canale sono eseguite in stato di
lock.
Ovviamente la latenza di questa fase eseguita su IP non va a sovrapporsi al calcolo e, specie se il
calcolo è di grana fine, va considerata esplicitamente nel tempo calcolo (Tcalc).
La delega a KP viene effettuata (vedi sez. 3.2) passandogli la capability da una struttura dati
contenente i parametri della send. KP esegue la send “normalmente” (eventualmente svegliando il
processo destinatario), salvo non controllare se ha riempito il buffer. Nessun esito è restituito al
mittente.
La receive è interamente seguita su IP senza modifiche rispetto all’algoritmo senza KP.
2
Per ridurre la latenza della fase della send eseguita su IP è possibile pensare di memorizzare nello
stesso blocco di cache tutte le informazioni utilizzate in tale fase. Inoltre, in una architettura
NUMA, nel caso che il descrittore di canale sia remoto, può convenire introdurre una struttura dati,
in memoria locale del mittente, contenente le informazioni usate nella fase IP e mantenute
aggiornate.
Nota: come in ogni soluzione, la sovrapposizione della comunicazione al calcolo deve essere
implementata garantendo, a programma (a compilazione), la consistenza del valore del messaggio
durante l’esecuzione della send su KP.
2. Architettura a memoria distribuita
Una soluzione analoga è utilizzabile anche per architetture a memoria distribuita, in alternativa a
quella studiata nel Cap. VII, sez. 3, senza usare esiti espliciti e senza modificare lo scheduling a
basso livello.
La struttura dati CHmitt sul nodo mittente (che non contiene l’informazione canale_in_uso)
contiene anche l’informazione sul numero di elementi attualmente nel buffer (buffer_size) e la
varabile booleana sender_wait.
All’atto dello send, su IP vengono effettuate, su CHmitt, le stesse azioni del caso multiprocessor.
KPmitt a sua volta delega KPdest all’esecuzione della send, che si conclude senza verificare lo stato
del buffer e senza inviare un esito.
Ad ogni esecuzione della receive da parte di IP del nodo destinatario, deve essere aggiornato il
valore di buffer_size nella struttura CHmitt del processo mittente. Questo viene fatto con una
comunicazione da KPdest a KPmitt; quest’ultimo aggiorna buffer_size in CHmitt (in stato di lock)
e, se trova sender_wait uguale a true, sveglia il processo mittente (resettando sender_wait).
Nell’algoritmo della sez. 3 del cap. VII vanno eliminate tutte le azioni che riguardano l’esito e lo
stato di attesa speciale.
Si noti che KPmitt può realmente lanciare più primitive contemporaneamente su uno o più KPdest,
il loro numero dipendendo dal fattore di utilizzazione della rete e dall’architettura dei nodi. Questa
possibilità esiste anche nelle architetture a memoria condivisa, progettando l’algoritmo di KP in
modo da sfruttare le latenze di accesso in memoria remota per eseguire istruzioni del supporto di
altre comunicazioni delegategli da IP (KP con architettura multithreading o, più semplicemente,
emulando tale comportamento su una architettura qualsiasi).