wu :: forums
« wu :: forums - Memory Dependencies Tracking »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 10:10pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: william wu, Grimbal, Icarus, SMQ, ThudnBlunder, Eigenray, towr)
   Memory Dependencies Tracking
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Memory Dependencies Tracking  (Read 1352 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Memory Dependencies Tracking  
« on: Jun 19th, 2014, 9:14am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board