[МУЗЫКА]

Логические команды.

Во многих ЭВМ логические команды устроены как-то странно с точки зрения

математика-программиста.

Например, в IBM 360 есть CC PSW — разряд в кодовом слове,

где вырабатывается в слове комбинация битов: 00 — это =,

01 — это <, 10 — это >, 11 — переполнение.

И, соответственно,

в командах условного перехода есть маски — четыре бита, единичка в котором означает,

что если вот условие совпало с маской, то переход произойдет.

Скажем, переход — вот как на слайде написан пример: BC- Branch on Condition,

1101 — это переход по ≤.

Можно сделать другую [НЕРАЗБОРЧИВО] — будет тогда по ≥ или еще как-то.

Это хорошо для условных передач управлений, но, скажем,

если вам надо программировать формулу, a < b & c > d,

то у вас получится длиннющая цепочка команд, совершенно несуразная.

И нам это сильно не нравилось.

Поэтому в «Самсоне» мы пошли другим путем.

Мы договорились, что истина — это 1 в стеке целых, а 0 — это ложь в стеке целых.

И, кстати, любое сравнение, хоть для целых,

хоть для вещественных, также вырабатывает 1 или 0.

Если условие выполняется, то 1 в стеке целых, если не выполняется,

то 0 в стеке целых.

И тогда логические команды, такие как AND, OR, XOR,

и все остальные логические команды просто работают абсолютно так же,

как команды с целой арифметикой: берут со стека целых два операнда и

кладут на стек целых результат: 1 или 0.

Команда NOT берет один операнд,

выполняет свое действие и кладет снова на стек целое.

И, таким образом, программирование УВК «Самсон» для логических

элементов ничем не отличается от программирования для целых.

И это сильно упрощает транслятор, а если вы помните это была одна из главных наших

целей — сделать машину для себя, чтобы транслятор был как можно проще.

И вот с точки зрения логических команд это тоже полностью выполняется.

Теперь рассмотрим команды передачи управления.

Все команды, как вы знаете, сидят в сегменте кодов,

длина которого не превышает 64 Кбайт.

У нас смещение всего может быть максимально 16 битов.

И есть главная команда — переход и

двухваттовый адрес перехода M16, [НЕРАЗБОРЧИВО] 16 битов.

Это [НЕРАЗБОРЧИВО] в кодовом сегменте,

смещенный на M16 от начала кодового сегмента.

Есть аналогичные условные команды — переход по 0 M16,

это значит перейти по адресу, смещенному на M16 от начала кодового сегмента,

если в стеке целых 0.

И аналогичная — П по 1.

Мы их чаще называем переход по 0 — это переход по лжи,

а переход по 1 — переход по истине.

На самом деле, команды передачи управления 16-разрядным смещением — это избыточные

команды, потому что очень часто смещение такого нам не надо, 16-разрядного.

И поэтому мы ввели команды перехода с коротким смещением.

Кстати, вот тут чуть-чуть статистики: за что надо бороться,

где надо стараться, а где не надо.

Есть международная статистика, что в любой программе 40 % всех команд

занимает команда чтение: в стек, в регистр, из памяти в процессор.

20 % занимают команды передачи передачи управления, все: условные,

безусловные — 20 %.

И, наконец, 10 % занимают команды сравнения: =, <, > и так далее.

И, исходя из этого, надо вот такие команды, как мы выражаемся,

языком резать — стараться их оптимизировать,

а на все остальные можно плевать, и сделаем как получится, так и получится.

Итак, рассмотрим короткие передачи управления.

Они — короткие, потому что они идут не от начала сегмента кода,

а от Program Counter — от указателя на текущую исполняемую команду.

Как вы помните, у нас, как и во многих других машинах, Program Counter указывает

не на текущую команду, а буквально на следующую после нее.

Так легче организовывать водопровод, ну какая разница.

Итак, есть безусловный переход только вперед — M8.

Заметьте, это всего два байта, код операции — байт, и 8 — тоже байт.

Так вот, эта двухбайтовая команда позволяет прыгнуть вперед,

на M8 от Program Counter.

B по 0 — это условный переход по 0 в стеке целых,

а B вперед по 1 — это условный переход по 1 в стеке целых.

И есть одна команда назад M8, но условных передач нет.

