/* | |

* Copyright (c) 2014-2015 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: Kanishk Sugand | |

* Andreas Hansson | |

*/ | |

#ifndef __MEM_STACK_DIST_CALC_HH__ | |

#define __MEM_STACK_DIST_CALC_HH__ | |

#include <limits> | |

#include <map> | |

#include <vector> | |

#include "base/types.hh" | |

/** | |

* The stack distance calculator is a passive object that merely | |

* observes the addresses pass to it. It calculates stack distances | |

* of incoming addresses based on the partial sum hierarchy tree | |

* algorithm described by Alamasi et al. | |

* http://doi.acm.org/10.1145/773039.773043. | |

* | |

* A tree structure is maintained and updated at each transaction | |

* (unique or non-unique). The tree is implemented as an STL vector | |

* with layers of the form <map> Each layer in this tree is an | |

* ordered map <uint64_t, Node*>. Nodes are structs which take form | |

* of leaf, intermediate and root nodes. For example, in a tree with 3 | |

* layers, tree[0][5] gives a leaf node pointer for key=5 tree[1][1] | |

* gives an intermediate node pointer for key=1 tree[2][0] gives the | |

* root node in the tree. | |

* | |

* At every transaction a hash-map (aiMap) is looked up to check if | |

* the address was already encountered before. Based on this lookup a | |

* transaction can be termed as unique or non-unique. | |

* | |

* In addition to the normal stack distance calculation, a feature to | |

* mark an old node in the tree is added. This is useful if it is | |

* required to see the reuse pattern. For example, BackInvalidates | |

* from a lower level (e.g. membus to L2), can be marked (isMarked | |

* flag of Node set to True). Then later if this same address is | |

* accessed (by L1), the value of the isMarked flag would be | |

* True. This would give some insight on how the BackInvalidates | |

* policy of the lower level affect the read/write accesses in an | |

* application. | |

* | |

* There are two functions provided to interface with the calculator: | |

* 1. pair<uint64_t, bool> calcStackDistAndUpdate(Addr r_address, | |

* bool addNewNode) | |

* At every unique transaction a new leaf node is added at tree[0](leaf layer) | |

* and linked to the layer above (if addNewNode is True). The sums of all | |

* the intermediate nodes is updated till the root. The stack-distance is | |

* returned as a Constant representing INFINITY. | |

* | |

* At every non-unique transaction the tree is traversed from the | |

* leaf at the returned index to the root, the old node is deleted | |

* from the tree, and the sums (to the right are collected) and | |

* decremented. The collected sum represets the stack distance of the | |

* found node. If this node was marked then a bool flag set to True | |

* is returned with the stack_distance. During this operation a node | |

* is discarded at the leaf layer always. Moreover during the | |

* traversal upwards using the updateSum() method, if an intermediate | |

* node is found with no children connected to it, then that is | |

* discarded too. | |

* | |

* The return value of this function is a pair representing the | |

* stack_distance and the value of the marked flag. | |

* | |

* 2. pair<uint64_t , bool> calcStackDist(Addr r_address, bool mark) | |

* This is a stripped down version of the above function which is used to | |

* just inspect the tree, and mark a leaf node (if mark flag is set). The | |

* functionality to add a new node is removed. | |

* | |

* At every unique transaction the stack-distance is returned as a constant | |

* representing INFINITY. | |

* | |

* At every non-unique transaction the tree is traversed from the | |

* leaf at the returned index to the root, and the sums (to the right) | |

* are collected. The collected sum represets the stack distance of | |

* the found node. | |

* | |

* This function does NOT Modify the stack. (No node is added or | |

* deleted). It is just used to mark a node already created and get | |

* its stack distance. | |

* | |

* The return value of this function is a pair representing the stack | |

* distance and the value of the marked flag. | |

* | |

* The table below depicts the usage of the Algorithm using the functions: | |

* pair<uint64_t Stack_dist, bool isMarked> calcStackDistAndUpdate | |

* (Addr r_address, bool addNewNode) | |

* pair<uint64_t Stack_dist, bool isMarked> calcStackDist | |

* (Addr r_address, bool mark) | |

* | |

* | Function | Arguments |Return Val |Use For| | |

* |calcStackDistAndUpdate|r_address, True|I/SD,False |A,GD,GM| | |

* |calcStackDistAndUpdate|r_address,False|SD,prevMark|D,GD,GM| | |

* |calcStackDist |r_address,False|SD,prevMark| GD,GM| | |

* |calcStackDist |r_address, True|SD,prevMark| GD,GM| | |

* | |

* (*A: Allocate an address in stack, if old entry present then it is deleted, | |

* *U: Delete old-address from stack, no new entry is added | |

* *GD: Get-Stack distance of an address, | |

* *GM: Get value of Mark flag, indicates if that address has been touched | |

* before, | |

* *I: stack-distance = infinity, | |

* *SD: Stack Distance | |

* *r_address: address to be added, *prevMark: value of isMarked flag | |

* of the Node) | |

* | |

* Invalidates refer to a type of packet that removes something from | |

* a cache, either autonoumously (due-to cache's own replacement | |

* policy), or snoops from other caches which invalidate something | |

* inside our cache. | |

* | |

* Usage | Function to use |Typical Use | | |

* Add new entry |calcStackDistAndUpdate|Read/Write Allocate | | |

* Delete Old Entry |calcStackDistAndUpdate|Writebacks/Cleanevicts| | |

* Dist.of Old entry|calcStackDist |Cleanevicts/Invalidate| | |

* | |

* Node Balancing: The tree structure is maintained by an | |

* updateTree() operation called when an intermediate node is | |

* required. The update operation is roughly categorized as a root | |

* update or intermediate layer update. When number of leaf nodes | |

* grow over a power of 2 then a new layer is added at the top of the | |

* tree and a new root node is initialized. The old node at the lower | |

* layer is connected to this. In an intermediate node update | |

* operation a new intermediate node is added to the required layer. | |

* | |

* Debugging: Debugging can be enabled by setting the verifyStack flag | |

* true. Debugging is implemented using a dummy stack that behaves in | |

* a naive way, using STL vectors (i.e each unique address is pushed | |

* on the top of an STL vector stack, and SD is returned as | |

* Infinity. If a non unique address is encountered then the previous | |

* entry in the STL vector is removed, all the entities above it are | |

* pushed down, and the address is pushed at the top of the stack). | |

* | |

* A printStack(int numOfEntitiesToPrint) is provided to print top n entities | |

* in both (tree and STL based dummy stack). | |

*/ | |

