文档介绍：Understanding Bloom Filter Intersection for Lazy Address-Set Disambiguation Mark Jeffrey and J. Gregory Steffan ECE, University of Toronto June 6, 2011 Mark Jeffrey and Greg Steffan, U of Toronto Parallel Programming is Hard 2T 1Rd(a) Rd(b) Wr (a) T 2Rd(a) Wr (c) Rd(a) T 3Rd(x) Rd(a) Tools offload some burden of managing data accesses: – Memory Race Replay – Atomicity Violation Survival – Transactional Memory – Speculative Optimizations Many tools are using Bloom filters Mark Jeffrey and Greg Steffan, U of Toronto 3 Bloom Filter ? Bit-vector-based data structure [1970] – offers fast set operations – in exchange for some imprecision ? Recently used pare memory accesses ? With unconventional practices: Intersection ? We show new practices are inefficient! (in theory) 3& Mark Jeffrey and Greg Steffan, U of Toronto 4 Bloom Filters in Concurrency Tools 4 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 We provide new theory to guide tool designers! Mark Jeffrey and Greg Steffan, U of Toronto 5 Tracking Address-Set Conflicts 5 Mark Jeffrey and Greg Steffan, U of Toronto Address-Sets 6T 1Rd(a) Rd(b) Wr (a) T 2Rd(a) Wr (c) Rd(a) T 3Rd(x) Rd(a) Read Set: ? memory locations read ?R T1= { , } Write Set: ? memory locations written ?W T1={a} ab Mark Jeffrey and Greg Steffan, U of Toronto 7 Burden: Address-Set Conflicts 7T 1Rd(a) Rd(b) Wr (a) T 2Rd(a) Wr (c) Rd(a) T 3Rd(x) Rd(a) Conflicts – address accesses are dependent – independence -> parallelism! – address conflicts -> no parallelism Conflict Detection requires – read and write parison – runtime address disambiguation Mark Jeffrey and Greg Steffan, U of Toronto 8 Conflict Detection – When? ? E