Условия и решения некоторых задач

1. На сколько блоков необходимо расслоить параллельнуо работающую память, для того чтобы полностью загрузить векторные функциональные устройства при выполнении векторного оператора Q=(A + B)*(C/D), при условие, что чтение из блока памяти осуществляется за 12 тактов, а функиональное устройство осуществляет ступень вычисления за 1 такт.
   
   

Ну недлого подумав, я решил и эту задачку, ответ - на 60 блоков ОП

1. Какое максимальное количество устройств можно подключить к коммутатору второго уровня ПМ6 системы АС-6, при условии что можно пользоваться только контроллерами работающими с 16, 8, 4 и 2 устройствами, причем хотя бы один из таких контроллеров должен присутствовать.
   
   

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

итого
1контр на 16 устройств
1 на 8 уст
5*8+7 на 4 уст
1 на 2уст
--------
214 уст-в

16-ть надо только к исходному потому что если не так тогда надо не меньше 3+3+4 битов для адрессации (3 бит для 8 выходов исходного К2 и + еще 3 бит для 8 выходов другого К2 , который прямо подключит к исходному + 4 бит для адрессации 16 выходов контролера)
Анологично 8-ть тоже надо посединить к исходному (иначе нжно 3+3+3 =9 битов для адресации)

1. Посчитайте сколько минимально понадобится регистров и тактов для вычисления след. выражения:
   (k/c+(N-p)*l)/(a+b*e)
   при учете, что в наличи имеются два ФУ на сложение/вычитание, одно на деление, одно на умножение. Все ФУ четырехступенчатые, каждая ступень выполняется за один такт.
   
   

У меня получилось 11регистров, и 16+63=79 тактов. Проверял аспер, принял со словами:"Верю, что использовали конвеер, иначе бы не получили 9".

1. Дано выражение: Q = ((A + B) * (C - D)) / (K * L + P * T). За сколько тактов оно вычислится и сколько регистров понадобится? Вектора по 128 элементов
   
   

Ответ: 524 такта, 4 регистра. В решении не совсем разобрался (ещё не начинал ботать :))
Порядок вычислений вроде такой:

R1 A + B
R2 K * L
R3 C - D
R4 P * T

R1 (A + B) * (C - D)
R2 K * L + P * T

Вроде неправильно, а правильно как первый человек считал (с. 29) по странице 29 получается 139 – это если с зацеплением

1. Какое максимальное количество устройств можно подключить к коммутатору второго уровня ПМ6 системы АС-6, при условии что можно пользоваться только контроллерами работающими с 32, 8, 4 устройствами, причем хотя бы один из таких контроллеров должен присутствовать (ну т.е. каждый из них хотя бы один раз). Ну и схемку надо нарисовать.

Задача такого типа разбирается на смс. Здесь ответ - к исходному коммутатору присоединяем 6 контроллеров на 32 и один на 8 (ну просто потому, что он должен быть). На оставшуюся ветку вешаем ещё коммутатор и ему фигачим все контроллеры по 4. Во, как. :)

1. БЭСМ-6
   В общем я не ручаюсь за правильность условия, но вроде так.
   Есть три команды:
   счит <адрес>
   запись <адрес>
   + <адрес>
   
   Вопрос: Мин число обращений в оп?

Вроде 2

1. Значит, первой он разобрал уже знакомую задачу про вычислении количества тактов для выражения.
   Постановка задачи: Есть выражение Q = (A + B) * (C - D) / (P * K + L / N). Считаем, что регистров сколько угодно. В векторе 64 компонента. Операция в ФУ проходит за 4 такта, на одну часть действия приходится 1 такт.
   
   

а) теперь фокус. Считаем, что ФУ - бесконечно количество. За сколько тактов получим первый элемент вектора-результата?

Решение: Ну чего тут. Всё как всегда, по шагам:

1ый шаг:
A + B
C - D
P * K
L / N
на это нам понадобится 4 такта.

2ой шаг:
(A + B) * (C - D)
P * K + L / N
ещё 4 такта

3ий шаг:
наше деление... ещё 4 такта.


Вот. Итого 3 * 4 = 12 тактов.

б) Теперь всё ограничим и решим более сложную задачу. Пусть у нас есть 1 ФУ на +-, один на * и один на /. За сколько тактов получим полный результат-вектор?

1ый шаг:
R1 A + B
R2 P * K
R3 L / N

Больше ничего сделать не можем, все ФУ заняты. Ну 63 + 4 = 67 тактов.

2ой шаг:
А теперь (хитрый дядя Томилин :) ) используем зацепление и одновременно вычислим C - D и (A + B) * (C - D).
Т.е. что происходит? Вычисляем 1ый элемент вектора (C - D) и сразу подаём его на вход умножителю на другой вход которого подаются элементы из R1. Тогда первый элемент результата мы получим за 4 * 2 = 8 тактов. Ну и как всегда + 63 = 71 такт на втором шаге

3ий шаг: аналогично второму для сложения в знаменателе и деления - тоже 71 такт.

