summaryrefslogtreecommitdiff
path: root/src/cpu/minor/buffers.hh
diff options
context:
space:
mode:
Diffstat (limited to 'src/cpu/minor/buffers.hh')
-rw-r--r--src/cpu/minor/buffers.hh653
1 files changed, 653 insertions, 0 deletions
diff --git a/src/cpu/minor/buffers.hh b/src/cpu/minor/buffers.hh
new file mode 100644
index 000000000..f4ae91a70
--- /dev/null
+++ b/src/cpu/minor/buffers.hh
@@ -0,0 +1,653 @@
+/*
+ * Copyright (c) 2013-2014 ARM Limited
+ * All rights reserved
+ *
+ * The license below extends only to copyright in the software and shall
+ * not be construed as granting a license to any other intellectual
+ * property including but not limited to intellectual property relating
+ * to a hardware implementation of the functionality of the software
+ * licensed hereunder. You may use the software subject to the license
+ * terms below provided that you ensure that this notice is replicated
+ * unmodified and in its entirety in all distributions of the software,
+ * modified or unmodified, in source code or in binary form.
+ *
+ * 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: Andrew Bardsley
+ */
+
+/**
+ * @file
+ *
+ * Classes for buffer, queue and FIFO behaviour.
+ */
+
+#ifndef __CPU_MINOR_BUFFERS_HH__
+#define __CPU_MINOR_BUFFERS_HH__
+
+#include <iostream>
+#include <queue>
+#include <sstream>
+
+#include "cpu/minor/trace.hh"
+#include "cpu/activity.hh"
+#include "cpu/timebuf.hh"
+
+namespace Minor
+{
+
+/** Interface class for data with reporting/tracing facilities. This
+ * interface doesn't actually have to be used as other classes which need
+ * this interface uses templating rather than inheritance but it's provided
+ * here to document the interface needed by those classes. */
+class ReportIF
+{
+ public:
+ /** Print the data in a format suitable to be the value in "name=value"
+ * trace lines */
+ virtual void reportData(std::ostream &os) const = 0;
+
+ virtual ~ReportIF() { }
+};
+
+/** Interface class for data with 'bubble' values. This interface doesn't
+ * actually have to be used as other classes which need this interface uses
+ * templating rather than inheritance but it's provided here to document
+ * the interface needed by those classes. */
+class BubbleIF
+{
+ public:
+ virtual bool isBubble() const = 0;
+};
+
+/** ...ReportTraits are trait classes with the same functionality as
+ * ReportIF, but with elements explicitly passed into the report...
+ * functions. */
+
+/** Allow a template using ReportTraits to call report... functions of
+ * ReportIF-bearing elements themselves */
+template <typename ElemType> /* ElemType should implement ReportIF */
+class ReportTraitsAdaptor
+{
+ public:
+ static void
+ reportData(std::ostream &os, const ElemType &elem)
+ { elem.reportData(os); }
+};
+
+/** A similar adaptor but for elements held by pointer
+ * ElemType should implement ReportIF */
+template <typename PtrType>
+class ReportTraitsPtrAdaptor
+{
+ public:
+ static void
+ reportData(std::ostream &os, const PtrType &elem)
+ { elem->reportData(os); }
+};
+
+/** ... BubbleTraits are trait classes to add BubbleIF interface
+ * functionality to templates which process elements which don't necessarily
+ * implement BubbleIF themselves */
+
+/** Default behaviour, no bubbles */
+template <typename ElemType>
+class NoBubbleTraits
+{
+ public:
+ static bool isBubble(const ElemType &) { return false; }
+ static ElemType bubble() { assert(false); }
+};
+
+/** Pass on call to the element */
+template <typename ElemType>
+class BubbleTraitsAdaptor
+{
+ public:
+ static bool isBubble(const ElemType &elem)
+ { return elem.isBubble(); }
+
+ static ElemType bubble() { return ElemType::bubble(); }
+};
+
+/** Pass on call to the element where the element is a pointer */
+template <typename PtrType, typename ElemType>
+class BubbleTraitsPtrAdaptor
+{
+ public:
+ static bool isBubble(const PtrType &elem)
+ { return elem->isBubble(); }
+
+ static PtrType bubble() { return ElemType::bubble(); }
+};
+
+/** TimeBuffer with MinorTrace and Named interfaces */
+template <typename ElemType,
+ typename ReportTraits = ReportTraitsAdaptor<ElemType>,
+ typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
+class MinorBuffer : public Named, public TimeBuffer<ElemType>
+{
+ protected:
+ /** The range of elements that should appear in trace lines */
+ int reportLeft, reportRight;
+
+ /** Name to use for the data in a MinorTrace line */
+ std::string dataName;
+
+ public:
+ MinorBuffer(const std::string &name,
+ const std::string &data_name,
+ int num_past, int num_future,
+ int report_left = -1, int report_right = -1) :
+ Named(name), TimeBuffer<ElemType>(num_past, num_future),
+ reportLeft(report_left), reportRight(report_right),
+ dataName(data_name)
+ { }
+
+ public:
+ /* Is this buffer full of only bubbles */
+ bool
+ empty() const
+ {
+ bool ret = true;
+
+ for (int i = -this->past; i <= this->future; i++) {
+ if (!BubbleTraits::isBubble((*this)[i]))
+ ret = false;
+ }
+
+ return ret;
+ }
+
+ /** Report buffer states from 'slot' 'from' to 'to'. For example 0,-1
+ * will produce two slices with current (just assigned) and last (one
+ * advance() old) slices with the current (0) one on the left.
+ * Reverse the numbers to change the order of slices */
+ void
+ minorTrace() const
+ {
+ std::ostringstream data;
+
+ int step = (reportLeft > reportRight ? -1 : 1);
+ int end = reportRight + step;
+ int i = reportLeft;
+
+ while (i != end) {
+ const ElemType &datum = (*this)[i];
+
+ ReportTraits::reportData(data, datum);
+ i += step;
+ if (i != end)
+ data << ',';
+ }
+
+ MINORTRACE("%s=%s\n", dataName, data.str());
+ }
+};
+
+/** Wraps a MinorBuffer with Input/Output interfaces to ensure that units
+ * within the model can only see the right end of buffers between them. */
+template <typename Data>
+class Latch
+{
+ public:
+ typedef MinorBuffer<Data> Buffer;
+
+ protected:
+ /** Delays, in cycles, writing data into the latch and seeing it on the
+ * latched wires */
+ Cycles delay;
+
+ Buffer buffer;
+
+ public:
+ /** forward/backwardDelay specify the delay from input to output in each
+ * direction. These arguments *must* be >= 1 */
+ Latch(const std::string &name,
+ const std::string &data_name,
+ Cycles delay_ = Cycles(1),
+ bool report_backwards = false) :
+ delay(delay_),
+ buffer(name, data_name, delay_, 0, (report_backwards ? -delay_ : 0),
+ (report_backwards ? 0 : -delay_))
+ { }
+
+ public:
+ /** Encapsulate wires on either input or output of the latch.
+ * forward/backward correspond to data direction relative to the
+ * pipeline. Latched and Immediate specify delay for backward data.
+ * Immediate data is available to earlier stages *during* the cycle it
+ * is written */
+ class Input
+ {
+ public:
+ typename Buffer::wire inputWire;
+
+ public:
+ Input(typename Buffer::wire input_wire) :
+ inputWire(input_wire)
+ { }
+ };
+
+ class Output
+ {
+ public:
+ typename Buffer::wire outputWire;
+
+ public:
+ Output(typename Buffer::wire output_wire) :
+ outputWire(output_wire)
+ { }
+ };
+
+ bool empty() const { return buffer.empty(); }
+
+ /** An interface to just the input of the buffer */
+ Input input() { return Input(buffer.getWire(0)); }
+
+ /** An interface to just the output of the buffer */
+ Output output() { return Output(buffer.getWire(-delay)); }
+
+ void minorTrace() const { buffer.minorTrace(); }
+
+ void evaluate() { buffer.advance(); }
+};
+
+/** A pipeline simulating class that will stall (not advance when advance()
+ * is called) if a non-bubble value lies at the far end of the pipeline.
+ * The user can clear the stall before calling advance to unstall the
+ * pipeline. */
+template <typename ElemType,
+ typename ReportTraits,
+ typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
+class SelfStallingPipeline : public MinorBuffer<ElemType, ReportTraits>
+{
+ protected:
+ /** Wire at the input end of the pipeline (for convenience) */
+ typename TimeBuffer<ElemType>::wire pushWire;
+ /** Wire at the output end of the pipeline (for convenience) */
+ typename TimeBuffer<ElemType>::wire popWire;
+
+ public:
+ /** If true, advance will not advance the pipeline */
+ bool stalled;
+
+ /** The number of slots with non-bubbles in them */
+ unsigned int occupancy;
+
+ public:
+ SelfStallingPipeline(const std::string &name,
+ const std::string &data_name,
+ unsigned depth) :
+ MinorBuffer<ElemType, ReportTraits>
+ (name, data_name, depth, 0, -1, -depth),
+ pushWire(this->getWire(0)),
+ popWire(this->getWire(-depth)),
+ stalled(false),
+ occupancy(0)
+ {
+ assert(depth > 0);
+
+ /* Write explicit bubbles to get around the case where the default
+ * constructor for the element type isn't good enough */
+ for (unsigned i = 0; i <= depth; i++)
+ (*this)[-i] = BubbleTraits::bubble();
+ }
+
+ public:
+ /** Write an element to the back of the pipeline. This doesn't cause
+ * the pipeline to advance until advance is called. Pushing twice
+ * without advance-ing will just cause an overwrite of the last push's
+ * data. */
+ void push(ElemType &elem)
+ {
+ assert(!alreadyPushed());
+ *pushWire = elem;
+ if (!BubbleTraits::isBubble(elem))
+ occupancy++;
+ }
+
+ /** Peek at the end element of the pipe */
+ ElemType &front() { return *popWire; }
+
+ const ElemType &front() const { return *popWire; }
+
+ /** Have we already pushed onto this pipe without advancing */
+ bool alreadyPushed() { return !BubbleTraits::isBubble(*pushWire); }
+
+ /** There's data (not a bubble) at the end of the pipe */
+ bool isPopable() { return !BubbleTraits::isBubble(front()); }
+
+ /** Try to advance the pipeline. If we're stalled, don't advance. If
+ * we're not stalled, advance then check to see if we become stalled
+ * (a non-bubble at the end of the pipe) */
+ void
+ advance()
+ {
+ bool data_at_end = isPopable();
+
+ if (!stalled) {
+ TimeBuffer<ElemType>::advance();
+ /* If there was data at the end of the pipe that has now been
+ * advanced out of the pipe, we've lost data */
+ if (data_at_end)
+ occupancy--;
+ /* Is there data at the end of the pipe now? */
+ stalled = isPopable();
+ /* Insert a bubble into the empty input slot to make sure that
+ * element is correct in the case where the default constructor
+ * for ElemType doesn't produce a bubble */
+ ElemType bubble = BubbleTraits::bubble();
+ *pushWire = bubble;
+ }
+ }
+};
+
+/** Base class for space reservation requestable objects */
+class Reservable
+{
+ public:
+ /** Can a slot be reserved? */
+ virtual bool canReserve() const = 0;
+
+ /** Reserve a slot in whatever structure this is attached to */
+ virtual void reserve() = 0;
+
+ /** Free a reserved slot */
+ virtual void freeReservation() = 0;
+};
+
+/** Wrapper for a queue type to act as a pipeline stage input queue.
+ * Handles capacity management, bubble value suppression and provides
+ * reporting.
+ *
+ * In an ideal world, ElemType would be derived from ReportIF and BubbleIF,
+ * but here we use traits and allow the Adaptors ReportTraitsAdaptor and
+ * BubbleTraitsAdaptor to work on data which *does* directly implement
+ * those interfaces. */
+template <typename ElemType,
+ typename ReportTraits = ReportTraitsAdaptor<ElemType>,
+ typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
+class Queue : public Named, public Reservable
+{
+ private:
+ std::deque<ElemType> queue;
+
+ /** Number of slots currently reserved for future (reservation
+ * respecting) pushes */
+ unsigned int numReservedSlots;
+
+ /** Need this here as queues usually don't have a limited capacity */
+ unsigned int capacity;
+
+ /** Name to use for the data in MinorTrace */
+ std::string dataName;
+
+ public:
+ Queue(const std::string &name, const std::string &data_name,
+ unsigned int capacity_) :
+ Named(name),
+ numReservedSlots(0),
+ capacity(capacity_),
+ dataName(data_name)
+ { }
+
+ virtual ~Queue() { }
+
+ public:
+ /** Push an element into the buffer if it isn't a bubble. Bubbles are
+ * just discarded. It is assummed that any push into a queue with
+ * reserved space intends to take that space */
+ void
+ push(ElemType &data)
+ {
+ if (!BubbleTraits::isBubble(data)) {
+ freeReservation();
+ queue.push_back(data);
+
+ if (queue.size() > capacity) {
+ warn("%s: No space to push data into queue of capacity"
+ " %u, pushing anyway\n", name(), capacity);
+ }
+
+ }
+ }
+
+ /** Clear all allocated space. Be careful how this is used */
+ void clearReservedSpace() { numReservedSlots = 0; }
+
+ /** Clear a single reserved slot */
+ void freeReservation()
+ {
+ if (numReservedSlots != 0)
+ numReservedSlots--;
+ }
+
+ /** Reserve space in the queue for future pushes. Enquiries about space
+ * in the queue using unreservedRemainingSpace will only tell about
+ * space which is not full and not reserved. */
+ void
+ reserve()
+ {
+ /* Check reservable space */
+ if (unreservedRemainingSpace() == 0)
+ warn("%s: No space is reservable in queue", name());
+
+ numReservedSlots++;
+ }
+
+ bool canReserve() const { return unreservedRemainingSpace() != 0; }
+
+ /** Number of slots available in an empty buffer */
+ unsigned int totalSpace() const { return capacity; }
+
+ /** Number of slots already occupied in this buffer */
+ unsigned int occupiedSpace() const { return queue.size(); }
+
+ /** Number of slots which are reserved. */
+ unsigned int reservedSpace() const { return numReservedSlots; }
+
+ /** Number of slots yet to fill in this buffer. This doesn't include
+ * reservation. */
+ unsigned int
+ remainingSpace() const
+ {
+ int ret = capacity - queue.size();
+
+ return (ret < 0 ? 0 : ret);
+ }
+
+ /** Like remainingSpace but does not count reserved spaces */
+ unsigned int
+ unreservedRemainingSpace() const
+ {
+ int ret = capacity - (queue.size() + numReservedSlots);
+
+ return (ret < 0 ? 0 : ret);
+ }
+
+ /** Head value. Like std::queue::front */
+ ElemType &front() { return queue.front(); }
+
+ const ElemType &front() const { return queue.front(); }
+
+ /** Pop the head item. Like std::queue::pop */
+ void pop() { queue.pop_front(); }
+
+ /** Is the queue empty? */
+ bool empty() const { return queue.empty(); }
+
+ void
+ minorTrace() const
+ {
+ std::ostringstream data;
+ /* If we become over-full, totalSpace() can actually be smaller than
+ * occupiedSpace(). Handle this */
+ unsigned int num_total = (occupiedSpace() > totalSpace() ?
+ occupiedSpace() : totalSpace());
+
+ unsigned int num_reserved = reservedSpace();
+ unsigned int num_occupied = occupiedSpace();
+
+ int num_printed = 1;
+ /* Bodge to rotate queue to report elements */
+ while (num_printed <= num_occupied) {
+ ReportTraits::reportData(data, queue[num_printed - 1]);
+ num_printed++;
+
+ if (num_printed <= num_total)
+ data << ',';
+ }
+
+ int num_printed_reserved = 1;
+ /* Show reserved slots */
+ while (num_printed_reserved <= num_reserved &&
+ num_printed <= num_total)
+ {
+ data << 'R';
+ num_printed_reserved++;
+ num_printed++;
+
+ if (num_printed <= num_total)
+ data << ',';
+ }
+
+ /* And finally pad with empty slots (if there are any) */
+ while (num_printed <= num_total) {
+ num_printed++;
+
+ if (num_printed <= num_total)
+ data << ',';
+ }
+
+ MINORTRACE("%s=%s\n", dataName, data.str());
+ }
+};
+
+/** Like a Queue but with a restricted interface and a setTail function
+ * which, when the queue is empty, just takes a reference to the pushed
+ * item as the single element. Calling pushTail will push that element
+ * onto the queue.
+ *
+ * The purpose of this class is to allow the faster operation of queues of
+ * items which usually don't get deeper than one item and for which the copy
+ * associated with a push is expensive enough to want to avoid
+ *
+ * The intended use case is the input buffer for pipeline stages, hence the
+ * class name */
+template <typename ElemType,
+ typename ReportTraits = ReportTraitsAdaptor<ElemType>,
+ typename BubbleTraits = BubbleTraitsAdaptor<ElemType> >
+class InputBuffer : public Reservable
+{
+ protected:
+ /** Underlying queue */
+ mutable Queue<ElemType, ReportTraits, BubbleTraits> queue;
+
+ /** Pointer to the single element (if not NULL) */
+ mutable ElemType *elementPtr;
+
+ public:
+ InputBuffer(const std::string &name, const std::string &data_name,
+ unsigned int capacity_) :
+ queue(name, data_name, capacity_),
+ elementPtr(NULL)
+ { }
+
+ public:
+ /** Set the tail of the queue, this is like push but needs
+ * to be followed by pushTail for the new tail to make its
+ * way into the queue proper */
+ void
+ setTail(ElemType &new_element)
+ {
+ assert(!elementPtr);
+ if (!BubbleTraits::isBubble(new_element)) {
+ if (queue.empty())
+ elementPtr = &new_element;
+ else
+ queue.push(new_element);
+ }
+ }
+
+ /** No single element or queue entries */
+ bool empty() const { return !elementPtr && queue.empty(); }
+
+ /** Return the element, or the front of the queue */
+ const ElemType &front() const
+ { return (elementPtr ? *elementPtr : queue.front()); }
+
+ ElemType &front()
+ { return (elementPtr ? *elementPtr : queue.front()); }
+
+ /** Pop either the head, or if none, the head of the queue */
+ void
+ pop()
+ {
+ if (elementPtr) {
+ /* A popped element was expected to be pushed into queue
+ * and so take a reserved space */
+ elementPtr = NULL;
+ queue.freeReservation();
+ } else {
+ queue.pop();
+ }
+ }
+
+ /** Push the single element (if any) into the queue proper. If the
+ * element's reference points to a transient object, remember to
+ * always do this before the end of that object's life */
+ void
+ pushTail() const
+ {
+ if (elementPtr)
+ queue.push(*elementPtr);
+ elementPtr = NULL;
+ }
+
+ /** Report elements */
+ void
+ minorTrace() const
+ {
+ pushTail();
+ queue.minorTrace();
+ }
+
+ /** Reservable interface, passed on to queue */
+ bool canReserve() const { return queue.canReserve(); }
+ void reserve() { queue.reserve(); }
+ void freeReservation() { queue.freeReservation(); }
+
+ /** Like remainingSpace but does not count reserved spaces */
+ unsigned int
+ unreservedRemainingSpace()
+ {
+ pushTail();
+ return queue.unreservedRemainingSpace();
+ }
+};
+
+}
+
+#endif /* __CPU_MINOR_BUFFERS_HH__ */