inorder: resource scheduling backend

replace priority queue with vector of lists(1 list per stage) and place inside a class
so that we have more control of when an instruction uses a particular schedule entry
...
also, this is the 1st step toward making the InOrderCPU fully parameterizable. See the
wiki for details on this process

7 files changed, 300 insertions, 59 deletions

diff --git a/src/cpu/inorder/SConscript b/src/cpu/inorder/SConscript
index 3717c2f57..90cb285f5 100644
--- a/src/cpu/inorder/SConscript
+++ b/src/cpu/inorder/SConscript
@@ -82,6 +82,7 @@ if 'InOrderCPU' in env['CPU_MODELS']:
 	Source('resources/fetch_seq_unit.cc')
 	Source('resources/mult_div_unit.cc')
 	Source('resource_pool.cc')
+	Source('resource_sked.cc')	
 	Source('reg_dep_map.cc')
 	Source('thread_state.cc')
 	Source('thread_context.cc')
diff --git a/src/cpu/inorder/cpu.cc b/src/cpu/inorder/cpu.cc
index d36867439..a895fdb0e 100644
--- a/src/cpu/inorder/cpu.cc
+++ b/src/cpu/inorder/cpu.cc
@@ -1354,7 +1354,7 @@ InOrderCPU::cleanUpRemovedInsts()
         // Make Sure Resource Schedule Is Emptied Out
         ThePipeline::ResSchedule *inst_sched = &inst->resSched;
         while (!inst_sched->empty()) {
-            ThePipeline::ScheduleEntry* sch_entry = inst_sched->top();
+            ScheduleEntry* sch_entry = inst_sched->top();
             inst_sched->pop();
             delete sch_entry;
         }
diff --git a/src/cpu/inorder/inorder_dyn_inst.hh b/src/cpu/inorder/inorder_dyn_inst.hh
index 1a349676f..ffb795e1e 100644
--- a/src/cpu/inorder/inorder_dyn_inst.hh
+++ b/src/cpu/inorder/inorder_dyn_inst.hh
@@ -50,6 +50,7 @@
 #include "cpu/inorder/inorder_trace.hh"
 #include "cpu/inorder/pipeline_traits.hh"
 #include "cpu/inorder/resource.hh"
+#include "cpu/inorder/resource_sked.hh"
 #include "cpu/inorder/thread_state.hh"
 #include "cpu/inst_seq.hh"
 #include "cpu/op_class.hh"
@@ -436,7 +437,7 @@ class InOrderDynInst : public FastAlloc, public RefCounted
     void deleteStages();
 
     /** Add A Entry To Reource Schedule */
-    void addToSched(ThePipeline::ScheduleEntry* sched_entry)
+    void addToSched(ScheduleEntry* sched_entry)
     { resSched.push(sched_entry); }
 
 
@@ -481,7 +482,7 @@ class InOrderDynInst : public FastAlloc, public RefCounted
     void popSchedEntry()
     {
         if (!resSched.empty()) {
-            ThePipeline::ScheduleEntry* sked = resSched.top();
+            ScheduleEntry* sked = resSched.top();
             resSched.pop();
             if (sked != 0) {
                 delete sked;
diff --git a/src/cpu/inorder/pipeline_traits.cc b/src/cpu/inorder/pipeline_traits.cc
index 397170163..fe400471a 100644
--- a/src/cpu/inorder/pipeline_traits.cc
+++ b/src/cpu/inorder/pipeline_traits.cc
@@ -77,6 +77,8 @@ void createFrontEndSchedule(DynInstPtr &inst)
     D->needs(Decode, DecodeUnit::DecodeInst);
     D->needs(BPred, BranchPredictor::PredictBranch);
     D->needs(FetchSeq, FetchSeqUnit::UpdateTargetPC);
+
+    inst->resSched.init();
 }
 
 bool createBackEndSchedule(DynInstPtr &inst)
@@ -152,4 +154,18 @@ InstStage::InstStage(DynInstPtr inst, int stage_num)
     instSched = &inst->resSched;
 }
 
+void
+InstStage::needs(int unit, int request) {
+    instSched->push( new ScheduleEntry(
+                         stageNum, nextTaskPriority++, unit, request
+                         ));
+}
+
+void
+InstStage::needs(int unit, int request, int param) {
+    instSched->push( new ScheduleEntry(
+                         stageNum, nextTaskPriority++, unit, request, param
+                         ));
+}
+
 };
diff --git a/src/cpu/inorder/pipeline_traits.hh b/src/cpu/inorder/pipeline_traits.hh
index 0f996023b..7abfc9a81 100644
--- a/src/cpu/inorder/pipeline_traits.hh
+++ b/src/cpu/inorder/pipeline_traits.hh
@@ -42,6 +42,8 @@
 #include "params/InOrderCPU.hh"
 
 class InOrderDynInst;
