buffers.hh revision 11800:54436a1784dc
1/* 2 * Copyright (c) 2013-2014 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions are 16 * met: redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer; 18 * redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution; 21 * neither the name of the copyright holders nor the names of its 22 * contributors may be used to endorse or promote products derived from 23 * this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 * Authors: Andrew Bardsley 38 */ 39 40/** 41 * @file 42 * 43 * Classes for buffer, queue and FIFO behaviour. 44 */ 45 46#ifndef __CPU_MINOR_BUFFERS_HH__ 47#define __CPU_MINOR_BUFFERS_HH__ 48 49#include <iostream> 50#include <queue> 51#include <sstream> 52 53#include "base/misc.hh" 54#include "cpu/minor/trace.hh" 55#include "cpu/activity.hh" 56#include "cpu/timebuf.hh" 57 58namespace Minor 59{ 60 61/** Interface class for data with reporting/tracing facilities. This 62 * interface doesn't actually have to be used as other classes which need 63 * this interface uses templating rather than inheritance but it's provided 64 * here to document the interface needed by those classes. */ 65class ReportIF 66{ 67 public: 68 /** Print the data in a format suitable to be the value in "name=value" 69 * trace lines */ 70 virtual void reportData(std::ostream &os) const = 0; 71 72 virtual ~ReportIF() { } 73}; 74 75/** Interface class for data with 'bubble' values. This interface doesn't 76 * actually have to be used as other classes which need this interface uses 77 * templating rather than inheritance but it's provided here to document 78 * the interface needed by those classes. */ 79class BubbleIF 80{ 81 public: 82 virtual bool isBubble() const = 0; 83}; 84 85/** ...ReportTraits are trait classes with the same functionality as 86 * ReportIF, but with elements explicitly passed into the report... 87 * functions. */ 88 89/** Allow a template using ReportTraits to call report... functions of 90 * ReportIF-bearing elements themselves */ 91template <typename ElemType> /* ElemType should implement ReportIF */ 92class ReportTraitsAdaptor 93{ 94 public: 95 static void 96 reportData(std::ostream &os, const ElemType &elem) 97 { elem.reportData(os); } 98}; 99 100/** A similar adaptor but for elements held by pointer 101 * ElemType should implement ReportIF */ 102template <typename PtrType> 103class ReportTraitsPtrAdaptor 104{ 105 public: 106 static void 107 reportData(std::ostream &os, const PtrType &elem) 108 { elem->reportData(os); } 109}; 110 111/** ... BubbleTraits are trait classes to add BubbleIF interface 112 * functionality to templates which process elements which don't necessarily 113 * implement BubbleIF themselves */ 114 115/** Default behaviour, no bubbles */ 116template <typename ElemType> 117class NoBubbleTraits 118{ 119 public: 120 static bool isBubble(const ElemType &) { return false; } 121 static ElemType bubble() { assert(false); } 122}; 123 124/** Pass on call to the element */ 125template <typename ElemType> 126class BubbleTraitsAdaptor 127{ 128 public: 129 static bool isBubble(const ElemType &elem) 130 { return elem.isBubble(); } 131 132 static ElemType bubble() { return ElemType::bubble(); } 133}; 134 135/** Pass on call to the element where the element is a pointer */ 136template <typename PtrType, typename ElemType> 137class BubbleTraitsPtrAdaptor 138{ 139 public: 140 static bool isBubble(const PtrType &elem) 141 { return elem->isBubble(); } 142 143 static PtrType bubble() { return ElemType::bubble(); } 144}; 145 146/** TimeBuffer with MinorTrace and Named interfaces */ 147template <typename ElemType, 148 typename ReportTraits = ReportTraitsAdaptor<ElemType>, 149 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> > 150class MinorBuffer : public Named, public TimeBuffer<ElemType> 151{ 152 protected: 153 /** The range of elements that should appear in trace lines */ 154 int reportLeft, reportRight; 155 156 /** Name to use for the data in a MinorTrace line */ 157 std::string dataName; 158 159 public: 160 MinorBuffer(const std::string &name, 161 const std::string &data_name, 162 int num_past, int num_future, 163 int report_left = -1, int report_right = -1) : 164 Named(name), TimeBuffer<ElemType>(num_past, num_future), 165 reportLeft(report_left), reportRight(report_right), 166 dataName(data_name) 167 { } 168 169 public: 170 /* Is this buffer full of only bubbles */ 171 bool 172 empty() const 173 { 174 bool ret = true; 175 176 for (int i = -this->past; i <= this->future; i++) { 177 if (!BubbleTraits::isBubble((*this)[i])) 178 ret = false; 179 } 180 181 return ret; 182 } 183 184 /** Report buffer states from 'slot' 'from' to 'to'. For example 0,-1 185 * will produce two slices with current (just assigned) and last (one 186 * advance() old) slices with the current (0) one on the left. 187 * Reverse the numbers to change the order of slices */ 188 void 189 minorTrace() const 190 { 191 std::ostringstream data; 192 193 int step = (reportLeft > reportRight ? -1 : 1); 194 int end = reportRight + step; 195 int i = reportLeft; 196 197 while (i != end) { 198 const ElemType &datum = (*this)[i]; 199 200 ReportTraits::reportData(data, datum); 201 i += step; 202 if (i != end) 203 data << ','; 204 } 205 206 MINORTRACE("%s=%s\n", dataName, data.str()); 207 } 208}; 209 210/** Wraps a MinorBuffer with Input/Output interfaces to ensure that units 211 * within the model can only see the right end of buffers between them. */ 212template <typename Data> 213class Latch 214{ 215 public: 216 typedef MinorBuffer<Data> Buffer; 217 218 protected: 219 /** Delays, in cycles, writing data into the latch and seeing it on the 220 * latched wires */ 221 Cycles delay; 222 223 Buffer buffer; 224 225 public: 226 /** forward/backwardDelay specify the delay from input to output in each 227 * direction. These arguments *must* be >= 1 */ 228 Latch(const std::string &name, 229 const std::string &data_name, 230 Cycles delay_ = Cycles(1), 231 bool report_backwards = false) : 232 delay(delay_), 233 buffer(name, data_name, delay_, 0, (report_backwards ? -delay_ : 0), 234 (report_backwards ? 0 : -delay_)) 235 { } 236 237 public: 238 /** Encapsulate wires on either input or output of the latch. 239 * forward/backward correspond to data direction relative to the 240 * pipeline. Latched and Immediate specify delay for backward data. 241 * Immediate data is available to earlier stages *during* the cycle it 242 * is written */ 243 class Input 244 { 245 public: 246 typename Buffer::wire inputWire; 247 248 public: 249 Input(typename Buffer::wire input_wire) : 250 inputWire(input_wire) 251 { } 252 }; 253 254 class Output 255 { 256 public: 257 typename Buffer::wire outputWire; 258 259 public: 260 Output(typename Buffer::wire output_wire) : 261 outputWire(output_wire) 262 { } 263 }; 264 265 bool empty() const { return buffer.empty(); } 266 267 /** An interface to just the input of the buffer */ 268 Input input() { return Input(buffer.getWire(0)); } 269 270 /** An interface to just the output of the buffer */ 271 Output output() { return Output(buffer.getWire(-delay)); } 272 273 void minorTrace() const { buffer.minorTrace(); } 274 275 void evaluate() { buffer.advance(); } 276}; 277 278/** A pipeline simulating class that will stall (not advance when advance() 279 * is called) if a non-bubble value lies at the far end of the pipeline. 280 * The user can clear the stall before calling advance to unstall the 281 * pipeline. */ 282template <typename ElemType, 283 typename ReportTraits, 284 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> > 285class SelfStallingPipeline : public MinorBuffer<ElemType, ReportTraits> 286{ 287 protected: 288 /** Wire at the input end of the pipeline (for convenience) */ 289 typename TimeBuffer<ElemType>::wire pushWire; 290 /** Wire at the output end of the pipeline (for convenience) */ 291 typename TimeBuffer<ElemType>::wire popWire; 292 293 public: 294 /** If true, advance will not advance the pipeline */ 295 bool stalled; 296 297 /** The number of slots with non-bubbles in them */ 298 unsigned int occupancy; 299 300 public: 301 SelfStallingPipeline(const std::string &name, 302 const std::string &data_name, 303 unsigned depth) : 304 MinorBuffer<ElemType, ReportTraits> 305 (name, data_name, depth, 0, -1, -depth), 306 pushWire(this->getWire(0)), 307 popWire(this->getWire(-depth)), 308 stalled(false), 309 occupancy(0) 310 { 311 assert(depth > 0); 312 313 /* Write explicit bubbles to get around the case where the default 314 * constructor for the element type isn't good enough */ 315 for (unsigned i = 0; i <= depth; i++) 316 (*this)[-i] = BubbleTraits::bubble(); 317 } 318 319 public: 320 /** Write an element to the back of the pipeline. This doesn't cause 321 * the pipeline to advance until advance is called. Pushing twice 322 * without advance-ing will just cause an overwrite of the last push's 323 * data. */ 324 void push(ElemType &elem) 325 { 326 assert(!alreadyPushed()); 327 *pushWire = elem; 328 if (!BubbleTraits::isBubble(elem)) 329 occupancy++; 330 } 331 332 /** Peek at the end element of the pipe */ 333 ElemType &front() { return *popWire; } 334 335 const ElemType &front() const { return *popWire; } 336 337 /** Have we already pushed onto this pipe without advancing */ 338 bool alreadyPushed() { return !BubbleTraits::isBubble(*pushWire); } 339 340 /** There's data (not a bubble) at the end of the pipe */ 341 bool isPopable() { return !BubbleTraits::isBubble(front()); } 342 343 /** Try to advance the pipeline. If we're stalled, don't advance. If 344 * we're not stalled, advance then check to see if we become stalled 345 * (a non-bubble at the end of the pipe) */ 346 void 347 advance() 348 { 349 bool data_at_end = isPopable(); 350 351 if (!stalled) { 352 TimeBuffer<ElemType>::advance(); 353 /* If there was data at the end of the pipe that has now been 354 * advanced out of the pipe, we've lost data */ 355 if (data_at_end) 356 occupancy--; 357 /* Is there data at the end of the pipe now? */ 358 stalled = isPopable(); 359 /* Insert a bubble into the empty input slot to make sure that 360 * element is correct in the case where the default constructor 361 * for ElemType doesn't produce a bubble */ 362 ElemType bubble = BubbleTraits::bubble(); 363 *pushWire = bubble; 364 } 365 } 366}; 367 368/** Base class for space reservation requestable objects */ 369class Reservable 370{ 371 public: 372 /** Can a slot be reserved? */ 373 virtual bool canReserve() const = 0; 374 375 /** Reserve a slot in whatever structure this is attached to */ 376 virtual void reserve() = 0; 377 378 /** Free a reserved slot */ 379 virtual void freeReservation() = 0; 380}; 381 382/** Wrapper for a queue type to act as a pipeline stage input queue. 383 * Handles capacity management, bubble value suppression and provides 384 * reporting. 385 * 386 * In an ideal world, ElemType would be derived from ReportIF and BubbleIF, 387 * but here we use traits and allow the Adaptors ReportTraitsAdaptor and 388 * BubbleTraitsAdaptor to work on data which *does* directly implement 389 * those interfaces. */ 390template <typename ElemType, 391 typename ReportTraits = ReportTraitsAdaptor<ElemType>, 392 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> > 393class Queue : public Named, public Reservable 394{ 395 private: 396 std::deque<ElemType> queue; 397 398 /** Number of slots currently reserved for future (reservation 399 * respecting) pushes */ 400 unsigned int numReservedSlots; 401 402 /** Need this here as queues usually don't have a limited capacity */ 403 unsigned int capacity; 404 405 /** Name to use for the data in MinorTrace */ 406 std::string dataName; 407 408 public: 409 Queue(const std::string &name, const std::string &data_name, 410 unsigned int capacity_) : 411 Named(name), 412 numReservedSlots(0), 413 capacity(capacity_), 414 dataName(data_name) 415 { } 416 417 virtual ~Queue() { } 418 419 public: 420 /** Push an element into the buffer if it isn't a bubble. Bubbles are 421 * just discarded. It is assummed that any push into a queue with 422 * reserved space intends to take that space */ 423 void 424 push(ElemType &data) 425 { 426 if (!BubbleTraits::isBubble(data)) { 427 freeReservation(); 428 queue.push_back(data); 429 430 if (queue.size() > capacity) { 431 warn("%s: No space to push data into queue of capacity" 432 " %u, pushing anyway\n", name(), capacity); 433 } 434 435 } 436 } 437 438 /** Clear all allocated space. Be careful how this is used */ 439 void clearReservedSpace() { numReservedSlots = 0; } 440 441 /** Clear a single reserved slot */ 442 void freeReservation() 443 { 444 if (numReservedSlots != 0) 445 numReservedSlots--; 446 } 447 448 /** Reserve space in the queue for future pushes. Enquiries about space 449 * in the queue using unreservedRemainingSpace will only tell about 450 * space which is not full and not reserved. */ 451 void 452 reserve() 453 { 454 /* Check reservable space */ 455 if (unreservedRemainingSpace() == 0) 456 warn("%s: No space is reservable in queue", name()); 457 458 numReservedSlots++; 459 } 460 461 bool canReserve() const { return unreservedRemainingSpace() != 0; } 462 463 /** Number of slots available in an empty buffer */ 464 unsigned int totalSpace() const { return capacity; } 465 466 /** Number of slots already occupied in this buffer */ 467 unsigned int occupiedSpace() const { return queue.size(); } 468 469 /** Number of slots which are reserved. */ 470 unsigned int reservedSpace() const { return numReservedSlots; } 471 472 /** Number of slots yet to fill in this buffer. This doesn't include 473 * reservation. */ 474 unsigned int 475 remainingSpace() const 476 { 477 int ret = capacity - queue.size(); 478 479 return (ret < 0 ? 0 : ret); 480 } 481 482 /** Like remainingSpace but does not count reserved spaces */ 483 unsigned int 484 unreservedRemainingSpace() const 485 { 486 int ret = capacity - (queue.size() + numReservedSlots); 487 488 return (ret < 0 ? 0 : ret); 489 } 490 491 /** Head value. Like std::queue::front */ 492 ElemType &front() { return queue.front(); } 493 494 const ElemType &front() const { return queue.front(); } 495 496 /** Pop the head item. Like std::queue::pop */ 497 void pop() { queue.pop_front(); } 498 499 /** Is the queue empty? */ 500 bool empty() const { return queue.empty(); } 501 502 void 503 minorTrace() const 504 { 505 std::ostringstream data; 506 /* If we become over-full, totalSpace() can actually be smaller than 507 * occupiedSpace(). Handle this */ 508 unsigned int num_total = (occupiedSpace() > totalSpace() ? 509 occupiedSpace() : totalSpace()); 510 511 unsigned int num_reserved = reservedSpace(); 512 unsigned int num_occupied = occupiedSpace(); 513 514 int num_printed = 1; 515 /* Bodge to rotate queue to report elements */ 516 while (num_printed <= num_occupied) { 517 ReportTraits::reportData(data, queue[num_printed - 1]); 518 num_printed++; 519 520 if (num_printed <= num_total) 521 data << ','; 522 } 523 524 int num_printed_reserved = 1; 525 /* Show reserved slots */ 526 while (num_printed_reserved <= num_reserved && 527 num_printed <= num_total) 528 { 529 data << 'R'; 530 num_printed_reserved++; 531 num_printed++; 532 533 if (num_printed <= num_total) 534 data << ','; 535 } 536 537 /* And finally pad with empty slots (if there are any) */ 538 while (num_printed <= num_total) { 539 num_printed++; 540 541 if (num_printed <= num_total) 542 data << ','; 543 } 544 545 MINORTRACE("%s=%s\n", dataName, data.str()); 546 } 547}; 548 549/** Like a Queue but with a restricted interface and a setTail function 550 * which, when the queue is empty, just takes a reference to the pushed 551 * item as the single element. Calling pushTail will push that element 552 * onto the queue. 553 * 554 * The purpose of this class is to allow the faster operation of queues of 555 * items which usually don't get deeper than one item and for which the copy 556 * associated with a push is expensive enough to want to avoid 557 * 558 * The intended use case is the input buffer for pipeline stages, hence the 559 * class name */ 560template <typename ElemType, 561 typename ReportTraits = ReportTraitsAdaptor<ElemType>, 562 typename BubbleTraits = BubbleTraitsAdaptor<ElemType> > 563class InputBuffer : public Reservable 564{ 565 protected: 566 /** Underlying queue */ 567 mutable Queue<ElemType, ReportTraits, BubbleTraits> queue; 568 569 /** Pointer to the single element (if not NULL) */ 570 mutable ElemType *elementPtr; 571 572 public: 573 InputBuffer(const std::string &name, const std::string &data_name, 574 unsigned int capacity_) : 575 queue(name, data_name, capacity_), 576 elementPtr(NULL) 577 { } 578 579 public: 580 /** Set the tail of the queue, this is like push but needs 581 * to be followed by pushTail for the new tail to make its 582 * way into the queue proper */ 583 void 584 setTail(ElemType &new_element) 585 { 586 assert(!elementPtr); 587 if (!BubbleTraits::isBubble(new_element)) { 588 if (queue.empty()) 589 elementPtr = &new_element; 590 else 591 queue.push(new_element); 592 } 593 } 594 595 /** No single element or queue entries */ 596 bool empty() const { return !elementPtr && queue.empty(); } 597 598 /** Return the element, or the front of the queue */ 599 const ElemType &front() const 600 { return (elementPtr ? *elementPtr : queue.front()); } 601 602 ElemType &front() 603 { return (elementPtr ? *elementPtr : queue.front()); } 604 605 /** Pop either the head, or if none, the head of the queue */ 606 void 607 pop() 608 { 609 if (elementPtr) { 610 /* A popped element was expected to be pushed into queue 611 * and so take a reserved space */ 612 elementPtr = NULL; 613 queue.freeReservation(); 614 } else { 615 queue.pop(); 616 } 617 } 618 619 /** Push the single element (if any) into the queue proper. If the 620 * element's reference points to a transient object, remember to 621 * always do this before the end of that object's life */ 622 void 623 pushTail() const 624 { 625 if (elementPtr) 626 queue.push(*elementPtr); 627 elementPtr = NULL; 628 } 629 630 /** Report elements */ 631 void 632 minorTrace() const 633 { 634 pushTail(); 635 queue.minorTrace(); 636 } 637 638 /** Reservable interface, passed on to queue */ 639 bool canReserve() const { return queue.canReserve(); } 640 void reserve() { queue.reserve(); } 641 void freeReservation() { queue.freeReservation(); } 642 643 /** Like remainingSpace but does not count reserved spaces */ 644 unsigned int 645 unreservedRemainingSpace() 646 { 647 pushTail(); 648 return queue.unreservedRemainingSpace(); 649 } 650}; 651 652} 653 654#endif /* __CPU_MINOR_BUFFERS_HH__ */ 655