AddressProfiler.cc (6433:0f0f0fbef977) AddressProfiler.cc (6896:649e40aad897)
1
2/*
3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met: redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer;
10 * redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution;
13 * neither the name of the copyright holders nor the names of its
14 * contributors may be used to endorse or promote products derived from
15 * this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30/*
31 * AddressProfiler.cc
32 *
33 * Description: See AddressProfiler.hh
34 *
35 * $Id$
36 *
37 */
38
39#include "mem/ruby/profiler/AddressProfiler.hh"
40#include "mem/protocol/CacheMsg.hh"
41#include "mem/ruby/profiler/AccessTraceForAddress.hh"
42#include "mem/gems_common/PrioHeap.hh"
43#include "mem/gems_common/Map.hh"
44#include "mem/ruby/system/System.hh"
45#include "mem/ruby/profiler/Profiler.hh"
46
47// Helper functions
1
2/*
3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met: redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer;
10 * redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution;
13 * neither the name of the copyright holders nor the names of its
14 * contributors may be used to endorse or promote products derived from
15 * this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30/*
31 * AddressProfiler.cc
32 *
33 * Description: See AddressProfiler.hh
34 *
35 * $Id$
36 *
37 */
38
39#include "mem/ruby/profiler/AddressProfiler.hh"
40#include "mem/protocol/CacheMsg.hh"
41#include "mem/ruby/profiler/AccessTraceForAddress.hh"
42#include "mem/gems_common/PrioHeap.hh"
43#include "mem/gems_common/Map.hh"
44#include "mem/ruby/system/System.hh"
45#include "mem/ruby/profiler/Profiler.hh"
46
47// Helper functions
48static AccessTraceForAddress& lookupTraceForAddress(const Address& addr, Map<Address, AccessTraceForAddress>* record_map);
49static void printSorted(ostream& out, const Map<Address, AccessTraceForAddress>* record_map, string description);
48static AccessTraceForAddress& lookupTraceForAddress(const Address& addr,
49 Map<Address,
50 AccessTraceForAddress>* record_map);
50
51
51AddressProfiler::AddressProfiler()
52static void printSorted(ostream& out,
53 int num_of_sequencers,
54 const Map<Address, AccessTraceForAddress>* record_map,
55 string description);
56
57AddressProfiler::AddressProfiler(int num_of_sequencers)
52{
53 m_dataAccessTrace = new Map<Address, AccessTraceForAddress>;
54 m_macroBlockAccessTrace = new Map<Address, AccessTraceForAddress>;
55 m_programCounterAccessTrace = new Map<Address, AccessTraceForAddress>;
56 m_retryProfileMap = new Map<Address, AccessTraceForAddress>;
58{
59 m_dataAccessTrace = new Map<Address, AccessTraceForAddress>;
60 m_macroBlockAccessTrace = new Map<Address, AccessTraceForAddress>;
61 m_programCounterAccessTrace = new Map<Address, AccessTraceForAddress>;
62 m_retryProfileMap = new Map<Address, AccessTraceForAddress>;
63 m_num_of_sequencers = num_of_sequencers;
57 clearStats();
58}
59
60AddressProfiler::~AddressProfiler()
61{
62 delete m_dataAccessTrace;
63 delete m_macroBlockAccessTrace;
64 delete m_programCounterAccessTrace;
65 delete m_retryProfileMap;
66}
67
68void AddressProfiler::setHotLines(bool hot_lines){
69 m_hot_lines = hot_lines;
70}
71void AddressProfiler::setAllInstructions(bool all_instructions){
72 m_all_instructions = all_instructions;
73}
74
75void AddressProfiler::printStats(ostream& out) const
76{
77 if (m_hot_lines) {
78 out << endl;
79 out << "AddressProfiler Stats" << endl;
80 out << "---------------------" << endl;
81
82 out << endl;
83 out << "sharing_misses: " << m_sharing_miss_counter << endl;
84 out << "getx_sharing_histogram: " << m_getx_sharing_histogram << endl;
85 out << "gets_sharing_histogram: " << m_gets_sharing_histogram << endl;
86
87 out << endl;
88 out << "Hot Data Blocks" << endl;
89 out << "---------------" << endl;
90 out << endl;
64 clearStats();
65}
66
67AddressProfiler::~AddressProfiler()
68{
69 delete m_dataAccessTrace;
70 delete m_macroBlockAccessTrace;
71 delete m_programCounterAccessTrace;
72 delete m_retryProfileMap;
73}
74
75void AddressProfiler::setHotLines(bool hot_lines){
76 m_hot_lines = hot_lines;
77}
78void AddressProfiler::setAllInstructions(bool all_instructions){
79 m_all_instructions = all_instructions;
80}
81
82void AddressProfiler::printStats(ostream& out) const
83{
84 if (m_hot_lines) {
85 out << endl;
86 out << "AddressProfiler Stats" << endl;
87 out << "---------------------" << endl;
88
89 out << endl;
90 out << "sharing_misses: " << m_sharing_miss_counter << endl;
91 out << "getx_sharing_histogram: " << m_getx_sharing_histogram << endl;
92 out << "gets_sharing_histogram: " << m_gets_sharing_histogram << endl;
93
94 out << endl;
95 out << "Hot Data Blocks" << endl;
96 out << "---------------" << endl;
97 out << endl;
91 printSorted(out, m_dataAccessTrace, "block_address");
98 printSorted(out, m_num_of_sequencers, m_dataAccessTrace, "block_address");
92
93 out << endl;
94 out << "Hot MacroData Blocks" << endl;
95 out << "--------------------" << endl;
96 out << endl;
99
100 out << endl;
101 out << "Hot MacroData Blocks" << endl;
102 out << "--------------------" << endl;
103 out << endl;
97 printSorted(out, m_macroBlockAccessTrace, "macroblock_address");
104 printSorted(out, m_num_of_sequencers, m_macroBlockAccessTrace, "macroblock_address");
98
99 out << "Hot Instructions" << endl;
100 out << "----------------" << endl;
101 out << endl;
105
106 out << "Hot Instructions" << endl;
107 out << "----------------" << endl;
108 out << endl;
102 printSorted(out, m_programCounterAccessTrace, "pc_address");
109 printSorted(out, m_num_of_sequencers, m_programCounterAccessTrace, "pc_address");
103 }
104
105 if (m_all_instructions){
106 out << endl;
107 out << "All Instructions Profile:" << endl;
108 out << "-------------------------" << endl;
109 out << endl;
110 }
111
112 if (m_all_instructions){
113 out << endl;
114 out << "All Instructions Profile:" << endl;
115 out << "-------------------------" << endl;
116 out << endl;
110 printSorted(out, m_programCounterAccessTrace, "pc_address");
117 printSorted(out, m_num_of_sequencers, m_programCounterAccessTrace, "pc_address");
111 out << endl;
112 }
113
114 if (m_retryProfileHisto.size() > 0) {
115 out << "Retry Profile" << endl;
116 out << "-------------" << endl;
117 out << endl;
118 out << "retry_histogram_absolute: " << m_retryProfileHisto << endl;
119 out << "retry_histogram_write: " << m_retryProfileHistoWrite << endl;
120 out << "retry_histogram_read: " << m_retryProfileHistoRead << endl;
121
122 out << "retry_histogram_percent: ";
123 m_retryProfileHisto.printPercent(out);
124 out << endl;
125
118 out << endl;
119 }
120
121 if (m_retryProfileHisto.size() > 0) {
122 out << "Retry Profile" << endl;
123 out << "-------------" << endl;
124 out << endl;
125 out << "retry_histogram_absolute: " << m_retryProfileHisto << endl;
126 out << "retry_histogram_write: " << m_retryProfileHistoWrite << endl;
127 out << "retry_histogram_read: " << m_retryProfileHistoRead << endl;
128
129 out << "retry_histogram_percent: ";
130 m_retryProfileHisto.printPercent(out);
131 out << endl;
132
126 printSorted(out, m_retryProfileMap, "block_address");
133 printSorted(out, m_num_of_sequencers, m_retryProfileMap, "block_address");
127 out << endl;
128 }
129
130}
131
132void AddressProfiler::clearStats()
133{
134 // Clear the maps
135 m_sharing_miss_counter = 0;
136 m_dataAccessTrace->clear();
137 m_macroBlockAccessTrace->clear();
138 m_programCounterAccessTrace->clear();
139 m_retryProfileMap->clear();
140 m_retryProfileHisto.clear();
141 m_retryProfileHistoRead.clear();
142 m_retryProfileHistoWrite.clear();
143 m_getx_sharing_histogram.clear();
144 m_gets_sharing_histogram.clear();
145}
146
147void AddressProfiler::profileGetX(const Address& datablock, const Address& PC, const Set& owner, const Set& sharers, NodeID requestor)
148{
149 Set indirection_set;
150 indirection_set.addSet(sharers);
151 indirection_set.addSet(owner);
152 indirection_set.remove(requestor);
153 int num_indirections = indirection_set.count();
154
155 m_getx_sharing_histogram.add(num_indirections);
156 bool indirection_miss = (num_indirections > 0);
157
158 addTraceSample(datablock, PC, CacheRequestType_ST, AccessModeType(0), requestor, indirection_miss);
159}
160
161void AddressProfiler::profileGetS(const Address& datablock, const Address& PC, const Set& owner, const Set& sharers, NodeID requestor)
162{
163 Set indirection_set;
164 indirection_set.addSet(owner);
165 indirection_set.remove(requestor);
166 int num_indirections = indirection_set.count();
167
168 m_gets_sharing_histogram.add(num_indirections);
169 bool indirection_miss = (num_indirections > 0);
170
171 addTraceSample(datablock, PC, CacheRequestType_LD, AccessModeType(0), requestor, indirection_miss);
172}
173
174void AddressProfiler::addTraceSample(Address data_addr, Address pc_addr, CacheRequestType type, AccessModeType access_mode, NodeID id, bool sharing_miss)
175{
176 if (m_all_instructions) {
177 if (sharing_miss) {
178 m_sharing_miss_counter++;
179 }
180
181 // record data address trace info
182 data_addr.makeLineAddress();
183 lookupTraceForAddress(data_addr, m_dataAccessTrace).update(type, access_mode, id, sharing_miss);
184
185 // record macro data address trace info
186 Address macro_addr(data_addr.maskLowOrderBits(10)); // 6 for datablock, 4 to make it 16x more coarse
187 lookupTraceForAddress(macro_addr, m_macroBlockAccessTrace).update(type, access_mode, id, sharing_miss);
188
189 // record program counter address trace info
190 lookupTraceForAddress(pc_addr, m_programCounterAccessTrace).update(type, access_mode, id, sharing_miss);
191 }
192
193 if (m_all_instructions) {
194 // This code is used if the address profiler is an all-instructions profiler
195 // record program counter address trace info
196 lookupTraceForAddress(pc_addr, m_programCounterAccessTrace).update(type, access_mode, id, sharing_miss);
197 }
198}
199
200void AddressProfiler::profileRetry(const Address& data_addr, AccessType type, int count)
201{
202 m_retryProfileHisto.add(count);
203 if (type == AccessType_Read) {
204 m_retryProfileHistoRead.add(count);
205 } else {
206 m_retryProfileHistoWrite.add(count);
207 }
208 if (count > 1) {
209 lookupTraceForAddress(data_addr, m_retryProfileMap).addSample(count);
210 }
211}
212
213// ***** Normal Functions ******
214
134 out << endl;
135 }
136
137}
138
139void AddressProfiler::clearStats()
140{
141 // Clear the maps
142 m_sharing_miss_counter = 0;
143 m_dataAccessTrace->clear();
144 m_macroBlockAccessTrace->clear();
145 m_programCounterAccessTrace->clear();
146 m_retryProfileMap->clear();
147 m_retryProfileHisto.clear();
148 m_retryProfileHistoRead.clear();
149 m_retryProfileHistoWrite.clear();
150 m_getx_sharing_histogram.clear();
151 m_gets_sharing_histogram.clear();
152}
153
154void AddressProfiler::profileGetX(const Address& datablock, const Address& PC, const Set& owner, const Set& sharers, NodeID requestor)
155{
156 Set indirection_set;
157 indirection_set.addSet(sharers);
158 indirection_set.addSet(owner);
159 indirection_set.remove(requestor);
160 int num_indirections = indirection_set.count();
161
162 m_getx_sharing_histogram.add(num_indirections);
163 bool indirection_miss = (num_indirections > 0);
164
165 addTraceSample(datablock, PC, CacheRequestType_ST, AccessModeType(0), requestor, indirection_miss);
166}
167
168void AddressProfiler::profileGetS(const Address& datablock, const Address& PC, const Set& owner, const Set& sharers, NodeID requestor)
169{
170 Set indirection_set;
171 indirection_set.addSet(owner);
172 indirection_set.remove(requestor);
173 int num_indirections = indirection_set.count();
174
175 m_gets_sharing_histogram.add(num_indirections);
176 bool indirection_miss = (num_indirections > 0);
177
178 addTraceSample(datablock, PC, CacheRequestType_LD, AccessModeType(0), requestor, indirection_miss);
179}
180
181void AddressProfiler::addTraceSample(Address data_addr, Address pc_addr, CacheRequestType type, AccessModeType access_mode, NodeID id, bool sharing_miss)
182{
183 if (m_all_instructions) {
184 if (sharing_miss) {
185 m_sharing_miss_counter++;
186 }
187
188 // record data address trace info
189 data_addr.makeLineAddress();
190 lookupTraceForAddress(data_addr, m_dataAccessTrace).update(type, access_mode, id, sharing_miss);
191
192 // record macro data address trace info
193 Address macro_addr(data_addr.maskLowOrderBits(10)); // 6 for datablock, 4 to make it 16x more coarse
194 lookupTraceForAddress(macro_addr, m_macroBlockAccessTrace).update(type, access_mode, id, sharing_miss);
195
196 // record program counter address trace info
197 lookupTraceForAddress(pc_addr, m_programCounterAccessTrace).update(type, access_mode, id, sharing_miss);
198 }
199
200 if (m_all_instructions) {
201 // This code is used if the address profiler is an all-instructions profiler
202 // record program counter address trace info
203 lookupTraceForAddress(pc_addr, m_programCounterAccessTrace).update(type, access_mode, id, sharing_miss);
204 }
205}
206
207void AddressProfiler::profileRetry(const Address& data_addr, AccessType type, int count)
208{
209 m_retryProfileHisto.add(count);
210 if (type == AccessType_Read) {
211 m_retryProfileHistoRead.add(count);
212 } else {
213 m_retryProfileHistoWrite.add(count);
214 }
215 if (count > 1) {
216 lookupTraceForAddress(data_addr, m_retryProfileMap).addSample(count);
217 }
218}
219
220// ***** Normal Functions ******
221
215static void printSorted(ostream& out, const Map<Address, AccessTraceForAddress>* record_map, string description)
222static void printSorted(ostream& out,
223 int num_of_sequencers,
224 const Map<Address, AccessTraceForAddress>* record_map,
225 string description)
216{
217 const int records_printed = 100;
218
219 uint64 misses = 0;
220 PrioHeap<AccessTraceForAddress*> heap;
221 Vector<Address> keys = record_map->keys();
222 for(int i=0; i<keys.size(); i++){
223 AccessTraceForAddress* record = &(record_map->lookup(keys[i]));
224 misses += record->getTotal();
225 heap.insert(record);
226 }
227
228 out << "Total_entries_" << description << ": " << keys.size() << endl;
229 if (g_system_ptr->getProfiler()->getAllInstructions())
230 out << "Total_Instructions_" << description << ": " << misses << endl;
231 else
232 out << "Total_data_misses_" << description << ": " << misses << endl;
233
234 out << "total | load store atomic | user supervisor | sharing | touched-by" << endl;
235
236 Histogram remaining_records(1, 100);
237 Histogram all_records(1, 100);
238 Histogram remaining_records_log(-1);
239 Histogram all_records_log(-1);
240
241 // Allows us to track how many lines where touched by n processors
242 Vector<int64> m_touched_vec;
243 Vector<int64> m_touched_weighted_vec;
226{
227 const int records_printed = 100;
228
229 uint64 misses = 0;
230 PrioHeap<AccessTraceForAddress*> heap;
231 Vector<Address> keys = record_map->keys();
232 for(int i=0; i<keys.size(); i++){
233 AccessTraceForAddress* record = &(record_map->lookup(keys[i]));
234 misses += record->getTotal();
235 heap.insert(record);
236 }
237
238 out << "Total_entries_" << description << ": " << keys.size() << endl;
239 if (g_system_ptr->getProfiler()->getAllInstructions())
240 out << "Total_Instructions_" << description << ": " << misses << endl;
241 else
242 out << "Total_data_misses_" << description << ": " << misses << endl;
243
244 out << "total | load store atomic | user supervisor | sharing | touched-by" << endl;
245
246 Histogram remaining_records(1, 100);
247 Histogram all_records(1, 100);
248 Histogram remaining_records_log(-1);
249 Histogram all_records_log(-1);
250
251 // Allows us to track how many lines where touched by n processors
252 Vector<int64> m_touched_vec;
253 Vector<int64> m_touched_weighted_vec;
244 m_touched_vec.setSize(RubySystem::getNumberOfSequencers()+1);
245 m_touched_weighted_vec.setSize(RubySystem::getNumberOfSequencers()+1);
254 m_touched_vec.setSize(num_of_sequencers+1);
255 m_touched_weighted_vec.setSize(num_of_sequencers+1);
246 for (int i=0; i<m_touched_vec.size(); i++) {
247 m_touched_vec[i] = 0;
248 m_touched_weighted_vec[i] = 0;
249 }
250
251 int counter = 0;
252 while((heap.size() > 0) && (counter < records_printed)) {
253 AccessTraceForAddress* record = heap.extractMin();
254 double percent = 100.0*(record->getTotal()/double(misses));
255 out << description << " | " << percent << " % " << *record << endl;
256 all_records.add(record->getTotal());
257 all_records_log.add(record->getTotal());
258 counter++;
259 m_touched_vec[record->getTouchedBy()]++;
260 m_touched_weighted_vec[record->getTouchedBy()] += record->getTotal();
261 }
262
263 while(heap.size() > 0) {
264 AccessTraceForAddress* record = heap.extractMin();
265 all_records.add(record->getTotal());
266 remaining_records.add(record->getTotal());
267 all_records_log.add(record->getTotal());
268 remaining_records_log.add(record->getTotal());
269 m_touched_vec[record->getTouchedBy()]++;
270 m_touched_weighted_vec[record->getTouchedBy()] += record->getTotal();
271 }
272 out << endl;
273 out << "all_records_" << description << ": " << all_records << endl;
274 out << "all_records_log_" << description << ": " << all_records_log << endl;
275 out << "remaining_records_" << description << ": " << remaining_records << endl;
276 out << "remaining_records_log_" << description << ": " << remaining_records_log << endl;
277 out << "touched_by_" << description << ": " << m_touched_vec << endl;
278 out << "touched_by_weighted_" << description << ": " << m_touched_weighted_vec << endl;
279 out << endl;
280}
281
282static AccessTraceForAddress& lookupTraceForAddress(const Address& addr, Map<Address, AccessTraceForAddress>* record_map)
283{
284 if(record_map->exist(addr) == false){
285 record_map->add(addr, AccessTraceForAddress(addr));
286 }
287 return record_map->lookup(addr);
288}
256 for (int i=0; i<m_touched_vec.size(); i++) {
257 m_touched_vec[i] = 0;
258 m_touched_weighted_vec[i] = 0;
259 }
260
261 int counter = 0;
262 while((heap.size() > 0) && (counter < records_printed)) {
263 AccessTraceForAddress* record = heap.extractMin();
264 double percent = 100.0*(record->getTotal()/double(misses));
265 out << description << " | " << percent << " % " << *record << endl;
266 all_records.add(record->getTotal());
267 all_records_log.add(record->getTotal());
268 counter++;
269 m_touched_vec[record->getTouchedBy()]++;
270 m_touched_weighted_vec[record->getTouchedBy()] += record->getTotal();
271 }
272
273 while(heap.size() > 0) {
274 AccessTraceForAddress* record = heap.extractMin();
275 all_records.add(record->getTotal());
276 remaining_records.add(record->getTotal());
277 all_records_log.add(record->getTotal());
278 remaining_records_log.add(record->getTotal());
279 m_touched_vec[record->getTouchedBy()]++;
280 m_touched_weighted_vec[record->getTouchedBy()] += record->getTotal();
281 }
282 out << endl;
283 out << "all_records_" << description << ": " << all_records << endl;
284 out << "all_records_log_" << description << ": " << all_records_log << endl;
285 out << "remaining_records_" << description << ": " << remaining_records << endl;
286 out << "remaining_records_log_" << description << ": " << remaining_records_log << endl;
287 out << "touched_by_" << description << ": " << m_touched_vec << endl;
288 out << "touched_by_weighted_" << description << ": " << m_touched_weighted_vec << endl;
289 out << endl;
290}
291
292static AccessTraceForAddress& lookupTraceForAddress(const Address& addr, Map<Address, AccessTraceForAddress>* record_map)
293{
294 if(record_map->exist(addr) == false){
295 record_map->add(addr, AccessTraceForAddress(addr));
296 }
297 return record_map->lookup(addr);
298}