diff options
Diffstat (limited to 'src/gpgpu-sim/dwf.cc')
| -rw-r--r-- | src/gpgpu-sim/dwf.cc | 2609 |
1 files changed, 2609 insertions, 0 deletions
diff --git a/src/gpgpu-sim/dwf.cc b/src/gpgpu-sim/dwf.cc new file mode 100644 index 0000000..cd66084 --- /dev/null +++ b/src/gpgpu-sim/dwf.cc @@ -0,0 +1,2609 @@ +/* + * dwf.cc + * + * Copyright (c) 2009 by Tor M. Aamodt, Wilson W. L. Fung, and the + * University of British Columbia + * Vancouver, BC V6T 1Z4 + * All Rights Reserved. + * + * THIS IS A LEGAL DOCUMENT BY DOWNLOADING GPGPU-SIM, YOU ARE AGREEING TO THESE + * TERMS AND CONDITIONS. + * + * 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 OWNERS 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. + * + * NOTE: The files libcuda/cuda_runtime_api.c and src/cuda-sim/cuda-math.h + * are derived from the CUDA Toolset available from http://www.nvidia.com/cuda + * (property of NVIDIA). The files benchmarks/BlackScholes/ and + * benchmarks/template/ are derived from the CUDA SDK available from + * http://www.nvidia.com/cuda (also property of NVIDIA). The files from + * src/intersim/ are derived from Booksim (a simulator provided with the + * textbook "Principles and Practices of Interconnection Networks" available + * from http://cva.stanford.edu/books/ppin/). As such, those files are bound by + * the corresponding legal terms and conditions set forth separately (original + * copyright notices are left in files from these sources and where we have + * modified a file our copyright notice appears before the original copyright + * notice). + * + * Using this version of GPGPU-Sim requires a complete installation of CUDA + * which is distributed seperately by NVIDIA under separate terms and + * conditions. To use this version of GPGPU-Sim with OpenCL requires a + * recent version of NVIDIA's drivers which support OpenCL. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. 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. + * + * 3. 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. + * + * 4. This version of GPGPU-SIM is distributed freely for non-commercial use only. + * + * 5. No nonprofit user may place any restrictions on the use of this software, + * including as modified by the user, by any other authorized user. + * + * 6. GPGPU-SIM was developed primarily by Tor M. Aamodt, Wilson W. L. Fung, + * Ali Bakhoda, George L. Yuan, at the University of British Columbia, + * Vancouver, BC V6T 1Z4 + */ + + +#include "dwf.h" +#include "histogram.h" +#include <map> +#include <set> +#include <deque> +#include <queue> +#include <string.h> + +using namespace std; + +unsigned int gpgpu_dwf_regbk = 1; +unsigned int gpgpu_dwf_heuristic = 0; +enum { + MAJORITY = 0, + MINORITY = 1, + FIFO = 2, + PDOMPRIO = 3, + PC = 4, + MAJORITY_MAXHEAP = 5, + N_DWFMODE +}; + +typedef struct warp_entry { + address_type pc; + int* tid; // thread id's + int occ; // occupancy vector + int pdom_prio; // pdom_priority + int pdom_occ; // pdom_priority's aux data + int next_warp; // index to next warp in an implicit queue + void* lut_ptr; // pointer to the warp lut entry that last update this warp (a hack), done to decouple warp lut and warp pool + int uid; // unique id of a warp +} warp_entry_t; + +class issue_warp_majority { +public: + + virtual void add_threads( address_type pc, int *tid) = 0; + virtual void push_warp( address_type pc, int idx) = 0; + virtual int pop_warp( ) = 0; + virtual void print( FILE *fout ) = 0; + virtual ~issue_warp_majority( ) {} +}; + +typedef struct maxheap_lut_entry { + address_type pc; // pc of the warps + int maxheap_idx; // index to the max heap +} maxheap_lut_entry_t; + +typedef struct maxheap_entry { + address_type pc; // pc of the warps + int n_thds; // number of threads with this pc (from lut) + int wpool_head; // the first warp with this pc + int wpool_tail; // the last warp with this pc + int lut_idx; // reverse index to the lut (for update in entry movement) +} maxheap_entry_t; + +class mh_lut_class { +private: + + maxheap_lut_entry_t *lut_data; + list<int> *lru_stack; // front = LRU + int n_set; + int insn_size_lgb2; + +public: + + int size; + int assoc; + int n_read; + int n_write; + int n_read_per_cycle; + int n_write_per_cycle; + + int n_aliased; + static maxheap_lut_entry_t clean_entry; + + mh_lut_class (int size, int assoc, int n_read_per_cycle, int n_write_per_cycle ) { + int i; + + this->size = size; + this->assoc = assoc; + lut_data = new maxheap_lut_entry_t[size]; + + for (i=0; i<size; i++) { + lut_data[i] = clean_entry; + } + + n_set = size/assoc; + assert(n_set && !((n_set - 1) & n_set)); // make sure n_set is a power of 2 + + insn_size_lgb2 = 0; + + lru_stack = new list<int>[n_set]; + for (i=0; i<n_set; i++) { + int j; + for (j=0; j<assoc; j++) { + lru_stack[i].push_back(i * assoc + j); + } + } + + this->n_read_per_cycle = n_read_per_cycle; + this->n_write_per_cycle = n_write_per_cycle; + this->n_read = 0; + this->n_write = 0; + this->n_aliased = 0; + } + + ~mh_lut_class ( ) { + delete[] lut_data; + } + + // obtain entry at a known location + maxheap_lut_entry_t get( int lut_idx ) { + assert(lut_idx < size); + n_read++; + return lut_data[lut_idx]; + } + + // modify an entry at a known location + void set( int lut_idx, maxheap_lut_entry_t lut_entry ) { + n_write++; + lut_data[lut_idx] = lut_entry; + } + + // update a lut entry with a new index + void update_mh_idx( int lut_idx, int mh_idx ) { + n_write++; + lut_data[lut_idx].maxheap_idx = mh_idx; + } + + // lookup an entry with a pc + int lookup( address_type pc ) { + int i; + int lut_idx = -1; + int set_start_idx = get_set(pc) * assoc; + + // look for the matched entry within the set + for (i = set_start_idx; i < (set_start_idx + assoc); i++) { + if (lut_data[i].pc == pc) { + lut_idx = i; + } + } + + // update lru stack if hit + if (lut_idx != -1) { + int set_idx = set_start_idx / assoc; + list<int>::iterator it; + it = find(lru_stack[set_idx].begin(), lru_stack[set_idx].end(), lut_idx); + + if (it != lru_stack[set_idx].end()) { + lru_stack[set_idx].erase(it); + lru_stack[set_idx].push_back(lut_idx); + } + } + + return lut_idx; + } + + void free(int lut_idx) { + set(lut_idx, clean_entry); + + int set_idx = lut_idx / assoc; + list<int>::iterator it; + it = find(lru_stack[set_idx].begin(), lru_stack[set_idx].end(), lut_idx); + + if (it != lru_stack[set_idx].end()) { + lru_stack[set_idx].erase(it); + lru_stack[set_idx].push_front(lut_idx); + } + } + + // find the LRU entry to be replaced + int find_lru( maxheap_lut_entry_t lut_entry ) { + int set_idx = get_set(lut_entry.pc); + int lru_idx = lru_stack[set_idx].front(); + + return lru_idx; + } + + // actually replacing the LRU entry + int replace_lru( maxheap_lut_entry_t lut_entry ) { + int set_idx = get_set(lut_entry.pc); + int lru_idx = lru_stack[set_idx].front(); + lru_stack[set_idx].pop_front(); + + // counting the number of overwritten entries + if (lut_data[lru_idx].maxheap_idx != 0) n_aliased++; + + set(lru_idx, lut_entry); + lru_stack[set_idx].push_back(lru_idx); + + return lru_idx; + } + + // reset the number of accesses to zero + void reset_access( ) { + n_read = 0; + n_write = 0; + } + + // clear the number of accesses - done at the end of scheduler cycle + void clear_access( ) { + n_read -= n_read_per_cycle; + n_read = (n_read >= 0)? n_read : 0; + n_write -= n_write_per_cycle; + n_write = (n_write >= 0)? n_write : 0; + } + + // test if the structure is done with all the required accesses + int all_access_done( ) { + return(n_read == 0 && n_write == 0); + } + + void print_lut_e(FILE *fout, maxheap_lut_entry_t lut_e) { + fprintf(fout, "[%08x]mh%02d", + lut_e.pc, lut_e.maxheap_idx); + } + + void print(FILE *fout) { + int i, j; + for (i=0; i<n_set; i++) { + fprintf(fout, "S%02d", i); + for (j=0; j<assoc; j++) { + fprintf(fout, " |%02d:", i * assoc + j); + print_lut_e(fout, lut_data[i * assoc + j]); + } + fprintf(fout, " "); + list<int>::iterator it = lru_stack[i].begin(); + for (; it != lru_stack[i].end(); it++) { + fprintf(fout, "%02d-", *it); + } + fprintf(fout, "\n"); + } + } + +private: + + inline int get_set(address_type pc) { + return((pc >> insn_size_lgb2) & (n_set - 1)); + } +}; + +maxheap_lut_entry_t mh_lut_class::clean_entry = {0xDEADBEEF, 0}; + +// A class tracking the number of accesses done to the maxheap structure +// and the index ranges from 1..n_entries with 1 being the root +class maxheap_class { +private: + + maxheap_entry_t *maxheap_data; + mh_lut_class *lut; + +public: + + int n_read; + int n_write; + int n_entries; + int size; + int n_read_per_cycle; + int n_write_per_cycle; + + int max_n_entries; + static maxheap_entry_t clean_entry; + + maxheap_class( int size, mh_lut_class *lut, int n_read_per_cycle, int n_write_per_cycle ) { + n_read = 0; + n_write = 0; + n_entries = 0; // index to the last element + this->size = size; + maxheap_data = new maxheap_entry_t[size]; + + for (int i=0; i<size; i++) { + maxheap_data[i] = clean_entry; + } + + this->lut = lut; + + this->n_read_per_cycle = n_read_per_cycle; + this->n_write_per_cycle = n_write_per_cycle; + this->n_read = 0; + this->n_write = 0; + this->max_n_entries = 0; + } + + ~maxheap_class( ) { + delete[] maxheap_data; + } + + // insert a new entry into the maxheap + // return: the index to the new entry + int insert( maxheap_entry_t mh_entry ) { + assert(n_entries + 1 < size); + n_write++; + n_entries++; + maxheap_data[n_entries] = mh_entry; + max_n_entries = (max_n_entries >= n_entries)? max_n_entries : n_entries; + return n_entries; + } + + // retrieve the max heap entry at index [mh_idx] + maxheap_entry_t get( int mh_idx ) { + assert(mh_idx > 0); + assert(mh_idx <= n_entries); + n_read++; + return maxheap_data[mh_idx]; + } + + // replace the max heap entry at index [mh_idx] + void set( int mh_idx, maxheap_entry_t mh_entry ) { + assert(mh_idx > 0); + assert(mh_idx <= n_entries); + n_write++; + maxheap_data[mh_idx] = mh_entry; + } + + // a special version of set that only reset the lut_idx + void remove_lut_idx( int mh_idx ) { + assert(mh_idx > 0); + assert(mh_idx <= n_entries); + n_write++; + maxheap_data[mh_idx].lut_idx = -1; + } + + // read both childrens of a given node, count as one read + // return the number of child read + int get_childof(int mh_idx, maxheap_entry_t *child) { + int child_idx = childof(mh_idx); + int child_read = 0; + + if (child_idx <= n_entries) { + n_read++; + child[0] = maxheap_data[child_idx]; + child_read++; + } + if (child_idx + 1 <= n_entries) { + child[1] = maxheap_data[child_idx + 1]; + child_read++; + } + + return child_read; + } + + // pop the root entry of max heap + maxheap_entry_t pop_root( ) { + maxheap_entry_t old_root = get(1); + maxheap_entry_t curr_mhe[3]; + curr_mhe[0] = get(n_entries); + + set(1, curr_mhe[0]); + if (curr_mhe[0].lut_idx >= 0) + lut->update_mh_idx(curr_mhe[0].lut_idx, 1); + + n_entries--; + + int curr_node = 1; + int n_child = 0; + + n_child = get_childof(curr_node, curr_mhe + 1); + while (n_child > 0) { + int max_child = 0; + int i; + for (i = 1; i < n_child + 1; i++) { + if (cmp_mh(curr_mhe[i], curr_mhe[max_child])) { + max_child = i; + } + } + + n_child = 0; + if (max_child > 0) { + int max_child_node = childof(curr_node) + max_child - 1; + set(curr_node, curr_mhe[max_child]); + set(max_child_node, curr_mhe[0]); + + // update the lut for this swap + if (curr_mhe[max_child].lut_idx >= 0) + lut->update_mh_idx(curr_mhe[max_child].lut_idx, curr_node); + if (curr_mhe[0].lut_idx >= 0) + lut->update_mh_idx(curr_mhe[0].lut_idx, max_child_node); + + // get the next child + curr_node = max_child_node; + n_child = get_childof(curr_node, curr_mhe + 1); + } + } + + return old_root; + } + + // probe if the maxheap is empty + int empty( ) { + return(n_entries == 0); + } + + // reset the number of accesses to zero + void reset_access( ) { + n_read = 0; + n_write = 0; + } + + // clear the number of accesses - done at the end of scheduler cycle + void clear_access( ) { + n_read -= n_read_per_cycle; + n_read = (n_read >= 0)? n_read : 0; + n_write -= n_write_per_cycle; + n_write = (n_write >= 0)? n_write : 0; + } + + // test if the structure is done with all the required accesses + int all_access_done( ) { + return(n_read == 0 && n_write == 0); + } + + // sort the max heap again starting from start_idx + // (this entry can only go up in the tree to the root) + void sort_bottomup(int start_idx) { + maxheap_entry_t mh_entry; + maxheap_entry_t mh_parent; + + if (start_idx == 1) return; // no need to resort if the root is incremented + + int curr_idx = start_idx; + int parent_idx = parentof(start_idx); + + int continue_sort = 1; + while (curr_idx > 1 && continue_sort) { + mh_entry = get(curr_idx); + mh_parent = get(parent_idx); + + // swap the entries if it is now larger than it's parent + if (cmp_mh(mh_entry, mh_parent)) { + set(parent_idx, mh_entry); + set(curr_idx, mh_parent); + + // update the lut for this swap + if (mh_entry.lut_idx >= 0) + lut->update_mh_idx(mh_entry.lut_idx, parent_idx); + if (mh_parent.lut_idx >= 0) + lut->update_mh_idx(mh_parent.lut_idx, curr_idx); + + // update index for next iteration + curr_idx = parent_idx; + parent_idx = parentof(curr_idx); + } else { + // swap did not happen, no need to sort anymore + continue_sort = 0; + } + } + } + + void print_mh_e(FILE *fout, maxheap_entry_t mh_e) { + fprintf(fout, "[%08x]%03d(H%03dT%03d)p%02d | ", + mh_e.pc, mh_e.n_thds, mh_e.wpool_head, mh_e.wpool_tail, mh_e.lut_idx); + } + + void print(FILE *fout) { + fprintf(fout, "MaxHeap: "); + fprintf(fout, "N_entries = %d\n", n_entries); + for (int i=0; i<n_entries; i++) { + print_mh_e(fout, maxheap_data[i + 1]); + if (!((i + 2) & (i + 1))) fprintf(fout, "\n"); + } + fprintf(fout, "\n"); + } + +private: + + static inline int parentof(int mh_idx) { + assert(mh_idx > 0); + return(mh_idx / 2); + } + + static inline int childof(int mh_idx) { + return(mh_idx * 2); + } + + static inline int cmp_mh(maxheap_entry_t &a, maxheap_entry_t &b) { + if (a.n_thds > b.n_thds) return 1; + if (a.n_thds == b.n_thds) { + if (a.pc < b.pc) return 1; + } + return 0; + } + +}; + +maxheap_entry_t maxheap_class::clean_entry = {0, 0, -1, -1, -1}; + +typedef struct mh_update_struct { + int n_maxheap_read; + int n_maxheap_write; + int n_mhlut_read; + int n_mhlut_write; +} mh_update; + +// heap implementation of majority policy +class issue_warp_majority_heap : public issue_warp_majority { +public: + + mh_lut_class mh_lut; + maxheap_class maxheap; + + maxheap_lut_entry_t major_lut_e; + maxheap_entry_t major_mh_e; + + vector<warp_entry_t> *warp_pool; + int simd_width; + + int n_stall_on_maxheap; + + queue<mh_update> update_queue; + static pow2_histogram n_pending_updates_histo; + + issue_warp_majority_heap (int simd_width = 0, vector<warp_entry_t> *bp = NULL, + int lut_size = 32, int lut_assoc = 4, int maxheap_size = 128, + int n_read_lut = 4, int n_write_lut = 4, + int n_read_mh = 4, int n_write_mh = 4) + : mh_lut(lut_size, lut_assoc, n_read_lut, n_write_lut), + maxheap(maxheap_size, &mh_lut, n_read_mh, n_write_mh) + { + this->simd_width = simd_width; + this->warp_pool = bp; + + this->major_lut_e = mh_lut_class::clean_entry; + this->major_mh_e = maxheap_class::clean_entry; + + this->n_stall_on_maxheap = 0; + } + + // adding more threads to a specify pc + // these threads may end up in different warpes + void add_threads( address_type pc, int *tid) { + int i; + int n_thds = 0; + for (i=0; i<simd_width; i++) { + if (tid[i] >= 0) n_thds++; + } + + // handle special case with adding threads to current majority pc + if (major_lut_e.pc == pc) { + assert(major_mh_e.pc == pc); + major_mh_e.n_thds += n_thds; + return; + } + + maxheap_lut_entry_t lut_e; + maxheap_entry_t mh_entry; + + // snapshot the current maxheap read/write demand + mh_update new_mh_update; + new_mh_update.n_maxheap_read = maxheap.n_read; + new_mh_update.n_maxheap_write = maxheap.n_write; + new_mh_update.n_mhlut_read = mh_lut.n_read; + new_mh_update.n_mhlut_write = mh_lut.n_write; + + int lut_idx = mh_lut.lookup(pc); + + int sort_from_idx = 0; + + if (lut_idx >= 0) { + // obtain the entry + lut_e = mh_lut.get(lut_idx); + + // get the maxheap entry and update its number of threads + mh_entry = maxheap.get(lut_e.maxheap_idx); + mh_entry.n_thds += n_thds; + maxheap.set(lut_e.maxheap_idx, mh_entry); + + // sort from this specific entry + sort_from_idx = lut_e.maxheap_idx; + } else { + // create a new lut entry + lut_e = mh_lut_class::clean_entry; + lut_e.pc = pc; + + // get index to the LRU lut entry in this set + lut_idx = mh_lut.find_lru(lut_e); + + // get the replaced lut entry and remove its link with the maxheap entry + maxheap_lut_entry_t lut_old = mh_lut.get(lut_idx); + if (lut_old.maxheap_idx > 0) maxheap.remove_lut_idx(lut_old.maxheap_idx); + + // create a new maxheap entry + mh_entry = maxheap_class::clean_entry; + mh_entry.pc = pc; + mh_entry.n_thds = n_thds; + mh_entry.lut_idx = lut_idx; + + // push the new entry into the maxheap and lut respectively + lut_e.maxheap_idx = maxheap.insert(mh_entry); + mh_lut.replace_lru(lut_e); + + // start sorting from the bottom? + sort_from_idx = lut_e.maxheap_idx; + } + + maxheap.sort_bottomup(sort_from_idx); + + // record the newly generated maxheap read/write demand from this update + new_mh_update.n_maxheap_read = maxheap.n_read - new_mh_update.n_maxheap_read; + new_mh_update.n_maxheap_write = maxheap.n_write - new_mh_update.n_maxheap_write; + new_mh_update.n_mhlut_read = mh_lut.n_read - new_mh_update.n_mhlut_read; + new_mh_update.n_mhlut_write = mh_lut.n_write - new_mh_update.n_mhlut_write; + + update_queue.push(new_mh_update); + } + + // call this when a new warp allocated for a specific pc + void push_warp( address_type pc, int idx) { + maxheap_entry_t *p_mh_e = NULL; + maxheap_entry_t mh_e; + maxheap_lut_entry_t lut_e = mh_lut_class::clean_entry; + int lut_idx = -1; + + if (major_mh_e.pc == pc) { + p_mh_e = &major_mh_e; + } else { + lut_idx = mh_lut.lookup(pc); + assert(lut_idx >= 0); // if it is a miss, a new entry should have been created already + lut_e = mh_lut.get(lut_idx); + mh_e = maxheap.get(lut_e.maxheap_idx); + p_mh_e = &mh_e; + + // discounting these 'gets' + // because they should be combined with the 'gets' in add_threads() + mh_lut.n_read--; + maxheap.n_read--; + } + + if (p_mh_e->wpool_head == -1) { + p_mh_e->wpool_head = idx; + p_mh_e->wpool_tail = idx; + } else { + (*warp_pool)[p_mh_e->wpool_tail].next_warp = idx; + p_mh_e->wpool_tail = idx; + } + + if (major_mh_e.pc == pc) { + } else { + maxheap.set(lut_e.maxheap_idx, mh_e); + // discounting this 'set' + // because it should be combined with the 'set' in add_threads() + maxheap.n_write--; + } + } + + // obtain a warp index from this issue logic + int pop_warp( ) { + int bidx = -1; + if (major_mh_e.wpool_head == -1 && !maxheap.empty()) { + if (this->all_access_done( )) { + // pop the majority PC from max heap + major_mh_e = maxheap.pop_root(); + + // pop its corresponding entry from the lut as well (if it exists) + if (major_mh_e.lut_idx >= 0) { + major_lut_e = mh_lut.get(major_mh_e.lut_idx); + mh_lut.free(major_mh_e.lut_idx); + } else { + major_lut_e = mh_lut_class::clean_entry; + } + } else { + n_stall_on_maxheap += 1; + bidx = -1; + return bidx; + } + } + + // just pop and entry to from the virtual queue (and set the head pointer to next warp) + bidx = major_mh_e.wpool_head; + if (bidx >= 0) { + major_mh_e.wpool_head = (*warp_pool)[major_mh_e.wpool_head].next_warp; + } + + return bidx; + } + + void reset_access( ) { + maxheap.reset_access(); + mh_lut.reset_access(); + + while (!update_queue.empty()) { + update_queue.pop(); + } + } + + inline void consume_access( int &req_acc, int &avl_acc) { + if (req_acc > avl_acc) { + req_acc -= avl_acc; + avl_acc = 0; + } else { + avl_acc -= req_acc; + req_acc = 0; + } + } + + void clear_access( ) { + maxheap.clear_access(); + mh_lut.clear_access(); + + int n_maxheap_read_bw = maxheap.n_read_per_cycle; + int n_maxheap_write_bw = maxheap.n_write_per_cycle; + int n_mhlut_read_bw = mh_lut.n_read_per_cycle; + int n_mhlut_write_bw = mh_lut.n_write_per_cycle; + + while ((n_maxheap_read_bw > 0 || n_maxheap_read_bw > 0 || + n_mhlut_read_bw > 0 || n_mhlut_write_bw > 0) && !update_queue.empty()) { + mh_update &c_update = update_queue.front(); + + consume_access (c_update.n_maxheap_read, n_maxheap_read_bw); + consume_access (c_update.n_maxheap_write, n_maxheap_write_bw); + consume_access (c_update.n_mhlut_read, n_mhlut_read_bw); + consume_access (c_update.n_mhlut_write, n_mhlut_write_bw); + + if (c_update.n_maxheap_read == 0 && c_update.n_maxheap_write == 0 && + c_update.n_mhlut_read == 0 && c_update.n_mhlut_write == 0) { + update_queue.pop(); + } else { + break; + } + } + + n_pending_updates_histo.add2bin(update_queue.size()); + } + + void print( FILE *fout ) { + fprintf(fout, "LUT: "); + mh_lut.print_lut_e(fout, major_lut_e); + fprintf(fout, " \tMH: "); + maxheap.print_mh_e(fout, major_mh_e); + fprintf(fout, "\n"); + mh_lut.print(fout); + maxheap.print(fout); + } + + static void print_stat( FILE *fout) { + fprintf(fout, "n_pending_maxheap_updates = "); + n_pending_updates_histo.fprint(fout); + fprintf(fout, "\n"); + } + +private: + + int all_access_done( ) { + return(maxheap.all_access_done() && mh_lut.all_access_done()); + + } +}; +pow2_histogram issue_warp_majority_heap::n_pending_updates_histo; + +class warp_queue { +public: + int m_pc; + int n_thds; + int simd_width; + deque<int> idx_queue; + + warp_queue( address_type pc, int simd_width) { + this->m_pc = pc; + this->n_thds = 0; + this->simd_width = simd_width; + } + + // called right after a lut_entry is looked up + void add_threads( int *tid ) { + for (int i=0; i<simd_width; i++) { + if (tid[i] >= 0) this->n_thds++; + } + } + + // called right after a warp is issued + void sub_threads( int *tid ) { + for (int i=0; i<simd_width; i++) { + if (tid[i] >= 0) this->n_thds--; + } + } + + // if other warp queue should be ahead + bool operator<(const warp_queue& other) const { + if (n_thds == other.n_thds) { + return(m_pc > other.m_pc); // smaller pc first + } else { + return(n_thds < other.n_thds); + } + } + bool operator>(const warp_queue& other) const { + if (n_thds == other.n_thds) { + return(m_pc > other.m_pc); // smaller pc first + } else { + return(n_thds > other.n_thds); + } + } + + void print( FILE *fout ) { + fprintf(fout, "0x%08x(%03d)=[", m_pc, n_thds); + deque<int>::iterator dit = idx_queue.begin(); + for (; dit != idx_queue.end(); dit++) { + fprintf(fout, "%03d ", *dit); + } + fprintf(fout, "]\n"); + } +}; + +bool minor_warp( const warp_queue* a, const warp_queue* b ) { + return(*a<*b); +} + +// queue implementation of majority scheduling policy +class issue_warp_majority_queue : public issue_warp_majority { +public: + map<address_type, warp_queue* > majority_map; + set<warp_queue*> warpq_set; + warp_queue* maj_warp; + + vector<warp_entry_t> *warp_pool; + int simd_width; + + issue_warp_majority_queue(int simd_width = 0, vector<warp_entry_t> *bp = NULL) { + this->maj_warp = NULL; + this->simd_width = simd_width; + this->warp_pool = bp; + } + + // adding more threads to a specify pc + // these threads may end up in different warps + void add_threads( address_type pc, int *tid) { + warp_queue* bq = majority_map[pc]; + if (bq == NULL) { + bq = new warp_queue(pc,simd_width); + warpq_set.insert(bq); + majority_map[pc] = bq; + } + bq->add_threads(tid); + } + + // call this when a new warp allocated for a specific pc + void push_warp( address_type pc, int idx) { + warp_queue* bq = majority_map[pc]; + assert(bq != NULL); + bool check_redundant_idx = false; + if (check_redundant_idx) { + deque<int>::iterator dit = find(bq->idx_queue.begin(), bq->idx_queue.end(), idx); + assert(dit == bq->idx_queue.end()); + } + bq->idx_queue.push_back(idx); + } + + // obtain a warp index from this issue logic + int pop_warp( ) { + int bidx = -1; + + // find the new majority pc if it didn't exist + if (maj_warp == NULL && warpq_set.size()) { + maj_warp = *max_element(warpq_set.begin(), warpq_set.end(), minor_warp); + } + + // if a majority pc indeed exist + if (maj_warp) { + assert(!maj_warp->idx_queue.empty()); + bidx = maj_warp->idx_queue.front(); + maj_warp->idx_queue.pop_front(); + maj_warp->sub_threads((*warp_pool)[bidx].tid); + + // when the majority pc runs out of thread + if (maj_warp->n_thds == 0) { + // remove that warp queue + warpq_set.erase(maj_warp); + majority_map.erase(maj_warp->m_pc); + delete maj_warp; + maj_warp = NULL; + } + } + + return bidx; + } + + void print( FILE *fout ) { + fprintf(fout, "issue_warp_majority:\n"); + set<warp_queue*>::iterator dit = warpq_set.begin(); + for (; dit != warpq_set.end(); dit++) { + fprintf(fout, " %c ", ((*dit)==maj_warp)? 'M':' '); + (*dit)->print(fout); + } + } + + void check_consistency( ) { + set<warp_queue*>::iterator set_it = warpq_set.begin(); + for (; set_it != warpq_set.end(); set_it++) { + warp_queue* bq = (*set_it); + + int real_nthds = 0; + deque<int>::iterator dit = bq->idx_queue.begin(); + for (; dit != bq->idx_queue.end(); dit++) { + int *tid = (*warp_pool)[*dit].tid; + for (int i = 0; i < simd_width; i++) { + real_nthds += (tid[i] >= 0)? 1 : 0; + } + } + + assert(real_nthds == bq->n_thds); + } + } +}; + +// pdom priority +class lesspdom_first { +public: + vector<warp_entry_t> *warp_pool; + lesspdom_first( vector<warp_entry_t> *bp=NULL ) { + this->warp_pool = bp; + } + bool operator() (const int &idx_a, const int &idx_b) const { + if ((*warp_pool)[idx_a].pdom_prio != (*warp_pool)[idx_b].pdom_prio) { + return((*warp_pool)[idx_a].pdom_prio < (*warp_pool)[idx_b].pdom_prio); + } else { + return((*warp_pool)[idx_a].occ > (*warp_pool)[idx_b].occ); + } + } +}; + + +class issue_warp_pdom_prio { +public: + vector<warp_entry_t> *warp_pool; + int* thd_pdom_prio; + int simd_width; + int n_threads; + + int resort_needed; + list<int> pdom_pqueue; //the queue holding all index + + lesspdom_first lesspdom_cmp; + + static set<address_type> reconvgence_pt; //table holding all recvg pt + + issue_warp_pdom_prio (int simd_width = 0, vector<warp_entry_t> *bp = NULL, + int n_threads = 0) + : lesspdom_cmp(bp) + { + this->simd_width = simd_width; + this->warp_pool = bp; + this->n_threads = n_threads; + this->thd_pdom_prio = new int[n_threads]; + memset(this->thd_pdom_prio, 0, sizeof(int)*n_threads); + this->resort_needed = 0; + } + + ~issue_warp_pdom_prio( ) { + delete[] this->thd_pdom_prio; + } + + void reinit( ) { + memset(this->thd_pdom_prio, 0, sizeof(int)*n_threads); + } + + // adding more threads to a warp + void add_threads( int idx, address_type pc) { + assert((*warp_pool)[idx].pc == pc); + + // check to see if this is a newly allocated warp + bool check_pdom = false; + if ((*warp_pool)[idx].pdom_prio == -1) { + check_pdom = true; + } + + // check for newly assigned threads to the warp + int pdom_occ = (*warp_pool)[idx].pdom_occ; + int *tid = (*warp_pool)[idx].tid; + for (int i=0; i<simd_width; i++) { + if (tid[i] >= 0 && !(pdom_occ & (1<<i))) { + if ((*warp_pool)[idx].pdom_prio < thd_pdom_prio[tid[i]]) { + (*warp_pool)[idx].pdom_prio = thd_pdom_prio[tid[i]]; + resort_needed = 1; + } + pdom_occ |= (1<<i); + } + } + if (check_pdom) { + if (reconvgence_pt.find(pc) != reconvgence_pt.end()) { + (*warp_pool)[idx].pdom_prio += 1; + } + } + } + + // call this when a new warp allocated for a specific pc + void push_warp( address_type pc, int idx ) { + assert((*warp_pool)[idx].pc == pc); + // initialize the pdom_prio for this newly allocated warp + (*warp_pool)[idx].pdom_prio = -1; + (*warp_pool)[idx].pdom_occ = 0; + pdom_pqueue.push_back(idx); + } + + // obtain a warp index from this issue logic + int front_warp( ) { + int bidx = -1; + + if (!pdom_pqueue.empty()) { + if (resort_needed) { + pdom_pqueue.sort(lesspdom_cmp); + resort_needed = 0; + } + + bidx = pdom_pqueue.front(); + } + + return bidx; + } + + int size( ) { + return pdom_pqueue.size(); + } + + void enforce_resort( ) { + resort_needed = 1; + } + + int pop_warp( ) { + int bidx = -1; + + if (!pdom_pqueue.empty()) { + if (resort_needed) { + pdom_pqueue.sort(lesspdom_cmp); + resort_needed = 0; + } + + bidx = pdom_pqueue.front(); + pdom_pqueue.pop_front(); + + // update the pdom prio of each thread inside a warp + for (int i=0; i<simd_width; i++) { + if ((*warp_pool)[bidx].tid[i] >= 0) { + thd_pdom_prio[(*warp_pool)[bidx].tid[i]] = (*warp_pool)[bidx].pdom_prio; + } + } + } + + return bidx; + } + +}; + +set<address_type> issue_warp_pdom_prio::reconvgence_pt = set<address_type>(); +//*/ + + +class npc_tracker_class { +public: + map<address_type, unsigned> pc_count; + unsigned* acc_pc_count; + int simd_width; + static map<unsigned, unsigned> histogram; + + npc_tracker_class( ) { + this->acc_pc_count = NULL; + this->simd_width = 0; + } + + npc_tracker_class(unsigned* acc_pc_count, int simd_width) { + this->acc_pc_count = acc_pc_count; + this->simd_width = simd_width; + } + + void add_threads( int *tid, address_type pc ) { + for (int i=0; i<simd_width; i++) { + if (tid[i] != -1) pc_count[pc] += 1; // automatically create a new entry if not exist + } + } + + void sub_threads( int *tid, address_type pc ) { + for (int i=0; i<simd_width; i++) { + if (tid[i] != -1) { + pc_count[pc] -= 1; + assert((int)pc_count[pc] >= 0); + if (pc_count[pc] == 0) pc_count.erase(pc); // manually erasing entries with 0 count + } + } + } + + void update_acc_count( ) { + (*acc_pc_count) += pc_count.size(); + histogram[pc_count.size()] += 1; + } + + unsigned count( ) { return pc_count.size();} + + static void histo_print( FILE* fout ) { + map<unsigned, unsigned>::iterator i; + fprintf(fout, "DYHW nPC Histogram: "); + for (i = histogram.begin(); i != histogram.end(); i++) { + fprintf(fout, "%d:%d ", i->first, i->second); + } + fprintf(fout, "\n"); + } +}; + +map<unsigned, unsigned> npc_tracker_class::histogram; + +class pc_tag { +private: + + address_type m_pc; + +public: + + pc_tag () { + this->reset(); + } + + pc_tag (const pc_tag& p) { this->m_pc = p.m_pc;} + pc_tag (const address_type& other_pc) { this->m_pc = other_pc;} + + pc_tag& operator=(const pc_tag& p) { m_pc = p.m_pc; return *this;} + pc_tag& operator=(const address_type& other_pc) { m_pc = other_pc; return *this;} + + inline bool operator==(const pc_tag& p) const { return(m_pc == p.m_pc);} + inline bool operator==(const address_type& other_pc) const { return(m_pc == other_pc);} + + inline bool operator!=(const pc_tag& p) const { return(m_pc != p.m_pc);} + inline bool operator!=(const address_type& other_pc) const { return(m_pc != other_pc);} + + inline bool operator<(const pc_tag& p) const { return(m_pc < p.m_pc);} + + inline void reset() { + m_pc = -1; + } + + inline address_type get_pc() const { return m_pc;} + + // the hash function to warp LUT + inline unsigned lut_hash( int insn_size_lgb2, int lut_nsets ) const { + return(m_pc >> insn_size_lgb2) & (lut_nsets - 1); + } + + inline void to_print(char *buffer, unsigned length) { + snprintf(buffer, length, "0x%08x", m_pc); + } +}; + +template <class Tag> +class tag2warp_entry_t { +public: + + Tag tag; + int idx; // pointing to warp pool + int occ; // occupancy vector + int accessed; // is the entry accessed this cycle + + tag2warp_entry_t () { + this->reset(); + } + + ~tag2warp_entry_t () {} + + tag2warp_entry_t (const tag2warp_entry_t& p) { + this->tag = p.tag; + this->idx = p.idx; + this->occ = p.occ; + this->accessed = p.accessed; + } + + tag2warp_entry_t& operator=(const tag2warp_entry_t& p) { + if (this != &p) { + tag = p.tag; + idx = p.idx; + occ = p.occ; + accessed = p.accessed; + } + return *this; + } + + inline bool operator==(const tag2warp_entry_t& p) const { + return(tag == p.tag); + } + + inline bool operator==(const Tag& test_tag) const { + return(tag == test_tag); + } + + inline bool operator()(const tag2warp_entry_t& p) const { + return(tag == p.tag); + } + + inline void reset() { + tag.reset(); + idx = 0; + occ = 0; + accessed = 0; + } + + void print( FILE *fout ) { + static char buffer[20]; + tag.to_print(buffer,20); + fprintf(fout, "\t%s->%03d (%02x)\n", buffer, idx, occ); + } + +}; + +template <class Tag> +class tag2warp_set { +public: + vector< tag2warp_entry_t<Tag> > entry; + list< tag2warp_entry_t<Tag>* > lru_stack; + + tag2warp_set(int assoc = 0) : entry(assoc) { + for (unsigned j=0; j<this->entry.size(); j++) { + this->lru_stack.push_back(&(this->entry[j])); + } + } + + tag2warp_set(const tag2warp_set& other) : entry(other.entry.size()) { + for (unsigned j=0; j<this->entry.size(); j++) { + this->lru_stack.push_back(&(this->entry[j])); + } + } + + tag2warp_set& operator=(const tag2warp_set& p) { + printf("tag2warp_set assignment operator called!\n"); + return *this; + } + + ~tag2warp_set() {} +}; + +template <class Tag> +class warp_lut { +public: + virtual ~warp_lut() {} + virtual tag2warp_entry_t<Tag>* lookup_pc2warp( const Tag& tag, bool& lut_missed ) = 0; + virtual void invalidate_entry( tag2warp_entry_t<Tag>* lut_entry, int warp_idx ) = 0; + virtual void clear_accessed( ) = 0; + virtual void print( FILE* fout) = 0; +}; + +template <class Tag> +class warp_lut_sa : public warp_lut<Tag> { +private: + int lut_size; + int lut_assoc; + vector< tag2warp_set<Tag> > tag2warp_lut; + int insn_size_lgb2; + + queue< tag2warp_entry_t<Tag>* > lut_accessed_q; // store accessed lut entry for clear + + struct same_tag { + Tag tag; + bool operator()(tag2warp_entry_t<Tag>* a) { + return(a->tag == tag); + } + }; + + static unsigned int lut_aliased; + +public: + warp_lut_sa(int lut_size, int lut_assoc, int insn_size) { + this->lut_size = lut_size; + this->lut_assoc = lut_assoc; + + // optimize for LUT hash function + insn_size_lgb2 = 0; + while ( (1 << insn_size_lgb2) < insn_size ) insn_size_lgb2++; + + // initialize the pc2warp LUT + // note: lut_size is the absolute size of LUT regardless of assoc. + this->tag2warp_lut.assign(lut_size/lut_assoc, tag2warp_set<Tag>(lut_assoc)); + + // assert on #set in LUT to be power of 2 + int lut_nset_pow2 = 1; + while ( lut_nset_pow2 < (int)tag2warp_lut.size() ) lut_nset_pow2 <<= 1; + assert((int)tag2warp_lut.size() == lut_nset_pow2); + } + + tag2warp_entry_t<Tag>* lookup_pc2warp( const Tag& tag, bool& lut_missed ); + void invalidate_entry( tag2warp_entry_t<Tag>* lut_entry, int warp_idx ) { + if (lut_entry != NULL) { // check for warp lut entry invalidation + if (lut_entry->idx == warp_idx) { + lut_entry->reset(); + } + } + } + + void clear_accessed( ); + + void print( FILE* fout) { + for (unsigned i=0; i< tag2warp_lut.size(); i++) { + for (unsigned j=0; j< tag2warp_lut[i].entry.size(); j++) { + fprintf(fout, "lut%03d-%02d:", i, j); + tag2warp_lut[i].entry[j].print(fout); + } + } + } + + static void print_stats ( FILE* fout ) { + fprintf( fout, "lut_aliased = %d\n", lut_aliased); + } +}; +template <class Tag> unsigned int warp_lut_sa<Tag>::lut_aliased = 0; + + +// lookup function in LUT +// may return an entry that has different PC for replacement +// or return a NULL pointer to indicate that the entry is accessed by another port +template <class Tag> +tag2warp_entry_t<Tag>* warp_lut_sa<Tag>::lookup_pc2warp( const Tag &tag, bool &lut_missed ) +{ + tag2warp_entry_t<Tag>* lut_entry = NULL; + unsigned hashed_pc = tag.lut_hash(insn_size_lgb2, tag2warp_lut.size()); + list< tag2warp_entry_t<Tag>* > &hashed_lru_stack = tag2warp_lut.at(hashed_pc).lru_stack; + struct same_tag same_tag_f; + + same_tag_f.tag = tag; + typename list< tag2warp_entry_t<Tag>* >::iterator lut_it; + lut_it = find_if(hashed_lru_stack.begin(), + hashed_lru_stack.end(), + same_tag_f); + if (lut_it != hashed_lru_stack.end()) { + lut_entry = *lut_it; + lut_entry->accessed = 1; + lut_accessed_q.push(lut_entry); + hashed_lru_stack.splice(hashed_lru_stack.end(), hashed_lru_stack, lut_it); + assert(lut_entry == hashed_lru_stack.back()); + lut_missed = false; + } else { + assert(!hashed_lru_stack.empty()); + lut_entry = hashed_lru_stack.front(); + if (lut_entry->accessed) { + lut_entry = NULL; + } else { + lut_entry->accessed = 1; + lut_accessed_q.push(lut_entry); + hashed_lru_stack.splice(hashed_lru_stack.end(), hashed_lru_stack, hashed_lru_stack.begin()); + assert(lut_entry == hashed_lru_stack.back()); + lut_aliased++; + } + lut_missed = true; + } + assert(hashed_lru_stack.size() == tag2warp_lut[hashed_pc].entry.size()); + + return lut_entry; +} + +template <class Tag> +void warp_lut_sa<Tag>::clear_accessed( ) { + while ( !lut_accessed_q.empty() ) { + lut_accessed_q.front()->accessed = 0; + lut_accessed_q.pop(); + } +} + +// a perfect warp lut that never misses. +template <class Tag> +class warp_lut_perfect : public warp_lut<Tag> { +private: + typedef map< Tag, tag2warp_entry_t<Tag>* > warp_map_t; + warp_map_t m_tag2entry_map; + + static unsigned int lut_max_size; +public: + warp_lut_perfect() {} + ~warp_lut_perfect() { + typename warp_map_t::iterator mit = m_tag2entry_map.begin(); + for (; mit != m_tag2entry_map.end(); mit++) { + delete mit->second; + } + } + + // idealistic implementation of lookup: the entry is never aliased, + // and a new one is created automatically if it does not exist + tag2warp_entry_t<Tag>* lookup_pc2warp( const Tag& tag, bool& lut_missed ) { + typename warp_map_t::iterator mit = m_tag2entry_map.find(tag); + + tag2warp_entry_t<Tag>* lut_entry = NULL; + if (mit != m_tag2entry_map.end()) { + lut_entry = mit->second; + assert(lut_entry->tag == tag); + } else { + lut_entry = new tag2warp_entry_t<Tag>(); + m_tag2entry_map.insert(make_pair(tag, lut_entry)); + } + + lut_missed = false; + lut_max_size = (lut_max_size < m_tag2entry_map.size())? m_tag2entry_map.size() : lut_max_size; + + return lut_entry; + } + + void invalidate_entry( tag2warp_entry_t<Tag>* lut_entry, int warp_idx ) { + if (lut_entry == NULL) return; + if (lut_entry->idx != warp_idx) return; + + typename warp_map_t::iterator mit = m_tag2entry_map.find(lut_entry->tag); + if (mit != m_tag2entry_map.end()) { + assert(mit->second == lut_entry); + mit->second->reset(); + delete mit->second; + m_tag2entry_map.erase(mit); + } + } + + void clear_accessed( ) {} + + void print( FILE* fout) { + typename warp_map_t::iterator mit = m_tag2entry_map.begin(); + for (; mit != m_tag2entry_map.end(); mit++) { + mit->second->print(fout); + } + } + + static void print_stats ( FILE* fout ) { + fprintf( fout, "lut_max_size = %d\n", lut_max_size); + } +}; +template <class Tag> unsigned int warp_lut_perfect<Tag>::lut_max_size = 0; + + +typedef tag2warp_entry_t<pc_tag> warplut_entry_t; +typedef pc_tag warp_tag_t; + +class dwf_hw_sche_class { +public: + int m_id; + warp_lut<pc_tag> *warp_lut_pc; + vector<warp_entry_t> warp_pool; + deque<int> free_warp_q; // the warp allocator + int simd_width; + int regf_width; + int insn_size_lgb2; + bool just_resume; + + vector<char> m_req; // request vector from incoming warp + vector<char> m_occ_new; // occupancy vector of the new warp, double as conflict vector + vector<char> m_occ_upd; // occupancy vector of the updated existing warp + vector<char> m_occ_ext; // occupancy vector of the existing warp + + dwf_hw_sche_class( int lut_size, int lut_assoc, + int simd_width, int regf_width, + int n_threads, int insn_size, + int heuristic, int id, + char *policy_opt = NULL ); + ~dwf_hw_sche_class(); + + warplut_entry_t* lookup_pc2warp( const warp_tag_t& lookup_tag ); + int update_warp( int* tid, address_type pc ); + + // barrier handling + int m_nbarriers; + class dwf_barrier { + public: + bool m_release; // see if a barrier is to be released (ie. all warp in cta hit already) + deque<int> m_queue; // queue storing warps currently hitting a barrier, skipping warplut and scheduler + + dwf_barrier() : m_release(false) {} + dwf_barrier(const dwf_barrier& that) + : m_release(that.m_release), m_queue(that.m_queue) {} + bool ready_to_issue() { + return(m_release && !m_queue.empty()); + } + }; + set< int > m_cta_released_barrier; // set of cta with released barrier + map< int, dwf_barrier > m_barrier; // map <barrier id == cta id, barrier> + int update_warp_at_barrier( int* tid, address_type pc, int cta_id, int barrier_num = 0 ); + void hit_barrier( int cta_id, int barrier_num = 0 ); + void release_barrier( int cta_id, int barrier_num = 0 ); + + int allocate_warp( address_type pc, bool update_scheduler = true ); + void free_warp( int idx, bool update_warplut = true ); + + void issue_warp( int *tid, address_type *pc ); + + void clear_accessed( ) { + warp_lut_pc->clear_accessed(); + } + + void init_cta(int start_thread, int cta_size, address_type start_pc); + + void print_pc2warp_lut( FILE *fout ); + void print_warp_pool( FILE *fout ); + void print_free_warp_q( FILE *fout ); + + int heuristic; + + // FIFO warp issue logic + queue<int> issue_warp_FIFO_q; + + // PC warp issue logic + class pc_first { + public: + vector<warp_entry_t> &warp_pool; + pc_first( vector<warp_entry_t> &bp ) : warp_pool(bp) {} + bool operator() (const int &idx_a, const int &idx_b) const { + if (warp_pool[idx_a].pc != warp_pool[idx_b].pc) { + return(warp_pool[idx_a].pc > warp_pool[idx_b].pc); + } else { + return(warp_pool[idx_a].occ < warp_pool[idx_b].occ); + } + } + }; + pc_first mypc_first; + priority_queue<int, vector<int>, pc_first > issue_warp_PC_q; + + // Majority warp issue logic + issue_warp_majority *issue_warp_MAJ; + void clear_policy_access( ); + void reset_policy_access( ); + + // PDOM Priority issue logic + issue_warp_pdom_prio issue_warp_pdom; + + // statistics + npc_tracker_class npc_tracker; + int max_warppool_occ; + int *warppool_occ_histo; // histogram of warppool occupancy + static unsigned int lut_realmiss; + static unsigned int uid_cnt; + static unsigned int warp_fragmentation; + static unsigned int warp_merge_conflict; + static void print_stats ( FILE* fout ) { + warp_lut_perfect<warp_tag_t>::print_stats( fout ); + warp_lut_sa<warp_tag_t>::print_stats( fout ); + fprintf( fout, "lut_realmiss = %d\n", lut_realmiss); + fprintf( fout, "warp_fragmentation = %d\n", warp_fragmentation); + fprintf( fout, "warp_merge_conflict = %d\n", warp_merge_conflict); + } +}; + +unsigned int dwf_hw_sche_class::lut_realmiss = 0; +unsigned int dwf_hw_sche_class::uid_cnt = 0; +unsigned int dwf_hw_sche_class::warp_fragmentation = 0; +unsigned int dwf_hw_sche_class::warp_merge_conflict = 0; + + +dwf_hw_sche_class::dwf_hw_sche_class( int lut_size, int lut_assoc, + int simd_width, int regf_width, + int n_threads, int insn_size, + int heuristic, int id, + char *policy_opt ) +: m_id(id), +// WarpLUT w/ pc tag +warp_lut_pc( (lut_size == 0)? (warp_lut<pc_tag> *) new warp_lut_perfect<pc_tag>() : + (warp_lut<pc_tag> *) new warp_lut_sa<pc_tag>(lut_size, lut_assoc, insn_size) ), +m_nbarriers(1), // for barrier +mypc_first( warp_pool ), issue_warp_PC_q( mypc_first ), // DPC +issue_warp_pdom(simd_width, &warp_pool, n_threads), // DPdPri +npc_tracker( NULL, simd_width ) +{ + unsigned i; + + this->simd_width = simd_width; + this->regf_width = regf_width; + this->m_req.resize(regf_width); + this->m_occ_new.resize(regf_width); + this->m_occ_upd.resize(regf_width); + this->m_occ_ext.resize(regf_width); + + // initialize the warp pool + // (make sure the thread id's are init to -1) + this->warp_pool.resize(n_threads); + for (i=0; i<warp_pool.size(); i++) { + warp_pool[i].pc = -1; + warp_pool[i].tid = new int[simd_width]; + memset(warp_pool[i].tid, -1, sizeof(int)*simd_width); + warp_pool[i].occ = 0; + warp_pool[i].next_warp = -1; + + // push the index to the warp allocator + free_warp_q.push_back(i); + } + + // setup for various heuristics + this->heuristic = heuristic; + switch (heuristic) { + case MAJORITY: + issue_warp_MAJ = new issue_warp_majority_queue(simd_width, &warp_pool); + break; + case MAJORITY_MAXHEAP: { + int mh_lut_size = 32; + int mh_lut_assoc = 4; + int n_reads_per_cycle_lut = 4; + int n_writes_per_cycle_lut = 4; + int mh_size = 128; + int n_reads_per_cycle_mh = 4; + int n_writes_per_cycle_mh = 4; + if (policy_opt != NULL) { + sscanf(policy_opt, ";LUT=%d:%dr%dw%d;MH=%dr%dw%d", + &mh_lut_size, &mh_lut_assoc, &n_reads_per_cycle_lut, &n_writes_per_cycle_lut, + &mh_size, &n_reads_per_cycle_mh, &n_writes_per_cycle_mh); + } + issue_warp_MAJ = new issue_warp_majority_heap(simd_width, &warp_pool, + mh_lut_size, mh_lut_assoc, mh_size, + n_reads_per_cycle_lut, n_writes_per_cycle_lut, + n_reads_per_cycle_mh, n_writes_per_cycle_mh); + } + break; + } + + this->just_resume = false; + + this->max_warppool_occ = 0; + this->warppool_occ_histo = new int[n_threads]; + memset(this->warppool_occ_histo, 0, n_threads*sizeof(int)); +} + +// should never be called (only at exit?) +dwf_hw_sche_class::~dwf_hw_sche_class( ) +{ + unsigned i; + + for (i=0; i<warp_pool.size(); i++) { + free(warp_pool[i].tid); + } + + delete[] this->warppool_occ_histo; + + delete warp_lut_pc; +} + +// allocate a new warp in warp pool +int dwf_hw_sche_class::allocate_warp( address_type pc, bool update_scheduler ) +{ + int idx; + assert(!free_warp_q.empty()); + idx = free_warp_q.front(); + free_warp_q.pop_front(); + warp_pool[idx].uid = uid_cnt; + uid_cnt++; + warp_pool[idx].pc = pc; + warp_pool[idx].next_warp = -1; + warp_pool[idx].lut_ptr = NULL; + + if (update_scheduler) { + if (heuristic == FIFO) issue_warp_FIFO_q.push(idx); + if (heuristic == PC) issue_warp_PC_q.push(idx); + if (heuristic == MAJORITY || heuristic == MAJORITY_MAXHEAP) + issue_warp_MAJ->push_warp(pc, idx); + if (heuristic == PDOMPRIO) issue_warp_pdom.push_warp(pc, idx); + } + + return idx; +} + +// free a warp in warp pool +// it will reset the content of the warp entry as well +void dwf_hw_sche_class::free_warp( int idx, bool update_warplut ) +{ + bool redundant_idx_check = false; + if (redundant_idx_check) { + deque<int>::iterator dit = find(free_warp_q.begin(), free_warp_q.end(), idx); + assert(dit == free_warp_q.end()); + } + + warp_pool[idx].pc = -1; + memset(warp_pool[idx].tid, -1, sizeof(int)*simd_width); + warp_pool[idx].occ = 0; + warp_pool[idx].next_warp = -1; + if (update_warplut) { + warp_lut_pc->invalidate_entry( (warplut_entry_t*)warp_pool[idx].lut_ptr, idx ); + } + + free_warp_q.push_back(idx); + assert(free_warp_q.size() <= warp_pool.size()); +} + +warplut_entry_t* dwf_hw_sche_class::lookup_pc2warp( const warp_tag_t& lookup_tag ) +{ + bool lut_missed = false; + + warplut_entry_t* lut_entry; + lut_entry = warp_lut_pc->lookup_pc2warp( lookup_tag, lut_missed ); + + if (!lut_missed) { + if (lut_entry->tag != warp_pool[lut_entry->idx].pc) lut_missed = true; + } + + if (lut_missed) { + if (npc_tracker.pc_count.find(lookup_tag.get_pc()) != npc_tracker.pc_count.end()) { + lut_realmiss++; // ie. the incoming warp lost an opportunity to merge + } + } + + return lut_entry; +} + + +void fill_all (vector<char>& container, const char& value) +{ + fill(container.begin(), container.end(), value); +} + +int regfile_hash(signed istream_number, unsigned simd_size, unsigned n_banks); +int dwf_hw_sche_class::update_warp( int *tid, address_type pc ) +{ + int i; + bool newwarp = false; + bool newwarp_alloc = false; + warplut_entry_t* lut_entry; + warp_tag_t warp_tag(pc); + lut_entry = lookup_pc2warp(warp_tag); + + // no LUT entry returned, stall + if (!lut_entry) { + assert(0); + } + + if (heuristic == MAJORITY || heuristic == MAJORITY_MAXHEAP) { + issue_warp_MAJ->add_threads(pc, tid); + } + + npc_tracker.add_threads( tid, pc ); + + // if the pc of the LUT entry does not match, + // allocate a new entry + if (lut_entry->tag != warp_tag) { + lut_entry->idx = allocate_warp(pc); + lut_entry->tag = warp_tag; + lut_entry->occ = 0; + assert(warp_pool[lut_entry->idx].pc == pc); + newwarp = true; + newwarp_alloc = true; + } + + // create the request vector + bool tid_has_valid_entry = false; + fill_all(m_req, 0); + for (i = 0; i<simd_width; i++) { + if (tid[i] != -1) { + int lane = regfile_hash(tid[i],simd_width,regf_width); + // make sure we are not having two threads going to same lane + assert(lane < regf_width); + m_req[lane] += 1; + tid_has_valid_entry = true; + } + } + assert(tid_has_valid_entry); + + // read the old idx pointing to an existing warp + int old_idx = lut_entry->idx; + + // create the conflict vector + fill_all(m_occ_ext, 0); + int regf_mask = regf_width - 1; + for (i = 0; i<simd_width; i++) { + m_occ_ext[i & regf_mask] += ((lut_entry->occ & (1 << i)) == 0)? 0 : 1; + } + fill_all(m_occ_upd, 0); + fill_all(m_occ_new, 0); + int n_regf_slot = simd_width / regf_width; + bool conflict = false; + for (i = 0; i<regf_width; i++) { + if (m_occ_ext[i] + m_req[i] > n_regf_slot) { + m_occ_new[i] = m_occ_ext[i] + m_req[i] - n_regf_slot; + m_occ_upd[i] = n_regf_slot - m_occ_ext[i]; + conflict = true; + } else { + m_occ_upd[i] = m_req[i]; + } + } + + // if the pc of the warp mismatch with lut, + // set conflict vector to all one. + // that force all threads to the newly allocated warp + if (warp_pool[old_idx].pc != pc) { + conflict = true; + for (i = 0; i<regf_width; i++) { + m_occ_new[i] = m_req[i]; + m_occ_upd[i] = 0; + m_occ_ext[i] = n_regf_slot; + } + } + + // if there are conflicted entries, get a new warp + int new_idx = -1; + if (conflict) { + new_idx = allocate_warp(pc); + lut_entry->idx = new_idx; + lut_entry->occ = 0; //update the lut_entry + assert(warp_pool[new_idx].pc == pc); + + int total_occ = 0; + for (i = 0; i < regf_width; i++) + total_occ += m_occ_ext[i] + m_req[i]; + if (total_occ <= simd_width) warp_fragmentation += 1; + warp_merge_conflict += 1; + + newwarp_alloc = true; + } + + // update the warp as indicated by the LUT + // if the lane is conflicted, or the old warp is just not + // write to the new warp + int new_occ = 0; + fill_all(m_occ_new, 0); + for (i = 0; i<simd_width; i++) { + if (tid[i] != -1) { + int rfbank = regfile_hash(tid[i],simd_width,regf_width); + int lane = -1; + if ((m_occ_ext[rfbank] < n_regf_slot) || newwarp) { + lane = rfbank + m_occ_ext[rfbank] * regf_width; + assert(lane < simd_width); + warp_pool[old_idx].tid[lane] = tid[i]; + warp_pool[old_idx].occ++; + lut_entry->occ |= (1<<lane); + m_occ_ext[rfbank]++; + } else { + lane = rfbank + m_occ_new[rfbank] * regf_width; + assert(lane < simd_width); + warp_pool[new_idx].tid[lane] = tid[i]; + warp_pool[new_idx].occ++; + new_occ |= (1<<lane); + m_occ_new[rfbank]++; + assert(m_occ_new[rfbank] <= n_regf_slot); + } + } + } + + // to cover the case where the pc of the warp mismatch with lut + // (because the warp is issued) + if (warp_pool[old_idx].pc == pc) { + issue_warp_pdom.add_threads(old_idx, pc); + } + if (conflict) { + lut_entry->occ = new_occ; + issue_warp_pdom.add_threads(new_idx, pc); + } + + warp_pool[lut_entry->idx].lut_ptr = lut_entry; // link up the lut entry and warp + + bool scheduler_consistency_check = false; + if (scheduler_consistency_check && heuristic == MAJORITY) { + ((issue_warp_majority_queue*)issue_warp_MAJ)->check_consistency(); + } + + return 1; +} + +// called AFTER threads hit a barrier to insert them into the barrier queue +// ASSUME: threads from released barrier are not hitting second barrier right away +int dwf_hw_sche_class::update_warp_at_barrier( int* tid, address_type pc, int cta_id, int barrier_num ) +{ + assert(barrier_num < m_nbarriers); + assert(cta_id >= 0); + + int i; + int warp_index = 0xDEADBEEF; + + npc_tracker.add_threads( tid, pc ); + + // always allocate new warp + warp_index = allocate_warp(pc, false); + assert(warp_pool[warp_index].pc == pc); + + // no need to create the request vector + // no need to create the conflict vector + + // assign threads into the new warp + fill_all(m_occ_ext, 0); + int max_nthreads_per_rfbank = simd_width / regf_width; + for (i = 0; i<simd_width; i++) { + if (tid[i] != -1) { + int rfbank = regfile_hash(tid[i],simd_width,regf_width); + int lane = -1; + + assert(m_occ_ext[rfbank] < max_nthreads_per_rfbank); + lane = rfbank + m_occ_ext[rfbank] * regf_width; + assert(lane < simd_width); + warp_pool[warp_index].tid[lane] = tid[i]; + warp_pool[warp_index].occ++; + m_occ_ext[rfbank]++; + } + } + + warp_pool[warp_index].lut_ptr = NULL; // no link to any lut entry + + // put the warp id into barrier queue + m_barrier[cta_id].m_queue.push_back(warp_index); + + // notify issue module to check this barrier at issue + if ( m_barrier[cta_id].ready_to_issue() ) { + m_cta_released_barrier.insert(cta_id); + } + + return 1; +} + +// called at decode stage when thread hit a barrier +// ASSUME: threads from released barrier are not hitting second barrier right away +void dwf_hw_sche_class::hit_barrier( int cta_id, int barrier_num ) +{ + assert(barrier_num < m_nbarriers); + assert(cta_id >= 0); + + m_barrier[cta_id].m_release = false; +} + +// called at decode stage when all thread in cta hit the barrier +// ASSUME: threads from released barrier are not hitting second barrier right away +void dwf_hw_sche_class::release_barrier( int cta_id, int barrier_num ) +{ + assert(barrier_num < m_nbarriers); + assert(cta_id >= 0); + + map<int, dwf_barrier>::iterator i_barrier = m_barrier.find(cta_id); + assert(i_barrier != m_barrier.end()); // barrier has to exists in the first place! + i_barrier->second.m_release = true; +} + +void dwf_hw_sche_class::issue_warp( int *tid, address_type *pc ) +{ + int i; + bool warp_issued = false; + + // scan the released barriers for ready warp + // TODO: arbitrate between different queues? + set<int>::iterator i_ctabar = m_cta_released_barrier.begin(); + for (; i_ctabar != m_cta_released_barrier.end(); ++i_ctabar) { + int cta_id = *i_ctabar; + map<int, dwf_barrier>::iterator i_barrier = m_barrier.find(cta_id); + + if ( i_barrier->second.ready_to_issue() ) { + int warp_idx = i_barrier->second.m_queue.front(); + + for (i = 0; i < simd_width; i++) { + tid[i] = warp_pool[warp_idx].tid[i]; + } + *pc = warp_pool[warp_idx].pc; + + i_barrier->second.m_queue.pop_front(); + free_warp(warp_idx, false); // don't update warplut as the warp is not linked to it + + // remove cta from checking list if the queue is emptied + // (if the last threads haven't made it back to scheduler in time, + // update_warp_at_barrier will insert the cta id again) + if (i_barrier->second.m_queue.empty()) { + m_cta_released_barrier.erase(i_ctabar); + } + + warp_issued = true; + + break; + } + } + + if (!warp_issued) { + switch (heuristic) { + case FIFO: + // Oldest warp are issued first + if (!issue_warp_FIFO_q.empty()) { + int idx = issue_warp_FIFO_q.front(); + for (i = 0; i < simd_width; i++) { + tid[i] = warp_pool[idx].tid[i]; + } + *pc = warp_pool[idx].pc; + + issue_warp_FIFO_q.pop(); + free_warp(idx); + } else { + memset(tid, -1, sizeof(int)*simd_width); + *pc = -1; + } + break; + case PC: + // lowest PC warp are issued first + if (!issue_warp_PC_q.empty()) { + int idx = issue_warp_PC_q.top(); + for (i = 0; i < simd_width; i++) { + tid[i] = warp_pool[idx].tid[i]; + } + *pc = warp_pool[idx].pc; + + issue_warp_PC_q.pop(); + free_warp(idx); + } else { + memset(tid, -1, sizeof(int)*simd_width); + *pc = -1; + } + break; + case MAJORITY: + case MAJORITY_MAXHEAP: + // issue the most common PC first + { + int idx = issue_warp_MAJ->pop_warp(); + if (idx >= 0) { + for (i = 0; i < simd_width; i++) { + tid[i] = warp_pool[idx].tid[i]; + } + *pc = warp_pool[idx].pc; + free_warp(idx); + } else { + memset(tid, -1, sizeof(int)*simd_width); + *pc = -1; + } + } + break; + case PDOMPRIO: + // issue the warp with lowest PDOM count + { + int idx = issue_warp_pdom.front_warp(); + if (idx >= 0) { + issue_warp_pdom.pop_warp(); + + for (i = 0; i < simd_width; i++) { + tid[i] = warp_pool[idx].tid[i]; + } + *pc = warp_pool[idx].pc; + free_warp(idx); + + just_resume = false; + } else { + memset(tid, -1, sizeof(int)*simd_width); + *pc = -1; + } + } + break; + default: + printf("Unsupported Heuristics!\n"); + abort(); + break; + } + } + + npc_tracker.sub_threads( tid, *pc ); + + int warppool_occ = warp_pool.size() - free_warp_q.size(); + if (max_warppool_occ < warppool_occ) { + max_warppool_occ = warppool_occ; + } + warppool_occ_histo[warppool_occ] += 1; +} + +void dwf_hw_sche_class::init_cta(int start_thread, int cta_size, address_type start_pc) +{ + assert((start_thread % simd_width) == 0); // thread id starting at a warp + + int n_warp_2assign = cta_size / simd_width; + n_warp_2assign += (cta_size % simd_width)? 1 : 0; // round up + + static int *thd_id = NULL; + if (thd_id == NULL) thd_id = new int[simd_width]; + + for (int w = 0; w < n_warp_2assign; w++) { + // generate the warp update register for each warp + fill_n(thd_id, simd_width, -1); + int warp_start_tid = start_thread + w * simd_width; + for (int i = 0; (i < simd_width) && (warp_start_tid + i) < (start_thread + cta_size); i++) { + thd_id[i] = warp_start_tid + i; + } + + // push these warps into DWF scheduler + update_warp( thd_id, start_pc ); + } +} + +void dwf_hw_sche_class::print_free_warp_q( FILE *fout ) +{ + fprintf(fout, "free_node_q (%zd)= ", free_warp_q.size() ); + deque<int>::iterator dit = free_warp_q.begin(); + for (; dit != free_warp_q.end(); dit++) { + fprintf(fout, "%03d ", *dit); + } + fprintf(fout, "\n"); +} + +void print_warp( FILE *fout, warp_entry_t warp_e, int simd_width ) +{ + fprintf(fout, "\t%02d 0x%08x: (", warp_e.pdom_prio, warp_e.pc ); + for (int i=0;i<simd_width;i++) { + fprintf(fout, "%03d ", warp_e.tid[i]); + } + fprintf(fout, ")\n"); +} + +void dwf_hw_sche_class::print_warp_pool( FILE *fout ) +{ + for (unsigned i=0; i< warp_pool.size(); i++) { + if (warp_pool[i].pc != (address_type)-1) { + fprintf(fout, "bp%03d:", i); + print_warp(fout, warp_pool[i], simd_width); + } + } +} + +void dwf_hw_sche_class::clear_policy_access( ) { + if (heuristic == MAJORITY_MAXHEAP) { + ((issue_warp_majority_heap*)issue_warp_MAJ)->clear_access( ); + } +} + +void dwf_hw_sche_class::reset_policy_access( ) { + if (heuristic == MAJORITY_MAXHEAP) { + ((issue_warp_majority_heap*)issue_warp_MAJ)->reset_access( ); + } +} + +/////////////////////////////////////////////////////////////////////////// +// c-wrapper interface +/////////////////////////////////////////////////////////////////////////// + +int dwf_hw_n_sche = 0; +dwf_hw_sche_class **dwf_hw_sche; +unsigned *acc_dyn_pcs = NULL; + +void create_dwf_schedulers( int n_shaders, + int lut_size, int lut_assoc, + int simd_width, int regf_width, + int n_threads, int insn_size, + int heuristic, + char *policy_opt ) +{ + dwf_hw_n_sche = n_shaders; + dwf_hw_sche = new dwf_hw_sche_class*[n_shaders]; + for (int i=0; i<n_shaders; i++) { + dwf_hw_sche[i] = new dwf_hw_sche_class( lut_size, lut_assoc, + simd_width, regf_width, + n_threads, insn_size, + heuristic, i, + policy_opt ); + } + + if (acc_dyn_pcs == NULL) { + acc_dyn_pcs = new unsigned[n_shaders]; + std::fill_n(acc_dyn_pcs, n_shaders, 0); + } + for (int i=0; i<n_shaders; i++) { + dwf_hw_sche[i]->npc_tracker.acc_pc_count = &acc_dyn_pcs[i]; + } +} + +int dwf_update_warp( int shd_id, int* tid, address_type pc ) +{ + return dwf_hw_sche[shd_id]->update_warp( tid, pc ); +} + +int dwf_update_warp_at_barrier( int shd_id, int* tid, address_type pc, int cta_id ) +{ + return dwf_hw_sche[shd_id]->update_warp_at_barrier( tid, pc, cta_id); +} + +void dwf_hit_barrier( int shd_id, int cta_id ) +{ + dwf_hw_sche[shd_id]->hit_barrier( cta_id ); +} + +void dwf_release_barrier( int shd_id, int cta_id ) +{ + dwf_hw_sche[shd_id]->release_barrier( cta_id ); +} + +void dwf_issue_warp( int shd_id, int *tid, address_type *pc ) +{ + dwf_hw_sche[shd_id]->issue_warp( tid, pc ); +} + +void dwf_clear_accessed( int shd_id ) +{ + dwf_hw_sche[shd_id]->clear_accessed( ); +} + +void dwf_clear_policy_access( int shd_id ) +{ + dwf_hw_sche[shd_id]->clear_policy_access( ); +} + +void dwf_reset_policy_access( int shd_id ) +{ + dwf_hw_sche[shd_id]->reset_policy_access( ); +} + +void dwf_init_CTA(int shd_id, int start_thread, int cta_size, address_type start_pc) +{ + dwf_hw_sche[shd_id]->init_cta(start_thread, cta_size, start_pc); + dwf_hw_sche[shd_id]->clear_accessed( ); + dwf_hw_sche[shd_id]->clear_policy_access( ); +} + +void dwf_print_stat( FILE* fout ) +{ + dwf_hw_sche_class::print_stats( fout ); + npc_tracker_class::histo_print( fout ); + fprintf(fout, "max_warppool_occ = "); + for (int i=0; i<dwf_hw_n_sche; i++) { + fprintf(fout, "%d ", dwf_hw_sche[i]->max_warppool_occ); + } + fprintf(fout, "\n"); + for (int i=0; i<dwf_hw_n_sche; i++) { + fprintf(fout, "warppool_occ[%d] = ", i); + for (int j=0; j<dwf_hw_sche[i]->max_warppool_occ; j++) { + fprintf(fout, "%d ", dwf_hw_sche[i]->warppool_occ_histo[j]); + } + fprintf(fout, "\n"); + } + if (dwf_hw_sche[0]->heuristic == MAJORITY_MAXHEAP) { + fprintf(fout, "n_stall_on_maxheap = "); + for (int i=0; i<dwf_hw_n_sche; i++) { + fprintf(fout, "%d ", + ((issue_warp_majority_heap*)dwf_hw_sche[i]->issue_warp_MAJ)->n_stall_on_maxheap); + } + fprintf(fout, "\n"); + fprintf(fout, "maxheap_n_entries = "); + for (int i=0; i<dwf_hw_n_sche; i++) { + fprintf(fout, "%d ", + ((issue_warp_majority_heap*)dwf_hw_sche[i]->issue_warp_MAJ)->maxheap.max_n_entries); + } + fprintf(fout, "\n"); + fprintf(fout, "maxheap_lut_n_aliased = "); + for (int i=0; i<dwf_hw_n_sche; i++) { + fprintf(fout, "%d ", + ((issue_warp_majority_heap*)dwf_hw_sche[i]->issue_warp_MAJ)->mh_lut.n_aliased); + } + fprintf(fout, "\n"); + issue_warp_majority_heap::print_stat(fout); + } +} + +void dwf_reset_reconv_pt() +{ + issue_warp_pdom_prio::reconvgence_pt.clear(); +} + +void dwf_insert_reconv_pt(address_type pc) +{ + issue_warp_pdom_prio::reconvgence_pt.insert(pc); +} + +void dwf_reinit_schedulers( int n_shaders ) +{ + for (int i=0; i<n_shaders; i++) { + dwf_hw_sche[i]->issue_warp_pdom.reinit(); + } +} + +void dwf_update_statistics( int shader_id ) +{ + dwf_hw_sche[shader_id]->npc_tracker.update_acc_count(); +} + +void g_print_dmaj_scheduler(int sid) { + dwf_hw_sche[sid]->issue_warp_MAJ->print(stdout); +} + +void g_print_warp_lut(int sid) { + dwf_hw_sche[sid]->warp_lut_pc->print(stdout); +} + +void g_print_free_warp_q(int sid) { + dwf_hw_sche[sid]->print_free_warp_q(stdout); +} + +void g_print_warp_pool(int sid) { + dwf_hw_sche[sid]->print_warp_pool(stdout); +} + +void g_print_max_heap(int sid) { + dwf_hw_sche[sid]->issue_warp_MAJ->print(stdout); +} + +#ifdef UNIT_TEST + + #undef UNIT_TEST + #include "stat-tool.cc" + +unsigned gpgpu_thread_swizzling = 0; +unsigned long long gpu_sim_cycle = 0; + +int regfile_hash(signed istream_number, unsigned simd_size, unsigned n_banks) { + if (gpgpu_thread_swizzling) { + signed warp_ID = istream_number / simd_size; + return((istream_number + warp_ID) % n_banks); + } else { + return(istream_number % n_banks); + } +} + +int log2i(int n) { + int lg; + lg = -1; + while (n) { + n>>=1;lg++; + } + return lg; +} + +int test_FIFO() +{ + dwf_hw_sche_class *dwf_sche; + int i; + int tid[6][4] = { + { 0, 1, 2, 3}, + { 4, 5, 6, 7}, + { 8,-1,10,-1}, + {-1, 1,-1, 3}, + { 4, 9,-1,11}, + {-1,13,14,-1} + }; + + int expect_out[12][4] = { + { 0, 1, 2, 3}, + { 0, 1, 2, 3}, + { 0, 1, 2, 3}, + { 4, 5, 6, 7}, + { 8, 1,10, 3}, + { 4, 9,14,11}, + {-1,13,-1,-1}, + { 4, 9,-1,11}, + {-1,13,14,-1}, + { 8,-1,10,-1}, + { 4, 9,14,11}, + { 8,13,10,-1} + }; + + int tid_out[4]; + address_type pc_out; + + dwf_sche = new dwf_hw_sche_class(16, 2, 4, 4, 16, 1, FIFO); + + // same threads - different pc + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[0], 0x409a80); + dwf_sche->update_warp(tid[0], 0x409a88); + + // different threads - different pc + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[0], 0x409a90); + dwf_sche->update_warp(tid[1], 0x409a80); + + // different threads - same pc + // expect two warp to merge into one as there is no lane conflict + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[2], 0x409a90); + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[3], 0x409a90); + + // same as above, but with lane conflict + // expect a new warp allocated, + // but only the conflicting threads goes to new warp + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[4], 0x409a80); + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[5], 0x409a80); + + // different threads - different pc + // purposely try to alias an existing mapping + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[4], 0x410a80); + dwf_sche->update_warp(tid[5], 0x411a80); + + // going back to that mapping + // a new warp should be allocated (despite lack of conflict) + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[2], 0x409a80); + + // testing the occupancy vector + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[4], 0x409aa0); + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[5], 0x409aa0); + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[2], 0x409aa0); + + // fill the warp pool up + for (i=12; i<64; ) { + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[1], 0x409a80 + 8 * i++); + dwf_sche->update_warp(tid[4], 0x409a80 + 8 * i++); + } + // issue all the warp (do some auto checking on the way) + for (i=0; i<64; i++) { + dwf_sche->issue_warp(tid_out, &pc_out); + printf("0x%08x [%d %d %d %d]\n", pc_out, tid_out[0], tid_out[1], tid_out[2], tid_out[3]); + if (i<12) { + if ( memcmp(tid_out, expect_out[i], 4*sizeof(int) ) ) { + printf("%d warp mismatches\n", i); + assert(0); + } + } + } + + // now that all warpes are issue, no entries in the lut is valid + // updating warp with an old address that remains in the lut + // to see if detects the invalid lut entry + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[2], 0x409a80 + 8 * 63); + dwf_sche->update_warp(tid[3], 0x409a80 + 8 * 62); + dwf_sche->issue_warp(tid_out, &pc_out); + assert(!memcmp(tid_out, tid[2], 4*sizeof(int) )); + dwf_sche->issue_warp(tid_out, &pc_out); + assert(!memcmp(tid_out, tid[3], 4*sizeof(int) )); + + dwf_sche->print_warp_pool(stdout); + dwf_sche->warp_lut_pc->print(stdout); + dwf_hw_sche_class::print_stats(stdout); + + delete dwf_sche; + + return 0; +} + +int test_PC () +{ + dwf_hw_sche_class *dwf_sche; + int i; + int tid[4][4] = { + { 0, 1, 2, 3}, + { 4, 5, 6, 7}, + { 8,-1,10,-1}, + {-1,13,14,-1} + }; + + int tid_out[4]; + address_type pc_out; + + dwf_sche = new dwf_hw_sche_class(16, 2, 4, 4, 16, 1, PC); + + // fill the warp pool up in reverse PC order + for (i=0; i<4; i++) { + for (int j=0; j<4; j++) { + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[j], 0x409a80 - 8 * i); + } + } + + // issue the warps, expect them to be in PC order, with higher occ warp issued first + printf("PC Issue Logic:\n"); + for (i=0; i<4; i++) { + for (int j=0; j<4; j++) { + dwf_sche->issue_warp(tid_out, &pc_out); + printf("0x%08x [%d %d %d %d]\n", pc_out, tid_out[0], tid_out[1], tid_out[2], tid_out[3]); + } + } + +} + +int test_MAJ () +{ + dwf_hw_sche_class *dwf_sche; + int i; + int tid[4][4] = { + { 0, 1, 2, 3}, + { 4, 5, 6, 7}, + { 8,-1,10,-1}, + {-1,13,14,-1} + }; + + int tid_out[4]; + address_type pc_out; + + dwf_sche = new dwf_hw_sche_class(16, 2, 4, 4, 16, 1, MAJORITY); + + // fill the warp pool up in reverse PC order + for (i=0; i<4; i++) { + for (int j=0; j<(4-i); j++) { + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[j], 0x409a80 - 8 * i); + } + } + + // issue the warps, expect them to be in PC order, with higher occ warp issued first + printf("Majority Issue Logic:\n"); + for (i=0; i<4; i++) { + for (int j=0; j<4; j++) { + dwf_sche->issue_warp(tid_out, &pc_out); + printf("0x%08x [%d %d %d %d]\n", pc_out, tid_out[0], tid_out[1], tid_out[2], tid_out[3]); + } + } +} + +int test_MAJ_HEAP () +{ + printf("\ntest_MAJ_HEAP:\n"); + dwf_hw_sche_class *dwf_sche; + int i; + int tid[4][4] = { + { 0, 1, 2, 3}, + { 4, 5, 6, 7}, + { 8,-1,10,-1}, + {-1,13,14,-1} + }; + + int tid_out[4]; + address_type pc_out; + + dwf_sche = new dwf_hw_sche_class(16, 2, 4, 4, 16, 1, MAJORITY_MAXHEAP); + + // fill the warp pool up in reverse PC order + for (i=0; i<4; i++) { + for (int j=0; j<(i+1); j++) { + dwf_sche->clear_accessed(); + dwf_sche->update_warp(tid[j], 0x409a80 + 8 * i); + } + } + + dwf_sche->reset_policy_access(); + dwf_sche->issue_warp_MAJ->print(stdout); + + // issue the warps, expect them to be in PC order, with higher occ warp issued first + printf("Majority (Max Heap) Issue Logic:\n"); + for (i=0; i<4; i++) { + for (int j=0; j<4; j++) { + dwf_sche->issue_warp(tid_out, &pc_out); + printf("0x%08x [%d %d %d %d]\n", pc_out, tid_out[0], tid_out[1], tid_out[2], tid_out[3]); + } + dwf_sche->reset_policy_access(); + } +} + +void test_warp_lut_pc () +{ + printf("\ntest_warp_lut_pc:\n"); + warp_lut_sa<pc_tag> warp_lut_pc(16, // size + 4, // assoc + 1); // insn_size + + address_type pc_value[] = {0, 4, 0, 8, 12, 16, 20, 8, 8, 0}; + int n_entry = sizeof(pc_value) / sizeof(address_type); + vector<pc_tag> pc_stream(pc_value, pc_value + n_entry); + + int misses = 0; + for (int n = 0; n < n_entry * 100; n++) { + int i = n % n_entry; + tag2warp_entry_t<pc_tag> *lut_entry = NULL; + bool lut_miss = false; + + lut_entry = warp_lut_pc.lookup_pc2warp(pc_stream[i], lut_miss); + + if (lut_entry->tag != pc_stream[i]) { + lut_entry->tag = pc_stream[i]; + lut_entry->occ = 1; + misses += 1; + } + warp_lut_pc.clear_accessed(); + lut_entry->accessed = 0; + } + + printf("Number of Miss = %d\n", misses); +} + +int main () { + //test_FIFO(); + //test_PC(); + //test_MAJ(); + test_MAJ_HEAP(); + test_warp_lut_pc(); + return 0; +} + +#endif |