Rethinking Database Algorithms for Phase Change Memory

Slide Note

Exploring the potential of Phase Change Memory (PCM) technology, this paper presents algorithm design for PCM-based main memory in the context of database systems. The emerging non-volatile memory technology of PCM is compared to DRAM, showcasing its byte-addressable nature, lower latency, and higher endurance. Discussions include PCM-friendly algorithm designs such as B+-Tree indexing and hash joins, aiming to leverage PCM as the main memory component in future database systems.

jwolk Follow

Uploaded on Dec 12, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

Rethinking Database Algorithms for Phase Change Memory Shimin Chen* Phillip B. Gibbons* Suman Nath+ *Intel Labs Pittsburgh +Microsoft Research

Introduction PCM is an emerging non-volatile memory technology Samsung is producing a PCM chip for mobile handsets Expected to become a common component in memory/storage hierarchy Recent computer architecture and systems studies argue: PCM will replace DRAM to be main memory PCM-DB project: exploiting PCM for database systems This paper: algorithm design on PCM-based main memory Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 2

Outline Phase Change Memory PCM-Friendly Algorithm Design B+-Tree Index Hash Joins Related Work Conclusion Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 3

Phase Change Memory (PCM) Byte-addressable non-volatile memory Two states of phase change material: Amorphous: high resistance, representing 0 Crystalline: low resistance, representing 1 Operations: RESET to Amorphous e.g., ~610 C (Temperature) Current SET to Crystalline e.g., ~350 C READ Time Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 4

Comparison of Technologies DRAM 64B 20-50ns 20-50ns GB/s per die N/A 0.8 J/GB 1.2 J/GB 100 mW/GB PCM 64B 50ns 1 s 50-100 MB/s per die N/A 6 10 NAND Flash 4KB 25 s 500 s 5-40 MB/s per die 2 ms 4 10 Page size Page read latency Page write latency Write bandwidth Erase latency 8 5 Endurance 10 10 Read energy Write energy Idle power 1 J/GB 6 J/GB 1 mW/GB 1.5 J/GB [28] 17.5 J/GB [28] 1 10 mW/GB Density 1 2 4 4 Compared to NAND Flash, PCM is byte-addressable, has orders of magnitude lower latency and higher endurance. Sources: [Doller 09] [Lee et al. 09] [Qureshi et al. 09] Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 5

Comparison of Technologies DRAM 64B 20-50ns 20-50ns GB/s per die N/A 0.8 J/GB 1.2 J/GB 100 mW/GB PCM 64B 50ns 1 s 50-100 MB/s per die N/A 6 10 NAND Flash 4KB 25 s 500 s 5-40 MB/s per die 2 ms 4 10 Page size Page read latency Page write latency Write bandwidth Erase latency 8 5 Endurance 10 10 Read energy Write energy Idle power 1 J/GB 6 J/GB 1 mW/GB 1.5 J/GB [28] 17.5 J/GB [28] 1 10 mW/GB Density 1 2 4 4 Compared to DRAM, PCM has better density and scalability; PCM has similar read latency but longer write latency Sources: [Doller 09] [Lee et al. 09] [Qureshi et al. 09] Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 6

Relative Latencies: Read NAND Flash Hard Disk DRAM PCM 10ns 100ns 1us 10us 100us 1ms 10ms NAND Flash Hard Disk DRAM PCM Write Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 7

PCM-Based Main Memory Organizations PCM is a promising candidate for main memory Recent computer architecture and systems studies Three alternative proposals: [Condit et al 09] [Lee et al. 09] [Qureshi et al. 09] For algorithm analysis, we focus on PCM main memory, and view optional DRAM as another (transparent/explicit) cache Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 8

Challenge: PCM Writes PCM 64B 50ns 1 s 50-100 MB/s per die N/A 6 10 Page size Page read latency Page write latency Write bandwidth Limited endurance Wear out quickly for hot spots Erase latency High energy consumption 6-10X more energy than a read 8 Endurance 10 Read energy Write energy Idle power 1 J/GB 6 J/GB 1 mW/GB High latency & low bandwidth SET/RESET time > READ time PCM chip has limited instantaneous electric current level, requires multiple rounds of writes Density 2 4 Write operation and hardware optimization Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 9