class StackDistCalc | |

{ | |

private: | |

struct Node; | |

typedef std::map<uint64_t, Node*> IndexNodeMap; | |

typedef std::map<Addr, uint64_t> AddressIndexMap; | |

typedef std::vector<IndexNodeMap> TreeType; | |

/** | |

* Gets sum from the node upwards recursively till the root. This | |

* function is called first by getSumsLeavesToRoot, and then | |

* recursively calls itself. | |

* | |

* @param node pointer to the node which is updated | |

* @param from_left variable which says that the request arrived | |

* from the left | |

* @param sum_from_below Sum of left and right children below | |

* @param level level in the tree the calling node is located | |

* @param stack_dist stack distance of the node below | |

* @return The stack distance of the current address. | |

* | |

*/ | |

uint64_t getSum(Node* node, bool from_left, uint64_t sum_from_below, | |

uint64_t stack_dist, uint64_t level) const; | |

/** | |

* Gets the sum from the leaf node specified. This function | |

* is called by calcStackDist. | |

* | |

* @param node pointer to the node which is updated | |

* @return The stack distance of the current address. | |

* | |

*/ | |

uint64_t getSumsLeavesToRoot(Node* node) const; | |

/** | |

* Updates the nodes upwards recursively till the root. | |

* This function is first called by updateSumsLeavesToRoot, | |

* and then it recursively calls itself. | |

* | |

* @param node pointer to the node which is updated | |

* @param from_left variable which says that the request arrived | |

* from the left | |

* @param sum_from_below Sum of left and right children below | |

* @param level level in the tree the calling node is located | |

* @param stack_dist stack distance of the node below | |

* @param discard_node whether the calling node was discarded or not | |

* @return The stack distance of the current address. | |

* | |

*/ | |

uint64_t updateSum(Node* node, | |

bool from_left, uint64_t sum_from_below, uint64_t level, | |

uint64_t stack_dist, bool discard_node); | |

/** | |

* Updates the leaf nodes and nodes above. This function is | |

* called by the calcStackDistAndUpdate. | |

* | |

* @param node pointer to the node which is updated | |

* @param is_new_leaf is true if this is a newly added node | |

* @return The stack distance of the current address. | |

* | |

*/ | |

uint64_t updateSumsLeavesToRoot(Node* node, bool is_new_leaf); | |

/** | |

* updateTree is a tree balancing operation, which maintains the | |

* binary tree structure. | |

* This method is called whenever index%2 == 0 (i.e. every | |

* alternate cycle) The two main operation are : | |

* OP1. Moving the root node one layer up if index counter | |

* crosses power of 2 | |

* OP2. Addition of intermediate nodes as and when required | |

* and linking them to their parents in the layer above. | |

*/ | |

void updateTree(); | |

/** | |

* This method is used for verification purposes | |

* It recursively traverses upwards from the given node till | |

* the root to check if the ultimate parent node (root-node) points | |

* to null. | |

* | |

* @param node pointer to the node whose sanity is being checked | |

* @param level the level at which this node is located in the tree | |

* | |

*/ | |

void sanityCheckTree(const Node* node, uint64_t level = 0) const; | |

/** | |

* Return the counter for address accesses (unique and | |

* non-unique). This is further used to dump stats at | |

* regular intervals. | |

* | |

* @return The stack distance of the current address. | |

*/ | |

uint64_t getIndex() const { return index; } | |

/** | |

* Query depth of the tree (tree[0] represents leaf layer while | |

* tree[treeDepth] represents the root layer, all layers in | |

* between contain intermediate nodes) | |

* | |

* @return Tree depth | |

*/ | |

uint64_t getTreeDepth() const { return tree.size() - 1; } | |

/** | |

* Print the last n items on the stack. | |

* This method prints top n entries in the tree based implementation as | |

* well as dummy stack. | |

* @param n Number of entries to print | |

*/ | |

void printStack(int n = 5) const; | |

/** | |

* This is an alternative implementation of the stack-distance | |

* in a naive way. It uses simple STL vector to represent the stack. | |

* It can be used in parallel for debugging purposes. | |

* It is 10x slower than the tree based implemenation. | |

* | |

* @param r_address The current address to process | |

* @param update_stack Flag to indicate if stack should be updated | |

* @return Stack distance which is calculated by this alternative | |

* implementation | |

* | |

*/ | |

uint64_t verifyStackDist(const Addr r_address, | |

bool update_stack = false); | |

public: | |

StackDistCalc(bool verify_stack = false); | |

~StackDistCalc(); | |

/** | |

* A convenient way of refering to infinity. | |

*/ | |

static constexpr uint64_t Infinity = std::numeric_limits<uint64_t>::max(); | |

/** | |

* Process the given address. If Mark is true then set the | |

* mark flag of the leaf node. | |

* This function returns the stack distance of the incoming | |

* address and the previous status of the mark flag. | |

* | |

* @param r_address The current address to process | |

* @param mark set the mark flag for the address. | |

* @return The stack distance of the current address and the mark flag. | |

*/ | |

std::pair<uint64_t, bool> calcStackDist(const Addr r_address, | |

bool mark = false); | |

/** | |

* Process the given address: | |

* - Lookup the tree for the given address | |

* - delete old node if found in tree | |

* - add a new node (if addNewNode flag is set) | |

* This function returns the stack distance of the incoming | |

* address and the status of the mark flag. | |

* | |

* @param r_address The current address to process | |

* @param addNewNode If true, a new node is added to the tree | |

* @return The stack distance of the current address and the mark flag. | |

*/ | |

std::pair<uint64_t, bool> calcStackDistAndUpdate(const Addr r_address, | |

bool addNewNode = true); | |

private: | |

/** | |

* Node which takes form of Leaf, INode or Root | |

*/ | |

struct Node{ | |

// Sum of the left children | |

uint64_t sumLeft; | |

// Sum of the right children | |

uint64_t sumRight; | |

// Flag to indicate that sumLeft has gone from non-zero value to 0 | |

bool discardLeft; | |

// Flag to indicate that sumRight has gone from non-zero value to 0 | |

bool discardRight; | |

// Index of the current element in the Map | |

uint64_t nodeIndex; | |

// Pointer to the parent | |

Node* parent; | |

// Flag to mark the node as the right/left child | |

bool isLeftNode; | |

/** | |

* Flag to indicate if this address is marked. Used in case | |

* where stack distance of a touched address is required. | |

*/ | |

bool isMarked; | |

/** | |

* The discard flags are false by default they become true if | |

* the node is reached again in a future lookup. | |

*/ | |

Node() : sumLeft(0), sumRight(0), discardLeft(false), | |

discardRight(false), nodeIndex(0), | |

parent(nullptr), isLeftNode(true), isMarked(false) | |

{ } | |

}; | |

/** | |

* Internal counter for address accesses (unique and non-unique) | |

* This counter increments everytime the calcStackDist() method is | |

* called. This counter is used as a key for the hash- map at the | |

* leaf layer. Practically at every call to the calculator this | |

* counter is incremented and a new leaf node is added in the tree | |

* at the leaf layer using this counter value as the key. | |

*/ | |

uint64_t index; | |

// Binary tree of partial sums | |

TreeType tree; | |

// Hash map which returns last seen index of each address | |

AddressIndexMap aiMap; | |

// Keeps count of number of the next unique index for each | |

// level in the tree | |

std::vector<uint64_t> nextIndex; | |

// Dummy Stack for verification | |

std::vector<uint64_t> stack; | |

// Flag to enable verification of stack. (Slows down the simulation) | |

const bool verifyStack; | |

}; | |

#endif //__STACK_DIST_CALC_HH__ |