Adding a two level scheduler as described in the ISCA 2012 tutorial

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

8 files changed, 225 insertions, 13 deletions

diff --git a/CHANGES b/CHANGES
index 0d851e0..6a98c69 100644
--- a/CHANGES
+++ b/CHANGES
@@ -8,6 +8,7 @@ Version 3.1.0+edits (development branch) versus 3.1.0
 - Change cuobjdump_to_ptxplus to use std::string instead of char*.
 - Change Fermi configuration folder name to GTX480.
 - Added TeslaC2050 configuration.
+- Added a two level warp scheduler (as presented at ISCA 2012 tutorial).
 - Bug Fixes:
     - Fixed a couple of memory errors in cuobjdump_to_ptxplus code.
     - Implemented better support for handling memory operand type modifier
diff --git a/configs/GTX480/gpgpusim.config b/configs/GTX480/gpgpusim.config
index 1122bbe..72777a1 100644
--- a/configs/GTX480/gpgpusim.config
+++ b/configs/GTX480/gpgpusim.config
@@ -92,6 +92,10 @@
 
 # Fermi has two schedulers per core
 -gpgpu_num_sched_per_core 2
+# Two Level Scheduler
+#-gpgpu_scheduler tl:16
+# Loose round robbin scheduler
+-gpgpu_scheduler lrr
 
 # stat collection
 -gpgpu_memlatency_stat 14 
diff --git a/configs/TeslaC2050/gpgpusim.config b/configs/TeslaC2050/gpgpusim.config
index d51f0d4..7ff39b1 100644
--- a/configs/TeslaC2050/gpgpusim.config
+++ b/configs/TeslaC2050/gpgpusim.config
@@ -92,6 +92,10 @@
 
 # Fermi has two schedulers per core
 -gpgpu_num_sched_per_core 2
+# Two Level Scheduler
+#-gpgpu_scheduler tl:16
+# Loose round robbin scheduler
+-gpgpu_scheduler lrr
 
 # stat collection
 -gpgpu_memlatency_stat 14 
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<unsigned> > reg_table;
+    //Register that depend on a long operation (global, local or tex memory)
+    std::vector< std::set<unsigned> > 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<int>::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<int>::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<int>::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<int> 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<shd_warp_t>* 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<shd_warp_t>* 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<int> activeWarps;
+	std::list<int> 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<scheduler_unit>  schedulers;
+    std::vector<scheduler_unit*>  schedulers;
 
     // execute
     unsigned m_num_function_units;