Вы спросите: а как же ваша полярная ортогональность?

Мы просто посмотрели конструкции языков и не нашли такие конструкции,

где нужно было бы условный переход назад сделать.

Вот в языке C есть do while, но его легко сделать и существующими нашими командами.

Таким образом, вот такие есть короткие переходы.

И теперь вспомним еще раз — вернусь на предыдущий слайд — вот про эту статистику.

20 % — передача управления, 10 — команды сравнения.

И вот тут я вам расскажу еще одну,

практически семейную историю, но опять-таки в точности по этому пункту.

До того как был спаян первый провод УВК «Самсон»,

мы не меньше года играли с интерпретатором УВК «Самсон».

Играли — в каком смысле?

Гоняли тесты и смотрели, какие получаются команды, где, что удобно,

что неудобно, где есть [НЕРАЗБОРЧИВО], где можно соптимизировать.

Так вот, этот интерпретатор,

детальный интерпретатор УВК «Самсон» — настолько детальный, что условный переход,

если переход произошел, то команда занимает пять тактов в интерпретаторе.

А если не произошел, [НЕРАЗБОРЧИВО], то команда занимает только два такта.

Вот этот интерпретатор написала моя дочка Рина Терехова.

Она тогда была, ей было лет 17,

она была студенткой первого курса матмеха, она с шести лет в школу пошла.

как и все мои дети.

И, в общем, была совсем молодой.

И написала этот интерпретатор, и у нас была такая развлекуха дома.

Мы каждый вечер собирались дома, она приносила длиннющие вот такие распечатки,

где были для каждого теста список исполненных команд,

причем упорядочены по частоте их использования.

Я буквально ногтем отрезал верхние 15–20 команд, самые частые команды,

и мы занимались тем, что смотрели: что, почем, почему, как можно соптимизировать.

Остальные полтора метра меня не интересовало, потому что верхняя часть вот

в этих выделенных командах были команды, которые исполняют на тесте, скажем,

10 миллионов раз, 5 миллионов раз, сотни тысяч.

А потом были только тысячи раз или вообще единицы раз.

Зачем я буду думать и стараться над командой, которая тысячу раз исполнится,

когда рядом есть команды, исполняющиеся 10 миллионов раз.

Так вот, мы обнаружили, что очень часто это сочетание такое: что равно,

и потом вперед по 0 укорочены.

Понятно, откуда они идут — из конструкций if и while.

if a = b, then else — так вот надо

передать управление на else, если условие равно выдает false.

И решили склеить эти две команды,

и ввели такую команду: вперед по =, на M8.

И тем самым мы сэкономили, значит, как минимум 10 % кода.

Вы помните статистику?

И еще пару тактов удалось сэкономить,

то есть от введения такой команды мы сильно выиграли.

Опять-таки из соображения ортогональности тогда уж ввели вперед по <,

по ≤, по >, по ≥, по ≠, хотя эти команды реже,

значительно реже используются, чем вперед по =.

Но зато транслятору хорошо.

И вот такого рода эксперименты мы делали практически каждый вечер: смотрели,

иногда возвращались.

Когда кодов операций стало не хватать, так провели какую-то чистку.

Кстати, тут я хочу рассказать вам еще одну историю.

Значит, ведь это же все делалось за деньги КГБ,

«Самсон»: плановая работа, договор, этапы.

Приезжали каждый квартал офицеры из Москвы принимать этап работы.

И вот интерпретатор УВК «Самсон» тоже был плановой этапной работой.

И я, когда офицеры приехали, завел их в комнату пустую на матмехе,

привел Карину, сказал: вот это студентка матмеха,

она делала эту работу, она вас будет ее сдавать.

И ушел.

Через два часа я решил поглядеть, как там идет сдача этапа,

все-таки деньги, этап, ответственность.

Захожу: Карина с красными пятнами, офицеры все всклокочены, и она с ними,

так размахивая руками: это вы мне говорите, что вы говорите,

что нет автомата с нулевым состоянием?

Кто из нас математик, я или вы?

Офицеры говорят: да ладно, девочка успокойся, все будет хорошо.

Короче, она этот этап сдала, Вечер, полагается такое,

у нас было маленькое такое мероприятие подведения итогов.

