Support Belady on traces without future information

[1a1a11a]

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]

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]

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. :)