FAST Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs Slides

FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUsN. Satish, C. Kim, J. Chhugani, A. Nguyen, V. Lee, D. Kim, P. DubeySIGMOD 2010Presented by: Andy HwangMotivation• Index trees are not optimized for architecture• Only one node is accessed per tree level, ineffective cache line utilization • Prefetch cannot be used (depends on comparison ofsearch key to parent)• Nodes in different pages, causing TLB misses• Previous work optimized for page, cache, SIMD separately, not togeth