Kiwi Scientific Acceleration: Bloom Filter Example

A Bloom Filter is a well-known, compact way of storing a set where the membership test may have the occasional false positive.

Source Code in C#

A paramatric Bloom Filter is easy to write in C#, although one might want to put a little more care into the hash functions than we did here. Nonetheless, it seemingly works well enough.

class AcceleratedBloomFilter
{

  uint no_banks, banksize;

  uint [,] banks; // Use 32-bit words as bit vectors.

  public AcceleratedBloomFilter(uint nb, uint bs) // Constructor
  { no_banks = nb;
    banksize = bs;
    banks = new uint [nb, (bs+31)/32];
  }

  uint hasher(uint bn, uint key) // A set of hash functions.
  { return ((((bn+11111)^key)<<0)+
	    (((bn+54321)^key)<<5)+
	    (((bn+99887)^key)<<11)+
	    (((bn+55555)^key)<<16)
	    ) % banksize;
  }

 public void insert(uint key)
  {
    for (uint i=0; i<no_banks;i++)
      { uint h = hasher(i, key);
        uint j =  h / 32;
	// Console.WriteLine("{0} {1}", h, j);
	uint k = (uint)(1 << (int)(h % 32));
        banks[i, j] |= k;
      }
  }

 public bool probe(uint key)
  {
    bool v = true;
    for (uint i=0; i<no_banks;i++)
      { uint h = hasher(i, key);
        uint j =  h / 32;
        uint k = (uint)(1 << (int)(h % 32));
        v &= (banks[i, j] & k) != 0; 
        if (!v) break;
      }
    return v;
  }
}

A Simple Test Bench Proves the Point

class TestBench
{
  [Kiwi.OutputBitPort("done")] static bool done = false;

  [Kiwi.HardwareEntryPoint()]
  public static void Main()
  {
    Console.WriteLine("AcceleratedBloomFilter Demo Start");
    var abf = new AcceleratedBloomFilter(3, 512);
    int false_pos = 0, false_neg = 0, trials = 0;
    for (int pass=0;pass<2;pass++)
      {	for (int jojo=3;jojo<123456789*3;jojo += 3) 
	  { Kiwi.NoUnroll(); 
	    uint key = (uint) jojo;
	    bool oracle = (key & 33) > 0;
	    bool result = false;
	    if (pass == 0)
	      { if (oracle) abf.insert(key);
		result = oracle;
	      }
	    else if (pass == 1)
	      { trials += 1;
		result = abf.probe(key);		
		if (oracle && !result)
		  {
		    Console.WriteLine("False negative on {0}", key);
		    false_neg += 1;
		  }
		else if (!oracle && result)
		  {
		    Console.WriteLine("False positive on {0}", key);
		    false_pos += 1;
		  }
	      }
	    if (verbose) Console.WriteLine("  Pass {0} jojo={1}  test result={2}", pass, jojo, result); 
	  }  
      }  
    Console.WriteLine(" Trials ={0}  False_pos={1} False_neg={2}.", trials, false_pos, false_neg);
    Console.WriteLine(" Test AcceleratedBloomFilter finished.");
    done = true;
    Kiwi.Pause();
  }
}

Run under Mono

A million inserts and probes takes about 130ms on mono on my laptop (i-3 Fedora20).

  MONO_PATH=/home/djg11/d320/hprls/kiwipro/kiwic/distro/support:. time mono AcceleratedBloomFilters.exe
  AcceleratedBloomFilter Demo Start
  Done Reset
  Trials =999999  False_pos=0 False_neg=0.
  Test AcceleratedBloomFilter finished.
  0.13user 0.00system 0:00.14elapsed 96%CPU (0avgtext+0avgdata 15196maxresident)k
  0inputs+0outputs (0major+1017minor)pagefaults 0swaps

Kiwi Compilation

A simple, singled-threaded Kiwi Compilation with a time/space guiding metric of

Generated RTL file AcceleratedBloomFilters.v.

Results

The design compiles and runs well enough on Mono and FPGA. Discussion TBC ...

Conclusions

Feb 2017.               UP.