| /* |
| * Copyright (c) 2017 Advanced Micro Devices, Inc. |
| * All rights reserved. |
| * |
| * For use for simulation and test purposes only |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions are met: |
| * |
| * 1. Redistributions of source code must retain the above copyright notice, |
| * this list of conditions and the following disclaimer. |
| * |
| * 2. Redistributions in binary form must reproduce the above copyright notice, |
| * this list of conditions and the following disclaimer in the documentation |
| * and/or other materials provided with the distribution. |
| * |
| * 3. Neither the name of the copyright holder nor the names of its |
| * contributors may be used to endorse or promote products derived from this |
| * software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
| * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
| * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
| * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
| * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| * POSSIBILITY OF SUCH DAMAGE. |
| * |
| * Authors: Tuan Ta |
| */ |
| |
| #include "cpu/testers/gpu_ruby_test/AddressManager.hh" |
| |
| #include <algorithm> |
| |
| #include "base/intmath.hh" |
| #include "base/random.hh" |
| #include "base/trace.hh" |
| |
| const int AddressManager::INVALID_VALUE = -1; |
| const int AddressManager::INVALID_LOCATION = -1; |
| |
| AddressManager::AddressManager(int n_atomic_locs, int n_normal_locs_per_atomic) |
| : numAtomicLocs(n_atomic_locs), |
| numLocsPerAtomic(n_normal_locs_per_atomic) |
| { |
| assert(numAtomicLocs > 0 && numLocsPerAtomic > 0); |
| numNormalLocs = numAtomicLocs * numLocsPerAtomic; |
| |
| // generate random address map |
| randAddressMap.resize(numAtomicLocs + numNormalLocs); |
| for (Location i = 0; i < numAtomicLocs + numNormalLocs; ++i) { |
| // all addresses are sizeof(Value) (i.e., 4-byte) aligned |
| randAddressMap[i] = (Addr)((i + 128) << floorLog2(sizeof(Value))); |
| } |
| |
| // randomly shuffle randAddressMap |
| std::random_shuffle(randAddressMap.begin(), randAddressMap.end()); |
| |
| // initialize atomic locations |
| // first and last normal location per atomic location |
| Location first, last; |
| for (Location atomic_loc = 0; atomic_loc < numAtomicLocs; ++atomic_loc) { |
| first = numAtomicLocs + numLocsPerAtomic * atomic_loc; |
| last = first + numLocsPerAtomic - 1; |
| atomicStructs.push_back(new AtomicStruct(atomic_loc, first, last)); |
| } |
| |
| // initialize log table |
| for (Location loc = 0; loc < numAtomicLocs + numNormalLocs; ++loc) { |
| logTable.push_back(new LastWriter()); |
| } |
| } |
| |
| AddressManager::~AddressManager() |
| { |
| for (AtomicStruct* atomic_struct : atomicStructs) |
| delete atomic_struct; |
| for (LastWriter* lw : logTable) |
| delete lw; |
| } |
| |
| Addr |
| AddressManager::getAddress(Location loc) |
| { |
| assert(loc < numAtomicLocs + numNormalLocs && loc >= 0); |
| return randAddressMap[loc]; |
| } |
| |
| AddressManager::Location |
| AddressManager::getAtomicLoc() |
| { |
| Location ret_atomic_loc = random() % numAtomicLocs; |
| atomicStructs[ret_atomic_loc]->startLocSelection(); |
| return ret_atomic_loc; |
| } |
| |
| AddressManager::Location |
| AddressManager::getLoadLoc(Location atomic_loc) |
| { |
| assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs); |
| return atomicStructs[atomic_loc]->getLoadLoc(); |
| } |
| |
| AddressManager::Location |
| AddressManager::getStoreLoc(Location atomic_loc) |
| { |
| assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs); |
| return atomicStructs[atomic_loc]->getStoreLoc(); |
| } |
| |
| void |
| AddressManager::finishLocSelection(Location atomic_loc) |
| { |
| assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs); |
| atomicStructs[atomic_loc]->endLocSelection(); |
| } |
| |
| void |
| AddressManager::releaseLocation(Location atomic_loc, Location loc) |
| { |
| assert(atomic_loc >= 0 && atomic_loc < numAtomicLocs); |
| atomicStructs[atomic_loc]->releaseLoc(loc); |
| } |
| |
| std::string |
| AddressManager::printLastWriter(Location loc) const |
| { |
| return logTable[loc]->print(); |
| } |
| |
| // ------------------- AtomicStruct -------------------------- |
| AddressManager::AtomicStruct::AtomicStruct(Location atomic_loc, |
| Location loc_begin, |
| Location loc_end) |
| { |
| // the location range must have at least 1 location |
| assert(loc_begin <= loc_end); |
| |
| atomicLoc = atomic_loc; |
| arraySize = loc_end - loc_begin + 1; |
| locationBase = loc_begin; |
| |
| // allocate an array of arrray_size |
| locArray = new Location[arraySize]; |
| |
| // initialize locArray & locProps |
| Location loc; |
| for (int offset = 0; offset < arraySize; ++offset) { |
| loc = locationBase + offset; |
| locArray[offset] = loc; |
| locProps.push_back(LocProperty(offset, 0)); |
| } |
| |
| // region (1) and (3) are initially empty |
| firstMark = 0; |
| secondMark = arraySize; |
| // no request made at this location so far |
| requestCount = 0; |
| } |
| |
| AddressManager::AtomicStruct::~AtomicStruct() |
| { |
| delete[] locArray; |
| } |
| |
| void |
| AddressManager::AtomicStruct::startLocSelection() |
| { |
| assert(firstMark >= 0); |
| assert(firstMark <= secondMark); |
| assert(secondMark <= arraySize); |
| // make sure loadStoreMap has been cleared |
| assert(loadStoreMap.empty()); |
| |
| // this atomic location is picked for Atomic_ACQ |
| // and Atomic_REL in an episode |
| requestCount += 2; |
| // add two expected values in expectedValues set |
| expectedValues.insert(requestCount - 1); |
| expectedValues.insert(requestCount - 2); |
| } |
| |
| AddressManager::Location |
| AddressManager::AtomicStruct::getLoadLoc() |
| { |
| assert(firstMark >= 0); |
| assert(firstMark <= secondMark); |
| assert(secondMark <= arraySize); |
| |
| if (firstMark == arraySize) { |
| // no location can be picked for a LD now, so return an empty location |
| return INVALID_LOCATION; |
| } else { |
| // we can pick any location btw |
| // locArray [firstMark : arraySize-1] |
| int range_size = arraySize - firstMark; |
| Location ret_loc = locArray[firstMark + random() % range_size]; |
| |
| // update loadStoreMap |
| LdStMap::iterator it = loadStoreMap.find(ret_loc); |
| |
| if (it == loadStoreMap.end()) { |
| // insert a new entry to the map b/c the entry is not there yet |
| // to mark this location has been picked for a LD |
| loadStoreMap.insert(std::pair<Location, LdStBits> |
| (ret_loc, LdStBits(true,false))); |
| } else { |
| // otherwise, just update the LD bit |
| (it->second).first = true; |
| } |
| |
| return ret_loc; |
| } |
| } |
| |
| AddressManager::Location |
| AddressManager::AtomicStruct::getStoreLoc() |
| { |
| assert(firstMark >= 0); |
| assert(firstMark <= secondMark); |
| assert(secondMark <= arraySize); |
| |
| if (firstMark == secondMark) { |
| // no location can be picked for a ST now, return an invalid location |
| return INVALID_LOCATION; |
| } else { |
| // we can pick any location btw [firstMark : secondMark-1] |
| int range_size = secondMark - firstMark; |
| Location ret_loc = locArray[firstMark + random() % range_size]; |
| |
| // update loadStoreMap |
| LdStMap::iterator it = loadStoreMap.find(ret_loc); |
| |
| if (it == loadStoreMap.end()) { |
| // insert a new entry to the map b/c the entry is not there yet |
| // to mark this location has been picked for a ST |
| loadStoreMap.insert(std::pair<Location, LdStBits> |
| (ret_loc, LdStBits(false,true))); |
| } else { |
| // otherwise, just update the ST bit |
| (it->second).second = true; |
| } |
| |
| return ret_loc; |
| } |
| } |
| |
| // for each entry in loadStoreMap, |
| // if <LD_bit, ST_bit> == <1,0> |
| // - if the location is in (2), then move it to (3) |
| // - if the location is in (3), no move |
| // - otherwise, throw an error |
| // if <LD_bit, ST_bit> == <0,1> or <1,1> |
| // - move it from (2) to (1) |
| void |
| AddressManager::AtomicStruct::endLocSelection() |
| { |
| assert(firstMark >= 0); |
| assert(firstMark <= secondMark); |
| assert(secondMark <= arraySize); |
| |
| for (auto& it : loadStoreMap) { |
| Location loc = it.first; |
| LdStBits p = it.second; |
| |
| assert(loc >= locationBase && loc < locationBase + arraySize); |
| LocProperty& loc_prop = locProps[loc - locationBase]; |
| |
| if (p.first && !p.second) { |
| // this location has been picked for LD(s) but not ST |
| // it must be in either region (2) or (3) |
| assert(inSecondRegion(loc_prop.first) || |
| inThirdRegion(loc_prop.first)); |
| |
| if (inSecondRegion(loc_prop.first)) { |
| // there is no owner of this location yet |
| assert(loc_prop.second == 0); |
| |
| // pick the last location in (2) to swap |
| Location swapped_loc = locArray[secondMark - 1]; |
| LocProperty& swapped_loc_prop = |
| locProps[swapped_loc - locationBase]; |
| |
| // swap loc and swapped_loc |
| swap(loc_prop, swapped_loc_prop); |
| |
| // then, expand (3) |
| secondMark--; |
| } |
| |
| // increment the location's number of owners |
| loc_prop.second++; |
| } else if (p.second) { |
| // this location has been picked for ST(s) and/or LD(s) |
| // it must be in region (2) |
| assert(inSecondRegion(loc_prop.first) && loc_prop.second == 0); |
| |
| // pick the first location in (2) to swap |
| Location swapped_loc = locArray[firstMark]; |
| LocProperty& swapped_loc_prop = |
| locProps[swapped_loc - locationBase]; |
| |
| // swap loc and swapped_loc |
| swap(loc_prop, swapped_loc_prop); |
| |
| // then, expand (1) |
| firstMark++; |
| |
| // increment the location's number of owners |
| loc_prop.second++; |
| } else { |
| panic("Location in loadStoreMap but wasn't picked " |
| "in any action\n"); |
| } |
| } |
| |
| // clear the ld_st_map |
| loadStoreMap.clear(); |
| } |
| |
| void |
| AddressManager::AtomicStruct::releaseLoc(Location loc) |
| { |
| assert(loc >= locationBase && loc < locationBase + arraySize); |
| |
| LocProperty& loc_prop = locProps[loc - locationBase]; |
| |
| if (inFirstRegion(loc_prop.first)) { |
| // this location must have exactly 1 owner |
| assert(loc_prop.second == 1); |
| |
| // pick the last location in region 1 to swap |
| Location swapped_loc = locArray[firstMark - 1]; |
| LocProperty& swapped_loc_prop = locProps[swapped_loc - locationBase]; |
| |
| // swap loc and swapped_loc |
| swap(loc_prop, swapped_loc_prop); |
| |
| // then shrink (1) |
| firstMark--; |
| |
| // reset the location's number of owners |
| loc_prop.second = 0; |
| } else if (inThirdRegion(loc_prop.first)) { |
| // this location must have at least 1 owner |
| assert(loc_prop.second >= 1); |
| |
| if (loc_prop.second == 1) { |
| // pick the first location in region 3 to swap |
| Location swapped_loc = locArray[secondMark]; |
| LocProperty& swapped_loc_prop = |
| locProps[swapped_loc - locationBase]; |
| |
| // swap loc and swapped_loc |
| swap(loc_prop, swapped_loc_prop); |
| |
| // then shrink (3) |
| secondMark++; |
| } |
| // decrement the loc's number of owners |
| loc_prop.second--; |
| } else { |
| // some one else must already reset this counter |
| assert(inSecondRegion(loc_prop.first) && loc_prop.second == 0); |
| } |
| } |
| |
| bool |
| AddressManager::AtomicStruct::isExpectedValue(Value val) |
| { |
| ExpectedValueSet::iterator it = expectedValues.find(val); |
| |
| if (it == expectedValues.end()) { |
| return false; |
| } |
| |
| // erase this value b/c it's done |
| expectedValues.erase(it); |
| |
| return true; |
| } |
| |
| void |
| AddressManager::AtomicStruct::swap(LocProperty& prop_1, LocProperty& prop_2) |
| { |
| int new_idx_1 = prop_2.first; |
| int new_idx_2 = prop_1.first; |
| |
| // swap the two locations in locArray |
| Location tmp = locArray[prop_1.first]; |
| locArray[prop_1.first] = locArray[prop_2.first]; |
| locArray[prop_2.first] = tmp; |
| |
| // update their new indices |
| prop_1.first = new_idx_1; |
| prop_2.first = new_idx_2; |
| } |
| |
| // ------------------ log table --------------------- |
| void |
| AddressManager::updateLogTable(Location loc, int thread_id, int episode_id, |
| Value new_value, Tick cur_tick, int cu_id) |
| { |
| assert(loc >= 0 && loc < numAtomicLocs + numNormalLocs); |
| logTable[loc]->update(thread_id, cu_id, episode_id, new_value, cur_tick); |
| } |
| |
| AddressManager::Value |
| AddressManager::getLoggedValue(Location loc) const |
| { |
| assert(loc >= 0 && loc < numAtomicLocs + numNormalLocs); |
| return logTable[loc]->getLastStoredValue(); |
| } |
| |
| bool |
| AddressManager::validateAtomicResp(Location loc, Value ret_val) |
| { |
| assert(loc >= 0 && loc < numAtomicLocs); |
| return atomicStructs[loc]->isExpectedValue(ret_val); |
| } |