1) Преобразовать выражение в постфиксную форму;
2) Показать последовательность стековых операций при использовании полиз.
Лекция 6-7, слайд 46 и далее
䦋 |
Вход |
Выход |
Стек |
0 |
(A-B)*(((C-D*E)/F)/G)*H |
пусто |
пусто |
1 |
A-B)*(((C-D*E)/F)/G)*H |
пусто |
( |
2 |
-B)*(((C-D*E)/F)/G)*H |
A |
( |
3 |
B)*(((C-D*E)/F)/G)*H |
A |
( - |
4 |
)*(((C-D*E)/F)/G)*H |
A B |
( - |
5 |
*(((C-D*E)/F)/G)*H |
A B - |
пусто |
6 |
(((C-D*E)/F)/G)*H |
A B - |
* |
7 |
((C-D*E)/F)/G)*H |
A B - |
* ( |
8 |
(C-D*E)/F)/G)*H |
A B - |
* ( ( |
9 |
C-D*E)/F)/G)*H |
A B - |
* ( ( ( |
10 |
-D*E)/F)/G)*H |
A B - C |
* ( ( ( |
11 |
D*E)/F)/G)*H |
A B - C |
* ( ( ( - |
12 |
*E)/F)/G)*H |
A B – C D |
* ( ( ( - |
13 |
E)/F)/G)*H |
A B – C D |
* ( ( ( - * |
14 15 16 17 18 19 20 21 22 23 24 25 |
)/F)/G)*H /F)/G)*H
F)/G)*H )/G)*H /G)*H G)*H )*H *H H пусто пусто |
A B – C D E A B – C D E * -
A B – C D E * - A B – C D E * - F A B – C D E * - F / A B – C D E * - F / A B – C D E * - F / G A B – C D E * - F / G / A B – C D E * - F / G / A B – C D E * - F / G / H A B – C D E * - F / G / H ** |
* ( ( ( - * * ( (
* ( ( / * ( ( / * ( * ( / * ( / * ** ** пусто |
Задача 4 (4 варианта)
Заданы исходные данные:
— длина строки кэш-памяти — 16 байт;
— общий объем кэш-памяти — 2 кбайт;
— разрядность адреса центрального процессора — 18 бит;
— функция отображения кэш — множественно-ассоциативная с коэффициентом ассоциативности 4.
Требуется:
1) разработать логическую схему кэш-памяти;
2) показать интерпретацию адресной информации, передаваемой процессором.
Логика высчитывается следующим образом. КОэфициент ассоциативности (k) – есть количество строк в модуле. Тогда количество модулей (v) v = C/k, где С – общее количество строк, равное общему объему памяти (p) деленное на длину строки (l) .
Таким образом в данном примере имеем С = 2048/16 = 128 строк. Тогда v =128 /4 = 32
Следовательно логическая структура множественно ассоциативного КЭШа есть 32 модуля по 4 строки.
Далее идет интерпретация адресной информации. Разрядность адреса процессора = 18 бит. Далее высчитываем сколько бит нужно для интерпретации. В множественно ассоциативной организации адрес ячейки ОП задается как тег + модуль + слово. У нас длина строки = 16 байт. Значит для адресации слова в строке надо 2^n =16 => n = 4;
Значит для адресации слова надо 4 бита. Так как модулей у нас 32 то для их адресации используется 2^n = 32 => n = 5; Так как разрядность адреса порца = 18 бит то он адресует
2^18 слов (слово 8 бит) тогда 2^18 = 262 144 слов или 262 144/ 16 (длина строки) =
16 384 блоков. Так как у нас 32 модуля то на тег отводится 16 384 / 32 = 512 блоков. А это
2^9. Значит на интерпретацию тега отводится 9 бит. 9+ 5+ 4 = 18. Все работает правильно =)
Соответственно при поступлении 18 бит. Адреса в кэш вычисляют модуль по 5 битам потом блок по тегу и слово в блоке. Вуаля.
Задача 5 (4 варианта)
Заданы исходные данные:
— длина строки кэш-памяти — 16 байт;
— общий объем кэш-памяти — 32 кбайт;
— разрядность адреса центрального процессора — 24 бит;
— тип кэш — двухвходовой множественно-ассоциативный.
Требуется:
1) определить, в каких строках будут размещены блоки памяти со следующими начальными адресами (адреса записаны в шестнадцатеричном формате):
b60c11; a7a034; 123456;
2) определить, какие еще байты попадут в блок, содержащий байт из ячейки памяти с адресом:
ccfefe; 925605;abcdef.
Рассчитаем логику кэша. Имеем множественно-ассоциативный кэш, кол-во строк в модуле - 2. Рассчитаем количество строк: C = 32 Кб/16 байт = 2048. Тогда количество модулей v=2048/2=1024. Следовательно, КЭШ содержит 1024 модуля по 2 строки в каждом. Интерпретируем адресную информацию: всего адрес 24 бита, младшие 4 (3..0 биты) - хранят номер байта в строки (т.к. у нас длина строки 16 байт), биты 13..4 хранят номер модуля (т.к. у нас 1024 модуля), остальное (23..14 биты) - тег.
Теперь собсно, пора бы ответить на вопросы задачи.
1) Определим, в каких строках будут размещены блоки памяти со следующими начальным адресом b60c11h (не на все 100% уверен, но полагаю, что это собственно, номер блока. Если это именно адрес в памяти, тогда еще надо будет узнать номер блока, но это ведь несложно? :) ). Для этого выполняем b60c11h mod 1024=17. Таким образом, получаем, что блок b60c11h будет хранится в нулевой или первой строке 17ого модуля.
2) Определим, какие еще байты попадут в блок, содержащий байт из ячейки памяти с адресом: ccfefe. В интерпретации адреса видно, что байт в блоке определяют младшие 4 бита (одна шестнадцатеричная цифра). Т.е. байты блока будут отличатся только последней цифрой в шестнадцатеричном представлении. Ответ: ccfef0, ccfef1, ccfef2, ..., ccfeff.
Задача 7 (4 варианта)
Заданы системы команд одно-, двух- и трехадресного процессоров.
Требуется разработать программы вычисления приведенного выражения для указанных вариантов процессоров.
Одноадресный |
Двухадресный |
Трехадресный |
LOAD M |
MOVE(X←Y) |
MOVE(X←Y) |
STORE M |
|
|
ADD M |
ADD(X←X+Y) |
ADD(X←Y+Z) |
SUB M |
SUB(X←X-Y) |
SUB(X←Y-Z) |
MUL M |
MUL(X←X*Y) |
MUL(X←Y*Z) |
DIV M |
DIV(X←X/Y) |
DIV(X←Y/Z) |
Y = (А * В + С)/(D - Е * F)
Y = (А - В + С)/(D - Е * F)
Y = (А * В + С)/(D - Е + F)
Y = (А / В - С)/(D - Е * F)
Вариант 1.
Y = (А * В + С)/(D - Е * F)
Одноадресный |
Двухадресный |
Трехадресный |
LOAD E MUL F STORE Y LOAD D SUB Y STORE Y
LOAD A MUL B ADD C DIV Y
STORE Y |
MUL A, B ADD A, C
MUL E, F SUB D, E
DIV A, D
MOVE Y, A |
MUL Y, A, B ADD Y, Y, C
MUL E, E, F SUB E, D, E
DIV Y, Y, E |
Задача 8 (1 вариант)
В памяти компьютера с одноадресной системой команд содержатся следующие числа:
— по адресу А число (А + 2);
— по адресу А + 1 число (А + 2);
— по адресу А + 2 число (А + 3)
Программа содержит последовательность команд:
LOAD IMMEDIATE A
LOAD DIRECT A
LOAD INDIRECT A
Требуется определить:
1) какое значения будет содержаться в аккумуляторе после выполнения каждой команды;
2) изобразить схематично процесс обработки данных заданными командами.
Решение
Предполагается что
Все команды загружают данные в аккумулятор
LOAD IMMEDIATE A – загружает значение A
LOAD DIRECT A – загружает значение по адресу A
LOAD INDIRECT A – берет значение по адресу A в качестве адреса для загрузки
(C++ : eax = *(*a);)
В таком случае происходит следующее
LOAD IMMEDIATE A ;загрузить значение A eax = A
LOAD DIRECT A ;загрузить значение по адресу A eax = A+2
LOAD INDIRECT A ;загрузить значение по адресу A+2 (адрес по адресу A) eax = A+3
Задача № 9 (4 варианта).
Цикл выполнения команды процессором содержит 7 фаз с длительностью выполнения {55; 50; 60; 45; 10; 55; 50} (нс). При реализации синхронного конвейера команд накладные расходы принимаются равными 5 нс. Требуется:
выбрать такт конвейера;
T
= 60+5 = 65 нс, но не соответствует 2 условию
– 45+10 = 55 нс, выбрать такт нельзя (в этом
варианте).
определить метрики эффективности конвейерной обработки.
Метрики эффективности:
Ускорение
Эффективность
Производительность