Итого 1) + 2) + 3) = 67 + 71 + 71 = 209 тактов
Ради интереса посчитали количество операций, получилось 448.

1. Задача номер 2 (тут ещё интересно кому-нибудь? :))
   Вот это новая задачка относительно, хотя в лекциях есть. Короче так, есть два числа 28 1/2 (это 28 целых и одна вторая) и 5 3/8. Вот. Собственно надо сложить и посмотреть, что получится. Считаем, что на порядок у нас отводится 3 разряда, на мантиссу - 6. Также мантиссу считаем нормализованной и на знаки забиваем (он так сказал).

а) Переводим всё в двоичную систему. При этом предлагается использовать такой метод. Для определения порядка мы берём минимальную степень двойки такую, чтобы двойка в этой степени превышала наше число. Ну т.е. в данном случае это будет 5 (2 ^ 5 = 32 > 28) и 3. Значит в порядке для первого числа у нас будет 101, для второго - 011. Как считать мантиссу. Берём двойку в степени порядка (32) и делим на 2 (16). Если результат < нашего числа, то в первый разряд мантиссы пишем 1, от нашего числа (28 1/2) отнимаем получившееся после деления число (28 1 /2 - 16 = 12 1/2) и идём дальше. Опять делим на 2 (16 / 2 = 8), сравниваем (8 < 12 1/2) и пишем 1 (уже во второй разряд), если < и 0, если больше. Потом переходим к 3ему разряду и т.д. В итоге получим:

28 1/2 : 101 111001
5 3/8: 011 101011

То, что происходит дальше, написано в лекциях, так что я коротенько.

б) Выравниваем порядки:
5 3/8: 101 001010 11

в) складываем
101 111001
+
101 001010 11
=
101 000011 11
1 <- (одна единичка убежала влево)

г) мы эту единичку возвращаем (нормализация вправо) + соответствующий порядок

110 100001 111
В конце - это разряды, которые не влезают.

д) округляем- прибавляем 1 к старшему из выкинутых разрядов
110 100010 011

Ответ: 110 100010 = 34.

1. Задача 3 - это собственно одна их тех, что я вчера запостил. Итак, наш любимый БЭСМ-6. Есть программа
   Сч 12
   Зп 45
   * 77
   Зп 111
   * 45
   + 14
   * 111
   Сч 13
   
   Числа - это адреса, а не операнды!
   Вопрос: Сколько обращений к ОП?
   
   Решение: В чём здесь тема. Каждый раз, когда мы что-то считываем, записываем и т.п. мы обращаемся к ОП. Но! У нас же ещё есть кэш! Сразу оговорюсь, что случай, когда из кэша что-то надо выталкивать на консультации не рассматривался (хотя лектор пытался поговорить ещё и о том омоложении, которое тут происходит). Итак, по порядку.
   Сч 12 - есть обращение в ОП, т.к. надо считать ячейку с адресом 12
   Зп 45 - нет обращения, ячейку с адресом 45 записываем в КЭШ (БРЗ и БАС), а в память ничего не пишем
   * 77 - да, есть обращение. Считываем ячейку с адресом 77
   Зп 111 - аналогично Зп 45 - в кэш
   * 45 - вы думали есть обращение в память? А ни фига! ;) У нас же в кэше лежит ячейка с таким адресом, её никто оттуда не выталкивал (считаем, что кэш изначально пуст а величина его - 8 слов)
   + 14 - да, надо лезть в память
   * 111 - никуда лезть не надо, в кэше лежит
   Сч 13 - придётся залезть.
   
   Итак, что у нас получилось 4 обращения в память. Но это ещё не всё. Есть хитрость. Мы не учли, что команды вообще-то тоже надо считывать. Команда в два раза меньше обычного слова (24 разряда). Т.е. за раз у нас считывается сразц 2 команды. Ну вот. У нас тут 8 команд, значит надо считать ещё 4 слова, т.е. +4 обращения в память.
   
   Ответ: 8 обращений

1. О, интересная задачка. Я такой нигде не видел. Будем втыкать вместе :)
   Значит так, мультиплексный канал подсоединён к 4м устройствам. Соответственно со всеми ними производится обмен. Одновременно. Память (которая с другой стороны канала) не расслоена и время одного цикла обращения к ней равно Т. Т.е. у нас всего один блок. И нам нужно произвести такой обмен:
   
   

номер устройства  кол-во данных(слов)  размер блока обмена(слов)
1                          1000                                20
2                          500                                  50
3                          200                                  10
4                          2000                                100

Спрашивается, сколько времени будет длиться этот обмен (учитывается только время работы с памятью). Возможно, формулировка не совсем точная, но суть такая :)

Решение:

Сначала подсчитаем, сколько понадобится времени, чтобы произвести обмен с памятью (нашей убогонькой) на такое количество данных. Время обработки одного слова - Т => 1000Т + 500Т + 200Т + 2000Т = 3700Т - это чисто на обмен сколько времени нужно.

