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 */ 174class 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__ 418