wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Memory Dependencies Tracking
        
(Message started by: Barukh on Jun 19^th, 2014, 9:14am)

Title: Memory Dependencies Tracking
Post by Barukh on Jun 19^th, 2014, 9:14am

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.