// Copyright (c) 2009-2011, Tor M. Aamodt // The University of British Columbia // All rights reserved. // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are met: // // Redistributions of source code must retain the above copyright notice, this // list of conditions and the following disclaimer. // Redistributions in binary form must reproduce the above copyright notice, this // list of conditions and the following disclaimer in the documentation and/or // other materials provided with the distribution. // Neither the name of The University of British Columbia nor the names of its // contributors may be used to endorse or promote products derived from this // software without specific prior written permission. // // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #ifndef GPU_CACHE_H #define GPU_CACHE_H #include #include #include "gpu-misc.h" #include "mem_fetch.h" #include "../abstract_hardware_model.h" #include "../tr1_hash_map.h" enum cache_block_state { INVALID, RESERVED, VALID, MODIFIED }; enum cache_request_status { HIT, HIT_RESERVED, MISS, RESERVATION_FAIL }; enum cache_event { WRITE_BACK_REQUEST_SENT, READ_REQUEST_SENT, WRITE_REQUEST_SENT }; struct cache_block_t { cache_block_t() { m_tag=0; m_block_addr=0; m_alloc_time=0; m_fill_time=0; m_last_access_time=0; m_status=INVALID; } void allocate( new_addr_type tag, new_addr_type block_addr, unsigned time ) { m_tag=tag; m_block_addr=block_addr; m_alloc_time=time; m_last_access_time=time; m_fill_time=0; m_status=RESERVED; } void fill( unsigned time ) { assert( m_status == RESERVED ); m_status=VALID; m_fill_time=time; } new_addr_type m_tag; new_addr_type m_block_addr; unsigned m_alloc_time; unsigned m_last_access_time; unsigned m_fill_time; cache_block_state m_status; }; enum replacement_policy_t { LRU, FIFO }; enum write_policy_t { READ_ONLY, WRITE_BACK, WRITE_THROUGH }; enum allocation_policy_t { ON_MISS, ON_FILL }; enum write_allocate_policy_t { NO_WRITE_ALLOCATE, WRITE_ALLOCATE }; enum cache_scope_t { PRIVATE, SHARED }; enum mshr_config_t { TEX_FIFO, ASSOC // normal cache }; class cache_config { public: cache_config() { m_valid = false; m_disabled = false; m_config_string = NULL; // set by option parser } void init() { assert( m_config_string ); char rp, wp, ap, mshr_type, scope, wap; int ntok = sscanf(m_config_string,"%u:%u:%u:%c:%c:%c:%c:%c:%c:%u:%u:%u:%u", &m_nset, &m_line_sz, &m_assoc, &rp, &wp, &ap, &mshr_type, &scope, &wap, &m_mshr_entries,&m_mshr_max_merge, &m_miss_queue_size,&m_result_fifo_entries); if ( ntok < 10 ) { if ( !strcmp(m_config_string,"none") ) { m_disabled = true; return; } exit_parse_error(); } switch (rp) { case 'L': m_replacement_policy = LRU; break; case 'F': m_replacement_policy = FIFO; break; default: exit_parse_error(); } switch (wp) { case 'R': m_write_policy = READ_ONLY; break; case 'B': m_write_policy = WRITE_BACK; break; case 'T': m_write_policy = WRITE_THROUGH; break; default: exit_parse_error(); } switch (ap) { case 'm': m_alloc_policy = ON_MISS; break; case 'f': m_alloc_policy = ON_FILL; break; default: exit_parse_error(); } switch (mshr_type) { case 'F': m_mshr_type = TEX_FIFO; assert(ntok==13); break; case 'A': m_mshr_type = ASSOC; break; default: exit_parse_error(); } m_line_sz_log2 = LOGB2(m_line_sz); m_nset_log2 = LOGB2(m_nset); m_valid = true; switch(scope){ case 'P': m_cache_scope = PRIVATE; break; case 'S': m_cache_scope = SHARED; break; default: exit_parse_error(); } switch(wap){ case 'W': m_write_aclloc_policy = WRITE_ALLOCATE; break; case 'N': m_write_aclloc_policy = NO_WRITE_ALLOCATE; break; default: exit_parse_error(); } } bool disabled() const { return m_disabled;} unsigned get_line_sz() const { assert( m_valid ); return m_line_sz; } unsigned get_num_lines() const { assert( m_valid ); return m_nset * m_assoc; } void print( FILE *fp ) const { fprintf( fp, "Size = %d B (%d Set x %d-way x %d byte line)\n", m_line_sz * m_nset * m_assoc, m_nset, m_assoc, m_line_sz ); } unsigned set_index( new_addr_type addr ) const { return(addr >> m_line_sz_log2) & (m_nset-1); } new_addr_type tag( new_addr_type addr ) const { return addr >> (m_line_sz_log2+m_nset_log2); } new_addr_type block_addr( new_addr_type addr ) const { return addr & ~(m_line_sz-1); } char *m_config_string; private: void exit_parse_error() { printf("GPGPU-Sim uArch: cache configuration parsing error (%s)\n", m_config_string ); abort(); } bool m_valid; bool m_disabled; unsigned m_line_sz; unsigned m_line_sz_log2; unsigned m_nset; unsigned m_nset_log2; unsigned m_assoc; enum replacement_policy_t m_replacement_policy; // 'L' = LRU, 'F' = FIFO enum write_policy_t m_write_policy; // 'T' = write through, 'B' = write back, 'R' = read only enum allocation_policy_t m_alloc_policy; // 'm' = allocate on miss, 'f' = allocate on fill enum mshr_config_t m_mshr_type; cache_scope_t m_cache_scope; // 'P' = PRIVATE, 'S' = SHARED write_allocate_policy_t m_write_aclloc_policy; // 'W' = Write allocate, 'N' = No write allocate union { unsigned m_mshr_entries; unsigned m_fragment_fifo_entries; }; union { unsigned m_mshr_max_merge; unsigned m_request_fifo_entries; }; union { unsigned m_miss_queue_size; unsigned m_rob_entries; }; unsigned m_result_fifo_entries; friend class tag_array; friend class baseline_cache; friend class read_only_cache; friend class tex_cache; friend class data_cache; }; class tag_array { public: tag_array( const cache_config &config, int core_id, int type_id ); ~tag_array(); enum cache_request_status probe( new_addr_type addr, unsigned &idx ) const; enum cache_request_status access( new_addr_type addr, unsigned time, unsigned &idx ); enum cache_request_status access( new_addr_type addr, unsigned time, unsigned &idx, bool &wb, cache_block_t &evicted ); void fill( new_addr_type addr, unsigned time ); void fill( unsigned idx, unsigned time ); unsigned size() const { return m_config.get_num_lines();} cache_block_t &get_block(unsigned idx) { return m_lines[idx];} void flush(); // flash invalidate all entries void new_window(); void print( FILE *stream, unsigned &total_access, unsigned &total_misses ) const; float windowed_miss_rate( ) const; protected: const cache_config &m_config; cache_block_t *m_lines; /* nbanks x nset x assoc lines in total */ unsigned m_access; unsigned m_miss; unsigned m_pending_hit; // number of cache miss that hit a line that is allocated but not filled // performance counters for calculating the amount of misses within a time window unsigned m_prev_snapshot_access; unsigned m_prev_snapshot_miss; unsigned m_prev_snapshot_pending_hit; int m_core_id; // which shader core is using this int m_type_id; // what kind of cache is this (normal, texture, constant) }; class mshr_table { public: mshr_table( unsigned num_entries, unsigned max_merged ) : m_num_entries(num_entries), m_max_merged(max_merged) #if (tr1_hash_map_ismap == 0) ,m_data(2*num_entries) #endif { } // is there a pending request to the lower memory level already? bool probe( new_addr_type block_addr ) const; // is there space for tracking a new memory access? bool full( new_addr_type block_addr ) const; // add or merge this access void add( new_addr_type block_addr, mem_fetch *mf ); // true if cannot accept new fill responses bool busy() const {return false;} // accept a new cache fill response: mark entry ready for processing void mark_ready( new_addr_type block_addr, bool &has_atomic ); // true if ready accesses exist bool access_ready() const {return !m_current_response.empty();} // next ready access mem_fetch *next_access(); void display( FILE *fp ) const; private: // finite sized, fully associative table, with a finite maximum number of merged requests const unsigned m_num_entries; const unsigned m_max_merged; struct mshr_entry { std::list m_list; bool m_has_atomic; mshr_entry() : m_has_atomic(false) { } }; typedef tr1_hash_map table; table m_data; // it may take several cycles to process the merged requests bool m_current_response_ready; std::list m_current_response; }; /***************************************************************** Caches *****************************************************************/ class cache_t { public: virtual ~cache_t() {} virtual enum cache_request_status access( new_addr_type addr, mem_fetch *mf, unsigned time, std::list &events ) = 0; }; bool was_write_sent( const std::list &events ); bool was_read_sent( const std::list &events ); class baseline_cache : public cache_t { public: baseline_cache( const char *name, const cache_config &config, int core_id, int type_id, mem_fetch_interface *memport, enum mem_fetch_status status ) : m_config(config), m_tag_array(config,core_id,type_id), m_mshrs(config.m_mshr_entries,config.m_mshr_max_merge) { m_name = name; assert(config.m_mshr_type == ASSOC); m_memport=memport; m_miss_queue_status = status; } void cycle(); // interface for response from lower memory level (model bandwidth restictions in caller) void fill( mem_fetch *mf, unsigned time ); bool waiting_for_fill( mem_fetch *mf ); // are any (accepted) accesses that had to wait for memory now ready? (does not include accesses that "HIT") bool access_ready() const {return m_mshrs.access_ready();} // pop next ready access (does not include accesses that "HIT") mem_fetch *next_access(){return m_mshrs.next_access();} // flash invalidate all entries in cache void flush(){m_tag_array.flush();} void print(FILE *fp, unsigned &accesses, unsigned &misses) const; void display_state( FILE *fp ) const; protected: std::string m_name; const cache_config &m_config; tag_array m_tag_array; mshr_table m_mshrs; std::list m_miss_queue; enum mem_fetch_status m_miss_queue_status; mem_fetch_interface *m_memport; struct extra_mf_fields { extra_mf_fields() { m_valid = false;} extra_mf_fields( new_addr_type a, unsigned i, unsigned d ) { m_valid = true; m_block_addr = a; m_cache_index = i; m_data_size = d; } bool m_valid; new_addr_type m_block_addr; unsigned m_cache_index; unsigned m_data_size; }; typedef std::map extra_mf_fields_lookup; extra_mf_fields_lookup m_extra_mf_fields; bool miss_queue_full(unsigned num_miss){ // Checks whether this request can be handled on this cycle. num_miss equals max # of misses to be handled on this cycle return ( (m_miss_queue.size()+num_miss) >= m_config.m_miss_queue_size ); } void read_request(new_addr_type addr, new_addr_type block_addr, unsigned cache_index, mem_fetch *mf, unsigned time, bool &do_miss, std::list &events, bool read_only); void read_request(new_addr_type addr, new_addr_type block_addr, unsigned cache_index, mem_fetch *mf, unsigned time, bool &do_miss, bool &wb, cache_block_t &evicted, std::list &events, bool read_only); }; class read_only_cache : public baseline_cache { public: read_only_cache( const char *name, const cache_config &config, int core_id, int type_id, mem_fetch_interface *memport, enum mem_fetch_status status ) : baseline_cache(name,config,core_id,type_id,memport,status){} // access cache: returns RESERVATION_FAIL if request could not be accepted (for any reason) virtual enum cache_request_status access( new_addr_type addr, mem_fetch *mf, unsigned time, std::list &events ); }; // This is meant to model the first level data cache in Fermi. // It is write-evict (global) or write-back (local) at the granularity // of individual blocks (the policy used in fermi according to the CUDA manual) class data_cache : public baseline_cache { public: data_cache( const char *name, const cache_config &config, int core_id, int type_id, mem_fetch_interface *memport, mem_fetch_allocator *mfcreator, enum mem_fetch_status status ) : baseline_cache(name,config,core_id,type_id,memport,status) { m_memfetch_creator=mfcreator; } virtual enum cache_request_status access( new_addr_type addr, mem_fetch *mf, unsigned time, std::list &events ); private: mem_fetch_allocator *m_memfetch_creator; // Private functions for data cache access void write_request(mem_fetch *mf, cache_event request, unsigned time, std::list &events); }; /********************************************************************************************************************************************************/ // See the following paper to understand this cache model: // // Igehy, et al., Prefetching in a Texture Cache Architecture, // Proceedings of the 1998 Eurographics/SIGGRAPH Workshop on Graphics Hardware // http://www-graphics.stanford.edu/papers/texture_prefetch/ class tex_cache : public cache_t { public: tex_cache( const char *name, const cache_config &config, int core_id, int type_id, mem_fetch_interface *memport, enum mem_fetch_status request_status, enum mem_fetch_status rob_status ) : m_config(config), m_tags(config,core_id,type_id), m_fragment_fifo(config.m_fragment_fifo_entries), m_request_fifo(config.m_request_fifo_entries), m_rob(config.m_rob_entries), m_result_fifo(config.m_result_fifo_entries) { m_name = name; assert(config.m_mshr_type == TEX_FIFO); assert(config.m_write_policy == READ_ONLY); assert(config.m_alloc_policy == ON_MISS); m_memport=memport; m_cache = new data_block[ config.get_num_lines() ]; m_request_queue_status = request_status; m_rob_status = rob_status; } // return values: RESERVATION_FAIL if request could not be accepted // otherwise returns HIT_RESERVED or MISS; NOTE: *never* returns HIT // since unlike a normal CPU cache, a "HIT" in texture cache does not // mean the data is ready (still need to get through fragment fifo) enum cache_request_status access( new_addr_type addr, mem_fetch *mf, unsigned time, std::list &events ); void cycle(); // place returning cache block into reorder buffer void fill( mem_fetch *mf, unsigned time ); // are any (accepted) accesses that had to wait for memory now ready? (does not include accesses that "HIT") bool access_ready() const{return !m_result_fifo.empty();} // pop next ready access (includes both accesses that "HIT" and those that "MISS") mem_fetch *next_access(){return m_result_fifo.pop();} void display_state( FILE *fp ) const; private: std::string m_name; const cache_config &m_config; struct fragment_entry { fragment_entry() {} fragment_entry( mem_fetch *mf, unsigned idx, bool m, unsigned d ) { m_request=mf; m_cache_index=idx; m_miss=m; m_data_size=d; } mem_fetch *m_request; // request information unsigned m_cache_index; // where to look for data bool m_miss; // true if sent memory request unsigned m_data_size; }; struct rob_entry { rob_entry() { m_ready = false; m_time=0; m_request=NULL;} rob_entry( unsigned i, mem_fetch *mf, new_addr_type a ) { m_ready=false; m_index=i; m_time=0; m_request=mf; m_block_addr=a; } bool m_ready; unsigned m_time; // which cycle did this entry become ready? unsigned m_index; // where in cache should block be placed? mem_fetch *m_request; new_addr_type m_block_addr; }; struct data_block { data_block() { m_valid = false;} bool m_valid; new_addr_type m_block_addr; }; // TODO: replace fifo_pipeline with this? template class fifo { public: fifo( unsigned size ) { m_size=size; m_num=0; m_head=0; m_tail=0; m_data = new T[size]; } bool full() const { return m_num == m_size;} bool empty() const { return m_num == 0;} unsigned size() const { return m_num;} unsigned capacity() const { return m_size;} unsigned push( const T &e ) { assert(!full()); m_data[m_head] = e; unsigned result = m_head; inc_head(); return result; } T pop() { assert(!empty()); T result = m_data[m_tail]; inc_tail(); return result; } const T &peek( unsigned index ) const { assert( index < m_size ); return m_data[index]; } T &peek( unsigned index ) { assert( index < m_size ); return m_data[index]; } T &peek() const { return m_data[m_tail]; } unsigned next_pop_index() const { return m_tail; } private: void inc_head() { m_head = (m_head+1)%m_size; m_num++;} void inc_tail() { assert(m_num>0); m_tail = (m_tail+1)%m_size; m_num--;} unsigned m_head; // next entry goes here unsigned m_tail; // oldest entry found here unsigned m_num; // how many in fifo? unsigned m_size; // maximum number of entries in fifo T *m_data; }; tag_array m_tags; fifo m_fragment_fifo; fifo m_request_fifo; fifo m_rob; data_block *m_cache; fifo m_result_fifo; // next completed texture fetch mem_fetch_interface *m_memport; enum mem_fetch_status m_request_queue_status; enum mem_fetch_status m_rob_status; struct extra_mf_fields { extra_mf_fields() { m_valid = false;} extra_mf_fields( unsigned i ) { m_valid = true; m_rob_index = i; } bool m_valid; unsigned m_rob_index; }; typedef std::map extra_mf_fields_lookup; extra_mf_fields_lookup m_extra_mf_fields; }; #endif