diff options
| -rw-r--r-- | src/mem/SConscript | 4 | ||||
| -rw-r--r-- | src/mem/StackDistCalc.py | 54 | ||||
| -rw-r--r-- | src/mem/stack_dist_calc.cc | 670 | ||||
| -rw-r--r-- | src/mem/stack_dist_calc.hh | 454 |
4 files changed, 1181 insertions, 1 deletions
diff --git a/src/mem/SConscript b/src/mem/SConscript index e6973b1ac..50f58add1 100644 --- a/src/mem/SConscript +++ b/src/mem/SConscript @@ -44,6 +44,7 @@ SimObject('ExternalMaster.py') SimObject('ExternalSlave.py') SimObject('MemObject.py') SimObject('SimpleMemory.py') +SimObject('StackDistCalc.py') SimObject('XBar.py') Source('abstract_mem.cc') @@ -64,6 +65,7 @@ Source('port_proxy.cc') Source('physical.cc') Source('simple_mem.cc') Source('snoop_filter.cc') +Source('stack_dist_calc.cc') Source('tport.cc') Source('xbar.cc') @@ -101,7 +103,7 @@ DebugFlag('LLSC') DebugFlag('MMU') DebugFlag('MemoryAccess') DebugFlag('PacketQueue') - +DebugFlag('StackDist') DebugFlag("DRAMSim2") DebugFlag("MemChecker") diff --git a/src/mem/StackDistCalc.py b/src/mem/StackDistCalc.py new file mode 100644 index 000000000..4986da9be --- /dev/null +++ b/src/mem/StackDistCalc.py @@ -0,0 +1,54 @@ +# 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: Andreas Hansson + +from m5.SimObject import SimObject +from m5.params import * + +class StackDistCalc(SimObject): + type = 'StackDistCalc' + cxx_header = "mem/stack_dist_calc.hh" + + # enable verification stack + verify = Param.Bool(False, "Verify behaviuor with reference implementation") + + # linear histogram bins and enable/disable + linear_hist_bins = Param.Unsigned('16', "Bins in linear histograms") + disable_linear_hists = Param.Bool(False, "Disable linear histograms") + + # logarithmic histogram bins and enable/disable + log_hist_bins = Param.Unsigned('32', "Bins in logarithmic histograms") + disable_log_hists = Param.Bool(False, "Disable logarithmic histograms") diff --git a/src/mem/stack_dist_calc.cc b/src/mem/stack_dist_calc.cc new file mode 100644 index 000000000..c273ee7f4 --- /dev/null +++ b/src/mem/stack_dist_calc.cc @@ -0,0 +1,670 @@ +/* + * 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 + */ + +#include "base/intmath.hh" +#include "base/trace.hh" +#include "debug/StackDist.hh" +#include "mem/stack_dist_calc.hh" + +StackDistCalc::StackDistCalc(const StackDistCalcParams* p) : + SimObject(p), index(0), verifyStack(p->verify), + disableLinearHists(p->disable_linear_hists), + disableLogHists(p->disable_log_hists) +{ + // Instantiate a new root and leaf layer + // Map type variable, representing a layer in the tree + IndexNodeMap tree_level; + + // Initialize tree count for leaves + nextIndex.push_back(0); + + // Add the initial leaf layer to the tree + tree.push_back(tree_level); + + // Create a root node. Node type variable in the topmost layer + Node* root_node = new Node(); + + // Initialize tree count for root + nextIndex.push_back(1); + + // Add the empty root layer to the tree + tree.push_back(tree_level); + + // Add the initial root to the tree + tree[1][root_node->nodeIndex] = root_node; +} + +StackDistCalc::~StackDistCalc() +{ + // Walk through each layer and destroy the nodes + for (auto& layer : tree) { + for (auto& index_node : layer) { + // each map entry contains an index and a node + delete index_node.second; + } + // Clear each layer in the tree + layer.clear(); + } + + // Clear the tree + tree.clear(); + aiMap.clear(); + nextIndex.clear(); + + // For verification + stack.clear(); +} + +void +StackDistCalc::update(const MemCmd& cmd, Addr addr) +{ + // only capturing read and write requests (which allocate in the + // cache) + if (cmd.isRead() || cmd.isWrite()) { + auto returnType = calcStackDistAndUpdate(addr); + + uint64_t stackDist = returnType.first; + + if (stackDist != Infinity) { + // Sample the stack distance of the address in linear bins + if (!disableLinearHists) { + if (cmd.isRead()) + readLinearHist.sample(stackDist); + else + writeLinearHist.sample(stackDist); + } + + if (!disableLogHists) { + int stackDistLog2 = stackDist == 0 ? 1 : floorLog2(stackDist); + + // Sample the stack distance of the address in log bins + if (cmd.isRead()) + readLogHist.sample(stackDistLog2); + else + writeLogHist.sample(stackDistLog2); + } + } + } +} + +// The updateSum method is a recursive function which updates +// the node sums till the root. It also deletes the nodes that +// are not used anymore. +uint64_t +StackDistCalc::updateSum(Node* node, bool from_left, + uint64_t sum_from_below, uint64_t level, + uint64_t stack_dist, bool discard_node) +{ + ++level; + + // Make a copy of the node variables and work on them + // as a node may be deleted by this function + uint64_t node_sum_l = node->sumLeft; + uint64_t node_sum_r = node->sumRight; + bool node_left = node->isLeftNode; + bool node_discard_left = node->discardLeft; + bool node_discard_right = node->discardRight; + uint64_t node_n_index = node->nodeIndex; + Node* node_parent_ptr = node->parent; + + // For verification + if (verifyStack) { + // This sanity check makes sure that the left_sum and + // right_sum of the node is not greater than the + // maximum possible value given by the leaves below it + // for example a node in layer 3 (tree[3]) can at most + // have 8 leaves (4 to the left and 4 to the right) + // thus left_sum and right_sum should be <= 4 + panic_if(node_sum_l > (1 << (level - 1)), + "Error in sum left of level %ul, node index %ull, " + "Sum = %ull \n", level, node_n_index, node_sum_l); + + panic_if(node_sum_r > (1 << (level - 1)), + "Error in sum right of level %ul, node index %ull, " + "Sum = %ull \n", level, node_n_index, node_sum_r); + } + + // Update the left sum or the right sum depending on the + // from_left flag. Variable stack_dist is updated only + // when arriving from Left. + if (from_left) { + // update sumLeft + node_sum_l = sum_from_below; + stack_dist += node_sum_r; + } else { + // update sum_r + node_sum_r = sum_from_below; + } + + // sum_from_below == 0 can be a leaf discard operation + if (discard_node && !sum_from_below) { + if (from_left) + node_discard_left = true; + else + node_discard_right = true; + } + + // Update the node variables with new values + node->nodeIndex = node_n_index; + node->sumLeft = node_sum_l; + node->sumRight = node_sum_r; + node->isLeftNode = node_left; + node->discardLeft = node_discard_left; + node->discardRight = node_discard_right; + + // Delete the node if it is not required anymore + if (node_discard_left && node_discard_right && + discard_node && node_parent_ptr && !sum_from_below) { + delete node; + tree[level].erase(node_n_index); + discard_node = true; + } else { + // propogate discard_node as false upwards if the + // above conditions are not met. + discard_node = false; + } + + // Recursively call the updateSum operation till the + // root node is reached + if (node_parent_ptr) { + stack_dist = updateSum(node_parent_ptr, node_left, + node_sum_l + node_sum_r, + level, stack_dist, discard_node); + } + + return stack_dist; +} + +// This function is called by the calcStackDistAndUpdate function +// If is_new_leaf is true then a new leaf is added otherwise a leaf +// removed from the tree. In both cases the tree is updated using +// the updateSum operation. +uint64_t +StackDistCalc::updateSumsLeavesToRoot(Node* node, bool is_new_leaf) +{ + uint64_t level = 0; + uint64_t stack_dist = 0; + + if (is_new_leaf) { + node->sumLeft = 1; + updateSum(node->parent, + node->isLeftNode, node->sumLeft, + level, 0, false); + + stack_dist = Infinity; + } else { + node->sumLeft = 0; + stack_dist = updateSum(node->parent, + node->isLeftNode, 0, + level, stack_dist, true); + } + + return stack_dist; +} + +// This method is a recursive function which calculates +// the node sums till the root. +uint64_t +StackDistCalc::getSum(Node* node, bool from_left, uint64_t sum_from_below, + uint64_t stack_dist, uint64_t level) const +{ + ++level; + // Variable stack_dist is updated only + // when arriving from Left. + if(from_left) { + stack_dist += node->sumRight; + } + + // Recursively call the getSum operation till the + // root node is reached + if(node->parent) { + stack_dist = getSum(node->parent, node->isLeftNode, + node->sumLeft + node->sumRight, + stack_dist, level); + } + + return stack_dist; +} + +// This function is called by the calcStackDistance function +uint64_t +StackDistCalc::getSumsLeavesToRoot(Node* node) const +{ + return getSum(node->parent, node->isLeftNode, 0, 0, 0); +} + +// Update tree 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 +StackDistCalc::updateTree() +{ + uint64_t i; + + if (isPowerOf2(index)) { + // OP1. moving the root node one layer up if index counter + // crosses power of 2 + // If index counter crosses a power of 2, then add a + // new tree layer above and create a new Root node in it. + // After the root is created the old node + // in the layer below is updated to point to this + // newly created root node. The sum_l of this new root node + // becomes the sum_l + sum_r of the old node. + // + // After this root update operation a chain of intermediate + // nodes is created from root layer to tree[1](one layer + // above the leaf layer) + + // Create a new root node + Node* newRootNode = new Node(); + + // Update its sum_l as the sum_l+sum_r from below + newRootNode->sumLeft = tree[getTreeDepth()][0]->sumRight + + tree[getTreeDepth()][0]->sumLeft; + // Update its discard left flag if the node below has + // has both discardLeft and discardRight set. + newRootNode->discardLeft = tree[getTreeDepth()][0]->discardLeft && + tree[getTreeDepth()][0]->discardRight; + + // Map type variable, representing a layer in the tree + IndexNodeMap treeLevel; + // Add a new layer to the tree + tree.push_back(treeLevel); + nextIndex.push_back(1); + tree[getTreeDepth()][newRootNode->nodeIndex] = newRootNode; + + // Update the parent pointer at lower layer to + // point to newly created root node + tree[getTreeDepth() - 1][0]->parent = tree[getTreeDepth()][0]; + + // Add intermediate nodes from root till bottom (one layer above the + // leaf layer) + for (i = getTreeDepth() - 1; i >= 1; --i) { + Node* newINode = new Node(); + // newNode is left or right child depending on the number of nodes + // in that layer + if (nextIndex[i] % 2 == 0) { + newINode->isLeftNode = true; + } else { + newINode->isLeftNode = false; + } + + newINode->parent = tree[i + 1][nextIndex[i + 1] - 1]; + newINode->nodeIndex = ++nextIndex[i] - 1; + tree[i][newINode->nodeIndex] = newINode; + } + } else { + // OP2. Addition of intermediate nodes as and when required + // and linking them to their parents in the layer above. + // + // At layer 1 a new INode is added whenever index%(2^1)==0 + // (multiples of 2) + // + // At layer 2 a new INode is added whenever index%(2^2)==0 + // (multiples of 4) + // + // At layer 3 a new INode is added whenever index%(2^3)==0 + // (multiples of 8) + //... + // + // At layer N a new INode is added whenever index%(2^N)==0 + // (multiples of 2^N) + for (i = getTreeDepth() - 1; i >= 1; --i) { + // Traverse each layer from root to leaves and add a new + // intermediate node if required. Link the parent_ptr of + // the new node to the parent in the above layer. + + if ((index % (1 << i)) == 0) { + // Checks if current (index % 2^treeDepth) == 0 if true + // a new node at that layer is created + Node* newINode = new Node(); + + // newNode is left or right child depending on the + // number of nodes in that layer. + if (nextIndex[i] % 2 == 0) { + newINode->isLeftNode = true; + } else { + newINode->isLeftNode = false; + } + + // Pointing to its parent in the upper layer + newINode->parent = tree[i + 1][nextIndex[i + 1] - 1]; + newINode->nodeIndex = ++nextIndex[i] - 1; + tree[i][newINode->nodeIndex] = newINode; + } + } + } +} + +// This function is called everytime to get the stack distance and add +// a new node. 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 the lower level (Membus) +// to L2, can be marked (isMarked flag of Node set to True). And 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. +std::pair< uint64_t, bool> +StackDistCalc::calcStackDistAndUpdate(const Addr r_address, bool addNewNode) +{ + Node* newLeafNode; + // Return index if the address was already present in stack + uint64_t r_index = index; + + auto ai = aiMap.lower_bound(r_address); + + // Default value of flag indicating as the left or right leaf + bool isLeft = true; + // Default value of isMarked flag for each node. + bool _mark = false; + // By default stackDistacne is treated as infinity + uint64_t stack_dist; + + // Lookup aiMap by giving address as the key: + // If found take address and Lookup in tree + // Update tree from leaves by making B(found index) = 0 + // Add sums to right till root while Updating them + // Stack Distance of that address sums to right + if (ai != aiMap.end() && !(aiMap.key_comp()(r_address, ai->first))) { + // key already exists + // save the index counter value when this address was + // encountered before and update it to the current index value + r_index = ai->second; + + if (addNewNode) { + // Update aiMap aiMap(Address) = current index + ai->second = index; + } else { + aiMap.erase(r_address); + } + + // Call update tree operation on the tree starting with + // the r_index value found above. This function would return + // the value of the stack distcance. + stack_dist = updateSumsLeavesToRoot(tree[0][r_index], false); + newLeafNode = tree[0][r_index]; + // determine if this node was marked earlier + _mark = newLeafNode->isMarked; + delete newLeafNode; + tree[0].erase(r_index); + } else { + if (addNewNode) { + // Update aiMap aiMap(Address) = current index + aiMap[r_address] = index; + } + // Update infinity bin count + // By default stackDistacne is treated as infinity + stack_dist = Infinity; + } + + if (addNewNode) { + // If index%2 == 0 then update tree + if (index % 2 == 0) { + updateTree(); + } else { + // At odd values of index counter, a new right-type node is + // added to the leaf layer, else a left-type node is added + isLeft = false; + } + + // Add new leaf node in the leaf layer (tree[0]) + // set n_index = current index + newLeafNode = new Node(); + ++nextIndex[0]; + newLeafNode->nodeIndex=index; + newLeafNode->isLeftNode=isLeft; + // Point the parent pointer to the intermediate node above + newLeafNode->parent = tree[1][nextIndex[1] - 1]; + tree[0][index] = newLeafNode; + // call an update operation which would update the tree after + // addition of this new leaf node. + updateSumsLeavesToRoot(tree[0][index], true); + + // For verification + if (verifyStack) { + // This function checks the sanity of the tree to make sure the + // last node in the link of parent pointers is the root node. + // It takes a leaf node as an argument and traveses upwards till + // the root layer to check if the last parent is null + sanityCheckTree(tree[0][index]); + + // Push the same element in debug stack, and check + uint64_t verify_stack_dist = verifyStackDist(r_address, true); + panic_if(verify_stack_dist != stack_dist, + "Expected stack-distance for address \ + %#lx is %#lx but found %#lx", + r_address, verify_stack_dist, stack_dist); + printStack(); + } + + // The index counter is updated at the end of each transaction + // (unique or non-unique) + ++index; + } + + return (std::make_pair(stack_dist, _mark)); +} + +// This function is called everytime to get the stack distance +// no new node is added. It can be used to mark a previous access +// and inspect the value of the mark flag. +std::pair< uint64_t, bool> +StackDistCalc::calcStackDist(const Addr r_address, bool mark) +{ + // Return index if the address was already present in stack + uint64_t r_index = index; + // Default value of isMarked flag for each node. + bool _mark = false; + + auto ai = aiMap.lower_bound(r_address); + + // By default stackDistacne is treated as infinity + uint64_t stack_dist = 0; + + // Lookup aiMap by giving address as the key: + // If found take address and Lookup in tree + // Add sums to right till root + // Stack Distance of that address sums to right + if (ai != aiMap.end() && !(aiMap.key_comp()(r_address, ai->first))) { + // key already exists + // save the index counter value when this address was + // encountered before + r_index = ai->second; + + // Get the value of mark flag if previously marked + _mark = tree[0][r_index]->isMarked; + // Mark the leaf node if required + tree[0][r_index]->isMarked = mark; + + // Call get sums operation on the tree starting with + // the r_index value found above. This function would return + // the value of the stack distcance. + stack_dist = getSumsLeavesToRoot(tree[0][r_index]); + } else { + // Update infinity bin count + // By default stackDistacne is treated as infinity + stack_dist = Infinity; + } + + // For verification + if (verifyStack) { + // Calculate the SD of the same address in the debug stack + uint64_t verify_stack_dist = verifyStackDist(r_address); + panic_if(verify_stack_dist != stack_dist, + "Expected stack-distance for address \ + %#lx is %#lx but found %#lx", + r_address, verify_stack_dist, stack_dist); + + printStack(); + } + + return std::make_pair(stack_dist, _mark); +} + +// For verification +// Simple sanity check for the tree +void +StackDistCalc::sanityCheckTree(const Node* node, uint64_t level) const +{ + const Node* next_up = node->parent; + + for (uint64_t i = level + 1; i < getTreeDepth() - level; ++i) { + next_up = next_up->parent; + panic_if(!next_up, "Sanity check failed for node %ull \n", + node->nodeIndex); + } + + // At the root layer the parent_ptr should be null + panic_if(next_up->parent, "Sanity check failed for node %ull \n", + node->nodeIndex); +} + +// This method can be called to compute the stack distance in a naive +// way It can be used to verify the functionality of the stack +// distance calculator. It uses std::vector to compute the stack +// distance using a naive stack. +uint64_t +StackDistCalc::verifyStackDist(const Addr r_address, bool update_stack) +{ + bool found = false; + uint64_t stack_dist = 0; + auto a = stack.rbegin(); + + for (; a != stack.rend(); ++a) { + if (*a == r_address) { + found = true; + break; + } else { + ++stack_dist; + } + } + + if (found) { + ++a; + if (update_stack) + stack.erase(a.base()); + } else { + stack_dist = Infinity; + } + + if (update_stack) + stack.push_back(r_address); + + return stack_dist; +} + +// This method is useful to print top n entities in the stack. +void +StackDistCalc::printStack(int n) const +{ + Node* node; + uint64_t r_index; + int count = 0; + + DPRINTF(StackDist, "Printing last %d entries in tree\n", n); + + // Walk through leaf layer to display the last n nodes + for (auto it = tree[0].rbegin(); (count < n) && (it != tree[0].rend()); + ++it, ++count) { + node = it->second; + r_index = node->nodeIndex; + + // Lookup aiMap using the index returned by the leaf iterator + for (auto ai = aiMap.rbegin(); ai != aiMap.rend(); ++ai) { + if (ai->second == r_index) { + DPRINTF(StackDist,"Tree leaves, Rightmost-[%d] = %#lx\n", + count, ai->first); + break; + } + } + } + + DPRINTF(StackDist,"Tree depth = %#ld\n", getTreeDepth()); + + if (verifyStack) { + DPRINTF(StackDist,"Printing Last %d entries in VerifStack \n", n); + count = 0; + for (auto a = stack.rbegin(); (count < n) && (a != stack.rend()); + ++a, ++count) { + DPRINTF(StackDist, "Verif Stack, Top-[%d] = %#lx\n", count, *a); + } + } +} + +void +StackDistCalc::regStats() +{ + using namespace Stats; + + readLinearHist + .init(params()->linear_hist_bins) + .name(name() + ".readLinearHist") + .desc("Reads linear distribution") + .flags(disableLinearHists ? nozero : pdf); + + readLogHist + .init(params()->log_hist_bins) + .name(name() + ".readLogHist") + .desc("Reads logarithmic distribution") + .flags(disableLogHists ? nozero : pdf); + + writeLinearHist + .init(params()->linear_hist_bins) + .name(name() + ".writeLinearHist") + .desc("Writes linear distribution") + .flags(disableLinearHists ? nozero : pdf); + + writeLogHist + .init(params()->log_hist_bins) + .name(name() + ".writeLogHist") + .desc("Writes logarithmic distribution") + .flags(disableLogHists ? nozero : pdf); +} + +StackDistCalc* +StackDistCalcParams::create() +{ + return new StackDistCalc(this); +} 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__ |