Address Set Disambiguation in Bloom Filter Configuration

This research delves into optimizing Bloom filter configuration for lazy address-set disambiguation, revealing challenges in parallel programming, memory access management, and addressing conflicts. The study explores the efficiency and implications of using Bloom filters in concurrency tools and addresses the importance of detecting address-set conflicts for parallelism.

• Bloom Filter
• Address Set
• Disambiguation
• Parallel Programming
• Concurrency

osie_449 Follow

Uploaded on Feb 15, 2025 | 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.

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.

Presentation Transcript

1. Understanding and Improving Bloom Filter Configuration for Lazy Address-Set Disambiguation Mark Jeffrey September 16, 2011 MASc thesis defense

2. Parallel Programming is Hard T2 T1 T3 Rd(a) Tools offload some burden of managing data accesses: Memory Race Replay Atomicity Violation Survival Transactional Memory Speculative Optimizations Rd(a) Wr(c) Rd(x) Rd(b) Rd(a) Wr(a) Rd(a) Many tools are using Bloom filters Mark C. Jeffrey, MASc thesis defense 2

3. Bloom Filter & Bit-vector-based data structure [1970] offers fast set operations in exchange for some imprecision Recently used to compare memory accesses With unconventional practices: Intersection We show new practices are inefficient! (in theory and empirically) Mark C. Jeffrey, MASc thesis defense 3

4. Bloom Filters in Concurrency Tools We counter common intuition of tool designers System Year Application Bulk 2006 Hardware TM BulkSC 2007 Memory Consistency HARD 2007 Race Detection DeLorean 2008 Deterministic Race Replay SoftSig 2008 Code Analysis/Optimization/Debug RingSTM 2008 Software TM SigRace 2009 Race Detection ColorSafe 2010 Atomicity Violation InvalSTM 2010 Software TM AdapSig 2010 Software TM SvS 2011 Auto-protection of shared state Mark C. Jeffrey, MASc thesis defense 4

5. Tracking Address-Set Conflicts Mark C. Jeffrey, MASc thesis defense 5

6. Address-Sets Read Set: memory locations read RT1={a,b} T2 T1 T3 Rd(a) Rd(a) Rd(x) Wr(c) Rd(b) Rd(a) Wr(a) Rd(a) Write Set: memory locations written WT1={a} Mark C. Jeffrey, MASc thesis defense 6

7. Burden: Address-Set Conflicts Conflicts address accesses are dependent independence -> parallelism! address conflicts -> no parallelism T2 T1 T3 Rd(a) Rd(a) Rd(x) Wr(c) Rd(b) Rd(a) Wr(a) Rd(a) Conflict Detection requires read and write set comparison ie runtime address disambiguation Mark C. Jeffrey, MASc thesis defense 7

8. Lazy Conflict Detection Detect conflicts at the end of an epoch T1 T2 Rd(a)- -Rd(a) Wr(b)- Rd(c)- -Rd(b) R1={a,c} W1={b} = 0 ? W R 1 2 Test address-sets for null-intersections Mark C. Jeffrey, MASc thesis defense 8

9. Bloom Filters (BF) Mark C. Jeffrey, MASc thesis defense 9

