diff options
Diffstat (limited to 'src/mem/stack_dist_calc.hh')
| -rw-r--r-- | src/mem/stack_dist_calc.hh | 454 |
1 files changed, 454 insertions, 0 deletions
diff --git a/src/mem/stack_dist_calc.hh b/src/mem/stack_dist_calc.hh new file mode 100644 index 000000000..881b71179 --- /dev/null +++ b/src/mem/stack_dist_calc.hh @@ -0,0 +1,454 @@ +/* + * Copyright (c) 2014 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 <map> +#include <vector> + +#include "base/types.hh" +#include "mem/packet.hh" +#include "params/StackDistCalc.hh" +#include "sim/sim_object.hh" +#include "sim/stats.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 : public SimObject +{ + + 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; + + /** + * 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); + + /** + * 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: + + /** + * Convenience method to get the params when registering stats. + */ + const StackDistCalcParams* params() const + { return reinterpret_cast<const StackDistCalcParams*>(_params); } + + StackDistCalc(const StackDistCalcParams* p); + + ~StackDistCalc(); + + void regStats(); + + /** + * Update the tree and the statistics. + * + * @param cmd Command from the packet + * @param addr Address to put on the stack + */ + void update(const MemCmd& cmd, Addr addr); + + 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; + + // Disable the linear histograms + const bool disableLinearHists; + + // Disable the logarithmic histograms + const bool disableLogHists; + + // Reads linear histogram + Stats::Histogram readLinearHist; + + // Reads logarithmic histogram + Stats::SparseHistogram readLogHist; + + // Writes linear histogram + Stats::Histogram writeLinearHist; + + // Writes logarithmic histogram + Stats::SparseHistogram writeLogHist; + +}; + +#endif //__STACK_DIST_CALC_HH__ |