bit bit bit VAST N d i d 1 <d 2 <...<d k <...<d N d k VAST d k 3 d k 3 d k 2 d k 1 d k 4 w w=4 ) HW HW 32bit γ δ [4] PForDelta [3] HW CPU VAST VAST VA

Size: px

Start display at page:

Download "bit bit bit VAST N d i d 1 <d 2 <...<d k <...<d N d k VAST d k 3 d k 3 d k 2 d k 1 d k 4 w w=4 ) HW HW 32bit γ δ [4] PForDelta [3] HW CPU VAST VAST VA"

えいじろうおおはし
5 years ago
Views:

1 DEIM Forum 2013 F10-6 VAST CPU NTT, CPU HW HW HW VAST VAST SIMD CPU TLB bit VAST VAST VAST VAST CPU SIMD VAST-Tree Compression Penalty on Modern Processors - Experiments and Observations Takeshi YAMAMURO, Makoto ONIZUKA, and Fumikazu KONISHI NTT Service Innovation Laboratory Group, Midori-machi, Musashino-shi Tokyo, Japan {yamamuro.takeshi,onizuka.makoto,konishi.fumikazu}@lab.ntt.co.jp 1. Introduction CPU CPU HW HW N e.g., d i d 1 <d 2 <...<d N d k ID e.g., ID) ID 2 B+ HW CPU TLB [1] HW VAST [2] VAST CPU B+ SIMD CPU TLB VAST

2 bit bit bit VAST N d i d 1 <d 2 <...<d k <...<d N d k VAST d k 3 d k 3 d k 2 d k 1 d k 4 w w=4 ) HW HW 32bit γ δ [4] PForDelta [3] HW CPU VAST VAST VAST CPU 1 γ δ Variable-Byte [4] Varint-G8IU [19] Simple9 [13]/16 [14]/8b [17] BP [15] PForDelta [3] VSEncoding [16] VAST 4. VAST 1 n k Related Works CPU CPU [5] CPU B+ CPU [6] [7] [8] [9] B+ 2 TLB 3 TLB CPU [11] [10] SIMD [12] Intel Lab. FAST [1] TLB SIMD VAST [2] FAST FAST SIMD 3. VAST-Tree 32bit VAST Fig.4 4 VAST 4 bit 4 H PH CH SH 2 bit SH 32=3 SH 32bit 3 7 SH CPU SIMD CPU 1 Intel x86 CPU 128bit 2 CPU CPU 64B 3 Translation Look-aside Buffer CPU 4 64-bit VAST P 64 4

3 32bit 4 16bit 8 32bit 16 VAST SH 32=2 3 SH 16=3 7 SH 8=3 3 Intel CPU Haswell 256bit SH CH bit CH 32 CH 16 CH 8 bit 16bit 24bit CH bit bit CH bit bit PH CPU TLB 1 P 32 P 16 P 8 3 VAST 4. Leaf Compression P 16 P 8 16bit 8bit w > = 0 w VAST 4. 1 γ, δ, and Variable-Byte codes γ δ [4] γ d 2 bit 1 0 d d= bit γ γ bit δ γ 0 γ bit bit d=9 bit 4 γ γ δ bit byte Variable-Byte CPU bit byte Variable-Byte byte Variable-Byte 7bit 7bit 1byte 1bit byte byte bit 1 d= bit bit 100 bit byte bit byte bit 1 byte 4. 2 Varint-G8IU Variable-Byte Varint-G8IU [19] Varint-G8IU Google Group Variant [18] 2 8 Variable-Byte 1B 8B 8B 2 8 Variable-Byte 1bit bit 8B d[4]={2 15 (2B), 2 23 (3B), 2 7 (1B), 2 15 (2B)} Variable-Byte 1bit bit byte 8B 8B 0 byte 32-bit Varint-G8IU SIMD Intel SSE3 5 pshufb pshufb SIMD IN mask SIMD OUT mask byte 5 shuffle SIMD ARM SIMD NEON

