1. rewriting memory access generation code (from scratch), why not...

passing CUDA 3.1 and ptxplus correlation, but correlation still bad (0.62)... 

after debugging 1 to get it working with ptxplus, problem is very clear:
shared and constant cache accesses not occuring for operations that combine these with ALU operations.

TODO: 
have a "read-operands" stage, which somehow combines operand collector 
register reading with shared and const memory accesses...

[git-p4: depot-paths = "//depot/gpgpu_sim_research/fermi/distribution/": change = 7895]

1 files changed, 218 insertions, 150 deletions

diff --git a/src/abstract_hardware_model.cc b/src/abstract_hardware_model.cc
index 507e02f..ad5c983 100644
--- a/src/abstract_hardware_model.cc
+++ b/src/abstract_hardware_model.cc
@@ -2,7 +2,7 @@
 #include "cuda-sim/memory.h"
 #include <algorithm>
 
-unsigned mem_access_t::next_access_uid = 0;   
+unsigned mem_access_t::sm_next_access_uid = 0;   
 unsigned warp_inst_t::sm_next_uid = 0;
 
 void move_warp( warp_inst_t *&dst, warp_inst_t *&src )
@@ -24,173 +24,241 @@ gpgpu_t::gpgpu_t()
    m_dev_malloc=GLOBAL_HEAP_START; 
 }
 
-unsigned core_config::shmem_bank_func(address_type addr, unsigned) const
-{
-   return ((addr/WORD_SIZE) % gpgpu_n_shmem_bank);
-}
-
-address_type null_tag_func(address_type address, unsigned line_size)
-{
-   return address; //no modification: each address is its own tag.
-}
-
-address_type line_size_based_tag_func(address_type address, unsigned line_size)
+address_type line_size_based_tag_func(new_addr_type address, new_addr_type line_size)
 {
    //gives the tag for an address based on a given line size
-   return ((address) & (~((address_type)line_size - 1)));
+   return address & ~(line_size-1);
 }
 