PCM Write Operation [Cho&Lee 09] [Lee et al. 09] [Yang et al 07] [Zhou et al 09] Baseline: several rounds of writes for a cache line Which bits in which rounds are hard wired Optimization: data comparison write Goal: write only modified bits rather than entire cache line Approach: read-compare-write Skipping rounds with no modified bits Rounds highlighted w/ different colors Cache line 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 PCM 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 10

Outline Phase Change Memory PCM-Friendly Algorithm Design B+-Tree Index Hash Joins Related Work Conclusion Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 11

Algorithm Design Goals Algorithm design in main memory Prior design goals: Low computation complexity Good CPU cache performance Power efficiency (more recently) New goal: minimizing PCM writes Improve endurance, save energy, reduce latency Unlike flash, PCM word granularity Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 12

PCM Metrics Algorithm parameters: : cache misses (i.e. cache line fetches) : cache line write backs : words modified w N N N l N N l lw lw PCM N w We propose three analytical metrics Total Wear (for Endurance) Energy Total PCM Access Latency Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 13

B+-Tree Index Cache-friendly B+-Tree: Node size: one or a few cache lines large Problem: insertion/deletion in sorted nodes Incurs many writes! [Rao&Ross 00] [Chen et al 01] [Hankins et al. 03] Insert/delete keys num 5 2 4 7 8 9 pointers Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 14

Our Proposal: Unsorted Nodes Unsorted node num keys 5 8 2 9 4 7 pointers Unsorted node with bitmap keys bitmap 1011 1010 8 2 9 4 7 pointers Unsorted leaf nodes, but sorted non-leaf nodes Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 15

Simulation Platform Cycle-accurate out-of-order X86-64 simulator: PTLSim Extended the simulator with PCM support Details of Write Backs in Memory Controller PTLSim Data Comparison Writes PCM PCM PCM PCM Parameters based on computer architecture papers Sensitivity analysis for the parameters Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 16

Node size 8 cache lines; 50 million entries, 75% full; Three workloads: Inserting 500K random keys deleting 500K random keys searching 500K random keys B+-Tree Index Total wear Energy Execution time 16 3E+8 5E+9 14 num bits modified 4E+9 12 energy (mJ) 2E+8 10 3E+9 cycles 8 2E+9 6 1E+8 4 1E+9 2 0E+0 0 0E+0 insert delete search insert delete search insert delete search Unsorted leaf schemes achieve the best performance For insert intensive: unsorted-leaf For insert & delete intensive: unsorted-leaf with bitmap Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 17

Simple Hash Join Build hash table on smaller (build) relation Probe hash table using larger (probe) relation Build Probe Relation Relation Hash Table Problem: too many cache misses Build + hash table >> CPU cache Record size is small Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 18

Cache Partitioning Partition both tables into cache-sized partitions Join each pair of partitions [Shatdal et al. 94] [Boncz et al. 99] [Chen et al. 04] Problem: too many writes in partition phase! Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 19

Our Proposal: Virtual Partitioning Virtual partitioning: Record ID Lists Compressed Join a pair of virtual partitions: Build Probe Relation Relation Hash Table Preserve good CPU cache performance while reducing writes Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 20

Hash Joins 50MB joins 100MB; varying record size from 20B to 100B. Total wear Energy Execution time 1E+9 40 1E+10 num bits modified 8E+9 30 (log scale) energy (mJ) 1E+8 6E+9 cycles 20 4E+9 1E+7 10 2E+9 1E+6 0 0E+0 record size record size record size Virtual partitioning achieves the best performance Interestingly, cache partitioning is the worst in many cases Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 21

Related Work PCM Architecture Hardware design issues: endurance, write latency, error correction, etc. Our focus: PCM friendly algorithm design Byte-Addressable NVM-Based File Systems Battery-Backed DRAM Main Memory Database Systems & Cache Friendly Algorithms Not considering read/write asymmetry of PCM Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 22

Conclusion PCM is a promising non-volatile memory technology Expected to replace DRAM to be future main memory Algorithm design on PCM-based main memory New goal: minimize PCM writes Three analytical metrics PCM-friendly B+-tree and hash joins Experimental results show significant improvements Rethinking Database Algorithms for Phase Change Memory Shimin Chen, Phillip B. Gibbons, Suman Nath 23