A Computational Model for Parallel and Hierarchical Machines

Il parallelismo e ̀ una metodologia molto diffusa per aumentare la potenza di cal-colo disponibile e fronteggiare le richieste computazionali sempre crescenti delle odierne applicazioni. Negli ultimi trent’anni, la soluzione offerta dal parallelismo e ̀ stata ampiamente studiata ed applicata; nonostante i successi ottenuti, tuttavia, la programmazione parallela rimane una attivita ̀ laboriosa. Le difficolta ̀ nella pro-grammazione sono aggravate dalla persistente mancanza di un modello di calcolo parallelo che riscuota unanime consenso: una spiegazione di questo fatto e ̀ che un tale modello deve soddisfare requisiti parzialmente contrastanti. In anni recenti, la comunita ̀ scientifica ha riconosciuto la necessita ̀ di un “modello ponte ” (bridging model), capace di contemperare tali contrastanti necessità. Nella presente tesi si avanza la candidatura a bridging model del D-BSP, una estensione del popolare modello BSP di Valiant pensata per catturare una porzione sostanziale della struttura gerarchica presente nella rete di interconnessione dei calcolatori par-alleli. La prima parte di questa tesi presenta esempi dell’utilita ̀ della gerarchia di rete cos̀ı come modellata dal D-BSP. In particolare, nel Capitolo 2 si fornisce un