Skip to content

Latest commit

 

History

History
55 lines (41 loc) · 2.59 KB

Design.md

File metadata and controls

55 lines (41 loc) · 2.59 KB
Raw

Design

The paper requires three main functionalities to be used

  1. Binary bit calculation
  2. Look-up Table set bit calculation
  3. Cachegrid tool for calculating cache misses.

For comparison we have to implement:

  1. Look-up Table.
  2. Split-Look up.
  3. Bit-Counting Algorithm.

Initial

We will take input of two binary numbers .
XOR Operation will be performed on them and result will be taken
The result will be fed to one of the algorithm at a time
The cache misses will be calculated using cache grid tool by intel

look-up Table method

Look-up table is a tabular representation of corresponding values associated to a character i.e. we can lookup the corresponding number of bits in binary number.
It takes O(1) time for counting number bits in a binary number.The Look up table stores all the values of number of set bits in an integer from 0 to k.
So, when whenever we are implementing k bits of length we have a table with k rows.Whenever an input is given the number of bits is calculated and using this we calculate the hamming distance.

Split- Look-up Table:

We split the look up table into divisions and use the look up table.

Bit counting:

In,Bit counting you calculate the number of bits using Magic binary numbers.
We will have to implement the 12 cycle XOR operation algorithm for getting the desired results.

We have to use cachegrid tool by intel to get the results of cache misses .
The reulting graph will be verified only for intel processors due to lack of other processor Computers.

Finally, We will be proving that bit counting algorithm is one of the best methods for calculating hamming distance.

Expected results

The following result is expected from the implementation of the paper:

  • Cache misses in bit-count will have to be less.
  • Lookup-table should have a lot of potential cache misses and that should grow exponentially.
  • Look-up table should run in O(n).
  • bit count should run in O(Log n) time complexity.
  • Split look up table method should have time complexity of O(256) which is constant and the potential cache misses should be greater than bit counting Algorithm and less than Lookup table.
Expected graphs

Following are the expected graphs from the implementation:
Image 1 Image 2

  • Note:
  • Red lines represent the look-up table method;
  • Green lines represent the split look-up table method
  • blue lines represent the bit-count method