Project

General

Profile

MMU description » History » Version 77

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