Predictive B+ tree: differenze tra le versioni

Versione delle 22:07, 8 gen 2016

Versione delle 08:31, 27 gen 2016

Riga 9:

* Rimpiazzare direttamente la [[DRAM]] con una PCM in modo da avere una maggiore capacità di memoria principale

* Utilizzare una grande PCM insieme ad una piccola DRAM (quest’ultimaquest'ultima con capacità pari al 3%/8% della prima) come sistema di memoria principale.

Il modello utilizzato nel BP Tree è il secondo. In tal modo è possibile utilizzare la piccola DRAM come buffer per la PCM al fine di mantenere quei dati che devono essere spesso acceduti o modificati.

== Vantaggi e problematiche per sistemi operanti con PCM ==

Le memorie a cambiamento di fase promettono feature interessanti. Innanzitutto offrono uno storage non volatile ad accesso casuale con indirizzamento a byte e velocità di lettura e scrittura molto elevate. Hanno inoltre una densità molto superiore alle attuali DRAM ed un consumo energetico decisamente inferiore alle memorie NAND FLASH. In seguito è possibile vedere una semplice tabella prestazionale che confronta le performance degli attuali tipi di memorie analizzando principalmente la densità, la velocità, il consumo energetico e l’endurancel'endurance (ossia quante scritture è possibile eseguire su ogni blocco prima di un deterioramento).

{| class="wikitable"

Riga 62:

== Obiettivo del BP Tree ==

Date le prestazioni della tabella precedente, l’obiettivol'obiettivo principale del BP Tree è dunque quello di ridurre il più possibile le operazioni di scrittura sulla PCM.

A tal scopo sono state adottate diverse tecniche.

=== Modello predittivo ===

Per ridurre le scritture è stato adottato un modello predittivo per calcolare il valore futuro (o la distribuzione futura) di un valore casuale. Questo modello combina l’andamentol'andamento precedente e l’andamentol'andamento attuale della distribuzione dei valori dei dati al fine di predirne la futura distribuzione.

=== Strategia a foglie non ordinate ===

All’inserimentoAll'inserimento di una nuova chiave nel BP Tree non viene effettuato l’ordinamentol'ordinamento. Ciò riduce il numero di scritture aumentando però il costo di ricerca.

=== Minimizzazione delle operazioni di Split e Merge ===

Riga 76:

== Architettura del BP Tree ==

=== DRAM Buffer ===

Al suo interno viene memorizzato un piccolo B+ Tree (altezza h e branching factor 2m) e l’istogrammal'istogramma delle distribuzioni delle chiavi precedentemente inserite. Il B+ Tree viene utilizzato per gli inserimenti correnti delle chiavi; l’istogrammal'istogramma per poter attuare il modello predittivo. Quando il buffer è pieno, il B+ Tree verrà unito al BP Tree presente sulla PCM.

=== PCM ===

Riga 88:

[[File:BPTree-WarmUp.png|thumb|Esempio di fase di Warm-Up. Il B+ Tree è pieno e viene trasferito nella PCM. Nell’istogramma la parte blu rappresenta l’effettiva distribuzione delle chiavi, la parte rossa la predizione ottenuta con il modello matematico. Il nodo C del B+ Tree viene scisso nel BP Tree nei nodi C e C’ a causa della predizione futura.]]

Con questo termine si identifica la prima fase di creazione di un BP Tree. Inizialmente il BP Tree è vuoto e utilizziamo il B+ Tree presente nella DRAM per la creazione del primo albero binario. Ad ogni nodo inserito aggiorniamo l’istogrammal'istogramma delle distribuzioni. Quando il buffer sarà pieno lo svuoteremo sulla PCM, creando così lo scheletro del BP Tree. Durante la fase di trascrittura del B+ Tree nella PCM sarà utilizzato il modello predittivo in funzione dei dati presenti nell’istogrammanell'istogramma per scindere o concatenare i nodi che saranno parte del BP Tree.

=== Fase di Update ===

Riga 97:

La chiave viene ricercata sia nel B+ Tree che nel BP Tree.

==== Rimozione ====

La chiave viene ricercata e rimossa sia nel B+ Tree che nel BP Tree, con conseguente aggiornamento dell’istogrammadell'istogramma. In caso di underflow dei nodi del BP Tree, questi non vengono concatenati (riservando spazio per inserimenti futuri).

==== Aggiornamento ====

Viene trattato come una rimozione seguita da un inserimento.