TLBModel
This is the TLB model that works using ILOG. The level of abstraction provided to the user is of a higher degree. The TLB model has two classes, namely, tlb_context and the tlb. The tlb_context class is the one the user has to instantiate. The tlb_class is used fully by the constraint solver. The model is designed in such a way that, each action/scenario is modeled as a set of constraints, the solution to which, when applied to the TLB shall cause the scenario. Therefore, depending on the action or scenario, the tlb_class would be automatically instantiated and necessary constraints be added to the model. A constraint solver would act on this. The solution hence obtained would be applied on the TLB. In other words, the tlb_context would be modified accordingly as indicated by the solution. For the replacement strategy, an approximate LRU is implemented.
The TLB-2 Model environment
We assume that the TLB can store upto N entries.
1. The tlb_context class
Public Data:
_Miss // Status of a TLB Miss
_OUTPUT_PA // Physical address corresponding to a input Linear Address (if matched)
_LRU_ENTRY // Pointing to the Least Recently Used Entry
_V[N] // Array: Valid bits for each TLB entry
_LA[N] // Array: Linear Address of each TLB Entry
_PA[N] // Array: Physical Address of each TLB Entry
_U[N] // Array: Usage information for each TLB entry. Note that _LRU_ENTRY is the index of the minimum entry in _U[N].
Methods:
constructor()
Initializes the tlb_context with valid bit _V[i] = 0.
print_needs()
Prints the TLB context in a neat formatted way
2. The tlb Class
Public Data:
A Boolean variable Missset to ‘1’ when there is a TLB Miss.
OUTPUT_PA gives the physical address corresponding to the input Linear Address, if matched.
OUTPUT_PA_INDEX gives the index of the matched entry, if matched.
Following arrays of size N
- Linear Address variable LA taking value 0 <= LA <= 2M- 1
- Physical Address variable PA taking value 0 <= PA <= 2M – 1
- Valid variable V taking value 0 <= V <= 1
- Temporary arrays for setting up constraints
Methods
constructor()
Instantiates the TLB class with N records and loads the constraints based on the context such that the TLB entries are same as what is stored in the context. The method also sets up a constraint such that all the valid TLB entries in the TLB should have different Linear Addresses stored in them. This is an invariant property on the key element of any associative memory/Content-Addressable Memory (CAM). Setting up this constraint is a very interesting stuff. The following lines of code achieve the above.
for (IloInt i = 0; i < N; i++)
model.add(_TLB_TMP_ARR4[i] == _V[i]*_LA[i] + (_V[i] - 1)*(i+1));
model.add(IloAllDiff(model.getEnv(),_TLB_TMP_ARR4));
Note that TLB_TMP_ARR4[i], a temporary array stores the Linear Address if _V[i] = 1. So all the TLB_TMP_ARR4 array entries, for which the corresponding _V entries are one, are different. If _V[i] = 0, then we store –(i+1) in _TLB_TMP_ARR4[i]. These are negative numbers and so they are different from the positive valid linear addresses. They are also different from each other. Note that we used –(i+1), because (-0 == +0) and that “0” can be a valid Linear Address.
– FindPhysicalAddress(Addr)
Given a Linear Address Addr, the function outputs the Physical address if the entry exists, else it outputs “-1”. The function addsconstraints in such a way that, it will set the variable _OUTPUT_PA to the PA corresponding to the entry in the TLB that holds the LA = Addr,if such an entry exists. Else, it shall set _Miss = 1and _OUTPUT_PA = 0. The constraints are as follows:
for (i = 0; i < N; i++) {
model.add(_TLB_TMP_ARR[i] == (((_LA[i] == Addr) & (_V[i] == 1))*_PA[i]));
model.add(_TLB_TMP_ARR2[i] == (((_LA[i] == Addr) & (_V[i] ==1))*i));
model.add(_TLB_TMP_ARR3[i] == ((_LA[i] == Addr) & (_V[i] == 1)));
}
model.add(_OUTPUT_PA == IloSum(_TLB_TMP_ARR));
model.add(_OUTPUT_PA_INDEX == (1 - _Miss) * IloSum(_TLB_TMP_ARR2) - _Miss);
model.add(_Miss == (IloSum(_TLB_TMP_ARR3) == 0));
Note that if _LA[i] = Addr, then,TLB_TMP_ARR[i] = _PA[i] else it is 0. Since, all Linearaddresses are different, there shall be at mostone _TLB_TMP_ARR[] entry that is non zero. _OUTPUT_PA is the sum of the N elements in _TLB_TMP_ARR[] that yields the matched Physical address corresponding to the Linear Address, if Addr is present in the TLB, else_OUTPUT_PA is zero. Note that if _Miss is one, then, _OUTPUT_PA is zero. Similarly you can see that_OUTPUT_PA_INDEX is -1, if _Miss is one. Else, it corresponds tothe TLB index storing the Input Linear Address, Addr. This also returns the _OUTPUT_PA_INDEX. Note that everything is modeled as constraints.
-modify_usedInfo(int p)
Update the usage information and the _LRU_ENTRY field in the tlb context. This is called after every access to tlb. Here entry “p” of TLB is accessed.
For all “j”, such that, 0 <= j <= N-1,
TLB.TLB_ENTRY.U[j] = TLB.TLB_ENTRY.U[j]/2;
TLB.TLB_ENTRY.U[p] = TLB.TLB_ENTRY.U[p] + 2K-1 //This is for LRU
If (p == LRU_ENTRY) then the new LRU_ENTRY is the index of the first minimum entry in the _U array got while traversing the _U array in a circular fashion starting from the current _LRU_ENTRY to N and again from 1 to _LRU_ENTRY-1.
- refresh_tlb_context()
This function updates the tlb_context after every access. The values from the solver have to be read into the tlb_context. This function is called at the end of every event.
-load_tlb_context()
This function loads the tlb class with the values of the tlb_context. This is called at the beginning of every event.
-is_full()
Returns the number of valid entries in the TLB. Uses the constraint
model.add(_tmp = IloSum(_V))
which returns the number of valid entries in the TLB.
-a_missing_address()
Returns a integer not equal to any valid linear address stored in the TLB. This is useful for creating a TLB Miss scenario. This uses the constraint
model.add(_tmp != _LA[i]), for all 1 <= i <= N.
-a_hitting_address()
Returns an integer equal to a valid address stored in the TLB. Out of several such Linear addresses which are valid, the function chooses one at random. This is useful for creating a TLB Hit scenario. This uses the constraint
model.add(_tmp == _LA[j]), where j = random value i,
such that 1 <= i <= N and _V[i] = 1.
-not_hitting_specific_line(a)
Generate a TLB Hit that will not hit the TLB entry “a”. This function generates a hit that hits the _LRU_ENTRY, if it is valid, else any random entry other than “a”. This function is useful for creating TLB eviction of a specific entry in the TLB.
model.add(_tmp == _LA[j]), where j = random value i,
such that 1 <= i <= N, _V[i] = 1 and i != a.
3.The Basic Scenario
The following functions help build bigger scenarios using them. The use the methods of the classes mentioned above to perform their respective functionalities.
-action_invalidate_tlb_entry(Addr)
The function invalidates a TLB entry with Addr as the Linear Address
-action_add_physical_address(LAddr,PAddr)
The function adds the Linear and Physical Address pair (LAddr,PAddr) into the TLB, provided LAddr is not already added to the TLB.
-action_find_physical_address(LAddr)
Calls the tlb class function FindPhysicalAddress(LAddr,PAddr);
4.Creating Scenarios
-create_tlb_miss()
Causes a TLB miss using the basic actions described above
-create_tlb_hit()
Causes a TLB hit using the basic actions described above
-create_tlb_eviction()
Fills up the tlb and causes a TLB miss to force an eviction.
-create_tlb_specific_eviction(a)
Creates an eviction on the TLB entry “a”. It fills up the TLB (then only eviction is possible). Then, generate hits to cause the eviction.