moving all ipoly equstions to one file

6 files changed, 110 insertions, 194 deletions

diff --git a/src/gpgpu-sim/addrdec.cc b/src/gpgpu-sim/addrdec.cc
index 91ba47f..c01b8fa 100644
--- a/src/gpgpu-sim/addrdec.cc
+++ b/src/gpgpu-sim/addrdec.cc
@@ -31,9 +31,12 @@
 #include <string.h>
 #include "../option_parser.h"
 #include "gpu-sim.h"
+#include "hashing.h"
 
 static long int powli(long int x, long int y);
 static unsigned int LOGB2_32(unsigned int v);
+static unsigned next_powerOf2(unsigned n);
+
 static new_addr_type addrdec_packbits(new_addr_type mask, new_addr_type val,
                                       unsigned char high, unsigned char low);
 static void addrdec_getmasklimit(new_addr_type mask, unsigned char *high,
@@ -133,121 +136,29 @@ void linear_to_raw_address_translation::addrdec_tlx(new_addr_type addr,
       break;
     case BITWISE_PERMUTATION: {
       assert(!gap);
-      tlx->chip = (tlx->chip) ^ (rest_of_addr_high_bits & (m_n_channel - 1));
+      tlx->chip =
+          bitwise_hash_function(rest_of_addr_high_bits, tlx->chip, m_n_channel);
       assert(tlx->chip < m_n_channel);
       break;
     }
     case IPOLY: {
-      /*
-       * Set Indexing function from "Pseudo-randomly interleaved memory."
-       * Rau, B. R et al.
-       * ISCA 1991
-       * http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=348DEA37A3E440473B3C075EAABC63B6?doi=10.1.1.12.7149&rep=rep1&type=pdf
-       *
-       * equations are corresponding to IPOLY(37) and are adopted from:
-       * "Sacat: streaming-aware conflict-avoiding thrashing-resistant gpgpu
-       * cache management scheme." Khairy et al. IEEE TPDS 2017.
-       *
-       * equations for 32 banks are corresponding to IPOLY(37)
-       * equations for 64 banks are corresponding to IPOLY(67)
-       * To see all the IPOLY equations for all the degrees, see
-       * http://wireless-systems.ece.gatech.edu/6604/handouts/Peterson's%20Table.pdf
-       *
-       * We generate these equations using GF(2) arithmetic:
-       * http://www.ee.unb.ca/cgi-bin/tervo/calc.pl?num=&den=&f=d&e=1&m=1
-       *
-       * We go through all the strides 128 (10000000), 256 (100000000),...  and
-       * do modular arithmetic in GF(2) Then, we create the H-matrix and group
-       * each bit together, for more info read the ISCA 1991 paper
-       *
-       * IPOLY hashing guarantees conflict-free for all 2^n strides which widely
-       * exit in GPGPU applications and also show good performance for other
-       * strides.
-       */
-      assert(!gap);
-      if (m_n_channel == 32 && m_n_sub_partition_in_channel == 1) {
-        std::bitset<64> a(rest_of_addr_high_bits);
-        std::bitset<5> chip(tlx->chip);
-        chip[0] = a[13] ^ a[12] ^ a[11] ^ a[10] ^ a[9] ^ a[6] ^ a[5] ^ a[3] ^
-                  a[0] ^ chip[0];
-        chip[1] = a[14] ^ a[13] ^ a[12] ^ a[11] ^ a[10] ^ a[7] ^ a[6] ^ a[4] ^
-                  a[1] ^ chip[1];
-        chip[2] = a[14] ^ a[10] ^ a[9] ^ a[8] ^ a[7] ^ a[6] ^ a[3] ^ a[2] ^
-                  a[0] ^ chip[2];
-        chip[3] =
-            a[11] ^ a[10] ^ a[9] ^ a[8] ^ a[7] ^ a[4] ^ a[3] ^ a[1] ^ chip[3];
-        chip[4] =
-            a[12] ^ a[11] ^ a[10] ^ a[9] ^ a[8] ^ a[5] ^ a[4] ^ a[2] ^ chip[4];
-        tlx->chip = chip.to_ulong();
-        break;
-      } else if (m_n_channel == 16 && m_n_sub_partition_in_channel == 2) {
-        std::bitset<64> a(rest_of_addr_high_bits);
-        std::bitset<4> chip(tlx->chip);
-        std::bitset<32> bk(tlx->bk);
-        chip[0] = a[13] ^ a[12] ^ a[11] ^ a[10] ^ a[9] ^ a[6] ^ a[5] ^ a[3] ^
-                  a[0] ^ chip[0];
-        chip[1] = a[14] ^ a[13] ^ a[12] ^ a[11] ^ a[10] ^ a[7] ^ a[6] ^ a[4] ^
-                  a[1] ^ chip[1];
-        chip[2] = a[14] ^ a[10] ^ a[9] ^ a[8] ^ a[7] ^ a[6] ^ a[3] ^ a[2] ^
-                  a[0] ^ chip[2];
-        chip[3] =
-            a[11] ^ a[10] ^ a[9] ^ a[8] ^ a[7] ^ a[4] ^ a[3] ^ a[1] ^ chip[3];
-        tlx->chip = chip.to_ulong();
-        unsigned par_id =
-            a[12] ^ a[11] ^ a[10] ^ a[9] ^ a[8] ^ a[5] ^ a[4] ^ a[2] ^ bk[0];
-        tlx->sub_partition = tlx->chip * m_n_sub_partition_in_channel + par_id;
-        assert(tlx->chip < m_n_channel);
-        assert(tlx->sub_partition < m_n_channel * m_n_sub_partition_in_channel);
-        return;
-        break;
-      } else if (m_n_channel == 32 && m_n_sub_partition_in_channel == 2) {
-        std::bitset<64> a(rest_of_addr_high_bits);
-        std::bitset<5> chip(tlx->chip);
-        std::bitset<32> bk(tlx->bk);
-        chip[0] = a[18] ^ a[17] ^ a[16] ^ a[15] ^ a[12] ^ a[10] ^ a[6] ^ a[5] ^
-                  a[0] ^ chip[0];
-        chip[1] = a[15] ^ a[13] ^ a[12] ^ a[11] ^ a[10] ^ a[7] ^ a[5] ^ a[1] ^
-                  a[0] ^ chip[1];
-        chip[2] = a[16] ^ a[14] ^ a[13] ^ a[12] ^ a[11] ^ a[8] ^ a[6] ^ a[2] ^
-                  a[1] ^ chip[2];
-        chip[3] = a[17] ^ a[15] ^ a[14] ^ a[13] ^ a[12] ^ a[9] ^ a[7] ^ a[3] ^
-                  a[2] ^ chip[3];
-        chip[4] = a[18] ^ a[16] ^ a[15] ^ a[14] ^ a[13] ^ a[10] ^ a[8] ^ a[4] ^
-                  a[3] ^ chip[4];
-        tlx->chip = chip.to_ulong();
-        unsigned par_id =
-            a[17] ^ a[16] ^ a[15] ^ a[14] ^ a[11] ^ a[9] ^ a[5] ^ a[4] ^ bk[0];
-        tlx->sub_partition = tlx->chip * m_n_sub_partition_in_channel + par_id;
-        assert(tlx->chip < m_n_channel);
-        assert(tlx->sub_partition < m_n_channel * m_n_sub_partition_in_channel);
-        return;
-        break;
-      } else { /* Else incorrect number of channels for the hashing function */
-        assert(
-            "\nGPGPU-Sim memory_partition_indexing error: The number of "
-            "channels should be "
-            "32 or 64 for the hashing IPOLY index function.\n" &&
-            0);
-      }
-      assert(tlx->chip < m_n_channel);
-      break;
-    }
-    case PAE: {
-      // Page Address Entropy
-      // random selected bits from the page and bank bits
-      // similar to
-      // Liu, Yuxi, et al. "Get Out of the Valley: Power-Efficient Address
-      assert(!gap);
-      std::bitset<64> a(tlx->row);
-      std::bitset<5> chip(tlx->chip);
-      std::bitset<4> b(tlx->bk);
-      chip[0] = a[13] ^ a[10] ^ a[9] ^ a[5] ^ a[0] ^ b[3] ^ b[0] ^ chip[0];
-      chip[1] = a[12] ^ a[11] ^ a[6] ^ a[1] ^ b[3] ^ b[2] ^ b[1] ^ chip[1];
-      chip[2] = a[14] ^ a[9] ^ a[8] ^ a[7] ^ a[2] ^ b[1] ^ chip[2];
-      chip[3] = a[11] ^ a[10] ^ a[8] ^ a[3] ^ b[2] ^ b[3] ^ chip[3];
-      chip[4] = a[12] ^ a[9] ^ a[8] ^ a[5] ^ a[4] ^ b[1] ^ b[0] ^ chip[4];
-      tlx->chip = chip.to_ulong();
+      // assert(!gap);
+      unsigned sub_partition_addr_mask = m_n_sub_partition_in_channel - 1;
+      unsigned sub_partition = tlx->chip * m_n_sub_partition_in_channel +
+                               (tlx->bk & sub_partition_addr_mask);
+      sub_partition = ipoly_hash_function(
+          rest_of_addr_high_bits, sub_partition,
+          nextPowerOf2_m_n_channel * m_n_sub_partition_in_channel);
+
+      if (gap)  // if it is not 2^n partitions, then take modular
+        sub_partition =
+            sub_partition % (m_n_channel * m_n_sub_partition_in_channel);
+
+      tlx->chip = sub_partition / m_n_channel;
+      tlx->sub_partition = sub_partition;
       assert(tlx->chip < m_n_channel);
+      assert(tlx->sub_partition < m_n_channel * m_n_sub_partition_in_channel);
+      return;
       break;
     }
     case RANDOM: {
@@ -377,6 +288,8 @@ void linear_to_raw_address_translation::init(
   log2sub_partition = ::LOGB2_32(n_sub_partition_in_channel);
   m_n_channel = n_channel;
   m_n_sub_partition_in_channel = n_sub_partition_in_channel;
+  nextPowerOf2_m_n_channel = ::next_powerOf2(n_channel);
+  m_n_sub_partition_total = n_channel * n_sub_partition_in_channel;
 
   gap = (n_channel - ::powli(2, nchipbits));
   if (gap) {
@@ -663,6 +576,22 @@ static unsigned int LOGB2_32(unsigned int v) {
   return r;
 }
 
+// compute power of two greater than or equal to n
+// https://www.techiedelight.com/round-next-highest-power-2/
+unsigned next_powerOf2(unsigned n) {
+  // decrement n (to handle the case when n itself
+  // is a power of 2)
+  n = n - 1;
+
+  // do till only one bit is left
+  while (n & n - 1) n = n & (n - 1);  // unset rightmost bit
+
+  // n is now a power of two (less than n)
+
+  // return next power of 2
+  return n << 1;
+}
+
 static new_addr_type addrdec_packbits(new_addr_type mask, new_addr_type val,
                                       unsigned char high, unsigned char low) {
   unsigned pos = 0;
diff --git a/src/gpgpu-sim/addrdec.h b/src/gpgpu-sim/addrdec.h
index dd0e5a0..d8db416 100644
--- a/src/gpgpu-sim/addrdec.h
+++ b/src/gpgpu-sim/addrdec.h
@@ -87,8 +87,10 @@ class linear_to_raw_address_translation {
   unsigned int gap;
   unsigned m_n_channel;
   int m_n_sub_partition_in_channel;
+  int m_n_sub_partition_total;
   unsigned log2channel;
   unsigned log2sub_partition;
+  unsigned nextPowerOf2_m_n_channel;
 };
 
 #endif
diff --git a/src/gpgpu-sim/dram.cc b/src/gpgpu-sim/dram.cc
index 041cfce..ca47c46 100644
--- a/src/gpgpu-sim/dram.cc
+++ b/src/gpgpu-sim/dram.cc
@@ -31,6 +31,7 @@
 #include "dram_sched.h"
 #include "gpu-misc.h"
 #include "gpu-sim.h"
+#include "hashing.h"
 #include "l2cache.h"
 #include "mem_fetch.h"
 #include "mem_latency_stat.h"
@@ -207,8 +208,8 @@ dram_req_t::dram_req_t(class mem_fetch *mf, unsigned banks,
     }
     case BITWISE_XORING_BK_INDEX: {
       // xoring bank bits with lower bits of the page
-      int lbank = LOGB2(banks);
-      bk = tlx.bk ^ (tlx.row & ((1 << lbank) - 1));
+      bk = bitwise_hash_function(tlx.row, tlx.bk, banks);
+      assert(bk < banks);
       break;
     }
     case IPOLY_BK_INDEX: {
@@ -216,22 +217,9 @@ dram_req_t::dram_req_t(class mem_fetch *mf, unsigned banks,
        * memory." Rau, B. R et al. ISCA 1991
        * http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=348DEA37A3E440473B3C075EAABC63B6?doi=10.1.1.12.7149&rep=rep1&type=pdf
        */
-      if (banks == 16) {
-        std::bitset<64> a(tlx.row);
-        std::bitset<4> b(tlx.bk);
-        b[0] = a[11] ^ a[10] ^ a[9] ^ a[8] ^ a[6] ^ a[4] ^ a[3] ^ a[0] ^ b[0];
-        b[1] = a[12] ^ a[8] ^ a[7] ^ a[6] ^ a[5] ^ a[3] ^ a[1] ^ a[0] ^ b[1];
-        b[2] = a[9] ^ a[8] ^ a[7] ^ a[6] ^ a[4] ^ a[2] ^ a[1] ^ b[2];
-        b[3] = a[10] ^ a[9] ^ a[8] ^ a[7] ^ a[5] ^ a[3] ^ a[2] ^ b[3];
-        bk = b.to_ulong();
-        assert(bk < banks);
-      } else { /* Else incorrect number of channels for the hashing function */
-        assert(
-            "\nGPGPU-Sim memory_banking indexing error: The number of banks "
-            "should be "
-            "16 for the hashing IPOLY index function.\n" &&
-            0);
-      }
+      // xoring bank bits with lower bits of the page
+      bk = ipoly_hash_function(tlx.row, tlx.bk, banks);
+      assert(bk < banks);
       break;
     }
     case CUSTOM_BK_INDEX:
diff --git a/src/gpgpu-sim/gpu-cache.cc b/src/gpgpu-sim/gpu-cache.cc
index adce3a2..75c3691 100644
--- a/src/gpgpu-sim/gpu-cache.cc
+++ b/src/gpgpu-sim/gpu-cache.cc
@@ -29,6 +29,7 @@
 #include "gpu-cache.h"
 #include <assert.h>
 #include "gpu-sim.h"
+#include "hashing.h"
 #include "stat-tool.h"
 
 // used to allocate memory that is large enough to adapt the changes in cache
@@ -62,24 +63,31 @@ unsigned l1d_cache_config::set_bank(new_addr_type addr) const {
   // For sector cache, we select one sector per bank (sector interleaving)
   // This is what was found in Volta (one sector per bank, sector interleaving)
   // otherwise, line interleaving
-  if (m_cache_type == SECTOR)
-    return (addr >> m_sector_sz_log2) & (l1_banks - 1);
-  else
-    return (addr >> m_line_sz_log2) & (l1_banks - 1);
+  return cache_config::hash_function(addr, l1_banks, l1_banks_byte_interleaving,
+                                     m_l1_banks_log2,
+                                     l1_banks_hashing_function);
+}
+
+unsigned cache_config::set_index(new_addr_type addr) const {
+  return cache_config::hash_function(addr, m_nset, m_line_sz_log2, m_nset_log2,
+                                     m_set_index_function);
 }
 
-unsigned l1d_cache_config::set_index(new_addr_type addr) const {
-  unsigned set_index = m_nset;  // Default to linear set index function
-  unsigned lower_xor = 0;
-  unsigned upper_xor = 0;
+unsigned cache_config::hash_function(new_addr_type addr, unsigned m_nset,
+                                     unsigned m_line_sz_log2,
+                                     unsigned m_nset_log2,
+                                     unsigned m_index_function) const {
+  unsigned set_index = 0;
 
-  switch (m_set_index_function) {
-    case FERMI_HASH_SET_FUNCTION:
-    case BITWISE_XORING_FUNCTION:
+  switch (m_index_function) {
+    case FERMI_HASH_SET_FUNCTION: {
       /*
        * Set Indexing function from "A Detailed GPU Cache Model Based on Reuse
        * Distance Theory" Cedric Nugteren et al. HPCA 2014
        */
+      unsigned lower_xor = 0;
+      unsigned upper_xor = 0;
+
       if (m_nset == 32 || m_nset == 64) {
         // Lower xor value is bits 7-11
         lower_xor = (addr >> m_line_sz_log2) & 0x1F;
@@ -102,54 +110,34 @@ unsigned l1d_cache_config::set_index(new_addr_type addr) const {
             0);
       }
       break;
+    }
 
-    case HASH_IPOLY_FUNCTION:
-      /*
-       * Set Indexing function from "Pseudo-randomly interleaved memory."
-       * Rau, B. R et al.
-       * ISCA 1991
-       *
-       * "Sacat: streaming-aware conflict-avoiding thrashing-resistant gpgpu
-       * cache management scheme." Khairy et al. IEEE TPDS 2017.
-       */
-      if (m_nset == 32 || m_nset == 64) {
-        std::bitset<64> a(addr);
-        std::bitset<6> index;
-        index[0] = a[25] ^ a[24] ^ a[23] ^ a[22] ^ a[21] ^ a[18] ^ a[17] ^
-                   a[15] ^ a[12] ^ a[7];  // 10
-        index[1] = a[26] ^ a[25] ^ a[24] ^ a[23] ^ a[22] ^ a[19] ^ a[18] ^
-                   a[16] ^ a[13] ^ a[8];  // 10
-        index[2] = a[26] ^ a[22] ^ a[21] ^ a[20] ^ a[19] ^ a[18] ^ a[15] ^
-                   a[14] ^ a[12] ^ a[9];  // 10
-        index[3] = a[23] ^ a[22] ^ a[21] ^ a[20] ^ a[19] ^ a[16] ^ a[15] ^
-                   a[13] ^ a[10];  // 9
-        index[4] = a[24] ^ a[23] ^ a[22] ^ a[21] ^ a[20] ^ a[17] ^ a[16] ^
-                   a[14] ^ a[11];  // 9
-
-        if (m_nset == 64) index[5] = a[12];
-
-        set_index = index.to_ulong();
-
-      } else { /* Else incorrect number of sets for the hashing function */
-        assert(
-            "\nGPGPU-Sim cache configuration error: The number of sets should "
-            "be "
-            "32 or 64 for the hashing set index function.\n" &&
-            0);
-      }
+    case BITWISE_XORING_FUNCTION: {
+      new_addr_type higher_bits = addr >> (m_line_sz_log2 + m_nset_log2);
+      unsigned index = (addr >> m_line_sz_log2) & (m_nset - 1);
+      set_index = bitwise_hash_function(higher_bits, index, m_nset);
       break;
-
-    case CUSTOM_SET_FUNCTION:
+    }
+    case HASH_IPOLY_FUNCTION: {
+      new_addr_type higher_bits = addr >> (m_line_sz_log2 + m_nset_log2);
+      unsigned index = (addr >> m_line_sz_log2) & (m_nset - 1);
+      set_index = ipoly_hash_function(higher_bits, index, m_nset);
+      break;
+    }
+    case CUSTOM_SET_FUNCTION: {
       /* No custom set function implemented */
       break;
+    }
 
-    case LINEAR_SET_FUNCTION:
+    case LINEAR_SET_FUNCTION: {
       set_index = (addr >> m_line_sz_log2) & (m_nset - 1);
       break;
+    }
 
-    default:
+    default: {
       assert("\nUndefined set index function.\n" && 0);
       break;
+    }
   }
 
   // Linear function selected or custom set index function not implemented
@@ -166,13 +154,14 @@ void l2_cache_config::init(linear_to_raw_address_translation *address_mapping) {
 }
 
 unsigned l2_cache_config::set_index(new_addr_type addr) const {
-  if (!m_address_mapping) {
-    return (addr >> m_line_sz_log2) & (m_nset - 1);
-  } else {
+  new_addr_type part_addr = addr;
+
+  if (m_address_mapping) {
     // Calculate set index without memory partition bits to reduce set camping
-    new_addr_type part_addr = m_address_mapping->partition_address(addr);
-    return (part_addr >> m_line_sz_log2) & (m_nset - 1);
+    part_addr = m_address_mapping->partition_address(addr);
   }
+
+  return cache_config::set_index(part_addr);
 }
 
 tag_array::~tag_array() {
diff --git a/src/gpgpu-sim/gpu-cache.h b/src/gpgpu-sim/gpu-cache.h
index 2a37876..5c28b41 100644
--- a/src/gpgpu-sim/gpu-cache.h
+++ b/src/gpgpu-sim/gpu-cache.h
@@ -686,17 +686,11 @@ class cache_config {
             m_line_sz * m_nset * m_assoc, m_nset, m_assoc, m_line_sz);
   }
 
-  virtual unsigned set_index(new_addr_type addr) const {
-    if (m_set_index_function != LINEAR_SET_FUNCTION) {
-      printf(
-          "\nGPGPU-Sim cache configuration error: Hashing or "
-          "custom set index function selected in configuration "
-          "file for a cache that has not overloaded the set_index "
-          "function\n");
-      abort();
-    }
-    return (addr >> m_line_sz_log2) & (m_nset - 1);
-  }
+  virtual unsigned set_index(new_addr_type addr) const;
+
+  unsigned hash_function(new_addr_type addr, unsigned m_nset,
+                         unsigned m_line_sz_log2, unsigned m_nset_log2,
+                         unsigned m_index_function) const;
 
   new_addr_type tag(new_addr_type addr) const {
     // For generality, the tag includes both index and tag. This allows for more
@@ -793,10 +787,18 @@ class cache_config {
 class l1d_cache_config : public cache_config {
  public:
   l1d_cache_config() : cache_config() {}
-  virtual unsigned set_index(new_addr_type addr) const;
   unsigned set_bank(new_addr_type addr) const;
+  void init(char *config, FuncCache status) {
+    m_banks_byte_interleaving_log2 = LOGB2(l1_banks_byte_interleaving);
+    m_l1_banks_log2 = LOGB2(l1_banks);
+    cache_config::init(config, status);
+  }
   unsigned l1_latency;
   unsigned l1_banks;
+  unsigned m_l1_banks_log2;
+  unsigned l1_banks_byte_interleaving;
+  unsigned m_banks_byte_interleaving_log2;
+  unsigned l1_banks_hashing_function;
 };
 
 class l2_cache_config : public cache_config {
diff --git a/src/gpgpu-sim/gpu-sim.cc b/src/gpgpu-sim/gpu-sim.cc
index 03aebf3..1650688 100644
--- a/src/gpgpu-sim/gpu-sim.cc
+++ b/src/gpgpu-sim/gpu-sim.cc
@@ -252,6 +252,12 @@ void shader_core_config::reg_options(class OptionParser *opp) {
   option_parser_register(opp, "-gpgpu_l1_banks", OPT_UINT32,
                          &m_L1D_config.l1_banks, "The number of L1 cache banks",
                          "1");
+  option_parser_register(opp, "-gpgpu_l1_banks_byte_interleaving", OPT_UINT32,
+                         &m_L1D_config.l1_banks_byte_interleaving,
+                         "l1 banks byte interleaving granularity", "32");
+  option_parser_register(opp, "-gpgpu_l1_banks_hashing_function", OPT_UINT32,
+                         &m_L1D_config.l1_banks_hashing_function,
+                         "l1 banks hashing function", "0");
   option_parser_register(opp, "-gpgpu_l1_latency", OPT_UINT32,
                          &m_L1D_config.l1_latency, "L1 Hit Latency", "1");
   option_parser_register(opp, "-gpgpu_smem_latency", OPT_UINT32, &smem_latency,