Skip to content

todo.md

Latest commit

 

History

History
325 lines (242 loc) · 11.2 KB

todo.md

File metadata and controls

325 lines (242 loc) · 11.2 KB
Raw

Connect the results.

-- Urgent --

  • Workload specific results

  • FPR section

  • New SBBF implementation

  • Run it on GCloud machine

--- Old ---

  • [dist] Put % of practical access within LLC cache in the right top corner in mem_access.pdf

  • [stats] What's the L3 lantecy for the office machine.

Future

Untried, or open questions.

  • NT Reads in non cache parts for full-sort, partial-sort etc. [exp] NTI reads on non-cached portion, even with the PartialSort or other things. Does that help? This will add a branch, but I believe a branch predictor may hlep.

    • I could also kind of hard code, predict the bucket that would be out of cache, and only do NTI reads for those.

  • [exp] See if we can merge partialSort with minjust sort? That might be cool.

  • Why does fullsort have less LLC misses than partial sort? Dave thinks it's LRU effect.

Future notes

  • Positive queries are bad for our current implementation. Especially because the higher numbers come at the end of it. Only if we could reverse the probe order for positive queries.

OLD

Dec 20 - All the stuff collected at once

--- Next steps --- [DONE]

  • Run the experiments on the cloud. Get a newish machine and roll with it.

[DONE]

  • Cache partitioning on range mapping.

[DONE] --- Paper ---

  • Write down background section. For now you can just add the references there.

  • Write down more about the design of the paper.

  • Make more text for the evaluation section.

  • What is the take away for someone reading your paper?

  • What should be the title of your paper?

  • What should be the name of your technique? Iterate, think.

[DONE]

  • Start writing your thesis as well. Things are going to get hectic very soon. The more you delay it, the less feedback you get. The thesis should be with your reader and Dave by Mid November :)

  • Start designing a presentation for Early December.

-- URGENT -- [DONE]

  • [exp] Actual cache partition now.

[DONE]

  • [stats] L2 misses are a RAW events on the hardware processor.

[DONE]

  • [stats] L2 evictions, L2 cache-misses

--- [done] Here are some todos

  1. Try range mapping with 64-bit results
  • 64 bits it is
  1. cbf without non temporal reads
  • Faster than no-sort :)
  • But slower than full sort,
    • Why that might be, see assembly, see probes happening out of the thingie
  1. low descripancy filter
    • Force all the upper bits to be zero.

---- BIG QUESTION TO DAVE ---- [DONE] For the fully sorted version, why is the access style negative exponential? Shouldn't it access some of the lower bits equally? Is it because of the smile?

--- What are the most important things to answer? ------

[DONE]

  1. Analyse cache partition implementation and understand what is going on.
  • We know the answer for 128MB. It's the uneven distribution that is creating the thingy. see the cbf_mem_access(14).pdf on downloads folder

[DONE] 2. Answer and experiement with k-m questions.

[DONE]

  • Run Compressed LUT and non-compressed LUT avx2 again. for longer.

Order of things to do:

[DONE]

  1. Cache partitioning and compare

  2. NT Reads in non cache parts for full-sort, partial-sort etc.

  • Important is cache rates.

[DONE] - ISSUES WITH HUGE PAGES == Observation; Cached partitioning is substantially slower

  1. What is the stats? FP, founds, Number of probes?
  2. Sanity check:
  • mod and masks are reasonable.
  • have sanity checks. If previous hash is same as mine, panic, or print something
  • COnfirm MBITS and MBYTES are corect.
    • Confirmed
  • Probes per hash is different.
  • Total probes is higher.
  • Any other silly bugs.
  1. assert that hashes are really right, assert anything that could be slightly not right.
  2. memory distribution in first half and second half.
  3. After this look into the code generation. (Hopefully nothing wrong there)

[DONE] 3. following k-m questions.

[DONE]

  • k-m smile with range mapping, does it exist?
    • Range mapping has a smile with non-prime small multiplier

[DONE]

  • k-m make it low descirpancy sequence. top 3 bits of b to 011 measure false positive

[DONE]

  • lemire with small b, how does it wok on the distribution?

Oct 29 updates

  • Use the understanding from Dave about k-m, and apply it to observable results.
    • Why some LLC misses are lower than others? For each class
      • Unanswered yet
    • Why Some things may run faster than others?
      • They do not
    • Does no-sort has an unobservable smile? compare with a straight line?
      • or take "derivative" and check.
      • NO SMILE IN NO SORT

Oct 21 Updates

  • [exp] Pass the cache partition values as runtime constants instead of compile time

    • I have results for those too.

  • All the k-m mistery is solved: See emails with Dave.

    • k-m back to board, math the distribution better.
    • k-m generate all 8 and plot them.
      • you would expect PDF to be flat
      • Comapre the CDF of the two.
    • k-m always does modulo prime, the real world doesn't

  • I added as little AVX2 in nosort as possible. Now the results are more reasonable for smaller caches. I learned the AVX needed to be data dependent. I learned there needs to be one load.

  • [small] Invenstigate and find answer to why on smaller bloom filters PartialSort runs faster than NoSort even when it is doing more no-op work.
    • We know it's because of the CPU running at higher frequency than the NoSort.
    • We want to try to control that.
  • [small] Run the NoSort with tiny bit more of AVX2 to see if it clocks up and the weird effect we see with smaller Blooms running faster with more calculations go away.

