Implementazione di strutture dati in memorie a banchi.

In un sistema multiprocessore, la memoria è una risorsa critica perché condivisa. Per servire simultaneamente più richieste, tali sistemi possono organizzare la memoria è organizzata in più banchi. Il rapporto fra il numero di banchi di memoria disponibili e il numero di processori è detto fattore di espansione, e la sua importanza è tale da essere stato incluso tra i parametri di una recente estensione di uno dei più noti modelli per sistemi paralleli, il Bulk Synchronous Parallel Model (BSPM). Sistemi a memoria condivisa disponibili in commercio, come NEC SX-3 e il CRAYJ90, hanno configurazioni di base con da 4 a 16 processori e 1024 moduli di memoria, mentre il Tera MTA ha 256 processori e $2^{15}$ moduli. Anche un fattore di espansione pari ad 1, non esclude che in uno stesso ciclo di CPU occorrano conflitti, ossia che siano richiesti più dati tutti memorizzati nello stesso banco di memoria. Se ciò accade, i tempi di risposta della memoria degradano. Risultati sperimentali hanno provato che se il fattore di espansione è sufficientemente grande e l'accesso alla memoria è irregolare, distribuire i dati fra i banchi di memoria con un random mapping è sufficiente per minimizzare i conflitti e quindi per migliorare la prestazione dell'intero sistema. Tuttavia, se, la memoria è acceduta secondo schemi regolari, distribuzioni sofisticate, disegnate ad hoc per particolari tipi di accessi, si rendono utili. Non è difficile, ad esempio, immaginare applicazioni in cui si richieda di accedere senza conflitti colonne, righe di matrici, cammini o sottoalberi di alberi. Le tecniche più innovative sviluppate in questo contesto sono state presentate in [A5, A7]. Oltre a determinare caso per caso il lower bound del numero di banchi di memoria per accedere senza conflitti alle varie sottostrutture dati, i mapping proposti garantiscono, per una fissata configurazione di memoria, il minimo numero di conflitti. Inoltre, essi sono bilanciati, cioè distribuiscono in modo equo la struttura dati è fra i processori, diretti, cioè calcolano localmente, senza conoscenza dell'intera struttura ed in tempo costante, il modulo a cui un elemento della struttura è assegnato. Infine, i mapping studiati in [C1, A5] sono versatili, cioè minimizzano il numero di conflitti simultanealmente per più strutture dati.