Bloom Filter Intersection for Address Set Disambiguation

Slide Note

Bloom filters are utilized in parallel programming for efficient address set disambiguation, aiding tools in managing data accesses and detecting conflicts to enhance system performance. This study by Mark Jeffrey and J. Gregory Steffan from the University of Toronto delves into the efficiency and challenges of using Bloom filters in concurrency tools.

nahlanim 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.

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

Understanding Bloom Filter Intersection for Lazy Address-Set Disambiguation Mark Jeffrey and J. Gregory Steffan ECE, University of Toronto June 6, 2011

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 Jeffrey and Greg Steffan, U of Toronto 2

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) Mark Jeffrey and Greg Steffan, U of Toronto 3

Bloom Filters in Concurrency Tools We provide new theory to guide 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 FastPath 2009 Software TM (or TLS) SigRace 2009 Race Detection ColorSafe 2010 Atomicity Violation InvalSTM 2010 Software TM AdapSig 2010 Software TM Mark Jeffrey and Greg Steffan, U of Toronto 4

Tracking Address-Set Conflicts Mark Jeffrey and Greg Steffan, U of Toronto 5

Address-Sets Read Set: memory locations read RT1={ , } T2 T1 a b 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 Jeffrey and Greg Steffan, U of Toronto 6

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 runtime address disambiguation Mark Jeffrey and Greg Steffan, U of Toronto 7

Conflict Detection When? Eager Detect conflicts at the time of memory access Thread1 Thread2 -Rd(a) Wr b OK? Wr(b)- Lazy Detect conflicts at the end of an arbitrary epoch Thread1 Rd(a)- Thread2 -Rd(a) -Rd(b) Wr(b)- Rd(c)- {a,b,c} OK? Mark Jeffrey and Greg Steffan, U of Toronto 8

Conflict Detection When? Eager = Set Membership Query for that single address in the access sets Thread1 Thread2 -Rd(a) Wr(b)- b ? R 2 Lazy = Set Overlap Compare access sets for non-empty intersections Thread1 Rd(a)- Thread2 ? When determines the set operation -Rd(a) -Rd(b) W R Wr(b)- 1 2 Rd(c)- Mark Jeffrey and Greg Steffan, U of Toronto 9

Bloom Filters (BF) Mark Jeffrey and Greg Steffan, U of Toronto 10

