Support for concurrent cache instance

[ChaosD]

Support for concurrent cache instance

The current libCacheSim has limited support for concurrent simulation. It allows n threads to access n cache instances, but it does not permit n threads to read/write 1 cache instance. This limitation hinders researchers from evaluating the concurrent performance of their algorithms or systems. Therefore, we plan to add concurrent support to libCacheSim. The goal of this project is to implement thread-safe cache instances while maintaining the original performance of miss ratio and single-thread throughput.

The associated plan is moved to PR_8.

[1a1a11a]

Hi @ChaosD, this plan looks great! I like the concurrent hash table design. A few more thoughts.

1. You don't have to start from the current hash table, feel free to use cuckoo hash or anything you like.
2. But if you want to use the existing hash table, you can build the concurrent hash table as a layer above it.

[ChaosD]

@1a1a11a I'm glad that you agree with my plan. Considering your suggests, here is my thoughts:

1. Docking libcuckoo to libCacheSim and implementing concurrent hashtable based on existing design involve the similar code volume. I'll implement both of the two schemes, and make simple module tests for their concurrent throughput. I plan to spend 2-3 days on these tasks.

2. The implementation of the two concurrent hashtable will be independent with existing implementation. It means that there will be 4 optional types of hashtable: chained, chained_V2, cuckoo, and concurrent_chained (based on the code of chained_V2).

[1a1a11a]

Sounds great! Let me know if you need anything from me. :)

[ChaosD]

Hi @1a1a11a , to avoid potentially polluting the original code, could you please create a branch to merge my PR? (Although all the cachesim commands I tested are functioning well. )

[1a1a11a]

@ChaosD Sure, I have added a new branch called concurrent :)

[1a1a11a]

I just saw the results you added, very impressive work in a short amount of time!
Two very minor comments,

1. can you add the hash power or hash table size to help understand the numbers better?
2. it would be good to compare with skewed workloads in multi-threaded benchmark since most of the cache traces will be skewed. Feel free to ignore if this is too much work.