/*
- * Copyright (c) 2004-2005 The Regents of The University of Michigan
+ * Copyright (c) 2004-2006 The Regents of The University of Michigan
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-#ifndef __CPU_O3_CPU_INST_QUEUE_HH__
-#define __CPU_O3_CPU_INST_QUEUE_HH__
+#ifndef __CPU_O3_INST_QUEUE_HH__
+#define __CPU_O3_INST_QUEUE_HH__
#include <list>
#include <map>
#include "base/statistics.hh"
#include "base/timebuf.hh"
#include "cpu/inst_seq.hh"
+#include "cpu/o3/dep_graph.hh"
+#include "encumbered/cpu/full/op_class.hh"
#include "sim/host.hh"
+class FUPool;
+class MemInterface;
+
/**
* A standard instruction queue class. It holds ready instructions, in
* order, in seperate priority queues to facilitate the scheduling of
* floating point registers have their indices start after the integer
* registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
* and 96-191 are fp). This remains true even for both logical and
- * physical register indices.
+ * physical register indices. The IQ depends on the memory dependence unit to
+ * track when memory operations are ready in terms of ordering; register
+ * dependencies are tracked normally. Right now the IQ also handles the
+ * execution timing; this is mainly to allow back-to-back scheduling without
+ * requiring IEW to be able to peek into the IQ. At the end of the execution
+ * latency, the instruction is put into the queue to execute, where it will
+ * have the execute() function called on it.
+ * @todo: Make IQ able to handle multiple FU pools.
*/
template <class Impl>
class InstructionQueue
typedef typename Impl::DynInstPtr DynInstPtr;
typedef typename Impl::Params Params;
+ typedef typename Impl::CPUPol::IEW IEW;
typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
typedef typename Impl::CPUPol::IssueStruct IssueStruct;
typedef typename Impl::CPUPol::TimeStruct TimeStruct;
- // Typedef of iterator through the list of instructions. Might be
- // better to untie this from the FullCPU or pass its information to
- // the stages.
+ // Typedef of iterator through the list of instructions.
typedef typename std::list<DynInstPtr>::iterator ListIt;
- /**
- * Struct for comparing entries to be added to the priority queue. This
- * gives reverse ordering to the instructions in terms of sequence
- * numbers: the instructions with smaller sequence numbers (and hence
- * are older) will be at the top of the priority queue.
- */
- struct pqCompare
- {
- bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
- {
- return lhs->seqNum > rhs->seqNum;
- }
- };
+ friend class Impl::FullCPU;
- /**
- * Struct for comparing entries to be added to the set. This gives
- * standard ordering in terms of sequence numbers.
- */
- struct setCompare
- {
- bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
- {
- return lhs->seqNum < rhs->seqNum;
- }
+ /** FU completion event class. */
+ class FUCompletion : public Event {
+ private:
+ /** Executing instruction. */
+ DynInstPtr inst;
+
+ /** Index of the FU used for executing. */
+ int fuIdx;
+
+ /** Pointer back to the instruction queue. */
+ InstructionQueue<Impl> *iqPtr;
+
+ bool freeFU;
+
+ public:
+ /** Construct a FU completion event. */
+ FUCompletion(DynInstPtr &_inst, int fu_idx,
+ InstructionQueue<Impl> *iq_ptr);
+
+ virtual void process();
+ virtual const char *description();
+ void setFreeFU() { freeFU = true; }
};
- typedef std::priority_queue<DynInstPtr, vector<DynInstPtr>, pqCompare>
- ReadyInstQueue;
+ /** Constructs an IQ. */
+ InstructionQueue(Params *params);
- InstructionQueue(Params ¶ms);
+ /** Destructs the IQ. */
+ ~InstructionQueue();
+ /** Returns the name of the IQ. */
+ std::string name() const;
+
+ /** Registers statistics. */
void regStats();
- void setCPU(FullCPU *cpu);
+ void resetState();
+
+ /** Sets CPU pointer. */
+ void setCPU(FullCPU *_cpu) { cpu = _cpu; }
+ /** Sets active threads list. */
+ void setActiveThreads(std::list<unsigned> *at_ptr);
+
+ /** Sets the IEW pointer. */
+ void setIEW(IEW *iew_ptr) { iewStage = iew_ptr; }
+
+ /** Sets the timer buffer between issue and execute. */
void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
+ /** Sets the global time buffer. */
void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
+ void switchOut();
+
+ void takeOverFrom();
+
+ bool isSwitchedOut() { return switchedOut; }
+
+ /** Number of entries needed for given amount of threads. */
+ int entryAmount(int num_threads);
+
+ /** Resets max entries for all threads. */
+ void resetEntries();
+
+ /** Returns total number of free entries. */
unsigned numFreeEntries();
+ /** Returns number of free entries for a thread. */
+ unsigned numFreeEntries(unsigned tid);
+
+ /** Returns whether or not the IQ is full. */
bool isFull();
+ /** Returns whether or not the IQ is full for a specific thread. */
+ bool isFull(unsigned tid);
+
+ /** Returns if there are any ready instructions in the IQ. */
+ bool hasReadyInsts();
+
+ /** Inserts a new instruction into the IQ. */
void insert(DynInstPtr &new_inst);
+ /** Inserts a new, non-speculative instruction into the IQ. */
void insertNonSpec(DynInstPtr &new_inst);
- void advanceTail(DynInstPtr &inst);
+ /** Inserts a memory or write barrier into the IQ to make sure
+ * loads and stores are ordered properly.
+ */
+ void insertBarrier(DynInstPtr &barr_inst);
+ DynInstPtr getInstToExecute();
+
+ /**
+ * Records the instruction as the producer of a register without
+ * adding it to the rest of the IQ.
+ */
+ void recordProducer(DynInstPtr &inst)
+ { addToProducers(inst); }
+
+ /** Process FU completion event. */
+ void processFUCompletion(DynInstPtr &inst, int fu_idx);
+
+ /**
+ * Schedules ready instructions, adding the ready ones (oldest first) to
+ * the queue to execute.
+ */
void scheduleReadyInsts();
+ /** Schedules a single specific non-speculative instruction. */
void scheduleNonSpec(const InstSeqNum &inst);
- void wakeDependents(DynInstPtr &completed_inst);
+ /**
+ * Commits all instructions up to and including the given sequence number,
+ * for a specific thread.
+ */
+ void commit(const InstSeqNum &inst, unsigned tid = 0);
+
+ /** Wakes all dependents of a completed instruction. */
+ int wakeDependents(DynInstPtr &completed_inst);
+
+ /** Adds a ready memory instruction to the ready list. */
+ void addReadyMemInst(DynInstPtr &ready_inst);
+
+ /**
+ * Reschedules a memory instruction. It will be ready to issue once
+ * replayMemInst() is called.
+ */
+ void rescheduleMemInst(DynInstPtr &resched_inst);
+
+ /** Replays a memory instruction. It must be rescheduled first. */
+ void replayMemInst(DynInstPtr &replay_inst);
+ /** Completes a memory operation. */
+ void completeMemInst(DynInstPtr &completed_inst);
+
+ /** Indicates an ordering violation between a store and a load. */
void violation(DynInstPtr &store, DynInstPtr &faulting_load);
- // Change this to take in the sequence number
- void squash();
+ /**
+ * Squashes instructions for a thread. Squashing information is obtained
+ * from the time buffer.
+ */
+ void squash(unsigned tid);
- void doSquash();
+ /** Returns the number of used entries for a thread. */
+ unsigned getCount(unsigned tid) { return count[tid]; };
- void stopSquash();
+ /** Debug function to print all instructions. */
+ void printInsts();
private:
+ /** Does the actual squashing. */
+ void doSquash(unsigned tid);
+
+ /////////////////////////
+ // Various pointers
+ /////////////////////////
+
/** Pointer to the CPU. */
FullCPU *cpu;
+ /** Cache interface. */
+ MemInterface *dcacheInterface;
+
+ /** Pointer to IEW stage. */
+ IEW *iewStage;
+
/** The memory dependence unit, which tracks/predicts memory dependences
* between instructions.
*/
- MemDepUnit memDepUnit;
+ MemDepUnit memDepUnit[Impl::MaxThreads];
/** The queue to the execute stage. Issued instructions will be written
* into it.
/** Wire to read information from timebuffer. */
typename TimeBuffer<TimeStruct>::wire fromCommit;
- enum InstList {
- Int,
- Float,
- Branch,
- Memory,
- Misc,
- Squashed,
- None
- };
+ /** Function unit pool. */
+ FUPool *fuPool;
- /** List of ready int instructions. Used to keep track of the order in
- * which instructions should issue.
- */
- ReadyInstQueue readyIntInsts;
+ //////////////////////////////////////
+ // Instruction lists, ready queues, and ordering
+ //////////////////////////////////////
- /** List of ready floating point instructions. */
- ReadyInstQueue readyFloatInsts;
+ /** List of all the instructions in the IQ (some of which may be issued). */
+ std::list<DynInstPtr> instList[Impl::MaxThreads];
- /** List of ready branch instructions. */
- ReadyInstQueue readyBranchInsts;
+ std::list<DynInstPtr> instsToExecute;
- /** List of ready miscellaneous instructions. */
- ReadyInstQueue readyMiscInsts;
+ /**
+ * Struct for comparing entries to be added to the priority queue. This
+ * gives reverse ordering to the instructions in terms of sequence
+ * numbers: the instructions with smaller sequence numbers (and hence
+ * are older) will be at the top of the priority queue.
+ */
+ struct pqCompare {
+ bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
+ {
+ return lhs->seqNum > rhs->seqNum;
+ }
+ };
+
+ typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
+ ReadyInstQueue;
- /** List of squashed instructions (which are still valid and in IQ).
- * Implemented using a priority queue; the entries must contain both
- * the IQ index and sequence number of each instruction so that
- * ordering based on sequence numbers can be used.
+ /** List of ready instructions, per op class. They are separated by op
+ * class to allow for easy mapping to FUs.
*/
- ReadyInstQueue squashedInsts;
+ ReadyInstQueue readyInsts[Num_OpClasses];
/** List of non-speculative instructions that will be scheduled
* once the IQ gets a signal from commit. While it's redundant to
*/
std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
- typedef typename std::map<InstSeqNum, DynInstPtr>::iterator non_spec_it_t;
+ typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;
- /** Number of free IQ entries left. */
- unsigned freeEntries;
+ /** Entry for the list age ordering by op class. */
+ struct ListOrderEntry {
+ OpClass queueType;
+ InstSeqNum oldestInst;
+ };
- /** The number of entries in the instruction queue. */
- unsigned numEntries;
+ /** List that contains the age order of the oldest instruction of each
+ * ready queue. Used to select the oldest instruction available
+ * among op classes.
+ * @todo: Might be better to just move these entries around instead
+ * of creating new ones every time the position changes due to an
+ * instruction issuing. Not sure std::list supports this.
+ */
+ std::list<ListOrderEntry> listOrder;
+
+ typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;
+
+ /** Tracks if each ready queue is on the age order list. */
+ bool queueOnList[Num_OpClasses];
- /** The number of integer instructions that can be issued in one
- * cycle.
+ /** Iterators of each ready queue. Points to their spot in the age order
+ * list.
*/
- unsigned intWidth;
+ ListOrderIt readyIt[Num_OpClasses];
- /** The number of floating point instructions that can be issued
- * in one cycle.
+ /** Add an op class to the age order list. */
+ void addToOrderList(OpClass op_class);
+
+ /**
+ * Called when the oldest instruction has been removed from a ready queue;
+ * this places that ready queue into the proper spot in the age order list.
*/
- unsigned floatWidth;
+ void moveToYoungerInst(ListOrderIt age_order_it);
+
+ DependencyGraph<DynInstPtr> dependGraph;
+
+ //////////////////////////////////////
+ // Various parameters
+ //////////////////////////////////////
+
+ /** IQ Resource Sharing Policy */
+ enum IQPolicy {
+ Dynamic,
+ Partitioned,
+ Threshold
+ };
+
+ /** IQ sharing policy for SMT. */
+ IQPolicy iqPolicy;
- /** The number of branches that can be issued in one cycle. */
- unsigned branchWidth;
+ /** Number of Total Threads*/
+ unsigned numThreads;
- /** The number of memory instructions that can be issued in one cycle. */
- unsigned memoryWidth;
+ /** Pointer to list of active threads. */
+ std::list<unsigned> *activeThreads;
+
+ /** Per Thread IQ count */
+ unsigned count[Impl::MaxThreads];
+
+ /** Max IQ Entries Per Thread */
+ unsigned maxEntries[Impl::MaxThreads];
+
+ /** Number of free IQ entries left. */
+ unsigned freeEntries;
+
+ /** The number of entries in the instruction queue. */
+ unsigned numEntries;
/** The total number of instructions that can be issued in one cycle. */
unsigned totalWidth;
- //The number of physical registers in the CPU.
+ /** The number of physical registers in the CPU. */
unsigned numPhysRegs;
/** The number of physical integer registers in the CPU. */
*/
unsigned commitToIEWDelay;
- //////////////////////////////////
- // Variables needed for squashing
- //////////////////////////////////
+ bool switchedOut;
/** The sequence number of the squashed instruction. */
- InstSeqNum squashedSeqNum;
-
- /** Iterator that points to the youngest instruction in the IQ. */
- ListIt tail;
-
- /** Iterator that points to the last instruction that has been squashed.
- * This will not be valid unless the IQ is in the process of squashing.
- */
- ListIt squashIt;
-
- ///////////////////////////////////
- // Dependency graph stuff
- ///////////////////////////////////
-
- class DependencyEntry
- {
- public:
- DynInstPtr inst;
- //Might want to include data about what arch. register the
- //dependence is waiting on.
- DependencyEntry *next;
-
- //This function, and perhaps this whole class, stand out a little
- //bit as they don't fit a classification well. I want access
- //to the underlying structure of the linked list, yet at
- //the same time it feels like this should be something abstracted
- //away. So for now it will sit here, within the IQ, until
- //a better implementation is decided upon.
- // This function probably shouldn't be within the entry...
- void insert(DynInstPtr &new_inst);
-
- void remove(DynInstPtr &inst_to_remove);
-
- // Debug variable, remove when done testing.
- static unsigned mem_alloc_counter;
- };
-
- /** Array of linked lists. Each linked list is a list of all the
- * instructions that depend upon a given register. The actual
- * register's index is used to index into the graph; ie all
- * instructions in flight that are dependent upon r34 will be
- * in the linked list of dependGraph[34].
- */
- DependencyEntry *dependGraph;
+ InstSeqNum squashedSeqNum[Impl::MaxThreads];
/** A cache of the recently woken registers. It is 1 if the register
* has been woken up recently, and 0 if the register has been added
* is basically a secondary scoreboard, and should pretty much mirror
* the scoreboard that exists in the rename map.
*/
- vector<bool> regScoreboard;
+ std::vector<bool> regScoreboard;
+ /** Adds an instruction to the dependency graph, as a consumer. */
bool addToDependents(DynInstPtr &new_inst);
- void insertDependency(DynInstPtr &new_inst);
- void createDependency(DynInstPtr &new_inst);
+ /** Adds an instruction to the dependency graph, as a producer. */
+ void addToProducers(DynInstPtr &new_inst);
+
+ /** Moves an instruction to the ready queue if it is ready. */
void addIfReady(DynInstPtr &inst);
- private:
/** Debugging function to count how many entries are in the IQ. It does
* a linear walk through the instructions, so do not call this function
* during normal execution.
*/
int countInsts();
- /** Debugging function to dump out the dependency graph.
- */
- void dumpDependGraph();
-
/** Debugging function to dump all the list sizes, as well as print
* out the list of nonspeculative instructions. Should not be used
* in any other capacity, but it has no harmful sideaffects.
*/
void dumpLists();
+ /** Debugging function to dump out all instructions that are in the
+ * IQ.
+ */
+ void dumpInsts();
+
+ /** Stat for number of instructions added. */
Stats::Scalar<> iqInstsAdded;
+ /** Stat for number of non-speculative instructions added. */
Stats::Scalar<> iqNonSpecInstsAdded;
-// Stats::Scalar<> iqIntInstsAdded;
+
+ Stats::Scalar<> iqInstsIssued;
+ /** Stat for number of integer instructions issued. */
Stats::Scalar<> iqIntInstsIssued;
-// Stats::Scalar<> iqFloatInstsAdded;
+ /** Stat for number of floating point instructions issued. */
Stats::Scalar<> iqFloatInstsIssued;
-// Stats::Scalar<> iqBranchInstsAdded;
+ /** Stat for number of branch instructions issued. */
Stats::Scalar<> iqBranchInstsIssued;
-// Stats::Scalar<> iqMemInstsAdded;
+ /** Stat for number of memory instructions issued. */
Stats::Scalar<> iqMemInstsIssued;
-// Stats::Scalar<> iqMiscInstsAdded;
+ /** Stat for number of miscellaneous instructions issued. */
Stats::Scalar<> iqMiscInstsIssued;
+ /** Stat for number of squashed instructions that were ready to issue. */
Stats::Scalar<> iqSquashedInstsIssued;
- Stats::Scalar<> iqLoopSquashStalls;
+ /** Stat for number of squashed instructions examined when squashing. */
Stats::Scalar<> iqSquashedInstsExamined;
+ /** Stat for number of squashed instruction operands examined when
+ * squashing.
+ */
Stats::Scalar<> iqSquashedOperandsExamined;
+ /** Stat for number of non-speculative instructions removed due to a squash.
+ */
Stats::Scalar<> iqSquashedNonSpecRemoved;
+ Stats::VectorDistribution<> queueResDist;
+ Stats::Distribution<> numIssuedDist;
+ Stats::VectorDistribution<> issueDelayDist;
+
+ Stats::Vector<> statFuBusy;
+// Stats::Vector<> dist_unissued;
+ Stats::Vector2d<> statIssuedInstType;
+
+ Stats::Formula issueRate;
+// Stats::Formula issue_stores;
+// Stats::Formula issue_op_rate;
+ Stats::Vector<> fuBusy; //cumulative fu busy
+
+ Stats::Formula fuBusyRate;
};
-#endif //__CPU_O3_CPU_INST_QUEUE_HH__
+#endif //__CPU_O3_INST_QUEUE_HH__
projects / gem5.git / blobdiff