Author |
Topic: Memory Dependencies Tracking (Read 1360 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Memory Dependencies Tracking
« on: Jun 19th, 2014, 9:14am » |
 Quote  Modify
|
Imagine that you want to track all the memory stores/loads performed by a specific program, and connect every load to the latest store that wrote to the same address.
Assume that stores and loads are identified by their IPs. Assume also that stores and loads follow X86 semantics, that is their sizes are powers of 2, and there are no alignment restrictions. So, a single load may be dependent on multiple stores.
Could you propose efficient algorithms (in both time and/or memory) to handle this?
A simple algorithm would use a hash table, where every byte of a single store is used as a key, and value is store IP. Then, load will make multiple accesses to hash – for every load byte.
The question is: are there more efficient algorithms?
For instance, consider the case where all stores/loads are 8-byte wide, and all are aligned to 8 bytes. For this particular case, the above algorithm may be sped up by 8X in both time and space.
|
|
 IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print