gem5 v24.1.0.1
Loading...
Searching...
No Matches
address_manager.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2017-2020 Advanced Micro Devices, Inc.
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 met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its
16 * contributors may be used to endorse or promote products derived from this
17 * software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
33
34#include <algorithm>
35#include <climits>
36
37#include "base/intmath.hh"
38#include "base/logging.hh"
39#include "base/trace.hh"
40
41namespace gem5
42{
43
46
47AddressManager::AddressManager(int n_atomic_locs, int n_normal_locs_per_atomic)
48 : numAtomicLocs(n_atomic_locs),
49 numLocsPerAtomic(n_normal_locs_per_atomic)
50{
51 assert(numAtomicLocs > 0 && numLocsPerAtomic > 0);
53
54 // generate random address map
56 for (Location i = 0; i < numAtomicLocs + numNormalLocs; ++i) {
57 // all addresses are sizeof(Value) (i.e., 4-byte) aligned
58 randAddressMap[i] = (Addr)((i + 128) << floorLog2(sizeof(Value)));
59 }
60
61 // randomly shuffle randAddressMap. The seed is determined by the rng
62 // internal to the object to avoid interactions with other components
63 std::shuffle(
64 randAddressMap.begin(),
65 randAddressMap.end(),
66
67 // Note: This RNG has an upper bound of UINT_MAX - 1. This will fail
68 // if the number of locations exceeds this value. Please do not
69 // change this.
70 std::default_random_engine(rng->random<unsigned>(0,UINT_MAX - 1))
71 );
72
73 // initialize atomic locations
74 // first and last normal location per atomic location
75 Location first, last;
76 for (Location atomic_loc = 0; atomic_loc < numAtomicLocs; ++atomic_loc) {
77 first = numAtomicLocs + numLocsPerAtomic * atomic_loc;
78 last = first + numLocsPerAtomic - 1;
79 atomicStructs.push_back(new AtomicStruct(atomic_loc, first, last));
80 }
81
82 // initialize log table
83 for (Location loc = 0; loc < numAtomicLocs + numNormalLocs; ++loc) {
84 logTable.push_back(new LastWriter());
85 }
86}
87
89{
90 for (AtomicStruct* atomic_struct : atomicStructs)
91 delete atomic_struct;
92 for (LastWriter* lw : logTable)
93 delete lw;
94}
95
96Addr
98{
99 assert(loc < numAtomicLocs + numNormalLocs && loc >= 0);
100 return randAddressMap[loc];
101}
102
105{
106 Location ret_atomic_loc = \
107 rng->random<unsigned long>() % numAtomicLocs;
108 atomicStructs[ret_atomic_loc]->startLocSelection();
109 return ret_atomic_loc;
110}
111
114{
115 assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs);
116 return atomicStructs[atomic_loc]->getLoadLoc();
117}
118
121{
122 assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs);
123 return atomicStructs[atomic_loc]->getStoreLoc();
124}
125
126void
128{
129 assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs);
130 atomicStructs[atomic_loc]->endLocSelection();
131}
132
133void
135{
136 assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs);
137 atomicStructs[atomic_loc]->releaseLoc(loc);
138}
139
140std::string
142{
143 return logTable[loc]->print();
144}
145
146// ------------------- AtomicStruct --------------------------
148 Location loc_begin,
149 Location loc_end)
150{
151 // the location range must have at least 1 location
152 assert(loc_begin <= loc_end);
153
154 atomicLoc = atomic_loc;
155 arraySize = loc_end - loc_begin + 1;
156 locationBase = loc_begin;
157
158 // allocate an array of arrray_size
160
161 // initialize locArray & locProps
162 Location loc;
163 for (int offset = 0; offset < arraySize; ++offset) {
164 loc = locationBase + offset;
165 locArray[offset] = loc;
166 locProps.push_back(LocProperty(offset, 0));
167 }
168
169 // region (1) and (3) are initially empty
170 firstMark = 0;
172 // no request made at this location so far
173 requestCount = 0;
174}
175
177{
178 delete[] locArray;
179}
180
181void
183{
184 assert(firstMark >= 0);
185 assert(firstMark <= secondMark);
186 assert(secondMark <= arraySize);
187 // make sure loadStoreMap has been cleared
188 assert(loadStoreMap.empty());
189
190 // this atomic location is picked for Atomic_ACQ
191 // and Atomic_REL in an episode
192 requestCount += 2;
193 // add two expected values in expectedValues set
194 expectedValues.insert(requestCount - 1);
195 expectedValues.insert(requestCount - 2);
196}
197
200{
201 assert(firstMark >= 0);
202 assert(firstMark <= secondMark);
203 assert(secondMark <= arraySize);
204
205 if (firstMark == arraySize) {
206 // no location can be picked for a LD now, so return an empty location
207 return INVALID_LOCATION;
208 } else {
209 // we can pick any location btw
210 // locArray [firstMark : arraySize-1]
211 int range_size = arraySize - firstMark;
212 Location ret_loc = locArray[
213 firstMark + rng->random<unsigned int>() % range_size
214 ];
215
216 // update loadStoreMap
217 LdStMap::iterator it = loadStoreMap.find(ret_loc);
218
219 if (it == loadStoreMap.end()) {
220 // insert a new entry to the map b/c the entry is not there yet
221 // to mark this location has been picked for a LD
222 loadStoreMap.insert(std::pair<Location, LdStBits>
223 (ret_loc, LdStBits(true,false)));
224 } else {
225 // otherwise, just update the LD bit
226 (it->second).first = true;
227 }
228
229 return ret_loc;
230 }
231}
232
235{
236 assert(firstMark >= 0);
237 assert(firstMark <= secondMark);
238 assert(secondMark <= arraySize);
239
240 if (firstMark == secondMark) {
241 // no location can be picked for a ST now, return an invalid location
242 return INVALID_LOCATION;
243 } else {
244 // we can pick any location btw [firstMark : secondMark-1]
245 int range_size = secondMark - firstMark;
246 Location ret_loc = locArray[
247 firstMark + rng->random<unsigned int>() % range_size
248 ];
249
250 // update loadStoreMap
251 LdStMap::iterator it = loadStoreMap.find(ret_loc);
252
253 if (it == loadStoreMap.end()) {
254 // insert a new entry to the map b/c the entry is not there yet
255 // to mark this location has been picked for a ST
256 loadStoreMap.insert(std::pair<Location, LdStBits>
257 (ret_loc, LdStBits(false,true)));
258 } else {
259 // otherwise, just update the ST bit
260 (it->second).second = true;
261 }
262
263 return ret_loc;
264 }
265}
266
267// for each entry in loadStoreMap,
268// if <LD_bit, ST_bit> == <1,0>
269// - if the location is in (2), then move it to (3)
270// - if the location is in (3), no move
271// - otherwise, throw an error
272// if <LD_bit, ST_bit> == <0,1> or <1,1>
273// - move it from (2) to (1)
274void
276{
277 assert(firstMark >= 0);
278 assert(firstMark <= secondMark);
279 assert(secondMark <= arraySize);
280
281 for (auto& it : loadStoreMap) {
282 Location loc = it.first;
283 LdStBits p = it.second;
284
285 assert(loc >= locationBase && loc < locationBase + arraySize);
286 LocProperty& loc_prop = locProps[loc - locationBase];
287
288 if (p.first && !p.second) {
289 // this location has been picked for LD(s) but not ST
290 // it must be in either region (2) or (3)
291 assert(inSecondRegion(loc_prop.first) ||
292 inThirdRegion(loc_prop.first));
293
294 if (inSecondRegion(loc_prop.first)) {
295 // there is no owner of this location yet
296 assert(loc_prop.second == 0);
297
298 // pick the last location in (2) to swap
299 Location swapped_loc = locArray[secondMark - 1];
300 LocProperty& swapped_loc_prop =
301 locProps[swapped_loc - locationBase];
302
303 // swap loc and swapped_loc
304 swap(loc_prop, swapped_loc_prop);
305
306 // then, expand (3)
307 secondMark--;
308 }
309
310 // increment the location's number of owners
311 loc_prop.second++;
312 } else if (p.second) {
313 // this location has been picked for ST(s) and/or LD(s)
314 // it must be in region (2)
315 assert(inSecondRegion(loc_prop.first) && loc_prop.second == 0);
316
317 // pick the first location in (2) to swap
318 Location swapped_loc = locArray[firstMark];
319 LocProperty& swapped_loc_prop =
320 locProps[swapped_loc - locationBase];
321
322 // swap loc and swapped_loc
323 swap(loc_prop, swapped_loc_prop);
324
325 // then, expand (1)
326 firstMark++;
327
328 // increment the location's number of owners
329 loc_prop.second++;
330 } else {
331 panic("Location in loadStoreMap but wasn't picked in any"
332 " action\n");
333 }
334 }
335
336 // clear the ld_st_map
337 loadStoreMap.clear();
338}
339
340void
342{
343 assert(loc >= locationBase && loc < locationBase + arraySize);
344
345 LocProperty& loc_prop = locProps[loc - locationBase];
346
347 if (inFirstRegion(loc_prop.first)) {
348 // this location must have exactly 1 owner
349 assert(loc_prop.second == 1);
350
351 // pick the last location in region 1 to swap
352 Location swapped_loc = locArray[firstMark - 1];
353 LocProperty& swapped_loc_prop = locProps[swapped_loc - locationBase];
354
355 // swap loc and swapped_loc
356 swap(loc_prop, swapped_loc_prop);
357
358 // then shrink (1)
359 firstMark--;
360
361 // reset the location's number of owners
362 loc_prop.second = 0;
363 } else if (inThirdRegion(loc_prop.first)) {
364 // this location must have at least 1 owner
365 assert(loc_prop.second >= 1);
366
367 if (loc_prop.second == 1) {
368 // pick the first location in region 3 to swap
369 Location swapped_loc = locArray[secondMark];
370 LocProperty& swapped_loc_prop =
371 locProps[swapped_loc - locationBase];
372
373 // swap loc and swapped_loc
374 swap(loc_prop, swapped_loc_prop);
375
376 // then shrink (3)
377 secondMark++;
378 }
379 // decrement the loc's number of owners
380 loc_prop.second--;
381 } else {
382 // some one else must already reset this counter
383 assert(inSecondRegion(loc_prop.first) && loc_prop.second == 0);
384 }
385}
386
387bool
389{
390 ExpectedValueSet::iterator it = expectedValues.find(val);
391
392 if (it == expectedValues.end()) {
393 std::stringstream exp_val_ss;
394 for (auto& val : expectedValues) {
395 exp_val_ss << " " << val;
396 }
397
398 warn("Expected return values are:\n\t%s\n", exp_val_ss.str());
399
400 return false;
401 }
402
403 // erase this value b/c it's done
404 expectedValues.erase(it);
405
406 return true;
407}
408
409void
411{
412 int new_idx_1 = prop_2.first;
413 int new_idx_2 = prop_1.first;
414
415 // swap the two locations in locArray
416 Location tmp = locArray[prop_1.first];
417 locArray[prop_1.first] = locArray[prop_2.first];
418 locArray[prop_2.first] = tmp;
419
420 // update their new indices
421 prop_1.first = new_idx_1;
422 prop_2.first = new_idx_2;
423}
424
425// ------------------ log table ---------------------
426void
427AddressManager::updateLogTable(Location loc, int thread_id, int episode_id,
428 Value new_value, Tick cur_tick, int cu_id)
429{
430 assert(loc >= 0 && loc < numAtomicLocs + numNormalLocs);
431 logTable[loc]->update(thread_id, cu_id, episode_id, new_value, cur_tick);
432}
433
436{
437 assert(loc >= 0 && loc < numAtomicLocs + numNormalLocs);
438 return logTable[loc]->getLastStoredValue();
439}
440
441bool
443{
444 assert(loc >= 0 && loc < numAtomicLocs);
445 return atomicStructs[loc]->isExpectedValue(ret_val);
446}
447
448} // namespace gem5
AtomicStruct(Location atom_loc, Location loc_begin, Location loc_end)
void swap(LocProperty &prop_1, LocProperty &prop_2)
Addr getAddress(Location loc)
AtomicStructTable atomicStructs
Location getStoreLoc(Location atomic_loc)
Value getLoggedValue(Location loc) const
AddressManager(int n_atomic_locs, int numNormalLocsPerAtomic)
std::string printLastWriter(Location loc) const
void updateLogTable(Location loc, int threadId, int episodeId, Value new_value, Tick curTick, int cuId=-1)
Random::RandomPtr rng
static const int INVALID_LOCATION
Location getLoadLoc(Location atomic_loc)
static const int INVALID_VALUE
void finishLocSelection(Location atomic_loc)
void releaseLocation(Location atomic_loc, Location loc)
bool validateAtomicResp(Location loc, Value ret_val)
STL pair class.
Definition stl.hh:58
static constexpr std::enable_if_t< std::is_integral_v< T >, int > floorLog2(T x)
Definition intmath.hh:59
#define panic(...)
This implements a cprintf based panic() function.
Definition logging.hh:188
#define warn(...)
Definition logging.hh:256
Bitfield< 7 > i
Definition misc_types.hh:67
Bitfield< 23, 0 > offset
Definition types.hh:144
Bitfield< 0 > p
Bitfield< 63 > val
Definition misc.hh:804
Copyright (c) 2024 Arm Limited All rights reserved.
Definition binary32.hh:36
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition types.hh:147
uint64_t Tick
Tick count type.
Definition types.hh:58

Generated on Mon Jan 13 2025 04:28:32 for gem5 by doxygen 1.9.8