Dinero IV Trace Generator using Javascript

on Reading Time: 3 minutes

It’s quite surprising that around the time when this blog post was written, I couldn’t find a Dinero IV Trace Generator online. Dinero IV is a cache simulator software that had been developed around 20 years ago. To generate traces, you just have to do simple bit manipulations. Ironically, today, our modern browsers have the power to do this.

Consider an 16KB direct mapped cache, with a 32 byte block size. The first trace generated below, will insert to each cache set only once. Therefore, in the first round you will have all compulsory misses and the miss rate would be 100%. In the next rounds, it will always be a hit. Therefore, after two rounds, the miss rate would be 50%.

After a quick calculation, we can figure out that the number of sets is 512 ( = 16 * (2 ** 10) / 32). We need 9 bits for the index. The block offset if 5 bits.  If we can do a bit manipulation and figure out 512 addresses with unique set bits, we can fulfill the above requirement. The following javascript code just achieves that.

/** properties **/
let cacheSize = 8 * (2 ** 10);
let blockSize = 32;
let associativity = 1;
let numOfSets = cacheSize / (blockSize * associativity);
let numIndexBits = Math.log2(numOfSets);
let numBlockOffset = Math.log2(blockSize);
let label = [0, 1, 2];
let outputString = ''
/** generate random number **/
let startAddress = Math.floor(Math.random() * 10000000);
let binStartAddress = parseInt(startAddress, 2);

for (let i = 0; i < numOfSets; i ++) {
   bits = [];
   for (let j = 0; j < numIndexBits; j++) {
      if (i & 1 << j) { 
          bits.push(1); 
      } else { 
          bits.push(0); 
      } 
    } 
    number = startAddress; 
    bits.forEach((value, index) => {
        mask = 1 << (index + numBlockOffset);
        number = number & ~mask | value << (index + numBlockOffset) & mask;
    });
   outputString = outputString.concat(label[Math.floor(Math.random() * label.length)] + ' ' + parseInt(number, 16) + '\n')
}
console.log(outputString);

  What if you don’t know how to run the above code? If you’re on a Safari Browser, just press ⌥ + ⌘ + I. This will open up the developer console. Just paste the code above and hit enter. Results will be printed.

Another question would be given the associativity to be 2 (2-way set set associative cache), generate an address stream that would have 3 unique addresses per each set and only 3 misses per each set.

The first step would be to identify access patterns; Consider three unique address: a, b and c. If the cache follows an LRU (Least Recently Used) policy, the following patters per each set would fulfill our requirement.

`[[a, b, c, a, b], [a, b, c, c, b], [a, b, a, b, c] …..]`

Now all we need to do is generate an address stream that would map to each set (each address in each set). Then we can vary the tag bits so that multiple addresses would map in to the same cache. If we assumed that our cache properties are the same, the number of sets would now be 256 ( = 16 * (2 ** 10) / (32 * 2)). we will have 8 index bits, 5 block offset bits.

Since we only have three unique addresses, we need to vary the bits in the tag to form 0, 1, 2. Essentially, we are modifying the 14th and 15th bit from the end of the address and the addresses would be following one of the access patterns chosen at random from the above access patterns. For example,

00 00000000 00000. <— Maps to set 0 (index bits 0) (14th and 15th bits form 0)
01 00000000 00000 <— Maps to set 0 (index bits 0) (14th and 15th bits form 1)
10 00000000 00000 <— Maps to set 0 (index bits 0) (14th and 15th bits form 2)
00 00000000 00000 <— Maps to set 0 (index bits 0) (14th and 15th bits form 0)
01 00000000 00000 <— Maps to set 0 (index bits 0) (14th and 15th bits form 1)

Hence, the access pattern is a, b, c, a, b (a=0, b=1, c=2, a=0, b=1).

The following code exactly achieves this.

/** properties **/
let cacheSize = 8 * (2 ** 10);
let blockSize = 32;
let associativity = 1;
let numOfSets = cacheSize / (blockSize * associativity);
let numIndexBits = Math.log2(numOfSets);
let numBlockOffset = Math.log2(blockSize);
let numUnique = 3
let label = [0, 1, 2];
let accessPatterns = [[0, 1, 2, 1, 2], [0, 1, 2, 2, 1], [0, 1, 0, 1, 2], [0, 1, 1, 0, 2], [0, 1, 0, 2, 0], [0, 1, 0, 2, 2],
                       [0, 0, 1, 2, 1]]
let outputString = ''
/** generate random number **/
let startAddress = Math.floor(Math.random() * 10000000);
let binStartAddress = parseInt(startAddress, 2);

for (let i = 0; i < numOfSets; i ++) {
   bits = [];
   for (let j = 0; j < numIndexBits; j++) {
      if (i & 1 << j) { 
        bits.push(1); 
       } else { 
       bits.push(0); 
       } 
    } 
    number = startAddress; 
    bits.forEach((value, index) => {
        mask = 1 << (index + numBlockOffset)
        number = number & ~mask | value << (index + numBlockOffset) & mask 
    }); 
    /** change the tag bits according to an access pattern **/
     accessPatterns[Math.floor(Math.random() * label.length)].forEach( (value, index) => {
      for (let m = 0; m < numUnique; m++ ) {
          mask = 1 << (m + numBlockOffset + numIndexBits)
          if (value & 1 << m) {
               number = number & ~mask | 1 << (m + numBlockOffset + numIndexBits) & mask
          }
          else {
               number = number & ~mask | 0 << (m + numBlockOffset + numIndexBits) & mask
          }
      }
      outputString = outputString.concat(label[Math.floor(Math.random() * label.length)] + ' ' + parseInt(number, 16) + '\n')
   });
}
console.log(outputString);

That’s it!. That wasn’t too difficult. The next step would be to develop a javascript cache simulator allowing to run on a browser.

As text book writers say, “I’ll leave that as a challenge to the reader”.

Leave a Reply

avatar
  Subscribe  
Notify of