10. Bloom Filter Background S ) BF( x x h() Bloom filter is a compact set representation bit vector - much smaller than address space Mark C. Jeffrey, MASc thesis defense 10

11. Bloom Filter Background y BF(S Query for an address, y ? ) y h() {Yes, No} Mark C. Jeffrey, MASc thesis defense 11

12. Bloom Filter False Positives (FPs) Encode a large address space into a bit-vector response to query is actually No or Maybe ? is y in False Positives when maybe is wrong x y Mark C. Jeffrey, MASc thesis defense 12

13. Partitioned Bloom Filter S ) BF( x x h1() h2() hk() Insert an address, x: k hash functions encode k bit indices to set Mark C. Jeffrey, MASc thesis defense 13

14. Partitioned Bloom Filter y BF(S ? ) Query for an address, y: y h1() h2() hk() Probability of False Positives is well understood {Maybe, No} Mark C. Jeffrey, MASc thesis defense 14

15. Unconventional Bloom Filter Null-Intersection Tests Mark C. Jeffrey, MASc thesis defense 15

16. Bloom Filter Null-Intersection Tests Lazy systems perform set intersections Two existing approaches: 1. build a Queue of Queries (QoQ) a1 ? a5 a4 a3 a2 ? 2. batch queries into distinct Bloom filter replace many queries with 1 intersection! Mark C. Jeffrey, MASc thesis defense 16

17. Partitioned BF Intersection = 0 ? S S Do two sets share any elements? 1 2 & {Disjoint, Maybe Overlap} Mark C. Jeffrey, MASc thesis defense 17

18. Unpartitioned BF Intersection = 0 ? S S Any asserted bits indicate set overlap 1 2 & {Disjoint, Maybe Overlap} Mark C. Jeffrey, MASc thesis defense 18

19. False Set-Overlap by BF Intersection Bloom filter was intended for fast Querying Recent systems use filter for Intersection Imprecision can produce False Set-Overlaps (FSO) No prior study of Bloom filter FSOs Our goal is to Understand and improve Bloom filter intersection Mark C. Jeffrey, MASc thesis defense 19

20. Research Questions When using BFs for testing null-intersection 1. How do BF Intersection and QoQ compare? theoretical study 2. Can we compromise? new Bloom filter design 3. Does theory work in practice? empirical study Mark C. Jeffrey, MASc thesis defense 20

21. Bloom Filters for Null-Intersection Tests 1. How do BF Intersection and QoQ compare? Mark C. Jeffrey, MASc thesis defense 21

22. Definitions bits m disjoint ,B A address access sets Mark C. Jeffrey, MASc thesis defense 22

23. Definitions h1() h2() m hk() bits partitions k disjoint ,B A address access sets Mark C. Jeffrey, MASc thesis defense 23

24. Theorem: Probability of FSO h1 h2 hk Unpartitioned BF Intersection p ( ) 2 k A B 1 1 1 = UBF m h1 h2 hk Partitioned BF Intersection ( 1 ) ( 1 ) k A B p k = PBF m Queue of BF Queries ( 1 ) ( 1 ) ( ) B b5 b4 b3 b2 b1 ? k = A 1 1 QoQ p k m Mark C. Jeffrey, MASc thesis defense 24

25. Theorem: Intersection vs QoQ If equivalent probability of FSO, i.e., p = p Partitione d QueueofQue ries ( ) then = m B QueueofQue m Partitione d ries i.e., intersection requires at least square root factor more space. Mark C. Jeffrey, MASc thesis defense 25

26. Bloom Filters for Null-Intersection Tests 2. Can we compromise? A new Bloom filter design Mark C. Jeffrey, MASc thesis defense 26

27. Batch-of-Bloom-filters (BoB) S ) BoB( x x hpre x h1 hk h1 hk h1 hk BF( ) b S BF( BF(S ) BF( ) ) 1 S 2 S = S S S b S 1 2 Mark C. Jeffrey, MASc thesis defense 27

28. BoB Intersection = 0 ? S S 1 2 & {Disjoint, Maybe Overlap} Mark C. Jeffrey, MASc thesis defense 28

29. BoB Rate of False Set-Overlap Rate of FSO BF(A) Better BF(B) Bit-vector Length (bits) BoB: compromise between QoQ and Intersect Mark C. Jeffrey, MASc thesis defense 29

30. Bloom Filters for Null-Intersection Tests 3. Does theory work in practice? Mark C. Jeffrey, MASc thesis defense 30

31. Methodology Augment RingSTM with alternate BF configs [Spear et al. SPAA 08] unpartitioned Bloom filter intersection Stress BF configurations using STAMP bench 8-core Intel Xeon with SSE2 ISA 32-bit Linux 2.6.32-5-686 Mark C. Jeffrey, MASc thesis defense 31

32. Performance Results: Labyrinth Execution Time Aborts 21% Speedup Better QoQ, BoB, part. intersect outperform baseline Mark C. Jeffrey, MASc thesis defense 32

33. Performance Results: Kmeans-low Execution Time Aborts >25% slowdown Better Querying overhead counteracts reduced aborts Mark C. Jeffrey, MASc thesis defense 33

34. Conclusion Mark C. Jeffrey, MASc thesis defense 34

35. Summary Conflict detection often applies Bloom filters for fast set operations: y S and S1 S2 unconventionally using BF intersect Our recommendations (from theory & practice) 1. strongly consider querying before intersection 2. in hardware, consider intersecting BoBs 3. build adaptive systems for application behaviors Mark C. Jeffrey, MASc thesis defense 35

36. Thesis Contributions 1. Pr[FSO] for BF null-intersection tests QoQ and part./unpart. intersection 2. Analytical comparisons of Pr[FSO] s 3. Design of, and FSO rates for BoB intersection 4. Empirical evaluation of BF null-intersect tests 5. Evaluation of SIMD instructions in BF use Questions? Mark C. Jeffrey, MASc thesis defense 36

37. BACKUP Mark C. Jeffrey, MASc thesis defense 37

38. Backup Pr[FP] for single query Pr[FSO] by intersection Pr[FSO] by queue of queries Optimal BF Configuration Mark C. Jeffrey, MASc thesis defense 38

39. Conventional Query FP Probability Insert one address into the filter. Probability a bit is not set in segment i: h1() hi() hk() m bits k 1 = = 1 1 unset p k 1 | m m k Back Mark C. Jeffrey, MASc thesis defense 39

40. Conventional Query FP Probability Insert all n addresses of a set A into the filter. Probability of bit assertion in segment i: h1() hi() hk() ) ( n = = n 1 unset p p k | n m 1 | unset ( ) n = = 1 1 1 p unset p k | | set n n m Back Mark C. Jeffrey, MASc thesis defense 40

41. Conventional Query FP Probability False positive occurs when the queried bit is set in all k segments h1() hi() hk() ( ) n = 1 1 p k ( 1 ) ( ) | set n m k n = = k 1 p p k false m n | set Back Mark C. Jeffrey, MASc thesis defense 41

42. Theorem: BF(A)BF(B) vs. BF(AB) A B BF(A) BF(B) & h1 h2 hk BF(A) BF(B) BF(A B) Theorem [Guo TKDE 10]: A BF( ) BF( Pr ( = ) 2 k A A B B A B 1 1 = ) BF( ) B A B m Back Mark C. Jeffrey, MASc thesis defense 42

43. FSO by Intersection Probability ( = ) 2 k A A B B A B 1 1 = Pr BF( ) BF( ) BF( ) A B A B m If we assume A and B are disjoint, then A B = 0 ( = ) 2 k A B 1 1 = = Pr BF( ) BF( ) 0 | 0 A B A B m False positive results when BF(A) BF(B) 0 ( ) 2 k A B 1 1 1 = = Pr BF( ) BF( ) 0 | 0 A B A B m Back Mark C. Jeffrey, MASc thesis defense 43

44. FSO by Intersection Probability ( ) 2 k A B 1 1 1 = = Pr BF( ) BF( ) 0 | 0 A B A B m h1 h2 hk Guo s model assumes a non-partitioned filter k hashes into the single partition Partitioned model assumes k partitions of size m/k each 1 hash into each partition A BF( ) BF( Pr Back h1 h2 hk ( 1 ) ( ) k A B k = = ) 0 | 0 1 B A B m Mark C. Jeffrey, MASc thesis defense 44

45. Queue of Queries FSO Probability Query-based set intersection: for each elem. bi in set B, query bi in BF(A) b5 b4 b3 b2 b1 ? FSO requires non-empty intersection at least one query falsely returns true model as a Geometric random variable Back Mark C. Jeffrey, MASc thesis defense 45

46. Queue of Queries FSO Probability ( = ) p k = Pr 1 X k p Recall Geometric pmf: No FSO when |B| queries before a success FSO when <|B| queries result in a query FP q X = Pr 0 = Pr p X B falseBQ 1 B = = q ( 1 ) ( ) ( ) k A B = = 1 1 , 1 p p k m Back Mark C. Jeffrey, MASc thesis defense 46

47. What size? How many hash functions? BLOOM FILTER CONFIGURATION Mark C. Jeffrey, MASc thesis defense 47

48. Optimizing FPs ( ) , , , f m k A B = = Pr | 0 false A B 2 static parameters, |A| and |B| 2 tunable parameters, m and k What values minimize false positives? how to configure a Bloom filter for set intersection m = 16 bits, k = 2 m = 16 bits, k = 4 m = 32 bits, k = 4 m = 32 bits, k = 8 Back Mark C. Jeffrey, MASc thesis defense 48

49. Optimizing FPs with respect to k Optimally, m bits => no false positives What k minimizes the FP probability? Use Calc 101! Note: Differentiate wrt k; determine k* giving [Bloom70, Mitzenmacher03] ( ) kn n 1 e k m m dp = 0 dk =k * k Back Mark C. Jeffrey, MASc thesis defense 49

50. Optimal k* to minimize FP probability h1 h2 hk Partitioned BF Intersection m * = k ln 2 2 k p falsePInt A B Queue of BF Queries b5 b4 b3 b2 b1 ? ( 1 ) m B * = k ln 2 1 2 k p falseBQ A Back Mark C. Jeffrey, MASc thesis defense 50

Load More ...