benblack769 / SD3-implementation

Implementation of a efficient dynamic parallelism detector for my senior thesis
1 stars 0 forks source link

Efficient bitset pairwise conflict checking #4

Open benblack769 opened 6 years ago

benblack769 commented 6 years ago

The idea is that instead of compressing using strides, we compress data using bits

In a loop, say we have n instructions. Then we have a bitset b_i for each instruction.

We have bitset c that we are checking for conflicts with the n instructions.

The idea is that you maintain a particular tree structure that you use to do this conflict checking easily.

Each instruction is a leaf. Each node is the bitwise or of the two leaves.

When adding a new leaf, you just bitwise or it with every node above it.

When checking the root of a subtree for conflicts, if there are no conflicts, then there won't be conflicts of any of the leaves either. If there are conflicts, you can just compare the conflicts with the left and right nodes of the tree.

benblack769 commented 6 years ago

This is now implemented.

Code in non-main branches.

benblack769 commented 6 years ago

Two optimizations on this idea:

  1. Only merge up information up the tree when necessary, allowing O(n) time instead of O(n * log(n)) time.
  2. Don't every merge up information if we aren't going to need it (i.e., we have already detected conflicts in earlier iterations, so we don't need them).