From dadb44ad16727623476a1e6947453da81ed682c7 Mon Sep 17 00:00:00 2001 From: "Andrew M. B. Boktor" Date: Mon, 2 Jul 2012 22:11:33 -0800 Subject: Adding a two level scheduler as described in the ISCA 2012 tutorial [git-p4: depot-paths = "//depot/gpgpu_sim_research/fermi/distribution/": change = 13261] --- src/gpgpu-sim/gpu-sim.cc | 3 + src/gpgpu-sim/scoreboard.cc | 17 +++++ src/gpgpu-sim/scoreboard.h | 3 + src/gpgpu-sim/shader.cc | 149 +++++++++++++++++++++++++++++++++++++++++--- src/gpgpu-sim/shader.h | 57 +++++++++++++++-- 5 files changed, 216 insertions(+), 13 deletions(-) (limited to 'src/gpgpu-sim') diff --git a/src/gpgpu-sim/gpu-sim.cc b/src/gpgpu-sim/gpu-sim.cc index 35070d8..80ca398 100644 --- a/src/gpgpu-sim/gpu-sim.cc +++ b/src/gpgpu-sim/gpu-sim.cc @@ -261,6 +261,9 @@ void shader_core_config::reg_options(class OptionParser * opp) option_parser_register(opp, "-gpgpu_num_mem_units", OPT_INT32, &gpgpu_num_mem_units, "Number if ldst units (default=1) WARNING: not hooked up to anything", "1"); + option_parser_register(opp, "-gpgpu_scheduler", OPT_CSTR, &gpgpu_scheduler_string, + "Scheduler configuration: lrr|tl:num_active_warps default: lrr", + "lrr"); } void gpgpu_sim_config::reg_options(option_parser_t opp) diff --git a/src/gpgpu-sim/scoreboard.cc b/src/gpgpu-sim/scoreboard.cc index 4935715..e2379fd 100644 --- a/src/gpgpu-sim/scoreboard.cc +++ b/src/gpgpu-sim/scoreboard.cc @@ -32,10 +32,12 @@ //Constructor Scoreboard::Scoreboard( unsigned sid, unsigned n_warps ) +: longopregs() { m_sid = sid; //Initialize size of table reg_table.resize(n_warps); + longopregs.resize(n_warps); } // Print scoreboard contents @@ -69,10 +71,24 @@ void Scoreboard::releaseRegister(unsigned wid, unsigned regnum) reg_table[wid].erase(regnum); } +const bool Scoreboard::islongop (unsigned warp_id,unsigned regnum) { + return longopregs[warp_id].find(regnum) != longopregs[warp_id].end(); +} + void Scoreboard::reserveRegisters(const class warp_inst_t* inst) { for( unsigned r=0; r < 4; r++) if(inst->out[r] > 0) reserveRegister(inst->warp_id(), inst->out[r]); + + //Keep track of long operations + if (inst->is_load() && + ( inst->space.get_type() == global_space || + inst->space.get_type() == local_space || + inst->space.get_type() == tex_space)){ + for ( unsigned r=0; r<4; r++) { + if(inst->out[r] > 0) longopregs[inst->warp_id()].insert(r); + } + } } // Release registers for an instruction @@ -80,6 +96,7 @@ void Scoreboard::releaseRegisters(const class warp_inst_t *inst) { for( unsigned r=0; r < 4; r++) if(inst->out[r] > 0) releaseRegister(inst->warp_id(), inst->out[r]); + longopregs[inst->warp_id()].clear(); } /** diff --git a/src/gpgpu-sim/scoreboard.h b/src/gpgpu-sim/scoreboard.h index e6d54c8..8559131 100644 --- a/src/gpgpu-sim/scoreboard.h +++ b/src/gpgpu-sim/scoreboard.h @@ -47,6 +47,7 @@ public: bool checkCollision(unsigned wid, const inst_t *inst) const; bool pendingWrites(unsigned wid) const; void printContents() const; + const bool islongop(unsigned warp_id, unsigned regnum); private: void reserveRegister(unsigned wid, unsigned regnum); @@ -55,6 +56,8 @@ private: // keeps track of pending writes to registers // indexed by warp id, reg_id => pending write count std::vector< std::set > reg_table; + //Register that depend on a long operation (global, local or tex memory) + std::vector< std::set > longopregs; }; diff --git a/src/gpgpu-sim/shader.cc b/src/gpgpu-sim/shader.cc index ccd2a38..8ed907d 100644 --- a/src/gpgpu-sim/shader.cc +++ b/src/gpgpu-sim/shader.cc @@ -123,15 +123,30 @@ shader_core_ctx::shader_core_ctx( class gpgpu_sim *gpu, //scedulers //must currently occur after all inputs have been initialized. + std::string sched_config = m_config->gpgpu_scheduler_string; + bool tlsched = sched_config.find("tl") != std::string::npos; + int tlmaw; + if (tlsched){ + sscanf(m_config->gpgpu_scheduler_string, "tl:%d", &tlmaw); + } for (int i = 0; i < m_config->gpgpu_num_sched_per_core; i++) { - schedulers.push_back(scheduler_unit(m_stats,this,m_scoreboard,m_simt_stack,&m_warp, - &m_pipeline_reg[ID_OC_SP], - &m_pipeline_reg[ID_OC_SFU], - &m_pipeline_reg[ID_OC_MEM])); + //###CONFIGURATION + if (tlsched){ + schedulers.push_back(new TwoLevelScheduler(m_stats,this,m_scoreboard,m_simt_stack,&m_warp, + &m_pipeline_reg[ID_OC_SP], + &m_pipeline_reg[ID_OC_SFU], + &m_pipeline_reg[ID_OC_MEM], + tlmaw)); + } else { + schedulers.push_back(new LooseRoundRobbinScheduler(m_stats,this,m_scoreboard,m_simt_stack,&m_warp, + &m_pipeline_reg[ID_OC_SP], + &m_pipeline_reg[ID_OC_SFU], + &m_pipeline_reg[ID_OC_MEM])); + } } for (unsigned i = 0; i < m_warp.size(); i++) { //distribute i's evenly though schedulers; - schedulers[i%m_config->gpgpu_num_sched_per_core].add_supervised_warp_id(i); + schedulers[i%m_config->gpgpu_num_sched_per_core]->add_supervised_warp_id(i); } //op collector configuration @@ -543,7 +558,7 @@ void shader_core_ctx::issue_warp( register_set& pipe_reg_set, const warp_inst_t* void shader_core_ctx::issue(){ //really is issue; for (unsigned i = 0; i < schedulers.size(); i++) { - schedulers[i].cycle(); + schedulers[i]->cycle(); } } @@ -551,7 +566,7 @@ shd_warp_t& scheduler_unit::warp(int i){ return (*m_warp)[i]; } -void scheduler_unit::cycle() +void LooseRoundRobbinScheduler::cycle() { bool valid_inst = false; // there was one warp with a valid instruction to issue (didn't require flush due to control hazard) bool ready_inst = false; // of the valid instructions, there was one not waiting for pending register writes @@ -632,6 +647,126 @@ void scheduler_unit::cycle() m_stats->shader_cycle_distro[2]++; // pipeline stalled } +void TwoLevelScheduler::cycle() { + //Move waiting warps to pendingWarps + for ( std::list::iterator iter = activeWarps.begin(); + iter != activeWarps.end(); + iter ++) { + bool waiting = warp(*iter).waiting(); + for (int i=0; i<4; i++){ + const warp_inst_t* inst = warp(*iter).ibuffer_next_inst(); + //Is the instruction waiting on a long operation? + if ( inst && inst->in[i] > 0 && this->m_scoreboard->islongop(*iter, inst->in[i])){ + waiting = true; + } + } + + if(waiting){ + pendingWarps.push_back(*iter); + activeWarps.erase(iter); + break; + } + } + + //If there is space in activeWarps, try to find ready warps in pendingWarps + if (this->activeWarps.size() < maxActiveWarps){ + for ( std::list::iterator iter = pendingWarps.begin(); + iter != pendingWarps.end(); + iter++){ + if(!warp(*iter).waiting()){ + activeWarps.push_back(*iter); + pendingWarps.erase(iter); + break; + } + } + } + + //Do the scheduling only from activeWarps + //If you schedule an instruction, move it to the end of the list + + bool valid_inst = false; // there was one warp with a valid instruction to issue (didn't require flush due to control hazard) + bool ready_inst = false; // of the valid instructions, there was one not waiting for pending register writes + bool issued_inst = false; // of these we issued one + + for ( std::list::iterator warp_id = activeWarps.begin(); + warp_id != activeWarps.end(); + warp_id++) { + unsigned checked=0; + unsigned issued=0; + unsigned max_issue = m_shader->m_config->gpgpu_max_insn_issue_per_warp; + while(!warp(*warp_id).waiting() && !warp(*warp_id).ibuffer_empty() && (checked < max_issue) && (checked <= issued) && (issued < max_issue) ) { + const warp_inst_t *pI = warp(*warp_id).ibuffer_next_inst(); + bool valid = warp(*warp_id).ibuffer_next_valid(); + bool warp_inst_issued = false; + unsigned pc,rpc; + m_simt_stack[*warp_id]->get_pdom_stack_top_info(&pc,&rpc); + if( pI ) { + assert(valid); + if( pc != pI->pc ) { + // control hazard + warp(*warp_id).set_next_pc(pc); + warp(*warp_id).ibuffer_flush(); + } else { + valid_inst = true; + if ( !m_scoreboard->checkCollision(*warp_id, pI) ) { + ready_inst = true; + const active_mask_t &active_mask = m_simt_stack[*warp_id]->get_active_mask(); + assert( warp(*warp_id).inst_in_pipeline() ); + if ( (pI->op == LOAD_OP) || (pI->op == STORE_OP) || (pI->op == MEMORY_BARRIER_OP) ) { + if( m_mem_out->has_free() ) { + m_shader->issue_warp(*m_mem_out,pI,active_mask,*warp_id); + issued++; + issued_inst=true; + warp_inst_issued = true; + // Move it to pendingWarps + unsigned currwarp = *warp_id; + activeWarps.erase(warp_id); + activeWarps.push_back(currwarp); + } + } else { + bool sp_pipe_avail = m_sp_out->has_free(); + bool sfu_pipe_avail = m_sfu_out->has_free(); + if( sp_pipe_avail && (pI->op != SFU_OP) ) { + // always prefer SP pipe for operations that can use both SP and SFU pipelines + m_shader->issue_warp(*m_sp_out,pI,active_mask,*warp_id); + issued++; + issued_inst=true; + warp_inst_issued = true; + //Move it to end of the activeWarps + unsigned currwarp = *warp_id; + activeWarps.erase(warp_id); + activeWarps.push_back(currwarp); + } else if ( (pI->op == SFU_OP) || (pI->op == ALU_SFU_OP) ) { + if( sfu_pipe_avail ) { + m_shader->issue_warp(*m_sfu_out,pI,active_mask,*warp_id); + issued++; + issued_inst=true; + warp_inst_issued = true; + //Move it to end of the activeWarps + unsigned currwarp = *warp_id; + activeWarps.erase(warp_id); + activeWarps.push_back(currwarp); + + } + } + } + } + } + } else if( valid ) { + // this case can happen after a return instruction in diverged warp + warp(*warp_id).set_next_pc(pc); + warp(*warp_id).ibuffer_flush(); + } + if(warp_inst_issued) + warp(*warp_id).ibuffer_step(); + checked++; + } + if ( issued ) { + break; + } + } +} + void shader_core_ctx::read_operands() { } diff --git a/src/gpgpu-sim/shader.h b/src/gpgpu-sim/shader.h index 341915e..5612150 100644 --- a/src/gpgpu-sim/shader.h +++ b/src/gpgpu-sim/shader.h @@ -258,12 +258,14 @@ public: register_set* mem_out) : supervised_warps(), m_last_sup_id_issued(0), m_stats(stats), m_shader(shader), m_scoreboard(scoreboard), m_simt_stack(simt), /*m_pipeline_reg(pipe_regs),*/ m_warp(warp), - m_sp_out(sp_out),m_sfu_out(sfu_out),m_mem_out(mem_out){} - void add_supervised_warp_id(int i) { + m_sp_out(sp_out),m_sfu_out(sfu_out),m_mem_out(mem_out){} + virtual ~scheduler_unit(){} + virtual void add_supervised_warp_id(int i) { supervised_warps.push_back(i); } - void cycle(); -private: + + virtual void cycle()=0; +protected: shd_warp_t& warp(int i); std::vector supervised_warps; @@ -280,8 +282,45 @@ private: register_set* m_mem_out; }; +class LooseRoundRobbinScheduler : public scheduler_unit { +public: + LooseRoundRobbinScheduler (shader_core_stats* stats, shader_core_ctx* shader, + Scoreboard* scoreboard, simt_stack** simt, + std::vector* warp, + register_set* sp_out, + register_set* sfu_out, + register_set* mem_out) + : scheduler_unit (stats, shader, scoreboard, simt, warp, sp_out, sfu_out, mem_out){} + virtual ~LooseRoundRobbinScheduler () {} + virtual void cycle (); +}; +class TwoLevelScheduler : public scheduler_unit { +public: + TwoLevelScheduler (shader_core_stats* stats, shader_core_ctx* shader, + Scoreboard* scoreboard, simt_stack** simt, + std::vector* warp, + register_set* sp_out, + register_set* sfu_out, + register_set* mem_out, + unsigned maw) + : scheduler_unit (stats, shader, scoreboard, simt, warp, sp_out, sfu_out, mem_out), + activeWarps(), + pendingWarps(){ + maxActiveWarps = maw; + } + virtual ~TwoLevelScheduler () {} + virtual void cycle (); + virtual void add_supervised_warp_id(int i) { + pendingWarps.push_back(i); + } +private: + unsigned maxActiveWarps; + std::list activeWarps; + std::list pendingWarps; +}; + class opndcoll_rfu_t { // operand collector based register file unit @@ -985,6 +1024,8 @@ struct shader_core_config : public core_config unsigned max_warps_per_shader; unsigned max_cta_per_core; //Limit on number of concurrent CTAs in shader core + char * gpgpu_scheduler_string; + char* pipeline_widths_string; int pipe_widths[N_PIPELINE_STAGES]; @@ -1016,7 +1057,7 @@ struct shader_core_config : public core_config int gpgpu_num_sp_units; int gpgpu_num_sfu_units; - int gpgpu_num_mem_units; + int gpgpu_num_mem_units; //Shader core resources unsigned gpgpu_shader_registers; @@ -1101,6 +1142,8 @@ private: friend class ldst_unit; friend class simt_core_cluster; friend class scheduler_unit; + friend class TwoLevelScheduler; + friend class LooseRoundRobbinScheduler; }; class shader_core_mem_fetch_allocator : public mem_fetch_allocator { @@ -1218,6 +1261,8 @@ private: void issue(); friend class scheduler_unit; //this is needed to use private issue warp. + friend class TwoLevelScheduler; + friend class LooseRoundRobbinScheduler; void issue_warp( register_set& warp, const warp_inst_t *pI, const active_mask_t &active_mask, unsigned warp_id ); void func_exec_inst( warp_inst_t &inst ); @@ -1272,7 +1317,7 @@ private: opndcoll_rfu_t m_operand_collector; //schedule - std::vector schedulers; + std::vector schedulers; // execute unsigned m_num_function_units; -- cgit v1.3