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
35using namespace std;
36
37Histogram::Histogram(int binsize, uint32_t bins)
38{
39 m_binsize = binsize;
40 clear(bins);
41}
42
43Histogram::~Histogram()
44{
45}
46
47void
48Histogram::clear(int binsize, uint32_t bins)
49{
50 m_binsize = binsize;
51 clear(bins);
52}
53
54void
55Histogram::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
70void
71Histogram::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
86void
| 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
35using namespace std;
36
37Histogram::Histogram(int binsize, uint32_t bins)
38{
39 m_binsize = binsize;
40 clear(bins);
41}
42
43Histogram::~Histogram()
44{
45}
46
47void
48Histogram::clear(int binsize, uint32_t bins)
49{
50 m_binsize = binsize;
51 clear(bins);
52}
53
54void
55Histogram::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
70void
71Histogram::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
86void
|
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
121void
122Histogram::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
174double
175Histogram::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
186void
187Histogram::print(ostream& out) const
188{
189 printWithMultiplier(out, 1.0);
190}
191
192void
193Histogram::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
202void
203Histogram::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
232bool
233node_less_then_eq(const Histogram* n1, const Histogram* n2)
234{
235 return (n1->size() > n2->size());
236}
| 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
121void
122Histogram::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
174double
175Histogram::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
186void
187Histogram::print(ostream& out) const
188{
189 printWithMultiplier(out, 1.0);
190}
191
192void
193Histogram::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
202void
203Histogram::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
232bool
233node_less_then_eq(const Histogram* n1, const Histogram* n2)
234{
235 return (n1->size() > n2->size());
236}
|