4 pshufb 32-bit SIMD 8B SIMD 1 2 SIMD Algorithm bit 1: UNPACK8 32(uint32 t src[8], uint32 t dst[32]) 2: for i = 0 7 do 3: dst[i * 4] = src[i] & 0x0F; 4: dst[1 + i * 4] = (src[i] >> 8) & 0x0F; 5: dst[2 + i * 4] = (src[i] >> 16) & 0x0F; 6: dst[3 + i * 4] = (src[i] >> 24) & 0x0F; 7: end for Simple9/16/8b pshufb Varint-G8IU CPU 32bit 64bit word 32bit word Simple9 [13] Simple16 [14] 64bit Simple8b [17] word 4bit bit Simple9/16 28bit Simple8b 60bit 4bit bit Simple9/ bit 28bit bit 28bit 4bit Simple9 9 Simple16/8b BP: block packing BP [15] bit bit 8bit 4 32bit Algorithm 1 Algorithm 2 bit shift mask BP32 SIMD SIMD-BP32 Algorithm bit 1: PACK8 32(uint32 t src[32], uint32 t dst[8]) 2: for i = 0 7 do 3: dst[i] = src[i * 4] & 0x0F; 4: dst[i] = (src[1 + i * 4] & 0x0F) << 8; 5: dst[i] = (src[2 + i * 4] & 0x0F) << 16; 6: dst[i] = (src[3 + i * 4] & 0x0F) << 24; 7: end for 4. 5 PForDelta and the variants PForDelta [3] Simple9/16 BP PForDelta m 90% bit b b-bit b-bit bit m=10 1, 3, 2, 3, 1, 2, 203, 3, 0, % 2bit b=2 203 bit 2bit bit 1 2, 3 2, 2 2, 3 2, 1 2, 2 2, 3 2, 0 2, 2 2, bit 203 OPTPForDelta PForDelta OPTPForDelta b-bit b-bit bit Simple16 OPTPForDelta b-bit SIMD-BP32 SIMD SIMD-FastPFor Simple8b SimplePFor [15] 4. 6 VSEncoding PForDelta m b k B 1, B 1,..., B k bit bit VSEncoding [16] 4. 7 Block compression

5 k g g/k 4bit k B 64B CPU w CPU CPU CPU- [1] footprint k footprint k Experimental VAST 2 1 / 2 w 1 2 VAST w UniformData ClusterData [17] Gov2 ClueWeb09 6 UniformData ClusterData github 7 [0,2 29 ) 2 25 [15] Gov2 TREC Terabyte Track 1 gov html/text URL ID ClueWeb09 8 Web Gov2 ID URL δ i(=x i-x i 1-1) prefix-sum x i=δ i+x i 1 CPU 6 Intel Xeon GiB Xeon 5670 L1/L2/LL (Last-Level) 32KiB/256KiB/12MiB Xeon 5670 Westmere-EP SIMD SSE2 pshufb SSE3 C++ GNU Compiler Collection v O2 -march=nocona Comparison Results UniformData ClusterData coding / decoding bits/int 1 2 Gov2 ClueWeb / 1,000,000 mis million integers per second bit [0,2 29 ) ( )bits/int UniformData ClusteredData ClusteredData δ i byte Variable-Byte Varint-G8IU γ δ UniformData Simple16/Simple8b/BP32 ClusteredData BP32/SimplePFor/VSEncoding) γ δ OPTPForDelta VSEncoding 2 Varint-G8IU UniformData ClusteredData Gov2 ClueWeb byte SSE SSE

