На основании международного образовательного стандарта Computer Science был разработан стандарт СПбГУ с тем же названием. В дополнение к вопросам, обозначенным в международном стандарте, в этом курсе рассказывается о разработках кафедры и родственных ей IT предприятий в области создания новых архитектур ЭВМ и технологий их программирования. В курсе рассказывается о базовых понятиях архитектур ЭВМ (арифметико-логическое устройство, память, регистры, устройство управления, ввод/вывод), истории их создания, архитектурных способах ускорения ЭВМ (водопровод, RISC, спекулятивное исполнение, предсказание переходов, многопроцессорные и многомашинные архитектуры), о нетрадиционных архитектурах (систолические структуры, мобильные телефоны, встроенные системы реального времени). В теме «HLL компьютеры» подробно рассказывается о HLL компьютере "Самсон", разработанном под руководством автора этого курса. От слушателей курса не требуется начать программировать на машине "Самсон", гораздо более интересно обсудить, почему выбрана именно такая архитектура, такая система команд, какие предложены оптимизации, чем предлагаемые архитектуры лучше существующих. В заключение рассказывается о двух конкретных наиболее популярных архитектурах ЭВМ (самая старая из ныне живущих архитектур мейфрейм IBM/360 и наиболее массовая современная архитектура ARM). По завершении этого курса учащиеся будут: Уметь: - Разбираться в различных архитектурах ЭВМ, сравнивать их по длине кода, эффективность исполнения, оценивать сложность аппаратной реализации; - На основании знания внутренней структуры компьютера, устройства его кэш-памяти, знания реализации шин, уметь оптимизировать свои программы; - Спроектировать новую ЭВМ, хотя бы на бумаге. Знать: - Структурные схемы современных ЭВМ; - Способы аппаратной реализации основных элементов ЭВМ; - Принципы работы устройств ввода/вывода. Владеть: - Навыками ускорения программного обеспечения за счет знания внутренней организации кэш-памяти и шин; - Навыками ускорения ввода/вывода; - Способами рационального создания микропрограмм ЭВМ.
Работа с массивами
Loading...
Из курса от партнера Saint Petersburg State University
Архитектура ЭВМ (Computer Architecture)
15 оценки
Познакомьтесь с преподавателями
Терехов Андрей Николаевичпрофессор
Кафедра системного программирования
[МУЗЫКА]
[МУЗЫКА] Работа
с массивами в УВК «Самсон».
Здесь я начну с некоторой грустной истории.
Когда «Самсон» заработал, как вы помните, я помню это до часа,
в два часа дня пятого ноября 1987 года, когда приехали
всякие члены политбюро, как советские, так и болгарские.
Вот в этот момент «Самсон» заработал, потом мы еще несколько лет его «доводили»,
как это обычно бывает, и гоняли всякие тесты.
И в это время для сравнения мы использовали американскую машину
IBM PC/AT на 286-м процессоре, частота 16 мегагерц,
которая была в это время лучшей из машин такого класса на Западе.
А у нас «Самсон» получился с частотой 3,25 мегагерц.
Вообще-то инженеры обещали 4 мегагерца, но инженеры такие люди,
как всегда, не «дожали».
То есть «Самсон» работал на частоте 3,25 мегагерца.
В пять раз медленней, чем IBM PC/AT, частота.
Но на всех тестах, как ни удивительно,
мы выигрывали как минимум в три раза по времени.
То есть, если одну и ту же программу «прогнать» на IBM PC/AT и у нас,
то наше календарное время будет в три раза меньше, а при том, что частота в
пять раз хуже, то есть наш архитектурный выигрыш был 15, что не трудно посчитать.
И это не фокус: именно за счет того, что «Самсон» — HLL-машина,
ориентирован на языки высокого уровня, то, что аппаратно поддержаны основные
действия, это давало нам — я вот только в предыдущем модуле рассказывал,
как мы там оптимизировали команды, — все это давало
свои результаты: наш архитектурный выигрыш 15, мы этим очень гордились.
И вот как-то раз мой любимый ученик Петр Лавров написал тест
— маленькую телефонную станцию.
И на этом тесте мы вдруг проиграли IBM PC/AT.
Я рвал и метал.
Как это так может быть?
Мы всегда выигрывали, а тут проиграли.
Начали изучать это дело.
И оказалось это довольно трудно.
Тест был не очень большой: три страницы на Алголе 68.
И долго не могли понять, в чем дело, но потом, естественно, разобрались.
Там была таблица абонентов, это же тест «маленькая телефонная станция»,
и причем эта таблица занимала max int, то есть 32 на 767 элементов.
Когда абонент А хочет позвонить абоненту Б, мы должны найти
этого абонента Б в этой таблице, и там еще два параметра,
то есть каждый элемент таблицы занимал шесть байтов — три целых числа: номер
абонента и его характеристики, которые нужны были для соединения.
Так вот, оказалось, что все время тратится на «if «номер» равен tab(i)»,
на вырезки i-го элемента из таблицы.
Как вы помните, мы уже разбирали работу с массивами, как уже говорилось,
вырезка a[i] эквивалентна о исполнению формулы C0 + i*d.
Так вот, в этой таблице было d равно шести.
И поэтому C0 + i*6 и умножение занимало львиную долю времени,
в то время умножители были очень медленные.
Я решил, что я разделю таблицу на две части: сделаю один
массив только из номеров, а второй массив — из характеристик.
И тогда окажется, что умножать надо на два или четыре.
Я сообразил, что на два и на четыре умножать вовсе не надо,
это можно сложить само собой,
или сдвину влево на один или на четыре, на два разряда.
И, кроме того, я вспомнил, что есть строки,
и у них вообще шаг равен один, на единичку вообще глупо умножать.
Поэтому я подумал, что надо бы сделать дополнение к команде ИНД,
команде ИНД1, ИНДБ, ИНДЦ и ИНДП,
то есть в команды, в которых просто во время трансляции известно,
как обычно транслятор подсказывает машине, что шаг равен один,
два или четыре: для байтовых — один, для целых — два, для плавающих — четыре.
И тогда уже машина, получив такую команду, может понимать,
что умножать-то вовсе не надо, а можно сделать как-то намного быстрее.
Сказано — сделано.
Добавили к команде ИНД команды ИНДБ, ИНДЦ, ИНДП и ускорили.
Но тогда уж — аппетит приходит во время еды — решили: почему не
сэкономить еще и на C0?
C0+? Это, конечно, не такое медленное действие,
как умножение, но все-таки действие,
и его тоже хотелось бы как-нибудь «съесть» во время трансляции.
Но не тут-то было!
Дело в том, что шаг известен во время трансляции,
то есть это статическая величина, и транслятор может породить
подходящие команды и для ИНДБ, и для ИНДЦ, и для ИНДП.
А нижняя граница — это динамический объект,
который вычисляется во время счета.
И мы не можем всегда гарантировать,
что он будет всегда ноль или еще что-нибудь такое.
Так вот, договорились, что нижняя граница определяется во время генератора массива,
то есть подпрограммы, которая во время счета отводит память под массив.
Если массив имеет границу ноль или единичка,
а в случае единички мы легко сводим к нижней границе ноль, введя просто один
маленький фиктивный элемент, один элемент, который просто фиктивный.
Тогда мы массив объявляем «хорошим» и будем с ним работать одним способом.
А если нижняя граница — любая другая, не ноль или один,
то мы его обзываем «плохим» и будем работать другим способом.
Так вот, для «хороших» массивов генератор выдает адрес
начала сегмента массива: не реальный адрес начала, а смещенный на 17.
То есть 16 + 1.
16, чтобы избавиться от прибавления 16, а 1, чтобы указать,
что это «хороший» массив.
Микрокоманда в первом же такте вырезки проверяет,
массив «хороший» или «плохой» по четности, адреса, который идет машине,
и передает управление либо на «хорошую» ветку, либо на «плохую».
Если массив «хороший», то вырезка a[i] занимает всего три такта.
А общая вырезка общего вида занимает 33 такта.
И поэтому это действительно реально сильная оптимизация, и сейчас я думаю,
что команда с «хорошим» массивом используется во много раз чаще,
чем обычная индексация.
Просто так жизнь устроена, что в основном люди работают с байтами, с целыми или с
плавающими числами и очень редко работают с какими-то странными массивами,
например, как таблица-массив из структур по шесть байтов.
Это дало нам существенный выигрыш.
Петя Лавров говорил, что я жулик, подгоняю тест.
А я ему объясняю, что я не жулик, я занимаюсь оптимизацией.
Есть тест, любую программу можно написать так или эдак,
можно написать программу оптимально, можно написать неоптимально.
Если мы сообщаем авторам программ, что массивы из целых,
и плавающих, и литерных исполняются лучше и быстрее,
чем массивы из других, то авторы могут этим приемом воспользоваться.
Не только я это делаю, любой автор может это сделать.
В результате, когда мы внесли все эти оптимизации, тест,
который написал Петя Лавров, «маленькая телефонная станция», стал давать такой же
выигрыш в три раза, как и все остальные тесты, которые мы писали до того.
Я считаю, что это показательный пример.
Возникла ситуация, мы ее исследовали,
посмотрели, как ее можно улучшить, придумали.
Я много раз студентам говорил, что когда я проектирую машины,
я чувствую себя Господом Богом: что хочу, то и делаю.
И в данном случае это просто еще один из многочисленных примеров,
как мы столкнулись с неоптимальной ситуацией, подумали,
прооптимизировали и добились того, что и на этом примере «Самсон» стал
выигрывать у американской IBM PC/AT в свои законные
три раза, чем мы очень гордимся.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2019 Все права защищены.
