MicroTESK

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 Parameter

The @width@ parameter specifies the address width. The parameter is obligatory.

h4. Grammar

<pre>

width

    : ''width'' ''='' expr

    ;

</pre>

h3. Address Format Parameter

The @format@ parameter specifies the address format (a number of named fields). The parameter is optional. By default, the address is unstructured.

h4. Grammar

<pre>

format

    : ''format'' ''='' ''(''

        field ('','' field)*

      '')''

    ;

field

    : ID '':'' expr (''='' expr)?

    ;

</pre>

h2. Examples

<pre>

// The singleton.

address Void {

  width = 0;

}

</pre>

<pre>

// An unstructured 64-bit virtual addresses.

address VA {

  width = 64;

}

</pre>

<pre>

// A stuctured 40-bit physical addresses.

address PA {

  width = 40;

  format = (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'' ID ''{''

        (bufferParameter '';'')*

      ''}''

    ;

bufferParameter

    : ways

    | sets

    | format

    | index

    | match

    | policy

    ;

</pre>

h3. Buffer Associativity (ways)

h4. Grammar

h3. Buffer Size (sets)

h4. Grammar

h3. Buffer Line Format (format)

h4. Grammar

h3. Buffer Index Function (index)

h4. Grammar

h3. Buffer Match Predicate (match)

h3. Buffer Data Replacement Policy (policy)

h4. Grammar

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>

buffer TLB { 

  ways = 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 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 = (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) = addr<14..13>;

</pre>

The 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 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 given. The predicate which determines if there is a ''miss'' or ''hit'' situation is called *match*. There is the example below:

<pre>

line = (tag:22, data:1024);

match(addr:VA) = line.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 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;

}

</pre>

_Description of each constructor_ in the buffer example is below:

h3. buffer

<pre>

  has a name, ''L1'' in our example; it can have names ''L2'' and ''TLB'' also;

  _buffer_ can be described by different parameters, such _associativity_, _sets_, _index_, _match_, _policy_, and so on, which number is infixed;

</pre>

h3.  associativity 

<pre>

  _associativity_ is an associativity of a buffer; it returns the number of lines in a one set;

</pre>

h3.  sets

<pre>

  _sets_ is the number of sets in a given buffer;

</pre>

h3.  line

<pre>

  _line_ is an optional description of line''s fields;

  it designates each line of the cache; 

  _line_ includes its own parameters in the braces: _tag_ and _data_, each of them has an appropriate width of the fields kept in bytes;

  in our example _line_ has only two parameters, but in general case it can include more;

  it contains a 30-bit tag and a 256-bit data;

</pre>

h3.  index

<pre>

   _index_ is the function for index calculation;

   returns the initial and the final points of the field kept in bytes; they are marked in a three-cornered brackets, after _addr_; in our case index has 2 bits;

  _index_ depends on an _address_, which is ''physical'' (PA) in our case; the type of an address is set in the braces after _index_; 

</pre>

h3.  match 

<pre>

  _match_ is a predicate checking whether the line and the address match each other or not;

  it returns ''true'' or ''false'' depending on if the data required is in the given line or not; 

  it returns ''true'' if there is a ''hit'' in the line, and returns ''false'' otherwise; if the set contains a line with the tag equal to the 30 upper bits of the physical address, this is a ''hit''; if the set does not contain the line, this is a ''miss'' situation;

  _match_ description contains the the initial and the final points of the address field in the triangle brackets after _addr_; 

  as _index_ in the round braces _match_ also has the type of the address used; ''PA'' in our case;

</pre>

h3.  policy

<pre>

  _policy_ is the strategy of data displacement; 

  sets a policy which will be applied to our buffer, ''lru'' (Least Recently Used) in our example; 

  policy also can be ''plru'' (Pseudo LRU) and ''fifo'' (First Input First Out).

</pre>

h2. Code Structure

The MMU grammar is in ru.ispras.microtesk.translator.mmu.grammar folder. It contains Lexer, Parser and TreeWalker files. These files can be compiled by build.xml file (microtesk++/build.xml). The files generated (MMULexer.java, MMUParser.java, MMUTreeWalker.java) are in microtesk++.gen.ru.ispras.microtesk.translator.mmu.grammar folder. 

The folders ru.ispras.microtesk.translator.mmu.ir.* contain the inner representation of the MMU hierarchy of one buffer.  

MMU translator is in the ru.ispras.microtesk.translator.mmu.translator folder. 

Files in ru.ispras.microtesk.model.api.mmu folder contain different policies of cache. Folder ru.ispras.microtesk.model.api.mmu.buffer contains the model of MMU - the files which describe Buffer, Set, Line, Address expressions.  

After grammar files being generated the file ''BufferExample'' can be loaded to the translator.