Progettazione di reti di interconnessione
Un interconnection networkin una macchina parallela trasferisce le informazioni da qualsiasi nodo di origine a qualsiasi nodo di destinazione desiderato. Questa attività dovrebbe essere completata con la minore latenza possibile. Dovrebbe consentire che un gran numero di tali trasferimenti avvenga contemporaneamente. Inoltre, dovrebbe essere poco costoso rispetto al costo del resto della macchina.
La rete è composta da collegamenti e interruttori, che aiutano a inviare le informazioni dal nodo di origine al nodo di destinazione. Una rete è specificata dalla sua topologia, algoritmo di instradamento, strategia di commutazione e meccanismo di controllo del flusso.
Struttura organizzativa
Le reti di interconnessione sono composte dai seguenti tre componenti di base:
Links- Un collegamento è un cavo di una o più fibre ottiche o fili elettrici con un connettore a ciascuna estremità collegato a uno switch o a una porta di interfaccia di rete. Attraverso questo, un segnale analogico viene trasmesso da un'estremità, ricevuto dall'altra per ottenere il flusso di informazioni digitali originale.
Switches- Un interruttore è composto da un set di porte di ingresso e uscita, una "barra trasversale" interna che collega tutti gli ingressi a tutte le uscite, buffer interno e logica di controllo per effettuare la connessione ingresso-uscita in ogni momento. In genere, il numero di porte di input è uguale al numero di porte di output.
Network Interfaces- L'interfaccia di rete si comporta in modo molto diverso rispetto agli switch node e può essere collegata tramite collegamenti speciali. L'interfaccia di rete formatta i pacchetti e costruisce l'instradamento e le informazioni di controllo. Potrebbe avere un buffer di input e output, rispetto a uno switch. Può eseguire il controllo degli errori end-to-end e il controllo del flusso. Pertanto, il suo costo è influenzato dalla complessità di elaborazione, dalla capacità di archiviazione e dal numero di porte.
Rete di interconnessione
Le reti di interconnessione sono composte da elementi di commutazione. La topologia è il modello per collegare i singoli interruttori ad altri elementi, come processori, memorie e altri interruttori. Una rete consente lo scambio di dati tra processori nel sistema parallelo.
Direct connection networks- Le reti dirette hanno connessioni punto-punto tra i nodi vicini. Queste reti sono statiche, il che significa che le connessioni punto a punto sono fisse. Alcuni esempi di reti dirette sono anelli, maglie e cubi.
Indirect connection networks- Le reti indirette non hanno vicini fissi. La topologia di comunicazione può essere modificata dinamicamente in base alle esigenze dell'applicazione. Le reti indirette possono essere suddivise in tre parti: reti bus, reti multistadio e commutatori crossbar.
Bus networks- Una rete bus è composta da un numero di linee di bit su cui sono collegate più risorse. Quando i bus utilizzano le stesse linee fisiche per i dati e gli indirizzi, i dati e le linee degli indirizzi vengono multiplexati nel tempo. Quando ci sono più bus-master collegati all'autobus, è richiesto un arbitro.
Multistage networks- Una rete multistadio è composta da più fasi di interruttori. È composto da interruttori "axb" collegati mediante un particolare schema di connessione interstadio (ISC). Gli elementi switch piccoli 2x2 sono una scelta comune per molte reti multistadio. Il numero di fasi determina il ritardo della rete. Scegliendo diversi modelli di connessione interstadio, è possibile creare vari tipi di rete multistadio.
Crossbar switches- Un interruttore a barra trasversale contiene una matrice di semplici elementi di interruttore che possono essere attivati e disattivati per creare o interrompere una connessione. Attivando un elemento interruttore nella matrice, è possibile stabilire una connessione tra un processore e una memoria. Gli interruttori della barra trasversale non sono bloccanti, ovvero tutte le permutazioni di comunicazione possono essere eseguite senza blocco.
Valutazione dei compromessi di progettazione nella topologia di rete
Se la preoccupazione principale è la distanza di instradamento, la dimensione deve essere massimizzata e deve essere creato un ipercubo. Nell'instradamento store-and-forward, supponendo che il grado di commutazione e il numero di collegamenti non fossero un fattore di costo significativo e che il numero di collegamenti o il grado di commutazione siano i costi principali, la dimensione deve essere ridotta al minimo e una maglia costruito.
Nel peggiore dei casi, il modello di traffico per ciascuna rete, è preferibile avere reti ad alta dimensione in cui tutti i percorsi sono brevi. Nei modelli in cui ogni nodo comunica con solo uno o due vicini vicini, è preferibile avere reti di dimensioni ridotte, poiché vengono effettivamente utilizzate solo alcune dimensioni.
Routing
L'algoritmo di instradamento di una rete determina quale dei possibili percorsi dall'origine alla destinazione viene utilizzato come rotte e come viene determinato il percorso seguito da ogni particolare pacchetto. L'instradamento dell'ordine delle dimensioni limita l'insieme di percorsi legali in modo che esista esattamente un percorso da ciascuna origine a ciascuna destinazione. Quello ottenuto percorrendo prima la distanza corretta nella dimensione di ordine superiore, poi la dimensione successiva e così via.
Meccanismi di instradamento
Aritmetica, selezione della porta basata sulla sorgente e ricerca nella tabella sono tre meccanismi utilizzati dagli switch ad alta velocità per determinare il canale di uscita dalle informazioni nell'intestazione del pacchetto. Tutti questi meccanismi sono più semplici del tipo di calcolo del routing generale implementato nei router LAN e WAN tradizionali. Nelle reti di computer parallele, lo switch deve prendere la decisione di instradamento per tutti i suoi input in ogni ciclo, quindi il meccanismo deve essere semplice e veloce.
Routing deterministico
Un algoritmo di routing è deterministico se il percorso intrapreso da un messaggio è determinato esclusivamente dalla sua origine e destinazione e non da altro traffico nella rete. Se un algoritmo di routing seleziona solo i percorsi più brevi verso la destinazione, è minimo, altrimenti non è minimo.
Deadlock Freedom
Il deadlock può verificarsi in varie situazioni. Quando due nodi tentano di inviare dati l'un l'altro e ciascuno inizia a inviare prima di ricevere, potrebbe verificarsi un deadlock "frontale". Un altro caso di deadlock si verifica quando sono presenti più messaggi in competizione per le risorse all'interno della rete.
La tecnica di base per dimostrare che una rete è priva di deadlock, consiste nell'eliminare le dipendenze che possono verificarsi tra i canali a seguito di messaggi che si spostano attraverso le reti e nel mostrare che non ci sono cicli nel grafico delle dipendenze del canale complessivo; quindi non ci sono modelli di traffico che possono portare a un deadlock. Il modo comune per farlo è numerare le risorse del canale in modo che tutte le rotte seguano una particolare sequenza crescente o decrescente, in modo che non si verifichino cicli di dipendenza.
Cambia design
La progettazione di una rete dipende dalla progettazione dell'interruttore e dal modo in cui gli interruttori sono cablati insieme. Il grado dello switch, i suoi meccanismi di routing interni e il suo buffer interno decidono quali topologie possono essere supportate e quali algoritmi di routing possono essere implementati. Come qualsiasi altro componente hardware di un sistema informatico, uno switch di rete contiene il percorso, il controllo e l'archiviazione dei dati.
Porti
Il numero totale di pin è in realtà il numero totale di porte di input e output moltiplicato per la larghezza del canale. Poiché il perimetro del chip cresce lentamente rispetto all'area, gli interruttori tendono ad essere limitati dai pin.
Datapath interno
Il datapath è la connettività tra ciascun set di porte di input e ogni porta di output. Viene generalmente definita barra trasversale interna. Una barra trasversale non bloccante è quella in cui ciascuna porta di ingresso può essere collegata a un'uscita distinta in qualsiasi permutazione simultaneamente.
Buffer di canale
L'organizzazione della memoria buffer all'interno dello switch ha un impatto importante sulle prestazioni dello switch. I router e gli switch tradizionali tendono ad avere buffer SRAM o DRAM di grandi dimensioni esterni alla struttura dello switch, mentre negli switch VLSI il buffering è interno allo switch e proviene dallo stesso budget di silicio del percorso dati e della sezione di controllo. Man mano che le dimensioni e la densità del chip aumentano, è disponibile più buffering e il progettista della rete ha più opzioni, ma lo spazio del buffer è comunque una scelta primaria e la sua organizzazione è importante.
Controllo del flusso
Quando più flussi di dati nella rete tentano di utilizzare le stesse risorse di rete condivise contemporaneamente, è necessario intraprendere alcune azioni per controllare questi flussi. Se non vogliamo perdere alcun dato, alcuni flussi devono essere bloccati mentre altri procedono.
Il problema del controllo del flusso si pone in tutte le reti ea molti livelli. Ma è qualitativamente diverso nelle reti di computer parallele rispetto alle reti locali e geografiche. Nei computer paralleli, il traffico di rete deve essere fornito con la stessa precisione del traffico su un bus e vi è un numero molto elevato di flussi paralleli su scala temporale molto ridotta.