MMU Description¶

_{By Alexander Kamkin and Taya Sergeeva}

UNDER CONSTRUCTION

• Table of contents
• MMU Description
  • Grammar
  • Address Description
    • Grammar
    • Address Width (width)
      • Grammar
    • Address Format (format)
      • Grammar
  • Examples
  • Buffer Description
    • Grammar
    • Buffer Associativity (ways)
      • Grammar
    • Buffer Length (sets)
      • Grammar
    • Buffer Line Format (format)
      • Grammar
    • Buffer Index Function (index)
      • Grammar
    • Buffer Match Predicate (match)
      • Grammar
    • Buffer Data Replacement Policy (policy)
      • Grammar
    • Examples

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.

Grammar¶

startRule 
    : bufferOrAddress*
    ;

bufferOrAddress
    : address
    | buffer
    ;

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).

Grammar¶

address
    : ''address'' ID ''{''
        (addressParameter '';'')*
      ''}''
    ;

addressParameter
    : width
    | format
    ;

Address Width (width)¶

The width parameter specifies the address width. The parameter is obligatory; its value should be non-negative (zero-length addresses are permitted).

Grammar¶

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

Address Format (format)¶

The format parameter specifies the address 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.

Grammar¶

format
    : ''format'' ''='' ''(''
        field ('','' field)*
      '')''
    ;

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

Examples¶

// The singleton.
address Void {
  width = 0;
}

// An unstructured 64-bit virtual addresses.
address VA {
  width = 64;
}

// A stuctured 40-bit physical addresses.
address PA {
  width = 40;
  format = (tag:24, l1Index:7, dwPosition:2, bytePosition:3);
}

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).

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.

Grammar¶

buffer
    : ''buffer'' bufferTypeID ''{''
        (bufferParameter '';'')*
      ''}''
    ;

bufferParameter
    : ways
    | sets
    | format
    | index
    | match
    | policy
    ;

Buffer Associativity (ways)¶

The ways parameter specifies the buffer associativity (the number of lines in a set). The parameter is obligatory; its value should be positive.

Grammar¶

ways
    : ''ways'' ''='' expr
    ;

Buffer Length (sets)¶

The sets parameter specifies the buffer length (the number of sets a cache). The parameter is obligatory; its value should be positive.

Grammar¶

sets
    : ''sets'' ''='' expr
    ;

Buffer Line Format (format)¶

The format parameter specifies the buffer 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.

Grammar¶

format
    : ''format'' ''='' ''('' field ('','' field)* '')''
    ;

field
    : fieldID '':'' expr (''='' expr)?
    ;

Buffer Index Function (index)¶

The index parameter specifies the index calculation function, which maps an address into the set index. The function may be omitted if the number of sets is 1.

Grammar¶

index
    : ''index'' ''('' addressTypeID addressArgID '')'' ''='' expr
    ;

Buffer Match Predicate (match)¶

The match parameter specifies the line match predicate, which checks if an address matches a line. The parameter is obligatory.

Grammar¶

index
    : ''match'' ''('' addressTypeID addressArgID '')'' ''='' expr
    ;

Buffer Data Replacement Policy (policy)¶

The policy parameters specifies the data replacement (eviction) policy. The parameter is optional. The list of supported policies includes: random, fifo, plru and lru.

Grammar¶

policy
    : ''policy'' ''='' policyID
    ;

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.

buffer TLB { 
  ways = 8;
  sets = 64;
} 

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,

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

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,

index(addr:PA) = addr<14..13>;

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:

line = (tag:22, data:1024);
match(addr:VA) = line.tag == addr<14..1>;

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.

policy = LRU;

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:

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;
}

Description of each constructor in the buffer example is below: