MMU description » History » Revision 84
Revision 83 (Alexander Kamkin, 12/02/2014 06:57 AM) → Revision 84/132 (Alexander Kamkin, 12/02/2014 07:29 AM)
h1. MMU Description
_~By Alexander Kamkin and Taya Sergeeva~_
*UNDER CONSTRUCTION*
{{toc}}
A _memory management unit_ (_MMU_) is known to be one of the most complex and error-prone components of a modern microprocessor. MicroTESK has a special subsystem, called _MMU subsystem_, intended for (1) specifying memory devices and (2) deriving testing knowledge from such specifications. The subsystem provides unified facilities for describing memory buffers (like _L1_ and _L2 caches_, _translation look-aside buffers_ (_TLBs_), etc.) as well as a means for connecting several buffers into a memory hierarchy.
h2. Grammar
<pre>
startRule
: bufferOrAddress*
;
bufferOrAddress
: address
| buffer
;
</pre>
h2. Address Description
A buffer is accessed by an _address_, which is typically a _bit vector_ of a fixed length (width). Different buffers are allowed to have a common address space (e.g., L1 and L2 are usually both addressed by physical addresses). However, in general case, each buffer has its own domain.
An address space is described using a keyword @address@. The description can specify two parameters: @width@ (obligatory) and @format@ (optional).
h3. Grammar
<pre>
address
: ''address'' ID ''{''
(addressParameter '';'')*
''}''
;
addressParameter
: width
| format
;
</pre>
h3. Address Width (width)
The @width@ parameter specifies the address _width_. width. The parameter is obligatory; its value should be non-negative (zero-length addresses are permitted).
h4. Grammar
<pre>
width
: ''width'' ''='' expr
;
</pre>
h3. Address Format (format)
The @format@ parameter specifies the address _format_ format (a number of named fields). The parameter is optional. By default, the address is unstructured (no fields are specified).
A field has three attributes: a name, a width and, optionally, an initial value.
h4. Grammar
<pre>
format
: ''format'' ''='' ''(''
field ('','' field)*
'')''
;
field
: ID '':'' expr (''='' expr)?
;
</pre>
h2. Examples
<pre>
// The singleton.
address Void {
// The address width is zero (this is admissible for single-item buffers).
width = 0;
}
</pre>
<pre>
// An unstructured 64-bit virtual addresses.
address VA {
// The address width.
width = 64;
}
</pre>
<pre>
// A stuctured 40-bit physical addresses.
address PA {
// The address width.
width = 40;
// The address format.
format = (
TAG : 24, // The tag (the <35..12> address bits).
INDEX : 7, // The set index (the <11..5> address bits).
LOCAL : 5, // The byte position (the <0..4> address bits).
); (tag:24, l1Index:7, dwPosition:2, bytePosition:3);
}
</pre>
The code above defines three address spaces: (1) a singleton @Void@; (2) a space @VA@ consisting of 64-bit addresses (_virtual addresses_) and (3) a space @PA@ consisting of 40-bit addresses (_physical addresses_), each being divided into for fields: @tag@ (24 bits), @l1Index@ (7 bits), @dwPosition@ (2 bits) and @bytePosition@ (3 bits).
h2. Buffer Description
A buffer is described using a keyword @buffer@. The description specifies a set of parameters, including @ways@, @sets@, @format@, @index@, @match@ and @policy@. All of the parameters except @index@ (if @sets = 1@) and @policy@ are obligatory.
h3. Grammar
<pre>
buffer
: ''buffer'' bufferTypeID ''{''
(bufferParameter '';'')*
''}''
;
bufferParameter
: ways
| sets
| format
| index
| match
| policy
;
</pre>
h3. Buffer Associativity (ways)
The @ways@ parameter specifies the buffer _associativity_ associativity (the number of lines in a set). The parameter is obligatory; its value should be positive.
h4. Grammar
<pre>
ways
: ''ways'' ''='' expr
;
</pre>
h3. Buffer Length (sets)
The @sets@ parameter specifies the buffer _length_ length (the number of sets a cache). The parameter is obligatory; its value should be positive.
h4. Grammar
<pre>
sets
: ''sets'' ''='' expr
;
</pre>
h3. Buffer Line Format (format)
The @format@ parameter specifies the buffer _line format_ line format (a number of named fields). The parameter is optional. By default, the buffer line is unstructured (no fields are specified).
A field has three attributes: a name, a width and, optionally, an initial value.
h4. Grammar
<pre>
format
: ''format'' ''='' ''('' field ('','' field)* '')''
;
field
: fieldID '':'' expr (''='' expr)?
;
</pre>
h3. Buffer Index Function (index)
The @index@ parameter specifies the _address-to-index function_, index calculation function, which maps an address into the set index. The function may be omitted if the number of sets is @1@.
h4. Grammar
<pre>
index
: ''index'' ''('' addressTypeID addressArgID '')'' ''='' expr
;
</pre>
h3. Buffer Match Predicate (match)
The @match@ parameter specifies the _address-line line match predicate_, predicate, which checks if an address matches a line. The parameter is obligatory.
h4. Grammar
<pre>
index
: ''match'' ''('' addressTypeID addressArgID '')'' ''='' expr
;
</pre>
h3. Buffer Data Replacement Policy (policy)
The @policy@ parameters specifies the _data replacement_ (_eviction_) _policy_. data replacement (eviction) policy. The parameter is optional. The list of supported policies includes: @RANDOM@, @FIFO@, @PLRU@ @random@, @fifo@, @plru@ and @LRU@. @lru@.
h4. Grammar
<pre>
policy
: ''policy'' ''='' policyID
;
</pre>
h3. Examples
Let as consider a simple buffer which has only 2 attributes, such as the associativity, *associativity*, i.e. the set''s size, and the number of sets in the buffer, *sets*.
<pre>
// A 4-way set associative cache (L1).
buffer L1 TLB {
// The cache associativity.
ways = 4; 8;
// sets = 64;
}
</pre>
The example above describes translation lookaside buffer (_TLB_), which has an associativity being equal to 8, (i.e. the number of sets.
sets = 128;
// The lines in one set in this TLB buffer is equal to 8), and has the number of lines being equal to 64.
Each *line* of the buffer can be described optionally by _tag_ and _data_ parameters.
For example,
<pre>
line format.
format = (
VAL : 1 (tag:22, data:1024);
</pre>
describes lines of the cache, each of them containing a 22-bit tag and 1024-bit data.
In a MMU buffer also can have the *index* computing function. When accessing data, the cache determines a set by calculating a x-bit index. For example,
<pre>
index(addr:PA) = 0, // addr<14..13>;
</pre>
The validity flag (by default, cache calculates a 2-bit index. _index_ returns the initial and the final points of the field kept in bytes.
Each device stores some data which can be accessed (read from or written into) by their address. If a device contains a line with a given address, this situation is invalid).
TAG : 24, // The tag (the <35..12> called a ''hit''; the opposite situation referes to as a ''miss''. If a ''miss'' occurs, the device usually displaces one of the set''s line with the line associated with the address bits).
ROW : 256 // given. The data (4 double words).
);
// The address-to-index function.
index(PA addr) predicate which determines if there is a ''miss'' or ''hit'' situation is called *match*. There is the example below:
<pre>
line = addr<11..5>;
// The address-line predicate.
match(PA addr) (tag:22, data:1024);
match(addr:VA) = addr<35..12> line.tag == TAG;
// addr<14..1>;
</pre>
If the set contains a line with the tag equal to the 22 upper bits of the physical address, this is a ''hit''. _match_ returns ''true'' if there is a ''hit'' in the line, and returns ''false'' otherwise.
The strategy which will be used for the lines displacement is specified by *policy*.
<pre>
policy = LRU;
</pre>
Example above sets the strategy of data replacement policy.
to be _Last_ _Recently_ _Used_ policy, i.e. if the ''miss'' occured, the cache displaces the least-recently-used line of the set.
There is the example below, describing a real ''lower-level'' cache L1:
<pre>
buffer L1
{
associativity = 4;
sets = 128;
line = (tag:30, data:256);
index(addr:PA) = addr<9..8>;
match(addr:PA) = line.tag == addr<39..10>;
policy = LRU; lru;
}
</pre>
_Description of each constructor_ in the buffer example is below: