Appunti presi a lezione di Modelli e tecniche per big data

RAM)

Riassunto 28

bloccante o non bloccante,

in un’operazione di invio bloccante, il mittente deve attendere che il

destinatario confermi la ricezione del messaggio

in un’operazione di ricezione bloccante, il ricevitore attende che venga

ricevuto un messaggio ricevuto prima di procedere con i suoi compiti

Le operazioni di blocco sono spesso definite sincrone perché sia il

mittente che il destinatario sono sincronizzati durante la comunicazione

in un’operazione di invio non bloccante, il mittente continua le sue

operazioni senza attendere la conferma del ricevitore. Tuttavia, il mittente

di aspetta la conferma dal ricevitore nel caso in cui l’invio fallisca

in un’operazione di ricezione non bloccante, il ricevitore può accettare un

messaggio valido o nullo. Se la trasmissione continua a fallire, il ricevitore

potrebbe attendere indefinitamente

Le combinazioni consigliate sono:

invio bloccante e ricezione bloccante, chiamata rendez vous

invio e ricezione non bloccanti

invio non bloccante e ricezione bloccante, il più utilizzato

Comunicazione di gruppo

Nelle applicazioni distribuite parallele, un sistema di passaggio dei messaggi

potrebbe aver bisogno di primitive di comunicazione di gruppo per migliorare le

prestazione e la semplicità di sviluppo

uno a molti, un singolo mittente trasmette un messaggio a più destinatari

(multicast). I processi di ricezione stabiliscono un gruppo che può essere:

aperto, qualsiasi processo può inviare messaggi all’intero gruppo

chiuso, solo i membri possono inviare messaggi internamente

molti a uno, più mittenti trasmettono messaggi ad un singolo destinatario. Il

non determinismo rappresenta una sfida significativa, poiché potrebbe non

essere chiaro quale membro del gruppo avrà a disposizione per primo le

proprie informazioni

Riassunto 29

molti a molti, più mittenti trasmettono messaggi a più destinatari. La consegna

ordinata dei messaggi è fondamentale in quanto garantisce che tutti i

messaggi raggiungano i destinatari in ordine così da essere utilizzate dalle

applicazioni.

Modello: BSP

Bulk Synchronous Parallel è un modello di calcolo parallelo sviluppato da Leslie

Valiant, che propose un paradigma simile al modello di Von Neumann, collegando

hardware e software di macchine parallele. Questo approccio consente ai

programmatore di evitare una costosa gestione della memoria e delle

comunicazioni, ottenendo un calcolo parallelo efficiente con un basso grado di

sincronizzazione.

Un computer BSP è costituito da:

un insieme di processori (PE), che eseguono i calcoli locali

un router, che recapita messaggi tra coppie di PE

un sincronizzatore hardware che consente la sincronizzazione dei PE a

intervalli regolai di L unità di tempo (latenza di comunicazione o periodicità di

sincronizzazione)

Un calcolo nel modello BSP è costituito da un insieme di superstep, in cui a

ciascun processore viene assegnato un compito che comprende passaggi di

elaborazione locale, trasmissioni e arrivi di messaggi.

Un controllo globale avviene ogni L tot di tempo (periodicità) per verificare il

completamente del superstep da parte di tutti i processori prima di procedere a

quello successivo.

Ogni superstep è composto da tre fasi ordinate:

Riassunto 30

Calcolo simultaneo: ogni processore esegue in modo asincrono calcoli che

utilizzano dati locali

Comunicazione globale: i processori scambiano dati in risposta alle richieste

effettuate durante l’elaborazione locale

Sincronizzazione: i processi che raggiungono una barriera si aspettano che

tutti gli altri abbiano raggiunto la stessa barriera.

La comunicazione e la sincronizzazione sono disaccoppiate, garantendo

indipendenza tra i processi in un superstep e prevenzione di problemi relativi al

passaggio sincrono di messaggi, come i deadlock

Il modello BSP impone un limite temporale alla trasmissione in batch dei dati. Tutte

le comunicazioni sono considerate come singole unità, presupponendo una

dimensione del messaggio costante all’interno di tale unità. Infatti, un messaggio

di lunghezza m viene trattato come m messaggi di lunghezza uno, con un costo di

comunicazione è mg. Sia h il numero di messaggi per un superstep e g il rapporto

di throughput della comunicazione, il tempo impiegato da un processore per

inviare h messaggi di dimensione uno è uguale a hg.

Nonostante i potenziali costi, BSP si basa sulla comunicazione con

sincronizzazione tramite barriere, eliminando il rischio di dipendenze circolari e

prevedendo deadlock o livelock (i processi non sono bloccati ma non

progrediscono). I costi di sincronizzazione sono influenzati da fattori quali le

variazioni di tempi di completamento delle fasi di elaborazione locale e il costo per

mantenere la consistenza globale tra i processi. Per questo si devono assegnare

job proporzionali ai carichi di lavoro del processo e prendere in considerazione

Riassunto 31

l’efficienza della rete di comunicazione, hardware per la sincronizzazione e metodi

di gestione degli interrupt.

Costo Algoritmo

Per garantire lo scambio di almeno h messaggi in un superstep è necessario che

, dove L è la periodicità e hg rappresenta il tempo necessario a un

L ≥ hg

processo per inviare h messaggi di dimensione uno.