Oct 10 updates

  • Analyze the performance with prime and non-prime hashes for smiley

    • results/office1/prime_non_prime.jsonl

  • For the small, just permute and compare the last 4. and see if it clocks up.

    • You could do what the partial sort does, but just a round of it. Basically compare it with a alrge number and then see if what happens.
    • NoSort is now PartialSort with INF / 4 partition point. This clocks it up appropriately for smaller values.
      • Though there are still variations, run to run AND PartialSort with 16MB really does well here.
      • Is it reasonable to not show the 16MB partition for smaller values at all?

  • Is there a valley(smile) in partial sorts in mem_access.pdf?

    • There is a valley(smile). Why that might be?

    • Could there be a bug in the plotting script?

      • Feed it hashes we generate, and maybe something random, and see if that has any changes? Do really fast ChaCha8, and see what you see.
      • The smile really interesting.
      • After Dave's investigation, it turned out a feature of Kirsch & Mitzenmatcher's hashing scheme. If you use different multiplier the smile vanishes. Smile multipliers = [0, 1, 2, 3, 4, 5, 6, 7] New proposal (all primes) = [11, 17, 29, 37, 53, 67, 89, 139]

  • Running things at constant frequency of 3.6GHz.

    • Even when I fix the frequency at 4GHz

Oct 8 updates

  • [bench] Add bench for MinJustSort and PartialSort with 19MB, that would help answer [exp] question below

    • Following means 16MB and 19MB has no better or worse performance.
    • MinJustSort stats already existed, added it to the paper.
      hash_sort_and_limit/CustomFast<PartialSortLut2<0, 0, {16 * MBITS}>>
                        time:   [2.2826 ns 2.2860 ns 2.2897 ns]
  Found 13 outliers among 200 measurements (6.50%)
    5 (2.50%) low mild
    4 (2.00%) high mild
    4 (2.00%) high severe
  hash_sort_and_limit/CustomFast<PartialSortLut2<0, 0, {19 * MBITS}>>
                          time:   [2.2733 ns 2.2769 ns 2.2804 ns]
  Found 21 outliers among 200 measurements (10.50%)
    8 (4.00%) low mild
    4 (2.00%) high mild
    9 (4.50%) high severe

  • [exp] Look at the generated assembly code for 16MB vs 20MB?

    • This is to answer if 16MB is faster only because of better generated code?
    • see above

  • [dist] Change seed to generate mem_access.pdf and answer why there might a valley (smiley) in the partial sort line.

    • Even with a different seed, the smiley exist. This must be something fundamental to the hashing or modulo, or sorting, or something.

  • [small] Try with more number of queries on smaller bloom to see if it eventually clocks up the requency enough for even small bloom filters.

    • No it doesn't. The no-sort still runs at 3.6GHz when the governance is performance.
    • Intrestingly when the hash function is 'mod' the CPU runs at 4.2Ghz for the smaller blooms.
    • Also interestingly, when I add atleast 1 permute, 2 cmp, 1 blend to no-sort that also runs at 4.2 Ghz. I might create that as another option and run it against no-sort?

Oct 1 updates

Connect the results. Dave is exceptionally good at this. For example, He connected the sorting time results with what we are observing with the time really well. I handn't thought that far, or that clearly. Lots to learn!

  • Plot memory access probabilities -> mem distribution, for every sorting algo. something like bin_sort

    • look at mem_access.pdf

  • Look at Raw event stuff to figure out how to do it.

    • This is done!. Look at the history of perf commands, should be simple do.

  • Fast vs CustomFast, not useful anymore.

    • Confirm this with micro benchmarking.
    • Microbench tells me this is not true. CustomFast is still fast.
    • Same for CustomRangeMapping

--- next step ---

  • Create a benchmark, table, on the sort time statistics.
    • This is done.

Sept observations

---- Undiscussed observations ----

  • AVX512 is not faster/slower than AVX2 for our usecase.
  • long_run_1 == re read this and decide what do you want to discuss
    • 16 -> 17 -> 18 -> 19 -> 20, also there are experiments for 15 and 14.
  • LUT vs full computation using pext and pdep, (see where is this part of)
    • LUT is faster than full computation,
    • That is strange, Let me compute and benchmark the sorting.
    • I think it's Cache, LUT is highly cacheable, 8KB memory.
  • LUT vs Compressed LUT,
    • Didn't improve the performance any. Nor the cache misses (confirmed)

-- Hypothesis --

When you run avx2 or avx512 instructions, the CPU works at higher frequency compared to when you don't do it! So the time taken is not the right way to measure anything! Let's start measuring cycles :)

This hypothesis is true to some extent. We ended up changing the CPU power mode sudo cpupower frequency-set -g performance

Though above still didn't help for the small cases I was looking at.

Next step might be turning off the turbo-boost.

-> Dave suggests we do not count the cycles, since cycles hides the bahviour of cache. The CPU could have slowed down while the cache was being populated, so measuring real-time is what we should lean towards.

-- Observation --

  • Confirm input and output for the partial sort, why is partial sort any better than no sort on small sizes?

    • When I put asserts before and after the partial sort, and the assert fires as soon as I am above 16MB in the bloom size. So Partial is indeed a no-op.

  • swap orders of measures. See if the order makes any difference for the no-sort and partial sort. If anything, the partial sort should be slower than the no sort for smaller sizes than the partition point.

    • I now randomly decide order of the variant to run every "sweep", so nosort is not the first one to run any time.