Bloom Filter Background S ) BF( x x = [x31, ,x3,x2,x1,x0] h() [x4,x3,x2,x1] Bloom filter is a compact set representation Bit vector - much smaller than address space Mark Jeffrey and Greg Steffan, U of Toronto 11

Bloom Filter Background y BF(S Query for an address, y ? ) y h() [y4,y3,y2,y1] {Yes, No} Mark Jeffrey and Greg Steffan, U of Toronto 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 Jeffrey and Greg Steffan, U of Toronto 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 Jeffrey and Greg Steffan, U of Toronto 14

Partitioned Bloom Filter y BF(S ? ) Query for an address, y: y h1() h2() hk() {Maybe, No} Probability of False Positives is well understood Mark Jeffrey and Greg Steffan, U of Toronto 15

Unconventional Practices for Bloom Filters Mark Jeffrey and Greg Steffan, U of Toronto 16

Bloom Filter for Set Overlaps Lazy systems perform set intersections Two common 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 Jeffrey and Greg Steffan, U of Toronto 17

Partitioned BF Intersection = 0 ? S S Do two sets share any elements? 1 2 & {Disjoint, Maybe Not} Mark Jeffrey and Greg Steffan, U of Toronto 18

Unpartitioned BF Intersection = 0 ? S S Any asserted bits indicate set overlap 1 2 & {Disjoint, Maybe Not} Mark Jeffrey and Greg Steffan, U of Toronto 19

False Set Overlap with BF Intersection Bloom filter was intended for fast Querying Recent systems use filter for Intersection Imprecision can produce False Set Overlaps (FSO) Limited study of Bloom filter intersection Our goal is to Demystify Bloom filter Intersection Mark Jeffrey and Greg Steffan, U of Toronto 20

Important Questions When using BFs for address Set Overlaps: 1. how do BF Intersection and QoQ compare? Empirical Study 2. what is the exact FSO probability? Theoretical Study 3. what are the theoretical implications? Mark Jeffrey and Greg Steffan, U of Toronto 21

Bloom Filters for Set Overlap 1. How do BF Intersection and QoQ compare? Mark Jeffrey and Greg Steffan, U of Toronto 22

Methodology For many trials: 1. Create sets A = {a1,a2, ,an} B = {b1,b2, ,bm} - A and B are disjoint 2. // Measure Intersects with FSOs 3. count # trials with a FSO // Measure Queues of Queries with FSOs 4. For each bi in B: is bi B A count # trials with at least one FP Mark Jeffrey and Greg Steffan, U of Toronto 23

Queue of Queries vs. Intersection FSO Rate for (A B=0?), |A|=|B|= 32 1 For equivalent FSO rate, Intersection requires 4x more bits! 0.8 False Set Overlap Rate 0.6 QoQ into Part. BF 4x 0.4 Part. Intersect Unpart. Intersect 0.2 Better 4x4x 0 32 64 128 256 512 1k 2k 4k 8k 16k 32k 64k 128k Bloom filter Length (bits) Mark Jeffrey and Greg Steffan, U of Toronto 24

Queue of Queries vs. Intersection FSO Rate for (A B=0?), |A|=|B|= 64 1 Doubling address set from 32 to 64 => Doubling size from 4x to 8x 0.8 False Set Overlap Rate 0.6 QoQ into Part. BF 0.4 Part. Intersect Unpart. Intersect 8x 0.2 Better 8x 0 32 64 128 256 512 1k 2k 4k 8k 16k 32k 64k 128k Bloom filter Length (bits) Mark Jeffrey and Greg Steffan, U of Toronto 25

Empirical Study Summary i. BF Intersection requires > bits for == FSO rate ii. Space overhead increases with set size iii. Partitioned intersect is better than Unpartitioned Mark Jeffrey and Greg Steffan, U of Toronto 26

Bloom Filters for Set Overlap 2. What is the exact probability of False Set Overlap (FSO)? Mark Jeffrey and Greg Steffan, U of Toronto 27

Definitions bits m disjoint ,B A address access sets Mark Jeffrey and Greg Steffan, U of Toronto 28

Definitions h1() h2() m hk() bits m partitions of length bits k k disjoint ,B A address access sets Mark Jeffrey and Greg Steffan, U of Toronto 29

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 Jeffrey and Greg Steffan, U of Toronto 30

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 et al. TKDE 10]: B A ) BF( ) BF( Pr ( = ) 2 k A A B B A B 1 1 = BF( ) A B m Mark Jeffrey and Greg Steffan, U of Toronto 31

Bloom filters for Set Overlap 3. What are the Theoretical Implications? Mark Jeffrey and Greg Steffan, U of Toronto 32

False Conflicts: QoQ vs. Intersections Pr[FSO] for A B=0? , k = 2 1 0.8 Pr[FSO] 0.6 QoQ into Partitioned 0.4 Partitioned Intersect Better 0.2 Unpartitioned Intersect 0 32 128 512 2k 8k 32k 128k Bloom filter Length (bits) For any length m, and k > 1 hash functions, Queue of Queries gives fewer false conflicts p p Unpartitio p QueueofQue Partitioned intersection improves on Unpartitioned ries Partitione d ned Mark Jeffrey and Greg Steffan, U of Toronto 33

Space: QoQ vs. Intersection Pr[FSO] for A B=0? , k = 2 1 0.8 Pr[FSO] 0.6 QoQ into Partitioned 0.4 Partitioned Intersect 0.2 0 32 128 512 2k 8k 32k 128k Bloom filter Length (bits) For equivalent Pr[FSO], when mPartitioned |A||B|, k > 1, m + 1 1 1 B k QueueofQue m k Partitione d ries Mark Jeffrey and Greg Steffan, U of Toronto 34

Space: QoQ vs. Intersection Pr[FSO] for A B=0? , k = 2 1 0.8 ( ) Pr[FSO] 0.6 B QoQ into Partitioned 0.4 Partitioned Intersect 0.2 0 32 128 512 2k 8k 32k 128k Bloom filter Length (bits) ( ) For equivalent Pr[FSO], when mPartitioned |A||B|, k > 1, intersection requires at least square root factor more space. = m B QueueofQue m Partitione d ries Mark Jeffrey and Greg Steffan, U of Toronto 35

Single Hash: QoQ vs. Intersection Pr[FSO] for A B=0? , k = 1 1 0.8 Pr[FSO] 0.6 QoQ into Partitioned 0.4 Intersection Better 0.2 0 32 128 512 2k 8k 32k 128k Bloom filter Length (bits) For a single hash function, k = 1, = p p exploit the speed of intersection instead of queries! QueueofQue ries Intersecti on Mark Jeffrey and Greg Steffan, U of Toronto 36

Conclusion Mark Jeffrey and Greg Steffan, U of Toronto 37

Summary Conflict detection often applies Bloom filters for fast set operations: y S and S1 S2 Many new systems use BF intersect Our recommendations (in order of preference) 1. strongly consider querying before intersection 2. intersect partitioned Bloom filters 3. if single hash is required, exploit intersection! Mark Jeffrey and Greg Steffan, U of Toronto 38

Current Work: Implementations Analyze the effects of partitioning in RingSTM Analyze the effects of QoQ in RingSTM Develop a compromise in space and time Reduce sqrt space overhead of BF Intersect Reduce linear time complexity of Queue of Query Mark Jeffrey and Greg Steffan, U of Toronto 39