Программная модель кэш-памяти

К описанной в разд. 1.1программной модели учебной ЭВМ может быть подключена программная модель кэш-памяти. Конкретная реализация кэш-памяти в описываемой программной модели показана на рис. 15.

Кэш-память содержит Nячеек (в модели Nможет выбираться из множества {4, 8, 16, 32}), каждая из которых включает трехразрядное поле тега (адреса ОЗУ), шестиразрядное поле данных и три однобитовых признака (флага):

Z— признак занятости ячейки;

U — признак использования;

W — признак записи в ячейку.

Таким образом, каждая ячейка кэш-памяти может дублировать одну любую ячейку ОЗУ, причем отмечается ее занятость (в начале работы модели все ячейки кэш-памяти свободны, "Z_i = 0), факт записи информации в ячейку во время пребывания ее в кэш-памяти, а также использование ячейки (т. е. любое обращение к ней).

 

 

 

			Z	U	W
1
2	118	100236	1	1	0
i	Ti	Di	zi	ui	wi
	Теги	Данные
n

 

Рис. 15. Структура модели кэш-памяти

 

Текущее состояние кэш-памяти отображается на экране в отдельном окне в форме таблицы, причем количество строк соответствует выбранному числу ячеек кэш. Столбцы таблицы определяют содержимое полей ячеек, например, так, как показано в табл. 3.

Пример текущего состояния кэш-памяти

Таблица 3

	Теги	Данные	Z	U	W
1	012	220152	1	0	0
2	013	211003	1	1	0
3	050	000025	1	1	1
4	000	000000	0	0	0

 

Для настройки параметров кэш-памяти можно воспользоваться диалоговым окном Кэш-память, вызываемым командой Вид Кэш-память, а затем нажать первую кнопку на панели инструментов открытого окна. После этих действий появится диалоговое окно Параметры кэш-памяти, позволяющее выбрать размер кэш-памяти, способ записи в нее информации и алгоритм замещения ячеек.

Напомним, что при сквозной записи при кэш-попадании в процессорных циклах записи осуществляется запись как в ячейку кэш-памяти, так и в ячейку ОЗУ, а при обратной записи — только в ячейку кэш-памяти, причем эта ячейка отмечается битом записи (W_i:=1). При очистке ячеек, отмеченных битом записи, необходимо переписать измененное значение ноля данных в соответствующую ячейку ОЗУ.

При кэш-промахе следует поместить в кэш-память адресуемую процессором ячейку. При наличии свободных ячеек кэш-памяти требуемое слово помещается в одну из них (в порядке очереди). При отсутствии свободных ячеек следует отыскать ячейку кэш-памяти, содержимое которой можно удалить, записав на его место требуемые данные (команду). Поиск такой ячейки осуществляется с использованием алгоритма замещения строк.

В модели реализованы три различных алгоритма замещения строк:

случайное замещение, при реализации которого номер ячейки кэш-памяти выбирается случайным образом;

 очередь, при которой выбор замещаемой ячейки определяется временем пребывания ее в кэш-памяти;

бит использования, случайный выбор осуществляется только из тех ячеек, которые имеют нулевое значение флага использования.

Напомним, что бит использования устанавливается в 1 при любом обращении к ячейке, однако, как только все биты U_iустановятся в 1, все они тут же сбрасываются в 0, так что в кэш всегда ячейки разбиты на два непересекающихся подмножества по значению бита U — те, обращение к которым состоялось относительно недавно (послепоследнего сброса вектора U) имеют значение U = 1, иные — со значением U = 0 являются "кандидатами на удаление" при использовании алгоритма замещения "бит использования".

Если в параметрах кэш-памяти установлен флаг "с учетом бита записи", то все три алгоритма замещения осуществляют поиск "кандидата на удаление" прежде всего среди тех ячеек, признак записи которых не установлен, а при отсутствии таких ячеек (что крайне маловероятно) — среди всех ячеек кэш-памяти. При снятом флаге "с учетом бита записи" поиск осуществляется по всем ячейкам кэш-памяти без учета значения W.

Оценка эффективности работы системы с кэш-памятью определяется числом кэш-попаданий по отношению к общему числу обращений к памяти. Учитывая разницу в алгоритмах записи в режимах сквозной и обратной записи, эффективность использования кэш-памяти вычисляется по следующим выражениям (соответственно для сквозной и обратной записи):

 

,      (2)

 

          (3)

где:

K— коэффициент эффективности работы кэш-памяти;

S_o— общее число обращений к памяти;

S_K— число кэш-попаданий;

S_Kw — число сквозных записей при кэш-попадании (в режиме сквозной записи);

Sⁱ_Kw— число обратных записей (в режиме обратной записи).

Вспомогательные таблицы

В данном разделе представлены вспомогательные таблицы (табл. 4 —8) для работы с моделью учебной ЭВМ.

 

Таблица команд учебной ЭВМ

Таблица 4

Ст. Мл.	0	1	2	3	4
0	NOP	JMP		MOV
1	IN	JZ	RD	RD	RDI
2	OUT	JNZ	WR	WR
3	IRET	JS	ADD	ADD	ADI
4	WRRB	JNS	SUB	SUB	SBI
5	WRSP	JO	MUL	MUL	MULI
6	PUSH	JNO	DIV	DIV	DIVI
7	POP	JRNZ		IN
8	RET	INT	EI	OUT
9	HLT	CALL	DI

 

Типы адресации, их коды и обозначение

Таблица 5

Обозначение	Код	Тип адресации	Пример команды
	0	Прямая (регистровая)	ADD 23 (ADD R3)
#	1	Непосредственная	ADD # 33
@	2	Косвенная	ADD @ 33
[ ]	3	Относительная	ADD [33]
@R	4	Косвенно-регистровая	ADD @R3
@R+	5	Индексная с постинкрементом	ADD@R3+
-@R	6	Индексная с преддекрементом	ADD -@R3

 

В табл. 6 приняты следующие обозначения:

DD— данные, формируемые командой в качестве (второго) операнда: прямо или косвенно адресуемая ячейка памяти или трехразрядный непосредственный операнд;

R* — содержимое регистра или косвенно адресуемая через регистр ячейка памяти;

ADR* — два младших разряда ADR поля регистра CR;

V — адрес памяти, соответствующий вектору прерывания;

М(*) — ячейка памяти, прямо или косвенно адресуемая в команде;

I — пятиразрядный непосредственный операнд со знаком.

 

Система команд учебной ЭВМ

Таблица 6

КОП	Мнемо - код	Название	Действие
00	NOP	Пустая операция	Нет
01	IN	Ввод	Acc ← IR
02	OUT	Вывод	OR ← Acc
03	IRET	Возврат из прерывания	FLAGS.PC ←M(SP);INC (SP)
04	WRRB	Загрузка RB	RB ← CR [ADR]
05	WRSP	Загрузка SP	SP ← CR [ADR]
06	PUSH	Поместить в стек	DEC(SP); M(SP) ← R
07	POP	Извлечь из стека	R ® M(SP); INC (SP)
08	RET	Возврат	PC ® M(SP); INC (SP)
09	HLT	Стоп	Конец командных циклов
10	JMP	Безусловный переход	PC ← CR [ADR]
11	JZ	Переход, если 0	if Acc = 0 then PC ← CR [ADR]
12	JNZ	Переход, если не 0	if Acc¹ 0 then PC ← CR [ADR]
13	JS	Переход, если отрицательно	if Acc< 0 then PC ← CR [ADR]
14	JNS	Переход,если положительно	if Acc³ 0 then PC ← CR [ADR]
15	JO	Переход, если переполнение	if ½Acc½>0 then PC ← CR [ADR]
16	JNO	Переход, если нет переполнения	if½Acc½£ 0 then PC ← CR [ADR]
17	JRNZ	Цикл	DEC(R); if R >0 then PC← CR [ADR]
18	INT	Программное прерывание	DEC(SP); M(SP) ← FLAGS.PC; PC ← M(V)
19	CALL	Вызов подпрограммы	DEC(SP); M(SP)← PC; PC ←CR(ADR)
20	Нет
21	RD	Чтение	Acc ← DD
22	WR	Запись	M (*)← Acc
23	ADD	Сложение	Acc ← Acc + DD
24	SUB	Вычитание	Acc ← Acc - DD
25	MUL	Умножение	Acc ← Acc x DD
26	DIV	Деление	Acc ← Acc /DD
27	Нет
28	EI	Разрешить прерывание	IF ← 1
29	DI	Запретить прерывание	IF ← 0
30	MOV	Пересылка	R1 ← R2
31	RD	Чтение	Acc ← R*
32	WR	Запись	R* ← Acc
33	ADD	Сложение	Acc ← Acc+ R*
34	SUB	Вычитание	Acc ← Acc – R*
35	MUL	Умножение	Acc ← Acc - R*
36	DIV	Деление	Acc ← Acc/R*
37	IN	Ввод	Acc ← BY (CR[ADR*])
38	OUT	Вывод	BY (CR[ADR*]) ← Acc
39	Нет
40	Нет
41	RDI	Чтение	Acc ← I
42	Нет
43	JNS	Сложение	Acc ← Acc +I
44	JO	Вычитание	Acc ← Acc - I
45	JNO	Умножение	Acc ← Acc x I
46	JRNZ	Деление	Acc ← Acc/I

 

 

Таблица кодов ASCII (фрагмент)

Таблица 7

0

1

2

3

4

5

6

7

8

9

А

В

С

D

E

F

0

0

@

P

‘

p

A

Р

а

р

1

!

1

A

Q

a

q

Б

С

б

с

2

”

2

B

R

b

r

В

Т

в

т

3

#

3

C

S

c

s

Г

У

г

у

4

$

4

D

T

d

t

Д

Ф

д

ф

5

%

5

E

U

e

u

Е

Х

е

х

6

&

6

F

V

f

v

Ж

Ц

ж

ц

7

‘

7

G

W

g

w

З

Ч

з

ч

8

(

8

H

X

h

x

И

Ш

и

ш

9

)

9

I

Y

i

y

Й

Щ

й

щ

A

*

:

J

Z

j

z

К

Ъ

к

ъ

B

+

;

K

[

k

{

Л

Ы

л

ы

C

,

<

L

l

½

М

Ь

м

ь

D

-

=

M

]

m

}

Н

Э

н

э

E

.

>

N

n

Щ

Ю

щ

ю

F

/

?

O

_

o

П

Я

п

я

 

Перевод HEX-кодов в десятичные числа

Таблица 8

	0	1	2	3	4	5	6	7	8	9	А	В	С	D	E	F
0	0	16	32	48	64	80	96	112	128	144	160	176	192	208	224	240
1	1	17	33	49	65	81	97	113	129	145	161	177	193	209	225	241
2	2	18	34	50	66	82	98	114	130	146	162	178	194	210	226	242
3	3	19	35	51	67	83	99	115	131	147	163	179	195	211	227	243
4	4	20	36	52	68	84	100	116	132	148	164	180	196	212	228	244
5	5	21	37	53	69	85	101	117	133	149	165	181	197	213	229	245
6	6	22	38	54	70	86	102	118	134	150	166	182	198	214	230	246
7	7	23	39	55	71	87	103	119	135	151	167	183	199	215	231	247
8	8	24	40	56	72	88	104	120	136	152	168	184	200	216	232	248
9	9	25	41	57	73	89	105	121	137	153	169	185	201	217	233	249
A	10	26	42	58	74	90	106	122	138	154	170	186	202	218	234	250
B	11	27	43	59	75	91	107	123	139	155	171	187	203	219	235	251
C	12	28	44	60	76	92	108	124	140	156	172	188	204	220	236	252
D	13	29	45	61	77	93	109	125	141	157	173	189	205	221	237	253
E	14	30	46	62	78	94	110	126	142	158	174	190	206	222	238	254
F	15	31	47	63	79	95	111	127	143	159	175	191	207	223	239	255

 

Приложение 5

Задания

на лабораторные работы

по дисциплине «Основы информатики и программирования»

для группы № 21102

Номер варианта (соответствует номеру фамилии в списке группы)	Лаб. раб. №3 «Линейный алгоритм»	Лаб. раб. №4 «Программирование разветвляющегося процесса»
1		, если х < 10; , если x> 10;
2		, если х<15 , если x>15
3		, если x>12 , если x<12
4		, если x<12 , если x>12
5		, если x<14 , если x>14
6		, если x<16 , если x>16
7		, если x<18 , если x>18
8		, если x<19 , если x>19
9		, если x<20 , если x>20
10		, если x<13 , если x>13
11		, если x>14 , еслиx<14
12		, если x>10 , если x<10
13		,если x<6 , если x>6
14		, если x<6 , если x>6
15		, если x<8 , если x>8
16		, если x<9 , если x<9