Predictive B+ tree: differenze tra le versioni

Versione delle 00:48, 7 mar 2015

Versione attuale delle 22:39, 14 ott 2021

(18 versioni intermedie di 11 utenti non mostrate)

Riga 1:

Il '''Predictivepredictive B+ Treetree''' (abbreviato '''BP Treetree''' o '''<math>B^P</math> Treetree''') è una variante del [[B-Albero#B.2BTree|B+ Treetree]] studiata appositamente per operare con [[Memoria_a_cambiamento_di_faseMemoria a cambiamento di fase|memorie a cambiamento di fase]] (o PCM, Phase Change Memory) .

Il BP Treetree è stato presentato nel ''IEEE transaction on knowledge and data engineering, vol.26, N°10 di Ottobre 2014'' ed ancora in fase di sperimentazione<ref> {{cita web |url=http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6702416

|titolo=IEEE transaction on knowledge and data engineering, vol.26, N°10, OCT 2014 |lingua=en |sito=IEEE}}</ref>. Gli autori principali di questo albero binario sono Weiwei Hu, Dalie Sun, Guoliang Li, Kian-Lee Tan e Jiacai Ni. La prima presentazione del progetto è stata fatta presso l' [[Università_TsinghuaUniversità Tsinghua|Università di Tsinghua]] come tesi di laurea di Weiwei Hu dal titolo ''Redesign of database algorithms for next generation non-volatile memory technology''.<ref> {{cita web |url=http://www.scholarbank.nus.edu.sg/bitstream/handle/10635/36540/HuWW.pdf |titolo=Redesign of database algorithms for next generation non-volatile memory technology |lingua=en |sito=scholarbank.nus.edu.sg |urlmorto=sì }}</ref>.

|titolo=Redesign of database algorithms for next generation non-volatile memory technology |lingua=en |sito=scholarbank.nus.edu.sg}}</ref>.

== Posizione delle PCM nella gerarchia della memoria ==

In fase di progettazione del BP Treetree si è presentato il dilemma di come posizionare le PCM nella gerarchia della memoria. Le possibilità sono due.

* 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 Treetree è 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 19:

!

! [[DRAM]]

! [[Memoria_a_cambiamento_di_faseMemoria a cambiamento di fase|PCM]]

! [[Memoria_flashMemoria flash#NAND_FlashNAND Flash|NAND]]

! [[Disco_rigidoDisco rigido|HDD]]

|-

! Densità

Riga 60:

Come si evince dalla tabella, le PCM sono più lente delle attuali DRAM, soprattutto nelle operazioni di scrittura; inoltre tali operazioni hanno un consumo energetico nettamente superiore. Infine è importante evidenziare che il numero di scritture su singolo blocco non ha importanza per le DRAM, ma è un elemento critico sul lungo periodo per le PCM.

== Obiettivo del BP Treetree ==

Date le prestazioni della tabella precedente, l’obiettivol'obiettivo principale del BP Treetree è 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 Treetree non viene effettuato l’ordinamentol'ordinamento. Ciò riduce il numero di scritture aumentando però il costo di ricerca.

=== Minimizzazione delle operazioni di Splitsplit e Mergemerge ===

Soverchiando alcune delle regole principali del B+ Treetree (su cui il BP Treetree si basa), accettiamo nel BP Treetree un bilanciamento non canonico al fine di diminuire le operazioni di Split e Merge che rappresentano la fonte maggiore di scritture nei B+ Treetree.

== Architettura del BP Treetree ==

=== DRAM Buffer ===

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

=== PCM ===

Come anticipato, sulla PCM viene memorizzato il vero e proprio BP Treetree (altezza h e branching factor 2M), ossia un albero binario del tutto uguale al B+ Treetree ad eccezione di alcune caratteristiche:

* La struttura ed i nodi possono essere pre-allocati.

* Dato il branching factor 2M del BP Treetree, il numero di nodi figlio di un nodo interno può essere minore di M (comunque compreso tra 0 e 2M).

* Differente gestione degli inserimenti e delle cancellazione rispetto ai B+ Treetree.

* Dato il branching factor 2M del BP Tree, il numero di nodi figlio di un nodo interno può essere minore di M (comunque compreso tra 0 e 2M).

* Differente gestione degli inserimenti e delle cancellazione rispetto ai B+ Tree.

== Fasi ==

=== Fase di Warmwarm-Upup ===

[[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 Treetree. Inizialmente il BP Treetree è vuoto e utilizziamo il B+ Treetree 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 Treetree. Durante la fase di trascrittura del B+ Treetree 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 Treetree.

=== Fase di Updateupdate ===

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’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’istogramma per scindere o concatenare i nodi che saranno parte del BP Tree.

In seguito alla fase di Warmwarm-Upup nella PCM è presente la struttura del BP Treetree. La fase succesivasuccessiva, detta Updatedi ''update'', comprende tutte le operazioni future:

=== Fase di Update ===

In seguito alla fase di Warm-Up nella PCM è presente la struttura del BP Tree. La fase succesiva, detta Update, comprende tutte le operazioni future:

==== Inserimento ====

Le nuove chavi vengono inserite nel B+ Treetree con aggiornamento del relativo istogramma. Se il buffer DRAM è pieno, il B+ Treetree viene fuso con il BP Treetree nella PCM.

==== Ricerca ====

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

==== Rimozione ====

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

==== Aggiornamento ====

Viene trattato come una rimozione seguita da un inserimento.

== Prestazioni ==

Il BP Treetree è stato testato su un DBMS PostgreSQL. I dati raccolti hanno evidenziato che nelle architetture a memoria principale ibrida DRAM + PCM il BP Treetree è più performante del B+ Treetree.

== Note ==

{{<references|1}} />

== Voci correlate ==

* [[B-Treealbero]]

* [[Memoria a cambiamento di fase]]

* [[Memoria_a_cambiamento_di_fase|PCM]]

* [[DRAM]]

== Collegamenti esterni ==

* [{{cita web|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6702416 |titolo=IEEE transaction on knowledge and data engineering, vol.26, N°10, OCT 2014]}}

* [{{cita web | 1 = http://www.scholarbank.nus.edu.sg/bitstream/handle/10635/36540/HuWW.pdf | 2 = Redesign of database algorithms for next generation non-volatile memory technology] | urlmorto = sì }}

{{Portale|informatica}}

[[Categoria:Alberi di ricerca]]