Detail View

Phase change memory (PCM) is a byte-addressable type of non-volatile memory, which is two to four times denser than dynamic random access memory (DRAM). PCM has much lower both read and write latencies compared to the NAND flash memory. Although the write endurance of PCM is approximately 10 times better than NAND flash memory, the maximum number of writes per each PCM cell is bounded by 〖10〗^6 times. The endurance problem of PCM can be improved by reducing the number of writes and balancing them among all PCM cells, where possible, keep PCM cells usable.
Nowadays, storing spatial data is important, because the spatial data is being used by many applications such as location information. In this dissertation we propose to use R -Tree and R* -Tree over PCM. The objective of this dissertation is to design a PCM aware R -Tree and R* -Tree that can store spatial data while improving the endurance problems of PCM. Firstly, we examine how existing R -Tree and R* -Tree causes “endurance” problems in PCM, and we then optimize it for PCM. The experiments conducted for this dissertation show that split operation of existing R -Tree and R* -Tree drastically increases the number of writes. We propose to increase the size of leaf nodes that will decrease the number of splits, thus improve the endurance problem of PCM. Moreover, we propose to write a split node to a blank node, which will help to distribute the number of writes among all PCM cells proportionally. Furthermore, to improve the endurance of PCM, we propose to update parent nodes only once and not to merge the nodes after deletion when the minimum fill factor requirement does not meet. Additionally we propose moving once scheme while splitting R* -Tree nodes that will decrease the number of writes, thus improving the endurance problem of PCM. 
According to our experimental results, Proposed R -Tree and R* -Tree drastically reduce the number of write operations to PCM while using both the benchmark and synthetic datasets, thus improving the endurance problem of PCM. Moreover Proposed R -Tree and R* -Tree improve the performance in terms of processing time for insert, retrieval and delete operations. The results suggest that Proposed R -Tree and R* -Tree schemes outperform existing R -Tree and R* -Tree by improving the PCM endurance problem, as well as performance.

ABSTRACTITABLE OF CONTENTSVLIST OF FIGURESVIIILIST OF TABLESXII1. INTRODUCTION11.1.THEORETIC BACKGROUND AND OBJECTIVE OF RESEARCH11.2. DISSERTATION ORGANIZATION92. BACKGROUND112.1. PCM112.2. R -TREE AND R* -TREE132.2.1. R -Tree142.2.2. R* -Tree203. RELATED WORK274. MOTIVATION334.1. EXPERIMENT SETUP334.2. R -TREE354.3. R* -TREE394.4. ANALYSIS425. PCM BASED R -TREE AND R* -TREE445.1. INCREASED LEAD NODE SIZE445.2. REPLACE THE SPLIT NODE WITH A BLANK ONE455.3. SINGLE PARENT UPDATE465.4. NO MINIMUM FILL FACTOR REQUIREMENT ON DELETION485.5. MOVE ONCE FOR R* -TREE496. PERFORMANCE EVALUATION OF PROPOSED R -TREE516.1. PERFORMANCE FOR BENCHMARK DATASET516.1.1. Space Consumption of the Proposed R -Tree516.1.2. Number of Writes546.1.3. Processing Time586.1.4. Evaluation of not Merging R -Tree Nodes during Delete Operation596.2. PERFORMANCE FOR SYNTHETIC DATASET616.2.1. Number of Writes616.2.2. Processing Time696.3. PERFORMANCE FOR MULTIPLE SYNTHETIC DATASETS726.3.1. Number of Writes726.3.2. Processing time777. PERFORMANCE EVALUATION OF PROPOSED R* -TREE797.1. PERFORMANCE FOR BENCHMARK DATASET797.1.1. Space Consumption of the Proposed R* -Tree797.1.2. Number of Writes827.1.3. Processing Time867.1.4. Evaluation of not merging R* -Tree nodes during delete operation877.2. PERFORMANCE FOR SYNTHETIC DATASET897.2.1. Number of Writes897.2.2. Processing Time977.3. PERFORMANCE FOR MULTIPLE SYNTHETIC DATASETS997.3.1. Number of Writes997.3.2. Processing Time1048. CONCLUSION AND FUTURE WORK1069. REFERENCE111