-void warp_inst_t::get_memory_access_list()
-{
-   // Calculates memory accesses generated by this warp
-   // Returns acesses which are "coalesced" 
-   // Does not coalesce nor overlap bank accesses across warp "parts".
+struct transaction_info {
+    std::bitset<4> chunks; // bitmask: 32-byte chunks accessed
+    mem_access_byte_mask_t bytes;
+    active_mask_t active; // threads in this transaction
+};
 
-   // This is called once per warp_inst_t when the warp_inst_t enters the memory stage.
-   // It produces the set of distinct memory accesses that need to be peformed.
-   // These accessess are then performed over multiple cycles (stalling the pipeline) 
-   // if the accessses cannot be performed all at once.
-    
-   // In hardware, these accesses would be created at the specific unit handling the type 
-   // of memory access. We centralize the logic simply to reduce code duplication. 
+void warp_inst_t::generate_mem_accesses()
+{
+    if( empty() || op == MEMORY_BARRIER_OP || m_mem_accesses_created ) 
+        return;
+    if ( !( (op == LOAD_OP) || (op == STORE_OP) || (op == MEMORY_BARRIER_OP) ) )
+        return; 
 
-   // Below, accesses are assigned an "order" based on when that access may be issued. 
-   // Accesses with the same order number may occur at the same time: they are to different banks. 
-   // Later, when the queue is processed it will evaluate accesses of as many orders as 
-   // ports on that cache/shmem.
-   //  
-   // Accesses are placed in accessq sorted so that accesses of the same order are adjacent.
+    assert( is_load() || is_store() );
+    assert( m_per_scalar_thread_valid ); // need address information per thread
 
-    typedef unsigned (core_config::*bank_func_t)(address_type add, unsigned line_size) const;
-    typedef address_type (*tag_func_t)(address_type add, unsigned line_size);
-    bank_func_t bank_func = NULL;
-    tag_func_t tag_func = NULL;
-    unsigned warp_parts = 0;
-    unsigned line_size = 0;
-    bool limit_broadcast = 0; 
-    bool global_mem_access = false;
+    bool is_write = is_store();
 
-    switch( space.get_type() ) {
-    case shared_space: 
-        bank_func = &core_config::shmem_bank_func; 
-        tag_func = null_tag_func;
-        warp_parts = m_config->gpgpu_shmem_pipe_speedup; 
-        line_size = 1; //shared memory doesn't care about line_size, needs to be at least 1;
-        limit_broadcast = true; // limit broadcasts to single cycle. 
+    mem_access_type access_type;
+    switch (space.get_type()) {
+    case const_space:
+    case param_space_kernel: 
+        access_type = CONST_ACC_R; 
         break;
     case tex_space: 
-        bank_func = &core_config::null_bank_func;
-        tag_func = line_size_based_tag_func;
-        warp_parts = 1;
-        line_size = m_config->gpgpu_cache_texl1_linesize;
-        limit_broadcast = false;
+        access_type = TEXTURE_ACC_R;   
         break;
-    case const_space:  case param_space_kernel: 
-        bank_func = &core_config::null_bank_func; 
-        tag_func = line_size_based_tag_func;
-        warp_parts = 1;
-        line_size = m_config->gpgpu_cache_constl1_linesize;
-        limit_broadcast = false;
+    case global_space:       
+        access_type = is_write? GLOBAL_ACC_W: GLOBAL_ACC_R;   
         break;
-    case global_space: case local_space: case param_space_local: 
-        global_mem_access=true;
-        warp_parts = 1;
-        line_size = 0;
-        if( m_config->gpgpu_coalesce_arch == 13 ){
-           warp_parts = 2;
-           // line size is dependant on instruction;
-           switch (data_size) {
-           case 1: line_size = 32; break;
-           case 2: line_size = 64; break;
-           case 4: case 8: case 16: line_size = 128; break;
-           default: assert(0);
-           }
-        } else abort();
-        bank_func = &core_config::null_bank_func;
-        tag_func = line_size_based_tag_func;
-        limit_broadcast = false;
+    case local_space:
+    case param_space_local:  
+        access_type = is_write? LOCAL_ACC_W: LOCAL_ACC_R;   
         break;
-    default:
-        abort();
+    case shared_space: break;
+    default: assert(0); break; 
     }
 
-   // bank_accs tracks bank accesses for sorting into generations;
-   // each entry is (bank #, number of accesses)
-   // the idea is that you can only access a bank a number of times each cycle equal to 
-   // its number of ports in one cycle. 
-   std::map<unsigned,unsigned> bank_accs;
+    // Calculate memory accesses generated by this warp
+    new_addr_type cache_block_size = 32; // in bytes 
+
+    switch( space.get_type() ) {
+    case shared_space: {
+        unsigned subwarp_size = m_config->warp_size / m_config->shmem_warp_parts;
+        unsigned total_accesses=0;
+        for( unsigned subwarp=0; subwarp <  m_config->shmem_warp_parts; subwarp++ ) {
+
+            // data structures used per part warp 
+            std::map<unsigned,std::map<new_addr_type,unsigned> > bank_accs; // bank -> word address -> access count
 
-   // keep track of broadcasts with unique orders if limit_broadcast
-   // the normally calculated orders will never be greater than warp_size
-   unsigned broadcast_order =  warp_size();
-   unsigned qbegin = get_accessq_size();
-   unsigned qpartbegin = qbegin;
-   unsigned mem_pipe_size = warp_size() / warp_parts;
-   for (unsigned part = 0; part < warp_size(); part += mem_pipe_size) {
-      for (unsigned i = part; i < part + mem_pipe_size; i++) {
-         if ( !active(i) ) 
-            continue;
-         new_addr_type addr = get_addr(i);
-         address_type lane_segment_address = tag_func(addr, line_size);
-         unsigned quarter = 0;
-         if( line_size>=4 )
-            quarter = (addr / (line_size/4)) & 3;
-         bool match = false;
-         if( !isatomic() ) { //atomics must have own request
-            for( unsigned j = qpartbegin; j <get_accessq_size(); j++ ) {
-               if (lane_segment_address == accessq(j).addr) {
-                  accessq(j).quarter_count[quarter]++;
-                  accessq(j).warp_indices.push_back(i);
-                  if (limit_broadcast) // two threads access this address, so its a broadcast. 
-                     accessq(j).order = ++broadcast_order; //do broadcast in its own cycle.
-                  match = true;
-                  break;
-               }
+            // step 1: compute accesses to words in banks
+            for( unsigned thread=subwarp*subwarp_size; thread < (subwarp+1)*subwarp_size; thread++ ) {
+                if( !active(thread) ) 
+                    continue;
+                new_addr_type addr = m_per_scalar_thread[thread].memreqaddr;
+                unsigned bank = m_config->shmem_bank_func(addr);
+                new_addr_type word = line_size_based_tag_func(addr,m_config->WORD_SIZE);
+                bank_accs[bank][word]++;
             }
-         }
-         if (!match) { // does not match a previous request by another thread, so need a new request
-            assert( space != undefined_space );
-            m_accessq.push_back( mem_access_t( lane_segment_address, line_size, quarter, i) );
-            // Determine Bank Conflicts:
-            unsigned bank = (m_config->*bank_func)(get_addr(i), line_size);
-            // ensure no concurrent bank access accross warp parts. 
-            // ie. order will be less than part for all previous loads in previous parts, so:
-            if (bank_accs[bank] < part) 
-               bank_accs[bank]=part; 
-            accessq_back().order = bank_accs[bank];
-            bank_accs[bank]++;
-         }
-      }
-      qpartbegin = get_accessq_size(); //don't coalesce accross warp parts
-   }
-   //sort requests by order they will be processed in
-   std::stable_sort( m_accessq.begin()+qbegin,m_accessq.end());
 
-   if( global_mem_access ) {
-       // Now that we have the accesses, if we don't have a cache we can adjust request sizes to 
-       // include only the data referenced by the threads 
-       for (unsigned i = 0; i < get_accessq_size(); i++) {
-          if (m_config->gpgpu_coalesce_arch == 13) {
-             // do coalescing here.
-             char* quarter_counts = accessq(i).quarter_count;
-             bool low = quarter_counts[0] or quarter_counts[1];
-             bool high = quarter_counts[2] or quarter_counts[3];
-             if (accessq(i).req_size == 128) {
-                if (low xor high) { //can reduce size
-                   accessq(i).req_size = 64;
-                   if (high) accessq(i).addr += 64;
-                   low = quarter_counts[0] or quarter_counts[2]; //set low and high for next pass
-                   high = quarter_counts[1] or quarter_counts[3];
+            // step 2: look for and select a broadcast bank/word if one occurs
+            bool broadcast_detected = false;
+            new_addr_type broadcast_word=(new_addr_type)-1;
+            unsigned broadcast_bank=(unsigned)-1;
+            std::map<unsigned,std::map<new_addr_type,unsigned> >::iterator b;
+            for( b=bank_accs.begin(); b != bank_accs.end(); b++ ) {
+                unsigned bank = b->first;
+                std::map<new_addr_type,unsigned> &access_set = b->second;
+                std::map<new_addr_type,unsigned>::iterator w;
+                for( w=access_set.begin(); w != access_set.end(); ++w ) {
+                    if( w->second > 1 ) {
+                        // found a broadcast
+                        broadcast_detected=true;
+                        broadcast_bank=bank;
+                        broadcast_word=w->first;
+                        break;
+                    }
                 }
-             }
-             if (accessq(i).req_size == 64) {
-                if (low xor high) { //can reduce size
-                   accessq(i).req_size = 32;
-                   if (high) accessq(i).addr += 32;
+                if( broadcast_detected ) 
+                    break;
+            }
+
+            // step 3: figure out max bank accesses performed, taking account of broadcast case
+            unsigned max_bank_accesses=0;
+            for( b=bank_accs.begin(); b != bank_accs.end(); b++ ) {
+                unsigned bank_accesses=0;
+                std::map<new_addr_type,unsigned> &access_set = b->second;
+                std::map<new_addr_type,unsigned>::iterator w;
+                for( w=access_set.begin(); w != access_set.end(); ++w ) 
+                    bank_accesses += w->second;
+                if( broadcast_detected && broadcast_bank == b->first ) {
+                    for( w=access_set.begin(); w != access_set.end(); ++w ) {
+                        if( w->first == broadcast_word ) {
+                            unsigned n = w->second;
+                            assert(n > 1); // or this wasn't a broadcast
+                            assert(bank_accesses >= (n-1));
+                            bank_accesses -= (n-1);
+                            break;
+                        }
+                    }
                 }
-             }
-          }
-       }
-   }
-} 
+                if( bank_accesses > max_bank_accesses ) 
+                    max_bank_accesses = bank_accesses;
+            }
+
+            // step 4: accumulate
+            total_accesses+= max_bank_accesses;
+        }
+        assert( total_accesses > 0 && total_accesses <= m_config->warp_size );
+        cycles = total_accesses; // shared memory conflicts modeled as larger initiation interval 
+        break;
+    }
 
+    case tex_space: 
+        cache_block_size = m_config->gpgpu_cache_texl1_linesize;
+
+    case const_space:  case param_space_kernel:
+        cache_block_size = m_config->gpgpu_cache_constl1_linesize; {
+        mem_access_byte_mask_t byte_mask; 
+        std::map<new_addr_type,active_mask_t> accesses; // block address -> set of thread offsets in warp
+        std::map<new_addr_type,active_mask_t>::iterator a;
+        for( unsigned thread=0; thread < m_config->warp_size; thread++ ) {
+            if( !active(thread) ) 
+                continue;
+            new_addr_type addr = m_per_scalar_thread[thread].memreqaddr;
+            unsigned block_address = line_size_based_tag_func(addr,m_config->gpgpu_cache_texl1_linesize);
+            accesses[block_address].set(thread);
+            unsigned idx = addr-block_address; 
+            for( unsigned i=0; i < data_size; i++ ) 
+                byte_mask.set(idx+i);
+        }
+        for( a=accesses.begin(); a != accesses.end(); ++a ) 
+            m_accessq.push_back( mem_access_t(access_type,a->first,cache_block_size,is_write,a->second,byte_mask) );
+        }
+        break;
+
+    case global_space: case local_space: case param_space_local:
+         
+        if( m_config->gpgpu_coalesce_arch == 13 ) {
+            // see the CUDA manual where it discusses coalescing rules before reading this
+            unsigned segment_size = 0;
+            unsigned warp_parts = 2;
+            switch( data_size ) {
+            case 1: segment_size = 32; break;
+            case 2: segment_size = 64; break;
+            case 4: case 8: case 16: segment_size = 128; break;
+            }
+            unsigned subwarp_size = m_config->warp_size / warp_parts;
+
+            for( unsigned subwarp=0; subwarp <  warp_parts; subwarp++ ) {
+                std::map<new_addr_type,transaction_info> subwarp_transactions;
+
+                // step 1: find all transactions generated by this subwarp
+                for( unsigned thread=subwarp*subwarp_size; thread<subwarp_size*(subwarp+1); thread++ ) {
+                    if( !active(thread) ) 
+                        continue;
+                    new_addr_type addr = m_per_scalar_thread[thread].memreqaddr;
+                    unsigned block_address = line_size_based_tag_func(addr,segment_size);
+                    unsigned chunk = (addr&127)/32; // which 32-byte chunk within in a 128-byte chunk does this thread access?
+                    transaction_info &info = subwarp_transactions[block_address];
+                    info.chunks.set(chunk);
+                    info.active.set(thread);
+                    unsigned idx = (addr&127);
+                    for( unsigned i=0; i < data_size; i++ ) 
+                        info.bytes.set(idx+i);
+                }
+
+                // step 2: reduce each transaction size, if possible
+                std::map< new_addr_type, transaction_info >::iterator t;
+                for( t=subwarp_transactions.begin(); t !=subwarp_transactions.end(); t++ ) {
+                    new_addr_type addr = t->first;
+                    assert( (addr & (segment_size-1)) == 0 );
+                    const transaction_info &info = t->second;
+                    const std::bitset<4> &q = info.chunks;
+                    assert( q.count() >= 1 );
+                    std::bitset<2> h; // halves (used to check if 64 byte segment can be compressed into a single 32 byte segment)
+
+                    unsigned size=segment_size;
+                    if( segment_size == 128 ) {
+                        bool lower_half_used = q[0] || q[1];
+                        bool upper_half_used = q[2] || q[3]; 
+                        if( lower_half_used && !upper_half_used ) {
+                            // only lower 64 bytes used
+                            size = 64;
+                            if(q[0]) h.set(0);
+                            if(q[1]) h.set(1);
+                        } else if ( (!lower_half_used) && upper_half_used ) {
+                            // only upper 64 bytes used
+                            addr = addr+64;
+                            size = 64;
+                            if(q[2]) h.set(0);
+                            if(q[3]) h.set(1);
+                        } else {
+                            assert(lower_half_used && upper_half_used);
+                        }
+                    } else if( segment_size == 64 ) {
+                        // need to set halves
+                        if( (addr % 128) == 0 ) {
+                            if(q[0]) h.set(0);
+                            if(q[1]) h.set(1);
+                        } else {
+                            assert( (addr % 128) == 64 );
+                            if(q[2]) h.set(0);
+                            if(q[3]) h.set(1);
+                        }
+                    }
+                    if( size == 64 ) {
+                        bool lower_half_used = h[0];
+                        bool upper_half_used = h[1]; 
+                        if( lower_half_used && !upper_half_used ) {
+                            size = 32;
+                        } else if ( (!lower_half_used) && upper_half_used ) {
+                            addr = addr+32;
+                            size = 32;
+                        } else {
+                            assert(lower_half_used && upper_half_used);
+                        }
+                    }
+                    m_accessq.push_back( mem_access_t(access_type,addr,size,is_write,info.active,info.bytes) );
+                }
+            }
+            
+        } else abort();
+
+        break;
+
+    default:
+        abort();
+    }
+
+    m_mem_accesses_created=true;
+}