Project

General

Profile

MMU description » History » Version 66

Alexander Kamkin, 12/01/2014 02:15 PM

1 24 Alexander Kamkin
h1. MMU Description
2 1 Taya Sergeeva
3 66 Alexander Kamkin
_~By Alexander Kamkin and Taya Sergeeva~_
4 62 Alexander Kamkin
5 65 Alexander Kamkin
*UNDER CONSTRUCTION*
6
7 63 Alexander Kamkin
{{toc}}
8
9 35 Alexander Kamkin
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.
10 1 Taya Sergeeva
11 66 Alexander Kamkin
The grammar is as follows.
12
13
<pre>
14
startRule 
15
    : bufferOrAddress*
16
    ;
17
18
bufferOrAddress
19
    : address
20
    | buffer
21
    ;
22
</pre>
23
24 1 Taya Sergeeva
h2. Address Description
25 56 Taya Sergeeva
26 1 Taya Sergeeva
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.
27
28 66 Alexander Kamkin
An address space is described using a keyword *address*. The following parameters can be defined inside the address space definition:
29
# @width@ – the address width;
30
# @format@ – the address format.
31 1 Taya Sergeeva
32 66 Alexander Kamkin
A few examples are given below.
33
34 1 Taya Sergeeva
<pre>
35
// The singleton.
36 66 Alexander Kamkin
address Void {
37
  width = 0;
38
}
39 1 Taya Sergeeva
</pre>
40
41 61 Alexander Kamkin
<pre>
42 66 Alexander Kamkin
// An unstructured 64-bit virtual addresses.
43
address VA {
44
  width = 64;
45
}
46 1 Taya Sergeeva
</pre>
47 61 Alexander Kamkin
48 1 Taya Sergeeva
<pre>
49 66 Alexander Kamkin
// A stuctured 40-bit physical addresses.
50
address PA {
51
  width = 40;
52
  format = (tag:24, l1Index:7, dwPosition:2, bytePosition:3);
53
}
54 1 Taya Sergeeva
</pre>
55
56 66 Alexander Kamkin
</pre>
57
58
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).
59
60
The grammar is as follows.
61
62
<pre>
63
address
64
    : ''address'' ID ''{''
65
        (addressParameter '';'')*
66
      ''}''
67
    ;
68
69
addressParameter
70
    : width
71
    | format
72
    ;
73
74
width
75
    : ''width'' ''='' expr
76
    ;
77
78
format
79
    : ''format'' ''='' ''(''
80
        field ('','' field)*
81
      '')''
82
    ;
83
84
field
85
    : ID '':'' expr (''='' expr)?
86
    ;
87
</pre>
88 10 Alexander Kamkin
89 2 Taya Sergeeva
h2. Buffer Description
90 1 Taya Sergeeva
91 57 Taya Sergeeva
Buffer is described by the construct *buffer*. Buffer can have different parameters, such as an associativity, a number of lines, the tag computing function, the index computing function, and the structure of data unit displacement, the controlling bits, the strategies of data changing when ''miss'' occurs, and so on. 
92 1 Taya Sergeeva
93 64 Taya Sergeeva
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*. 
94 57 Taya Sergeeva
95 56 Taya Sergeeva
<pre>
96
buffer TLB 
97
{ 
98 64 Taya Sergeeva
  associativity=8;
99
  sets=64;
100 56 Taya Sergeeva
} 
101 1 Taya Sergeeva
</pre>
102
103 57 Taya Sergeeva
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.   
104 56 Taya Sergeeva
105 57 Taya Sergeeva
Each *line* of the buffer can be described optionally by _tag_ and _data_ parameters. 
106 56 Taya Sergeeva
For example, 
107
108 1 Taya Sergeeva
<pre>
109 56 Taya Sergeeva
line = (tag:22, data:1024);
110 1 Taya Sergeeva
</pre>
111 56 Taya Sergeeva
112 1 Taya Sergeeva
describes lines of the cache, each of them containing a 22-bit tag and 1024-bit data.
113 56 Taya Sergeeva
114 57 Taya Sergeeva
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,
115 56 Taya Sergeeva
116 1 Taya Sergeeva
<pre>
117 57 Taya Sergeeva
index(addr:PA) = addr<14..13>;
118 1 Taya Sergeeva
</pre>
119
120 57 Taya Sergeeva
The cache calculates a 2-bit index. _index_ returns the initial and the final points of the field kept in bytes.
121 1 Taya Sergeeva
122 57 Taya Sergeeva
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:
123
124 56 Taya Sergeeva
<pre>
125 57 Taya Sergeeva
line = (tag:22, data:1024);
126
match(addr:VA) = line.tag == addr<14..1>;
127 56 Taya Sergeeva
</pre>
128
129 57 Taya Sergeeva
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.
130 56 Taya Sergeeva
131 57 Taya Sergeeva
The strategy which will be used for the lines displacement is specified by *policy*. 
132 56 Taya Sergeeva
133 57 Taya Sergeeva
<pre>
134
policy = LRU;
135
</pre>
136 56 Taya Sergeeva
137 57 Taya Sergeeva
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.
138 56 Taya Sergeeva
139 57 Taya Sergeeva
There is the example below, describing a real ''lower-level'' cache L1: 
140 2 Taya Sergeeva
141 53 Taya Sergeeva
<pre>
142
buffer L1 
143
{
144 64 Taya Sergeeva
	associativity = 4;
145
	sets = 128;
146 53 Taya Sergeeva
	line = (tag:30, data:256);
147 10 Alexander Kamkin
	index(addr:PA) = addr<9..8>;
148 1 Taya Sergeeva
	match(addr:PA) = line.tag == addr<39..10>;
149
	policy = lru;
150
}
151
</pre>
152 19 Taya Sergeeva
153
_Description of each constructor_ in the buffer example is below:
154 49 Taya Sergeeva
155 21 Taya Sergeeva
h3. buffer
156 55 Taya Sergeeva
157 21 Taya Sergeeva
<pre>
158 1 Taya Sergeeva
  has a name, ''L1'' in our example; it can have names ''L2'' and ''TLB'' also;
