Predictive B+ tree: differenze tra le versioni

Versione delle 08:31, 27 gen 2016

Versione attuale delle 22:39, 14 ott 2021

(6 versioni intermedie di 4 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 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à 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'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 ==

Riga 61 ⟶ 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'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.

Riga 69 ⟶ 68:

=== Strategia a foglie non ordinate ===

All'inserimento di una nuova chiave nel BP Treetree non viene effettuato l'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'istogramma delle distribuzioni delle chiavi precedentemente inserite. Il B+ Treetree viene utilizzato per gli inserimenti correnti delle chiavi; l'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.

== Fasi ==

=== Fase di Warmwarm-Upup ===

[[File:BPTree-WarmUp.png|thumb|Esempio di fase di Warm''warm-Upup''. Il B+ Treetree è 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+ Treetree viene scisso nel BP Treetree 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'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'istogramma per scindere o concatenare i nodi che saranno parte del BP Treetree.

=== Fase di Updateupdate ===

In seguito alla fase di Warmwarm-Upup nella PCM è presente la struttura del BP Treetree. La fase successiva, 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 successiva, 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'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|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}}