Il costo totale di un superstep s può essere espresso come ,

T = w + h g + L

s s s

​ ​ ​

dove  indica il costo totale del calcolo effettuato dal superstep.

w s ​

Dato S come il numero totale di superstep, il costo totale di un algoritmo in BSP è:

T = ∑ T ∑ h g + L) = W + H g + S L

= (w +

S s s

​ ​ ​ ​ ​

1≤s≤S 1≤s≤S

W = il costo totale di calcolo

H = è il costo totale della comunicazione

Modello BSP basato su memoria condivisa

Il modello BSP non supporta direttamente la memoria condivisa, broadcast, e

combinazione. Queste funzionalità possono essere emulate con una macchina

parallela ad accesso casuale (PRAM) su un computer BSP. Un numero infinito di

processori sono collegati a una memoria condivisa con capacità illimitata. La

comunicazione avviene tramite la Memory Access Unit (MAU) e i calcoli sono

completamente sincroni.

Varianti:

Riassunto 32

Il modello basato BSP basato sulla memoria condivisa Bulk-Synchronous PPRAM

(BSPRAM) è stato introdotto per facilitare la programmazione in stile memoria

condivisa. E’ composto da p processori, che operano in superstep simili a BSP,

con memoria locale veloce e una singola memoria principale condivisa. Ogni

superstep comprende tre fasi: input, elaborazione locale e output, durante le quali

i processi interagiscono con la memoria principale, la sincronizzazione avviene tra

i superstep, mentre il calcolo all’interno di un superstep rimane asincrono

Riassunto 33

Modello: SQL Like - PGAS

I database relazionali non possono scalare orizzontalmente su più computer.

L’approccio NoSQL ha guadagnato popolarità come alternativa non relazionale,

che consente la scalabilità orizzontale per le operazioni di base di letture/scrittura

del database su più server. I database NoSQL generalmente aderiscono al modello

BASE. A differenza di ACID, che enfatizza atomicità, coerenza, isolamento e

durabilità, BASE dà priorità alla disponibilità di base, allo soft-state e alla coerenza

di finale. Questo spostamento elimina la necessità di coerenza immediata dopo

ogni transazione, consentendo l’elaborazione simultanea di più istanze su server

diversi. I databse NoSQL sono spesso inadatti per l’analisi dei dati. I sistemi di tipo

SQL mirano a combinare l’efficienza della programmazione MapReduce con la

semplicità del linguaggio di tipo SQL. In molti casi, i sistemi di tipo SQL ottimizzano

le query su repository di grandi dimensioni automaticamente utilizzando

MapReduce integrato

Soluzioni come Apache Hive sono state sviluppate per migliorare le capacità di

query dei sistemi MapReduce, semplificando lo sviluppo di applicazioni di analisi

dei database utilizzando un linguaggio simile a SQL. Lo sviluppatore scrive in SQL

e poi queste istruzioni si trasformano per essere compatibili per MapReduce.

I principali vantaggi dell’approccio con SQL includono:

Linguaggio dichiarativo: SQL è dichiarativo, descrive le trasformazioni dei dati

e le operazioni, rendendolo facilmente comprensibile;

Interoperabilità: essendo un linguaggio standardizzato

Riassunto 34

Basato sui dati: le operazioni SQL riflettono le trasformazioni e le modifiche

dei set di dati in input, rendendolo un modello di programmazione conveniente

per applicazioni incentrate sui dati in ambienti tradizionali e big data.

I sistemi di tipo SQL per i big data supportano la tecnica query-in-place,

esecuzione di query direttamente sui dati nella loro posizione originale. Questa

tecnica non solo preserva l’integrità dei dati originali, ma sblocca anche diversi

vantaggi chiave come ottimizzazione dell’utilizzo dei dati, eliminazione dei

processi ridondanti e riduzione della complessità associata allo spostamento dei

dati per la riallocazione, minore latenza per l’esecuzione di query SQL offrendo

disponibilità immediata dei dati.

Il partizionamento dei dati è fondamentale per interrogare in modo efficienti i big

data con SQL. Questo processo divide i dati di una tabella in base a valori di

colonna specifici, creando file e/o directory distinte. Una strategia di

partizionamento consente di ridurre i costi di I/O evitando letture non necessarie

di dati e velocizzando l’elaborazione delle query. un partizionamento eccessivo

può portare a un numero sostanziale di file e directory, con conseguente aumento

dei costi per il nodo del cluster, in quanto deve conservare i metadati nella

memoria.

Modello PGAS

Lo Spazio di Indirizzamento Globale Partizionato è un modello di

programmazione parallelo mirato ad aumentare la produttività. La sua idea

fondamentale ruota attorno all’utilizzo di uno spazio di indirizzamento condiviso a

livello globale per aumentare la produttività, implementando al contempo una

separazione tra l’accesso ai dati locale e quello remoto. Questa separazione

migliora le prestazioni e garantisce la scalabilità su architetture parallela.

Nel modello PGAS, un programma include più processi che eseguono

contemporaneamente lo stesso codice su nodi diversi. Ogni processo ha un

rango, corrispondente all’indice del nodo che lo gestisce. Tali processi hanno

accesso a uno spazio di indirizzamento globale suddiviso in spazi di

indirizzamento locali. Un indirizzo locale è direttamente accessibile da un

processo, mentre gli indir