src/mem/ruby/common/Histogram.cc

   1 /*
   2  * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include <cmath>
  30 #include <iomanip>
  31
  32 #include "base/intmath.hh"
  33 #include "mem/ruby/common/Histogram.hh"
  34
  35 using namespace std;
  36
  37 Histogram::Histogram(int binsize, uint32_t bins)
  38 {
  39     m_binsize = binsize;
  40     clear(bins);
  41 }
  42
  43 Histogram::~Histogram()
  44 {
  45 }
  46
  47 void
  48 Histogram::clear(int binsize, uint32_t bins)
  49 {
  50     m_binsize = binsize;
  51     clear(bins);
  52 }
  53
  54 void
  55 Histogram::clear(uint32_t bins)
  56 {
  57     m_largest_bin = 0;
  58     m_max = 0;
  59     m_data.resize(bins);
  60     for (uint32_t i = 0; i < bins; i++) {
  61         m_data[i] = 0;
  62     }
  63
  64     m_count = 0;
  65     m_max = 0;
  66     m_sumSamples = 0;
  67     m_sumSquaredSamples = 0;
  68 }
  69
  70 void
  71 Histogram::doubleBinSize()
  72 {
  73     assert(m_binsize != -1);
  74     uint32_t t_bins = m_data.size();
  75
  76     for (uint32_t i = 0; i < t_bins/2; i++) {
  77         m_data[i] = m_data[i*2] + m_data[i*2 + 1];
  78     }
  79     for (uint32_t i = t_bins/2; i < t_bins; i++) {
  80         m_data[i] = 0;
  81     }
  82
  83     m_binsize *= 2;
  84 }
  85
  86 void
  87 Histogram::add(int64 value)
  88 {
  89     assert(value >= 0);
  90     m_max = max(m_max, value);
  91     m_count++;
  92
  93     m_sumSamples += value;
  94     m_sumSquaredSamples += (value*value);
  95
  96     uint32_t index;
  97
  98     if (m_binsize == -1) {
  99         // This is a log base 2 histogram
 100         if (value == 0) {
 101             index = 0;
 102         } else {
 103             index = floorLog2(value) + 1;
 104             if (index >= m_data.size()) {
 105                 index = m_data.size() - 1;
 106             }
 107         }
 108     } else {
 109         // This is a linear histogram
 110         uint32_t t_bins = m_data.size();
 111
 112         while (m_max >= (t_bins * m_binsize)) doubleBinSize();
 113         index = value/m_binsize;
 114     }
 115
 116     assert(index < m_data.size());
 117     m_data[index]++;
 118     m_largest_bin = max(m_largest_bin, index);
 119 }
 120
 121 void
 122 Histogram::add(Histogram& hist)
 123 {
 124     uint32_t t_bins = m_data.size();
 125
 126     if (hist.getBins() != t_bins) {
 127         if (m_count == 0) {
 128             m_data.resize(hist.getBins());
 129         } else {
 130             fatal("Histograms with different number of bins "
 131                   "cannot be combined!");
 132         }
 133     }
 134
 135     m_max = max(m_max, hist.getMax());
 136     m_count += hist.size();
 137     m_sumSamples += hist.getTotal();
 138     m_sumSquaredSamples += hist.getSquaredTotal();
 139
 140     // Both histograms are log base 2.
 141     if (hist.getBinSize() == -1 && m_binsize == -1) {
 142         for (int j = 0; j < hist.getData(0); j++) {
 143             add(0);
 144         }
 145
 146         for (uint32_t i = 1; i < t_bins; i++) {
 147             for (int j = 0; j < hist.getData(i); j++) {
 148                 add(1<<(i-1));  // account for the + 1 index
 149             }
 150         }
 151     } else if (hist.getBinSize() >= 1 && m_binsize >= 1) {
 152         // Both the histogram are linear.
 153         // We are assuming that the two histograms have the same
 154         // minimum value that they can store.
 155
 156         while (m_binsize > hist.getBinSize()) hist.doubleBinSize();
 157         while (hist.getBinSize() > m_binsize) doubleBinSize();
 158
 159         assert(m_binsize == hist.getBinSize());
 160
 161         for (uint32_t i = 0; i < t_bins; i++) {
 162             m_data[i] += hist.getData(i);
 163
 164             if (m_data[i] > 0) m_largest_bin = i;
 165         }
 166     } else {
 167         fatal("Don't know how to combine log and linear histograms!");
 168     }
 169 }
 170
 171 // Computation of standard deviation of samples a1, a2, ... aN
 172 // variance = [SUM {ai^2} - (SUM {ai})^2/N]/(N-1)
 173 // std deviation equals square root of variance
 174 double
 175 Histogram::getStandardDeviation() const
 176 {
 177     if (m_count <= 1)
 178         return 0.0;
 179
 180     double variance =
 181         (double)(m_sumSquaredSamples - m_sumSamples * m_sumSamples / m_count)
 182         / (m_count - 1);
 183     return sqrt(variance);
 184 }
 185
 186 void
 187 Histogram::print(ostream& out) const
 188 {
 189     printWithMultiplier(out, 1.0);
 190 }
 191
 192 void
 193 Histogram::printPercent(ostream& out) const
 194 {
 195     if (m_count == 0) {
 196         printWithMultiplier(out, 0.0);
 197     } else {
 198         printWithMultiplier(out, 100.0 / double(m_count));
 199     }
 200 }
 201
 202 void
 203 Histogram::printWithMultiplier(ostream& out, double multiplier) const
 204 {
 205     if (m_binsize == -1) {
 206         out << "[binsize: log2 ";
 207     } else {
 208         out << "[binsize: " << m_binsize << " ";
 209     }
 210     out << "max: " << m_max << " ";
 211     out << "count: " << m_count << " ";
 212     //  out << "total: " <<  m_sumSamples << " ";
 213     if (m_count == 0) {
 214         out << "average: NaN |";
 215         out << "standard deviation: NaN |";
 216     } else {
 217         out << "average: " << setw(5) << ((double) m_sumSamples)/m_count
 218             << " | ";
 219         out << "standard deviation: " << getStandardDeviation() << " |";
 220     }
 221
 222     for (uint32_t i = 0; i <= m_largest_bin; i++) {
 223         if (multiplier == 1.0) {
 224             out << " " << m_data[i];
 225         } else {
 226             out << " " << double(m_data[i]) * multiplier;
 227         }
 228     }
 229     out << " ]";
 230 }
 231
 232 bool
 233 node_less_then_eq(const Histogram* n1, const Histogram* n2)
 234 {
 235     return (n1->size() > n2->size());
 236 }