Сами понимаете, какое.

Так вот, я им скажу, что это моя дочка.

Офицеры говорят: «Ну, ты что?

Мог бы предупредить».

Я говорю: «Нет-нет.

Тогда это был бы не чистый эксперимент.

А так, студентка матмеха сдавала вам этап и сдала.

Я видел, как она с вами ругалась.

Так и надо.

С вами только так и надо».

Во всяком случае, эта история у нас вошла в историю.

Мы её часто вспоминаем.

И сейчас у меня, дети то мои, Карина, доктор в Оксфорде, ей 47 лет.

Но и сегодня очень частый этап и важный для военных, в котором мы работаем,

мы сейчас тоже много работаем для военных дел, сдают мои студенты.

Но теперь-то это у меня не вызывает даже никакого трепета и удивления.

Это же традиция.

Работала — сдавай.

То, что там перед тобой сидит вояка, — это твоя работа,

мы тебе за это зарплату платим.

Нормально.

Теперь разберем более сложные команды передачи управления, а именно циклы.

Опять-таки начнем со статистики.

90 % всех циклов мира — это цикл for i to n do.

То есть есть переменная, которая бежит от нуля или от единички,

в разных языках по-разному, до n.

Еще процентов 8 занимает цикл to n do, только счетчик без переменной.

А все остальные циклы, их тоже довольно много, занимают оставшиеся 2 %.

И поэтому на них мы вообще внимания никак не обращаем.

Итак, начнем с простого цикла to n do.

Очень просто реализуется.

Перед входом в цикл на стек целых загружается n — количество повторений.

А потом исполняются такие три команды, то есть, смотрите, начало по счетчику

и метка «выход», потом идет тело цикла, сколько там команд, я не знаю, может быть,

очень много, и в конце цикла конец по счетчику — метка «начало тела цикла».

Начало по счетчику проверяет, n больше 0?

Если там 0 или отрицательное число, то значит,

тело цикла не должно выполняться ни разу.

Если отрицательное или 0, то сразу на пометке «выход» выходим из цикла.

А если больше, то входим в тело цикла.

А конец по счетчику вычитают из верхушки стека 1, смотрят,

больше ли 0, если больше, то идет пометка на начало тела цикла,

а иначе провалится на следующую команду.

И, кстати, n снимается со стека.

Здесь студенты часто спрашивают, зачем нужна команда начала счетчика.

Вообще-то, мы могли реализовать сразу перед этим управление на конец по

счетчику, а потом там и одной командой было бы меньше,

но тогда было бы два лишних разгона водопровода.

Вы бы прыгали на конец по счетчику.

Это реальный переход и разгон водопровода.

А потом из конца по счетчику на начало — лишние два водопровода.

Очень редко бывает, когда люди пишут to n do, где n отрицательна.

Поэтому мы сочли за благо ввести такую команду, которая проверяет,

нужно ли входить в цикл, чтобы семантика была корректной.

Но тем не менее это выгоднее.

И аналогично реализуется команда с переменной цикла.

Там есть команда «начало цикла» и «конец цикла» — НЦ и КЦ.

Абсолютно логично занимаются две позиции стека.

Сначала мы кладем 1, или начальное значение, на стек как переменную.

Выше стека на верхушку кладем n — число повторений.

И дальше опять-таки начало цикла — проверять,

надо ли вообще входить хоть раз в цикл.

Если не надо, то выходим из цикла.

А конец цикла прибавляем к подверхушке стека.

Единичка сравнивается с верхушкой стека, и если там условие «меньше или равно»,

то возвращается на начало тела цикла.

А если нет, то провалится на следующую команду и снимает два позиции со стека.

Таким образом,

я вам рассказал об организации почти всех команд УВК «Самсон».

И причем для меня самое интересное было — указать не просто, какие есть команды,

мало ли какие есть машины, какие есть командования, а почему мы выбирали такие

команды, а почему отказывались от каких-то других команд,

почему на одни команды мы обращали особое внимание, а на другие вообще,

нельзя сказать «чихали», но, в общем, не обращали внимание.

Это связано именно с мировой статистикой использования команд.

[БЕЗ_ЗВУКА]

Логика и передачи управления

Архитектура ЭВМ (Computer Architecture)

Rencontrer les enseignants