gem5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Histogram.cc
Go to the documentation of this file.
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 
30 
31 #include <cmath>
32 #include <iomanip>
33 
34 #include "base/intmath.hh"
35 
36 using namespace std;
37 
38 Histogram::Histogram(int binsize, uint32_t bins)
39 {
40  m_binsize = binsize;
41  clear(bins);
42 }
43 
45 {
46 }
47 
48 void
49 Histogram::clear(int binsize, uint32_t bins)
50 {
51  m_binsize = binsize;
52  clear(bins);
53 }
54 
55 void
56 Histogram::clear(uint32_t bins)
57 {
58  m_largest_bin = 0;
59  m_max = 0;
60  m_data.resize(bins);
61  for (uint32_t i = 0; i < bins; i++) {
62  m_data[i] = 0;
63  }
64 
65  m_count = 0;
66  m_max = 0;
67  m_sumSamples = 0;
68  m_sumSquaredSamples = 0;
69 }
70 
71 void
73 {
74  assert(m_binsize != -1);
75  uint32_t t_bins = m_data.size();
76 
77  for (uint32_t i = 0; i < t_bins/2; i++) {
78  m_data[i] = m_data[i*2] + m_data[i*2 + 1];
79  }
80  for (uint32_t i = t_bins/2; i < t_bins; i++) {
81  m_data[i] = 0;
82  }
83 
84  m_binsize *= 2;
85 }
86 
87 void
88 Histogram::add(int64_t value)
89 {
90  assert(value >= 0);
91  m_max = max(m_max, value);
92  m_count++;
93 
94  m_sumSamples += value;
95  m_sumSquaredSamples += (value*value);
96 
97  uint32_t index;
98 
99  if (m_binsize == -1) {
100  // This is a log base 2 histogram
101  if (value == 0) {
102  index = 0;
103  } else {
104  index = floorLog2(value) + 1;
105  if (index >= m_data.size()) {
106  index = m_data.size() - 1;
107  }
108  }
109  } else {
110  // This is a linear histogram
111  uint32_t t_bins = m_data.size();
112 
113  while (m_max >= (t_bins * m_binsize)) doubleBinSize();
114  index = value/m_binsize;
115  }
116 
117  assert(index < m_data.size());
118  m_data[index]++;
119  m_largest_bin = max(m_largest_bin, index);
120 }
121 
122 void
124 {
125  uint32_t t_bins = m_data.size();
126 
127  if (hist.getBins() != t_bins) {
128  if (m_count == 0) {
129  m_data.resize(hist.getBins());
130  } else {
131  fatal("Histograms with different number of bins "
132  "cannot be combined!");
133  }
134  }
135 
136  m_max = max(m_max, hist.getMax());
137  m_count += hist.size();
138  m_sumSamples += hist.getTotal();
139  m_sumSquaredSamples += hist.getSquaredTotal();
140 
141  // Both histograms are log base 2.
142  if (hist.getBinSize() == -1 && m_binsize == -1) {
143  for (int j = 0; j < hist.getData(0); j++) {
144  add(0);
145  }
146 
147  for (uint32_t i = 1; i < t_bins; i++) {
148  for (int j = 0; j < hist.getData(i); j++) {
149  add(1<<(i-1)); // account for the + 1 index
150  }
151  }
152  } else if (hist.getBinSize() >= 1 && m_binsize >= 1) {
153  // Both the histogram are linear.
154  // We are assuming that the two histograms have the same
155  // minimum value that they can store.
156 
157  while (m_binsize > hist.getBinSize()) hist.doubleBinSize();
158  while (hist.getBinSize() > m_binsize) doubleBinSize();
159 
160  assert(m_binsize == hist.getBinSize());
161 
162  for (uint32_t i = 0; i < t_bins; i++) {
163  m_data[i] += hist.getData(i);
164 
165  if (m_data[i] > 0) m_largest_bin = i;
166  }
167  } else {
168  fatal("Don't know how to combine log and linear histograms!");
169  }
170 }
171 
172 // Computation of standard deviation of samples a1, a2, ... aN
173 // variance = [SUM {ai^2} - (SUM {ai})^2/N]/(N-1)
174 // std deviation equals square root of variance
175 double
177 {
178  if (m_count <= 1)
179  return 0.0;
180 
181  double variance =
182  (double)(m_sumSquaredSamples - m_sumSamples * m_sumSamples / m_count)
183  / (m_count - 1);
184  return sqrt(variance);
185 }
186 
187 void
188 Histogram::print(ostream& out) const
189 {
190  printWithMultiplier(out, 1.0);
191 }
192 
193 void
194 Histogram::printPercent(ostream& out) const
195 {
196  if (m_count == 0) {
197  printWithMultiplier(out, 0.0);
198  } else {
199  printWithMultiplier(out, 100.0 / double(m_count));
200  }
201 }
202 
203 void
204 Histogram::printWithMultiplier(ostream& out, double multiplier) const
205 {
206  if (m_binsize == -1) {
207  out << "[binsize: log2 ";
208  } else {
209  out << "[binsize: " << m_binsize << " ";
210  }
211  out << "max: " << m_max << " ";
212  out << "count: " << m_count << " ";
213  // out << "total: " << m_sumSamples << " ";
214  if (m_count == 0) {
215  out << "average: NaN |";
216  out << "standard deviation: NaN |";
217  } else {
218  out << "average: " << setw(5) << ((double) m_sumSamples)/m_count
219  << " | ";
220  out << "standard deviation: " << getStandardDeviation() << " |";
221  }
222 
223  for (uint32_t i = 0; i <= m_largest_bin; i++) {
224  if (multiplier == 1.0) {
225  out << " " << m_data[i];
226  } else {
227  out << " " << double(m_data[i]) * multiplier;
228  }
229  }
230  out << " ]";
231 }
232 
233 bool
234 node_less_then_eq(const Histogram* n1, const Histogram* n2)
235 {
236  return (n1->size() > n2->size());
237 }
~Histogram()
Definition: Histogram.cc:44
Bitfield< 30, 0 > index
uint64_t getSquaredTotal() const
Definition: Histogram.hh:55
void doubleBinSize()
Definition: Histogram.cc:72
Bitfield< 7 > i
Definition: miscregs.hh:1378
int getBinSize() const
Definition: Histogram.hh:53
uint32_t getBins() const
Definition: Histogram.hh:52
void add(int64_t value)
Definition: Histogram.cc:88
bool node_less_then_eq(const Histogram *n1, const Histogram *n2)
Definition: Histogram.cc:234
#define fatal(...)
Definition: misc.hh:163
uint64_t getData(int index) const
Definition: Histogram.hh:56
int64_t getTotal() const
Definition: Histogram.hh:54
int64_t getMax() const
Definition: Histogram.hh:57
double getStandardDeviation() const
Definition: Histogram.cc:176
Bitfield< 24 > j
Definition: miscregs.hh:1369
int floorLog2(unsigned x)
Definition: intmath.hh:100
Histogram(int binsize=1, uint32_t bins=50)
Definition: Histogram.cc:38
void printWithMultiplier(std::ostream &out, double multiplier) const
Definition: Histogram.cc:204
void printPercent(std::ostream &out) const
Definition: Histogram.cc:194
void clear()
Definition: Histogram.hh:47
void print(std::ostream &out) const
Definition: Histogram.cc:188
uint64_t size() const
Definition: Histogram.hh:51

Generated on Fri Jun 9 2017 13:03:49 for gem5 by doxygen 1.8.6