Теперь вспомним цикл работы мультиплексного канала:
1) Считывание адресного слова - после каждого акта передачи мы будем для следующего устройства считывать адресное слово - +1 обращение в память
2) Считывание по адресному слову текущего управляющего слова - ну вот. Опять лезем в память за вот этим словом. Ещё +1 обращение.
3) Обмен данными - ну и пусть себе обмениваются, мы это уже учли
4) Изменение управляющего слова - ну изменили, не записали, так ведь? ;)
5) Запись изменённого управляющего слова - ... +1 обращение.

Итак, мы имеем +3Т затраты времени на обмен с памятью при каждом "акте обмена". Давайте посчитаем, сколько их всего, этих "актов". Для каждого устройства оно равно 'кол-во слов для передачи' / 'кол-во слов в блоке передачи'. Т.е. простым делением получаем:

номер устройства  кол-во актов
1                              50
2                              10
3                              20
4                              20

Т.е. (50 + 10 + 20 + 20) * 3Т = 300Т

Ответ: 3700Т + 300Т = 4000Т

1. В общем-то известная уже всем задачка на подсоединение устройств к каскаду 2ого уровня АС-6. Итак, есть контроллеры на 2, 4, 8, 32 устройства. Каждый из них надо использовать хотя бы по одному разу.
   Вопрос: какое максимальное число устройств можно подключить?

Решение: описывалось не раз. Но повторение - мать учения. Значит, какая тут ситуация. У нас адресация на каскаде 2ого уровня 8битная. Также (это, надеюсь, все помнят) у коммутатора 2ого уровня 8 выходов. Таким образом мы для идентификации выхода 1ого коммутатора 2ого уровня используем 3 разряда. Дальше мы можем поступить 2мя способами. Либо к выходу 1ого коммутатора подсоединить ещё коммутатор (получим 2ой каскад - третьего каскада уже дано!), либо контроллер. Давайте думать. Если контроллер на 32 устройства, то для идентификации выхода этого контроллера нам нужно 5 разрядов (вроде не ошибся). Т.е. мы не можем подсоединить контроллер на 32 устройства к каскаду 2ого уровня (К2 -> K2 -> 32 устр), т.к. просто не хватит бит для адресации (нам в этом случае понадобится 3 + 3 + 5 = 11 > 8). В общем-то точно так же обстоят дела с контроллером на 8 устройств. Таким образом нам можно их подключить только к 1ому коммутатору 2ого уровня. Подключим к 6 выходам этого коммутатора контроллеры на 32 устройства, на 1 выход дадим контроллер на 8 устройств (ну он должен быть, никуда не деться), а на оставшийся выход повесим коммутатор для второго каскада. Зачем? Ну потому что нам нужно ещё повесить контроллеры на 2 и 4 устройства. А вешать их туда, куда можно загнать контроллер на 32.... не слишком жирно. Так вот, на 2ой каскад (К2 -> K2) мы можем вешать только контроллеры на 4 и 2 устройства (т.к. нам на адресацию 2 бита осталось, 6 съели коммутаторы). Ну так давайте понавешаем: 7 * 4 + 2 (потому что надо). Итого, сколько у нас получилось: 32 * 6 + 8 + 7 * 4 + 2 = 230 устройств - ответ.

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

1. Частично ассоциативынй кэш (и не только)
   Тут задача так ставится: Есть 8 блоков. Каждый, допустим, размером 100 (в восьмиричной системе). Сколькими способами можно организовать ЧАК куда попадут адреса: 17, 333, 615, 210, 1711, 422, 1050 (всё в восьмиричной системе). А что произойдёт в случае полностью ассоциативного кэша? В случае прямой адресации?

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

1. Он так сформулировал: есть таблица адресной трансляции при сегментно-страничной организации памяти. Дано её содержимое (т.е. какие сегменты/страницы там лежат). Есть запрос к сегменту и странице этого сегмента (допустим 3 (номер сегмента) 2 (номер страницы)). Вопрос: сколько обращений в память при таком запросе.

Ответа он так и не дал, а начал распространяться про то, как же организовано сегментно-страничное разделение памяти, сколько таблиц и всё такое. Суть в том, что если в таблице адресной трансляции нет физического адреса искомой страницы, то нам надо залезть в таблицу сегментов (+1 обращение в память), там взять адрес начала таблицы страниц данного сегмента. Потом залезть в эту таблицу страниц для данного сегмента (+1 обращение в память) и получить физ адрес нужной страницы. Ну и записать его в таблицу адресной трансляции, предварительно кого-нибудь выкинув (впрочем к памяти это вроде не имеет отношения). И всё было бы круто, если бы не существовала возможность того, что все эти таблицы откачаны. Тогда надо ещё смотреть признак наличия страницы в памяти. И вот если её в памяти нет, то надо лезть в спец таблицу ОС, в которой написано, где же что находится. Ну и тогда количество запросов к памяти возрастает. Сплошной гемор, короче.