159 64 Taya Sergeeva
  _buffer_ can be described by different parameters, such _associativity_, _sets_, _index_, _match_, _policy_, and so on, which number is infixed;
160 16 Taya Sergeeva
</pre>
161 15 Taya Sergeeva
162 64 Taya Sergeeva
h3.  associativity 
163 15 Taya Sergeeva
164 1 Taya Sergeeva
<pre>
165 64 Taya Sergeeva
  _associativity_ is an associativity of a buffer; it returns the number of lines in a one set;
166 17 Taya Sergeeva
</pre>
167 15 Taya Sergeeva
168 64 Taya Sergeeva
h3.  sets
169 15 Taya Sergeeva
170 13 Taya Sergeeva
<pre>
171 64 Taya Sergeeva
  _sets_ is the number of sets in a given buffer;
172 1 Taya Sergeeva
</pre>
173 17 Taya Sergeeva
174 54 Taya Sergeeva
h3.  line
175
176 1 Taya Sergeeva
<pre>
177 52 Taya Sergeeva
  _line_ is an optional description of line''s fields;
178 54 Taya Sergeeva
  it designates each line of the cache; 
179 14 Taya Sergeeva
  _line_ includes its own parameters in the braces: _tag_ and _data_, each of them has an appropriate width of the fields kept in bytes;
180 1 Taya Sergeeva
  in our example _line_ has only two parameters, but in general case it can include more;
181
  it contains a 30-bit tag and a 256-bit data;
182 49 Taya Sergeeva
</pre>
183 17 Taya Sergeeva
184 54 Taya Sergeeva
h3.  index
185
186 1 Taya Sergeeva
<pre>
187
   _index_ is the function for index calculation;
188
   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;
189
  _index_ depends on an _address_, which is ''physical'' (PA) in our case; the type of an address is set in the braces after _index_; 
190 49 Taya Sergeeva
</pre>
191 17 Taya Sergeeva
192 54 Taya Sergeeva
h3.  match 
193
194
<pre>
195 1 Taya Sergeeva
  _match_ is a predicate checking whether the line and the address match each other or not;
196
  it returns ''true'' or ''false'' depending on if the data required is in the given line or not; 
197 52 Taya Sergeeva
  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;
198 1 Taya Sergeeva
  _match_ description contains the the initial and the final points of the address field in the triangle brackets after _addr_; 
199
  as _index_ in the round braces _match_ also has the type of the address used; ''PA'' in our case;
200
</pre>
201 49 Taya Sergeeva
202 1 Taya Sergeeva
h3.  policy
203 54 Taya Sergeeva
204 56 Taya Sergeeva
<pre>
205 52 Taya Sergeeva
  _policy_ is the strategy of data displacement; 
206 1 Taya Sergeeva
  sets a policy which will be applied to our buffer, ''lru'' (Least Recently Used) in our example; 
207 25 Alexander Kamkin
  policy also can be ''plru'' (Pseudo LRU) and ''fifo'' (First Input First Out).
208
</pre>
209
210
h2. Code Structure
211
212
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. 
213
214
The folders ru.ispras.microtesk.translator.mmu.ir.* contain the inner representation of the MMU hierarchy of one buffer.  
215 1 Taya Sergeeva
216
MMU translator is in the ru.ispras.microtesk.translator.mmu.translator folder. 
217 26 Alexander Kamkin
218
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.  
219 1 Taya Sergeeva
220
After grammar files being generated the file ''BufferExample'' can be loaded to the translator.