+class ScheduleEntry;
+class ResourceSked;
 
 /* This Namespace contains constants, typedefs, functions and
  * objects specific to the Pipeline Implementation.
@@ -88,51 +90,7 @@ namespace ThePipeline {
     //////////////////////////
     // RESOURCE SCHEDULING
     //////////////////////////
-    struct ScheduleEntry {
-        ScheduleEntry(int stage_num, int _priority, int res_num, int _cmd = 0,
-                      int _idx = 0) :
-            stageNum(stage_num), resNum(res_num), cmd(_cmd),
-            idx(_idx), priority(_priority)
-        { }
-
-        // Stage number to perform this service.
-        int stageNum;
-
-        // Resource ID to access
-        int resNum;
-
-        // See specific resource for meaning
-        unsigned cmd;
-
-        // See specific resource for meaning
-        unsigned idx;
-
-        // Some Resources May Need Priority?
-        int priority;
-    };
-
-    struct entryCompare {
-        bool operator()(const ScheduleEntry* lhs, const ScheduleEntry* rhs) 
-            const
-        {
-            // Prioritize first by stage number that the resource is needed
-            if (lhs->stageNum > rhs->stageNum) {
-                return true;
-            } else if (lhs->stageNum == rhs->stageNum) {
-                if (lhs->priority > rhs->priority) {
-                  return true;
-                } else {
-                  return false;
-                }
-            } else {
-                return false;
-            }
-        }
-    };
-
-
-    typedef std::priority_queue<ScheduleEntry*, std::vector<ScheduleEntry*>,
-                                         entryCompare> ResSchedule;
+    typedef ResourceSked ResSchedule;
 
     void createFrontEndSchedule(DynInstPtr &inst);
     bool createBackEndSchedule(DynInstPtr &inst);
@@ -147,17 +105,8 @@ namespace ThePipeline {
       public:
         InstStage(DynInstPtr inst, int stage_num);
 
-        void needs(int unit, int request) {
-            instSched->push( new ScheduleEntry(
-                stageNum, nextTaskPriority++, unit, request
-            ));
-        }
-
-        void needs(int unit, int request, int param) {
-            instSched->push( new ScheduleEntry(
-                stageNum, nextTaskPriority++, unit, request, param
-            ));
-        }
+        void needs(int unit, int request);
+        void needs(int unit, int request, int param);
     };
 };
 
diff --git a/src/cpu/inorder/resource_sked.cc b/src/cpu/inorder/resource_sked.cc
new file mode 100644
index 000000000..4104e6989
--- /dev/null
+++ b/src/cpu/inorder/resource_sked.cc
@@ -0,0 +1,187 @@
+/*
+ * Copyright (c) 2010 The Regents of The University of Michigan
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER 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.
+ *
+ * Authors: Korey Sewell
+ *
+ */
+
+#include "cpu/inorder/resource_sked.hh"
+#include "cpu/inorder/pipeline_traits.hh"
+
+#include <vector>
+#include <list>
+#include <stdio.h>
+
+using namespace std;
+using namespace ThePipeline;
+
+ResourceSked::ResourceSked()
+{
+    sked.resize(NumStages);
+}
+
+void
+ResourceSked::init()
+{
+    assert(!sked[0].empty());
+
+    curSkedEntry = sked[0].begin();
+}
+
+int
+ResourceSked::size()
+{
+    int total = 0;
+    for (int i = 0; i < sked.size(); i++) {
+        total += sked[i].size();
+    }
+
+    return total;
+}
+
+bool
+ResourceSked::empty()
+{
+    return size() == 0;
+}
+
+ScheduleEntry*
+ResourceSked::top()
+{
+    assert(size() > 0);
+
+    return *curSkedEntry;
+}
+
+void
+ResourceSked::pop()
+{
+    int stage_num = (*curSkedEntry)->stageNum;
+
+    sked[stage_num].erase(curSkedEntry);
+
+    if (!sked[stage_num].empty()) {
+        curSkedEntry = sked[stage_num].begin();
+    } else {
+        int next_stage = stage_num + 1;
+
+        while (next_stage < NumStages) {
+            if (sked[next_stage].empty()) {
+                next_stage++;
+            } else {
+                curSkedEntry = sked[next_stage].begin();
+                break;
+            }
+        }
+    }
+}
+
+void
+ResourceSked::push(ScheduleEntry* sked_entry)
+{
+    int stage_num = sked_entry->stageNum;
+    assert(stage_num < NumStages);
+
+    SkedIt pri_iter = findIterByPriority(sked_entry, stage_num);
+
+    sked[stage_num].insert(pri_iter, sked_entry);
+}
+
+void
+ResourceSked::pushBefore(ScheduleEntry* sked_entry, int sked_cmd,
+                         int sked_cmd_idx)
+{
+
+    int stage_num = sked_entry->stageNum;
+    assert(stage_num < NumStages);
+
+    SkedIt pri_iter = findIterByCommand(sked_entry, stage_num,
+                                        sked_cmd, sked_cmd_idx);
+
+    assert(pri_iter != sked[stage_num].end() &&
+           "Could not find command to insert in front of.");
+
+    sked[stage_num].insert(pri_iter, sked_entry);
+}
+
+ResourceSked::SkedIt
+ResourceSked::findIterByPriority(ScheduleEntry* sked_entry, int stage_num)
+{
+    if (sked[stage_num].empty()) {
+        return sked[stage_num].end();
+    }
+
+    int priority = sked_entry->priority;
+
+    SkedIt sked_it = sked[stage_num].begin();
+    SkedIt sked_end = sked[stage_num].end();
+
+    while (sked_it != sked_end) {
+        if ((*sked_it)->priority > priority)
+            break;
+
+        sked_it++;
+    }
+
+    return sked_it;
+}
+
+ResourceSked::SkedIt
+ResourceSked::findIterByCommand(ScheduleEntry* sked_entry, int stage_num,
+                                int sked_cmd, int sked_cmd_idx)
+{
+    if (sked[stage_num].empty()) {
+        return sked[stage_num].end();
+    }
+
+    SkedIt sked_it = sked[stage_num].begin();
+    SkedIt sked_end = sked[stage_num].end();
+
+    while (sked_it != sked_end) {
+        if ((*sked_it)->cmd == sked_cmd &&
+            (sked_cmd_idx != -1) ? (*sked_it)->idx == sked_cmd_idx : true)
+            break;
+
+        sked_it++;
+    }
+
+    return sked_it;
+}
+
+void
+ResourceSked::print()
+{
+    for (int i = 0; i < sked.size(); i++) {
+        cprintf("Stage %i\n====\n", i);
+        SkedIt sked_it = sked[i].begin();
+        SkedIt sked_end = sked[i].end();
+        while (sked_it != sked_end) {
+            cprintf("\t res:%i cmd:%i idx:%i\n", (*sked_it)->resNum, (*sked_it)->cmd, (*sked_it)->idx);
+            sked_it++;
+        }
+    }
+}
diff --git a/src/cpu/inorder/resource_sked.hh b/src/cpu/inorder/resource_sked.hh
new file mode 100644
index 000000000..22e29d728
--- /dev/null
+++ b/src/cpu/inorder/resource_sked.hh
@@ -0,0 +1,87 @@
+/*
+ * Copyright (c) 2010 The Regents of The University of Michigan
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER 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.
+ *
+ * Authors: Korey Sewell
+ *
+ */
+
+#ifndef __CPU_INORDER_RESOURCE_SKED_HH__
+#define __CPU_INORDER_RESOURCE_SKED_HH__
+
+#include <vector>
+#include <list>
+
+class ScheduleEntry {
+  public:
+    ScheduleEntry(int stage_num, int _priority, int res_num, int _cmd = 0,
+                  int _idx = 0) :
+        stageNum(stage_num), resNum(res_num), cmd(_cmd),
+        idx(_idx), priority(_priority)
+    { }
+
+    // Stage number to perform this service.
+    int stageNum;
+
+    // Resource ID to access
+    int resNum;
+
+    // See specific resource for meaning
+    unsigned cmd;
+
+    // See specific resource for meaning
+    unsigned idx;
+
+    // Some Resources May Need Priority
+    int priority;
+};
+
+class ResourceSked {
+  public:
+    typedef std::list<ScheduleEntry*>::iterator SkedIt;
+
+    ResourceSked();
+
+    void init();
+
+    int size();
+    bool empty();
+    ScheduleEntry* top();
+    void pop();
+    void push(ScheduleEntry* sked_entry);
+    void pushBefore(ScheduleEntry* sked_entry, int sked_cmd, int sked_cmd_idx);
+    void print();
+
+  private:
+    SkedIt curSkedEntry;
+    std::vector<std::list<ScheduleEntry*> > sked;
+
+    SkedIt findIterByPriority(ScheduleEntry *sked_entry, int stage_num);
+    SkedIt findIterByCommand(ScheduleEntry *sked_entry, int stage_num,
+                             int sked_cmd, int sked_cmd_idx = -1);
+};
+
+#endif //__CPU_INORDER_RESOURCE_SKED_HH__