src/mem/stack_dist_calc.hh

   1 /*
   2  * Copyright (c) 2014-2015 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: Kanishk Sugand
  38  *          Andreas Hansson
  39  */
  40
  41 #ifndef __MEM_STACK_DIST_CALC_HH__
  42 #define __MEM_STACK_DIST_CALC_HH__
  43
  44 #include <limits>
  45 #include <map>
  46 #include <vector>
  47
  48 #include "base/types.hh"
  49
  50 /**
  51   * The stack distance calculator is a passive object that merely
  52   * observes the addresses pass to it. It calculates stack distances
  53   * of incoming addresses based on the partial sum hierarchy tree
  54   * algorithm described by Alamasi et al.
  55   * http://doi.acm.org/10.1145/773039.773043.
  56   *
  57   * A tree structure is maintained and updated at each transaction
  58   * (unique or non-unique). The tree is implemented as an STL vector
  59   * with layers of the form <map> Each layer in this tree is an
  60   * ordered map <uint64_t, Node*>. Nodes are structs which take form
  61   * of leaf, intermediate and root nodes. For example, in a tree with 3
  62   * layers, tree[0][5] gives a leaf node pointer for key=5 tree[1][1]
  63   * gives an intermediate node pointer for key=1 tree[2][0] gives the
  64   * root node in the tree.
  65   *
  66   * At every transaction a hash-map (aiMap) is looked up to check if
  67   * the address was already encountered before. Based on this lookup a
  68   * transaction can be termed as unique or non-unique.
  69   *
  70   * In addition to the normal stack distance calculation, a feature to
  71   * mark an old node in the tree is added. This is useful if it is
  72   * required to see the reuse pattern. For example, BackInvalidates
  73   * from a lower level (e.g. membus to L2), can be marked (isMarked
  74   * flag of Node set to True). Then later if this same address is
  75   * accessed (by L1), the value of the isMarked flag would be
  76   * True. This would give some insight on how the BackInvalidates
  77   * policy of the lower level affect the read/write accesses in an
  78   * application.
  79   *
  80   * There are two functions provided to interface with the calculator:
  81   * 1. pair<uint64_t, bool> calcStackDistAndUpdate(Addr r_address,
  82   *                                                bool addNewNode)
  83   * At every unique transaction a new leaf node is added at tree[0](leaf layer)
  84   * and linked to the layer above (if addNewNode is True). The sums of all
  85   * the intermediate nodes is updated till the root. The stack-distance is
  86   * returned as a Constant representing INFINITY.
  87   *
  88   * At every non-unique transaction the tree is traversed from the
  89   * leaf at the returned index to the root, the old node is deleted
  90   * from the tree, and the sums (to the right are collected) and
  91   * decremented. The collected sum represets the stack distance of the
  92   * found node. If this node was marked then a bool flag set to True
  93   * is returned with the stack_distance. During this operation a node
  94   * is discarded at the leaf layer always. Moreover during the
  95   * traversal upwards using the updateSum() method, if an intermediate
  96   * node is found with no children connected to it, then that is
  97   * discarded too.
  98   *
  99   * The return value of this function is a pair representing the
 100   * stack_distance and the value of the marked flag.
 101   *
 102   * 2. pair<uint64_t , bool> calcStackDist(Addr r_address, bool mark)
 103   * This is a stripped down version of the above function which is used to
 104   * just inspect the tree, and mark a leaf node (if mark flag is set). The
 105   * functionality to add a new node is removed.
 106   *
 107   * At every unique transaction the stack-distance is returned as a constant
 108   * representing INFINITY.
 109   *
 110   * At every non-unique transaction the tree is traversed from the
 111   * leaf at the returned index to the root, and the sums (to the right)
 112   * are collected. The collected sum represets the stack distance of
 113   * the found node.
 114   *
 115   * This function does NOT Modify the stack. (No node is added or
 116   * deleted).  It is just used to mark a node already created and get
 117   * its stack distance.
 118   *
 119   * The return value of this function is a pair representing the stack
 120   * distance and the value of the marked flag.
 121   *
 122   * The table below depicts the usage of the Algorithm using the functions:
 123   * pair<uint64_t Stack_dist, bool isMarked> calcStackDistAndUpdate
 124   *                                      (Addr r_address, bool addNewNode)
 125   * pair<uint64_t Stack_dist, bool isMarked> calcStackDist
 126   *                                              (Addr r_address, bool mark)
 127   *
 128   * |   Function           |   Arguments   |Return Val |Use For|
 129   * |calcStackDistAndUpdate|r_address, True|I/SD,False |A,GD,GM|
 130   * |calcStackDistAndUpdate|r_address,False|SD,prevMark|D,GD,GM|
 131   * |calcStackDist         |r_address,False|SD,prevMark|  GD,GM|
 132   * |calcStackDist         |r_address, True|SD,prevMark|  GD,GM|
 133   *
 134   * (*A: Allocate an address in stack, if old entry present then it is deleted,
 135   *  *U: Delete old-address from stack, no new entry is added
 136   *  *GD: Get-Stack distance of an address,
 137   *  *GM: Get value of Mark flag, indicates if that address has been touched
 138   *                                                                  before,
 139   *  *I: stack-distance = infinity,
 140   *  *SD: Stack Distance
 141   *  *r_address: address to be added, *prevMark: value of isMarked flag
 142   *                                                              of the Node)
 143   *
 144   * Invalidates refer to a type of packet that removes something from
 145   * a cache, either autonoumously (due-to cache's own replacement
 146   * policy), or snoops from other caches which invalidate something
 147   * inside our cache.
 148   *
 149   * Usage            |   Function to use    |Typical Use           |
 150   * Add new entry    |calcStackDistAndUpdate|Read/Write Allocate   |
 151   * Delete Old Entry |calcStackDistAndUpdate|Writebacks/Cleanevicts|
 152   * Dist.of Old entry|calcStackDist         |Cleanevicts/Invalidate|
 153   *
 154   * Node Balancing: The tree structure is maintained by an
 155   * updateTree() operation called when an intermediate node is
 156   * required. The update operation is roughly categorized as a root
 157   * update or intermediate layer update. When number of leaf nodes
 158   * grow over a power of 2 then a new layer is added at the top of the
 159   * tree and a new root node is initialized. The old node at the lower
 160   * layer is connected to this.  In an intermediate node update
 161   * operation a new intermediate node is added to the required layer.
 162   *
 163   * Debugging: Debugging can be enabled by setting the verifyStack flag
 164   * true. Debugging is implemented using a dummy stack that behaves in
 165   * a naive way, using STL vectors (i.e each unique address is pushed
 166   * on the top of an STL vector stack, and SD is returned as
 167   * Infinity. If a non unique address is encountered then the previous
 168   * entry in the STL vector is removed, all the entities above it are
 169   * pushed down, and the address is pushed at the top of the stack).
 170   *
 171   * A printStack(int numOfEntitiesToPrint) is provided to print top n entities
 172   * in both (tree and STL based dummy stack).
 173   */
 174 class StackDistCalc
 175 {
 176
 177   private:
 178
 179     struct Node;
 180
 181     typedef std::map<uint64_t, Node*> IndexNodeMap;
 182     typedef std::map<Addr, uint64_t> AddressIndexMap;
 183     typedef std::vector<IndexNodeMap> TreeType;
 184
 185     /**
 186      * Gets sum from the node upwards recursively till the root.  This
 187      * function is called first by getSumsLeavesToRoot, and then
 188      * recursively calls itself.
 189      *
 190      * @param node pointer to the node which is updated
 191      * @param from_left variable which says that the request arrived
 192      *        from the left
 193      * @param sum_from_below Sum of left and right children below
 194      * @param level level in the tree the calling node is located
 195      * @param stack_dist stack distance of the node below
 196      * @return The stack distance of the current address.
 197      *
 198      */
 199     uint64_t getSum(Node* node, bool from_left, uint64_t sum_from_below,
 200                     uint64_t stack_dist, uint64_t level) const;
 201
 202     /**
 203      * Gets the sum from the leaf node specified. This function
 204      * is called by calcStackDist.
 205      *
 206      * @param node pointer to the node which is updated
 207      * @return The stack distance of the current address.
 208      *
 209      */
 210     uint64_t getSumsLeavesToRoot(Node* node) const;
 211
 212     /**
 213      * Updates the nodes upwards recursively till the root.
 214      * This function is first called by updateSumsLeavesToRoot,
 215      * and then it recursively calls itself.
 216      *
 217      * @param node pointer to the node which is updated
 218      * @param from_left variable which says that the request arrived
 219      * from the left
 220      * @param sum_from_below Sum of left and right children below
 221      * @param level level in the tree the calling node is located
 222      * @param stack_dist stack distance of the node below
 223      * @param discard_node whether the calling node was discarded or not
 224      * @return The stack distance of the current address.
 225      *
 226      */
 227     uint64_t updateSum(Node* node,
 228                        bool from_left, uint64_t sum_from_below, uint64_t level,
 229                        uint64_t stack_dist, bool discard_node);
 230
 231     /**
 232      * Updates the leaf nodes and nodes above. This function is
 233      * called by the calcStackDistAndUpdate.
 234      *
 235      * @param node pointer to the node which is updated
 236      * @param is_new_leaf is true if this is a newly added node
 237      * @return The stack distance of the current address.
 238      *
 239      */
 240     uint64_t updateSumsLeavesToRoot(Node* node, bool is_new_leaf);
 241
 242     /**
 243      * updateTree is a tree balancing operation, which maintains the
 244      * binary tree structure.
 245      * This method is called whenever index%2 == 0 (i.e. every
 246      * alternate cycle) The two main operation are :
 247      * OP1. Moving the root node one layer up if index counter
 248      *       crosses power of 2
 249      * OP2. Addition of intermediate nodes as and when required
 250      *      and linking them to their parents in the layer above.
 251      */
 252     void updateTree();
 253
 254     /**
 255      * This method is used for verification purposes
 256      * It recursively traverses upwards from the given node till
 257      * the root to check if the ultimate parent node (root-node) points
 258      * to null.
 259      *
 260      * @param node pointer to the node whose sanity is being checked
 261      * @param level the level at which this node is located in the tree
 262      *
 263      */
 264     void sanityCheckTree(const Node* node, uint64_t level = 0) const;
 265
 266     /**
 267      * Return the counter for address accesses (unique and
 268      * non-unique). This is further used to dump stats at
 269      * regular intervals.
 270      *
 271      * @return The stack distance of the current address.
 272      */
 273     uint64_t getIndex() const { return index; }
 274
 275     /**
 276      * Query depth of the tree (tree[0] represents leaf layer while
 277      * tree[treeDepth] represents the root layer, all layers in
 278      * between contain intermediate nodes)
 279      *
 280      * @return Tree depth
 281      */
 282     uint64_t getTreeDepth() const { return tree.size() - 1; }
 283
 284     /**
 285      * Print the last n items on the stack.
 286      * This method prints top n entries in the tree based implementation as
 287      * well as dummy stack.
 288      * @param n Number of entries to print
 289      */
 290     void printStack(int n = 5) const;
 291
 292     /**
 293      * This is an alternative implementation of the stack-distance
 294      * in a naive way. It uses simple STL vector to represent the stack.
 295      * It can be used in parallel for debugging purposes.
 296      * It is 10x slower than the tree based implemenation.
 297      *
 298      * @param r_address The current address to process
 299      * @param update_stack Flag to indicate if stack should be updated
 300      * @return  Stack distance which is calculated by this alternative
 301      * implementation
 302      *
 303      */
 304     uint64_t verifyStackDist(const Addr r_address,
 305                              bool update_stack = false);
 306
 307   public:
 308     StackDistCalc(bool verify_stack = false);
 309
 310     ~StackDistCalc();
 311
 312     /**
 313      * A convenient way of refering to infinity.
 314      */
 315     static constexpr uint64_t Infinity = std::numeric_limits<uint64_t>::max();
 316
 317
 318     /**
 319      * Process the given address. If Mark is true then set the
 320      * mark flag of the leaf node.
 321      * This function returns the stack distance of the incoming
 322      * address and the previous status of the mark flag.
 323      *
 324      * @param r_address The current address to process
 325      * @param mark set the mark flag for the address.
 326      * @return The stack distance of the current address and the mark flag.
 327      */
 328     std::pair<uint64_t, bool> calcStackDist(const Addr r_address,
 329                                             bool mark = false);
 330
 331     /**
 332      * Process the given address:
 333      *  - Lookup the tree for the given address
 334      *  - delete old node if found in tree
 335      *  - add a new node (if addNewNode flag is set)
 336      * This function returns the stack distance of the incoming
 337      * address and the status of the mark flag.
 338      *
 339      * @param r_address The current address to process
 340      * @param addNewNode If true, a new node is added to the tree
 341      * @return The stack distance of the current address and the mark flag.
 342      */
 343     std::pair<uint64_t, bool> calcStackDistAndUpdate(const Addr r_address,
 344                                                      bool addNewNode = true);
 345
 346   private:
 347
 348     /**
 349      * Node which takes form of Leaf, INode or Root
 350      */
 351     struct Node{
 352         // Sum of the left children
 353         uint64_t sumLeft;
 354
 355         // Sum of the right children
 356         uint64_t sumRight;
 357
 358         // Flag to indicate that sumLeft has gone from non-zero value to 0
 359         bool discardLeft;
 360
 361         // Flag to indicate that sumRight has gone from non-zero value to 0
 362         bool discardRight;
 363
 364         // Index of the current element in the Map
 365         uint64_t nodeIndex;
 366
 367         // Pointer to the parent
 368         Node* parent;
 369
 370         // Flag to mark the node as the right/left child
 371         bool isLeftNode;
 372
 373         /**
 374          * Flag to indicate if this address is marked. Used in case
 375          * where stack distance of a touched address is required.
 376          */
 377         bool isMarked;
 378
 379         /**
 380          * The discard flags are false by default they become true if
 381          * the node is reached again in a future lookup.
 382          */
 383         Node() : sumLeft(0), sumRight(0), discardLeft(false),
 384                  discardRight(false), nodeIndex(0),
 385                  parent(nullptr), isLeftNode(true), isMarked(false)
 386         { }
 387     };
 388
 389     /**
 390      * Internal counter for address accesses (unique and non-unique)
 391      * This counter increments everytime the calcStackDist() method is
 392      * called. This counter is used as a key for the hash- map at the
 393      * leaf layer. Practically at every call to the calculator this
 394      * counter is incremented and a new leaf node is added in the tree
 395      * at the leaf layer using this counter value as the key.
 396      */
 397     uint64_t index;
 398
 399     // Binary tree of partial sums
 400     TreeType tree;
 401
 402     // Hash map which returns last seen index of each address
 403     AddressIndexMap aiMap;
 404
 405     // Keeps count of number of the next unique index for each
 406     // level in the tree
 407     std::vector<uint64_t> nextIndex;
 408
 409     // Dummy Stack for verification
 410     std::vector<uint64_t> stack;
 411
 412     // Flag to enable verification of stack. (Slows down the simulation)
 413     const bool verifyStack;
 414 };
 415
 416
 417 #endif //__STACK_DIST_CALC_HH__