/*
* 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__