6 bits/int Gov2 Simle9/16 PForDelta OPTPForDelta VSEncoding Varint-G8IU bits/int Gov2 ClueWeb09 Varint-G8IU 1 / UniformData) γ δ Variable-Byte Varint-G8IU Simple Simple Simple8b BP SIMD-BP PForDelta OPTPForDelta SIMD-FastPFor SimplePFor VSEncoding / ClusteredData) γ δ Variable-Byte Varint-G8IU Simple Simple Simple8b BP SIMD-BP PForDelta OPTPForDelta SIMD-FastPFor SimplePFor VSEncoding / Gov2) γ δ Variable-Byte Varint-G8IU Simple Simple Simple8b BP SIMD-BP PForDelta OPTPForDelta SIMD-FastPFor SimplePFor VSEncoding / ClueWeb09) γ δ Variable-Byte Varint-G8IU Simple Simple Simple8b BP SIMD-BP PForDelta OPTPForDelta SIMD-FastPFor SimplePFor VSEncoding w w 6. Discussion 1 Gov2 ClueWeb UniformData w w=2 7 Gov2 ClueWeb09 VSEncoding γ δ PForDelta OPTPForDelta

7 4 ClusteredData 8 / ClueWeb09 γ δ PForDelta OPTPForDelta VSEncoding 5 Gov2 6 ClueWeb09 7 / gov2 7. Conclusions VAST VAST bit VAST VAST [1] Changkyu Kim et al. Designing Fast Architecture Sensitive Tree Search on Modern Multi-Core/Many-Core Processors, ACM Transactions on Database Systems, 9(4), [2] Takeshi Yamamuro et al. VAST-Tree: a vector-advanced and compressed structure for massive data tree traversal, Proc. of EDBT 12, pp , [3] Marcin Zukowski et al. Super-Scalar RAM-CPU Cache Compression, Proc. of ICDE 06, pp , [4] Ian H. Witten et al. Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann, 1999 [5] P. A. Boncz et al. Database Architecture Optimized for the New Bottleneck: Memory Access, Proc. of VLDB 99, pp , [6] J. Rao and K. A. Ross. Cache Conscious Indexing for Decision- Support in Main Memory, Proc. of VLDB 99, pp , [7] J. Rao and K. A. Ross. Making B+-trees cache conscious in main memory, Proc. of SIGMOD 00, pp , [8] G. Graefe and P.-A. Larson. B-Tree Indexes and CPU Caches, Proc. of ICDE 01, pp , [9] R. A. Hankins and J. M. Patel. Effect of node size on the performance of cache-conscious B+-trees., Proc. of SIGMETRICS 03, pp , [10] S. Chen, P. B. Gibbons, and T. C. Mowry. Improving index performance through prefetching., SIGMOD Record, 30(2), pp , [11] J. Zhou and K. A. Ross. Buffering accesses to memory-resident index structures., Proc. of VLDB 03, pp , [12] B. Schlegel, R. Gemulla, and W. Lehner. k-ary search on modern processors., Proc. of DaMoN 09, pp , [13] Vo Ngoc Anh and Alistair Moffat. Inverted Index Compression Using Word-Aligned Binary Codes, Journal of Information Retrieval, Vol. 8, Issue. 1, pp , [14] Hao Yan et al. Inverted index compression and query processing with optimized document ordering, Proc. of WWW 09, pp , [15] D. Lemire and L. Boytsov. Decoding billions of integers per second through vectorization, Journal of CoRR, [16] Fabrizio Silvestri and Rossano Venturini VSEncoding: efficient coding and fast decoding of integer lists via dynamic programming, Proc. of CIKM 10, pp , [17] Anh VN and Moffat A. Index compression using 64-bit words. Software, Practice and Experience, Vol. 40, Issue. 2, pp , [18] Dean J. Challenges in building large-scale information retrieval systems, Proc. of WSDM 09, [19] Stepanov AA. and et al. SIMD-based decoding of posting lists, Proc. of CIKM 11, 2011.

Microsoft Word - toyoshima-deim2011.doc

Microsoft Word - toyoshima-deim2011.doc DEIM Forum 2011 E9-4 252-0882 5322 252-0882 5322 E-mail: t09651yt, sashiori, kiyoki @sfc.keio.ac.jp CBIR A Meaning Recognition System for Sign-Logo by Color-Shape-Based Similarity Computations for Images