Time Lower Bounds for Parallel Network Computations

I Direct Acyclic Graphs (DAG, grafi orientati e aciclici) sono dei grafi che descrivono in modo semplice ed efficace le esecuzioni di algoritmi, e permettono di rappresentare graficamente le relazioni di precedenza tra le operazioni. Al di là dell’esecuzione di algoritmi, un DAG può anche rappresentare l’esecuzione di una rete parallela. Quest’ultimo tipo di DAG ha una struttura molto regolare, corrispondente alla ripetizione nel tempo della rete stessa; il fatto che l’esecuzione di algoritmi e di reti parallele abbiano questa rappresentazione comune ci suggerisce un possibile approccio unificato nel loro studio. I DAG sono stati molto usati nello studio di caratteristiche di algoritmi, in calcolo parallelo e nello studio della complessità computazionale. Ad esempio sono stati impiegati per ottenere lower bound per il tempo di esecuzione di algoritmi e di emulazione tra reti, per la quantità minima di memoria necessaria al calcolo di un algoritmo e il numero minimo di accessi in memoria lenta durante l’esecuzione di un algoritmo con una quantità di memoria veloce predeterminata. Le tecniche sviluppate in questi studi partono da ipotesi diverse, una delle più importanti è la possibilità o meno di ricalcolare i risultati intermedi: se ciò non è possibile infatti è necessario salvarli in memoria per poterli usare in momenti successivi del calcolo. Il trade-off tra ricalcolo e salvataggio in memoria dei dati è importante sia in ambito parallelo che nelle elaborazioni locali; infatti nel primo caso il ricalcolo può ridurre la latenza ed aumentare la banda con cui possiamo accedere ai dati in una rete di processori, calcolando gli stessi risultati in più punti della rete, mentre nel caso di elaborazioni locali il ricalcolo può evitare i problemi di latenza e banda nel recupero dei dati dalla memoria. Ad oggi non esiste una tecnica universale in grado di fornire lower bound stretti per ogni algoritmo od emulazione di rete eseguiti in reti parallele, e i risultati conosciuti derivano da diversi teoremi. Al contrario, ci sono molti casi in cui mancano risultati stretti, anche per reti molto studiate e relativamente semplici com gli array multidimensionali. La tesi inizia da questo stato dell’arte: la prima parte propone una panoramica delle tecniche di lower bound per DAG note, e termina con la presentazione dei teoremi originali sviluppati con la tesi, che migliorano o risolvono alcuni dei problemi aperti noti. In particolare, nella panoramica consideriamo tecniche di lower bound per l’esecuzione di algoritmi e emulazione di reti da parte di reti parallele, mostrando le idee su cui si basano e i loro limiti. Nello svolgimento vengono messe in evidenza le relazioni tra i teoremi, mostrando che attualmente nessuno di essi dà in assoluto risultati migliori: è possibile infatti presentare controesempi in cui ciascun teorema fornisce risultati più stretti degli altri. E' anche possibile mostrare esempi di coppie di reti dove il miglior bound tra le tecniche considerate non è stretto. Inoltre generalizziamo alcuni teoremi originariamente pensati per emulazioni di reti e che noi adattiamo all’esecuzione di DAG generici in reti parallele, mostrandone alcune applicazioni. Consideriamo anche teoremi per determinare la complessità minima di accessi alla memoria per il calcolo di un algoritmo, mostrandone similarità e differenze con i teoremi per le emulazioni. Uno dei risultati più interessanti della tesi è una nuova tecnica generale che fornisce lower bound quasi stretti – eccetto per un fattore moltiplicativo logaritmico – in una classe di emulazione di reti che include gli array multidimensionali. Precedentemente il miglior risultato noto differiva di un fattore polinomiale dal miglior tempo di emulazione noto. Il nostro teorema ammette il ricalcolo durante l’emulazione, ponendosi nel contesto più generale possibile. Infine consideriamo il ruolo del ricalcolo nelle performance, cercando di capire quando esso possa dare un reale vantaggio rispetto alla memorizzazione di risultati intermedi. Introduciamo il problema partendo da reti semplici, mostrando una classe di esse in cui il ricalcolo non migliora la complessità di accessi in memoria, terminando con i DAG a butterfly, dove il ricalcolo riesce a migliorare questa complessità di un termine almeno pari alla memoria usata durante il calcolo. L’approccio usato mette in luce la difficoltà` di usare proficuamente il ricalcolo durante l’esecuzione di algoritmi che presentano un’elevata connettività.