search

1a1a11a / libCacheSim

a high performance library for building cache simulators
GNU General Public License v3.0
142 stars 30 forks source link

Support Belady on traces without future information #62

Open 1a1a11a opened 4 months ago

1a1a11a commented 4 months ago

The current implementation of Belady's algorithm requires an oracleGeneral trace format, which has future access information. This design was chosen to reduce the memory requirement because we need to allocate an array of size N (number of requests) to store future access time. However, requiring the oracleGeneral trace makes ad-hoc experiments hard. It would be good to support Belady's MIN algorithm for non oracleGeneral traces, e.g., txt trace.

zztaki commented 4 months ago

Nice feature!

LRB Simulation can serve as a demonstration. It converts the non-oracle trace into an oracle trace and then executes the belady's MIN. :) https://github.com/sunnyszy/lrb/blob/9e8b4423383c01c4528deb447f152f0437a37c3a/src/caches/annotate.cpp#L19

1a1a11a commented 4 months ago

Yeah, this is one option.

Currently there is a traceConv tool that can perform the conversion from a trace to oracleGeneral format. I thought this is a better approach if one wants to run the same trace several times. Using the oracleGeneral trace often speeds up simulation by a few times (compared to txt trace), and also significantly reduces memory consumption.

However, the separate conversion process is not documented. I probably need to 1. add the description in the code and documentation and 2. allow people to run ad-hoc experiments with Belady without converting the trace.

Let me know if you have any thoughts and ideas. :)