АРХИТЕКТУРА ЭВМ

УТВЕРЖДАЮ

Проректор по учебной работе

8 декабря 2008 г.

ПРОГРАММА

по курсу ОСНОВЫ ИНФОРМАТИКИ (архитектура ЭВМ и язык Ассемблера)

по направлению 010600

факультет ФАЛТ

кафедра ИНФОРМАТИКИ

курс I

семестр 2 Экзамен – нет

лекции – 16 часов Зачет – дифференцированный

семинарские занятия – нет Задания – 2

практические занятия – 16 часов Контрольные работы – 2

ВСЕГО ЧАСОВ – 32

Программу составили: академик РАН, проф. ,

доцент, к. ф.-м. н. ,

доцент, к. т.н. ,

ст. преп.

Программа обсуждена

на заседании кафедры

информатики

5 декабря 2008 года

Заведующий кафедрой

АРХИТЕКТУРА ЭВМ

Структура ЭВМ

Краткое описание устройств ЭВМ и схема их взаимодействия. Структура центрального процессора (ЦП). Регистры, арифметико-логическое устройство, устройство управления. Схема работы ЦП. Понятие микропроцессора. Оперативная память ЭВМ. Ячейки, адреса, машинные слова, разряды, биты. Двоичное представление информации в ЭВМ, причины выбора такого представления. Логические схемы. Сведение любой машинной операции к простейшим логическим. Пример логической схемы. Внешняя память. Устройства ввода-вывода. Шины. Развитие элементной базы ЭВМ (лампы, транзисторы, интегральные схемы).

Представление информации в памяти ЭВМ

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

Машинные программы

Структура машинной программы, команды, коды операций, способы задания операндов. Система команд как важнейшая характеристика ЭВМ. Разнообразие систем команд в реальных ЭВМ (CISC, RISC и др.). Типы команд. Форматы команд. Количество адресов в команде. Принстонская архитектура. Гарвардская архитектура. Способы адресации операндов: непосредственная, прямая, косвенная, регистровая, косвенная регистровая. Модификация адресов. Способы адресации со смещением: относительная, базовая регистровая, индексная. Суть модификации адресов, исполнительные адреса. Основные случаи использования модификации адресов: индексирование, косвенные ссылки. Модификация по нескольким регистрам. Страничная адресация. Блочная адресация. Цикл команды. Режимы работы микропроцессоров.

Ввод-вывод и поддержка операционных систем

Внешние устройства. Модуль ввода-вывода: функции и структура. Адресное пространство ввода-вывода. Управление вводом-выводом: программное и по прерываниям. Прямой доступ к памяти. Управление памятью. Сегментная и страничная модели. Виртуальная память. Защита памяти. Обработка прерываний и исключений. Управление задачами. Виртуальные машины.

Архитектурные принципы повышения производительности ЭВМ

Микропрограммный способ реализации ЦП. Расслоение памяти. Кэш-память (назначение и структура кэш, алгоритмы размещения и поиска данных в кэш, алгоритмы записи в кэш). Конвейерный способ выполнения команд (идея конвейера команд и выгода от него, причины сбоев в конвейере, понятие о RISC – архитектуре). Суперскалярные процессоры.

ЯЗЫК АССЕМБЛЕРА

Начальные сведения

Понятие и достоинства языка Ассемблера (ЯА). Выбор языка для изучения. Запись лексем (идентификаторов, чисел и символьных данных). Типы предложений (комментарии, команды, директивы), их синтаксис и назначение. Понятие ссылки назад и ссылки вперед.

Программные сегменты

Особенности сегментирования (базирования) адресов в ПК. Префиксы сегментных регистров. Соглашения о выборе сегментных регистров по умолчанию. Описание программных сегментов, директива SEGMENT. Операторы SEG и OFFSET. Директива ASSUME и ее назначение. Начальная загрузка сегментных регистров. Директива INCLUDE. Типичная структура программы на ЯА. Модели памяти и упрощенные директивы сегментации.

Директивы описания переменных и констант

Директивы DB, DW, DD и EQU. Константные и адресные выражения. Операторы: TYPE, арифметические.

Учебные расширения языка: ввод-вывод и останов

Операции ввода с клавиатуры (INCH, ININT, FLUSH), вывода на экран (OUTCH, OUTSTR, OUTINT, OUTWORD, NEWLINE) и останова (FINISH). Пример программы с вводом-выводом.

Команды пересылки. Арифметические команды

Команды MOV, XCHG и LEA. Оператор PTR. Команды сложения (ADD, ADC, INC), вычитания (SUB, SBB, DEC, NEG), умножения (MUL, IMUL), деления (DIV, IDIV). Расширение чисел без знака и со знаком, команды CBW и CWD. Программирование вычислений по формулам. Операции над «длинными» числами.

Команды сравнения и перехода

Особенности машинных команд перехода в ПК. Команда безусловного перехода JMP, оператор SHORT. Команды сравнения (СМР), условного перехода (Jccc), управления циклом (LOOP). Программирование разветвлений и циклов.

Массивы и структуры

Описание массивов в ЯА. Особенности модификации адресов в ПК, запись модифицируемых адресов в ЯА. Структуры: описание типов в переменных, задание начальных значений полей, доступ к полям. Примеры обработки массивов и структур. Старшинство операторов ЯА.

Стек

Стек и регистры SS и SP. Описание сегмента стека, начальная загрузка регистров SS и SP. Стековые команды (PUSH, POP). Примеры использования стека. Регистр ВР и доступ к элементам стека.

Процедуры (подпрограммы)

Дальние переходы. Назначение процедур. Директива PROC, близкие и дальние процедуры. Вызовы процедур и возвраты из них, команды CALL и RET. Передача параметров (по значению и по адресу) через регистры и через стек. Локальные данные процедур. Рекурсивные процедуры.

Битовые операции. Упакованные данные

Логические команды (NOT, AND, TEST, OR, XOR). Программирование логических выражений. Команды сдвига (SHR, SHL). Реализация быстрого умножения и деления на степени 2. Упакованные данные, операция над частями машинных слов. Упакованные логические массивы и множества. Машинное представление, реализация операций над ними. Записи.

Динамические структуры данных

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

Программирование с использованием FPU

Команды FPU. Основные приемы программирования с использованием FPU.

Макросредства

Предварительное преобразование текста программы; понятие макроязыка этапа макрогенерации и макрогенератора. Условное ассемблирование: назначение, IF-блоки, IF-директивы (IF, IFE, IFIDN, IFDIF, IFB, IFNB). Запись логических выражений (операторы отношений, логические операторы). Блоки повторения: назначение, REPT-, IRP - и IRPC-блоки. Макрооператоры <>, & и!. Макросы: назначение, макроопределения, макрокоманды, макроподстановки, макрорасширения. Сравнение макросов и процедур. Директивы LOCAL и EXITM.

Многомодульные программы

Понятие модульного программирования, независимая трансляция модулей. Структура модуля. Внешние и общие имена, директивы EXTRN и PUBLIC; сегментирование внешних имен, доступ к ним. Объединение сегментов из разных модулей, параметры директивы SEGMENT. «Разноязычные» модули, соглашения о связях. Ассемблерные вставки.

Ввод-вывод. Прерывания

Машинные команды ввода-вывода (IN, OUT), порты. Использование механизма прерываний для контроля за событиями в ЭВМ, вектор прерывания INT. Примеры сервисных процедур ОС для ввода-вывода и построение на их основе операций ввода-вывода и останова, используемых в курсе.

ТЕХНОЛОГИЯ И СРЕДСТВА СОЗДАНИЯ ПРОГРАММ

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

Обработка текста программы. Задачи, решаемые современным редактором текстов программ.

Макрогенерация текста программы. Варианты взаимодействия макрогенератора с языком Ассемблера. Принципы обработки макросов, блоков повторения и директив условной трансляции.

Трансляция. Основные задачи транслятора. Проблема ссылок вперед и два прохода транслятора. Таблицы транслятора. Основные действия транслятора на каждом из проходов. Структура объектного модуля.

Компоновка. Основные действия компоновщика: объединение модулей, редактирование межмодульных связей, построение загрузочного модуля. Структура загрузочного модуля.

Загрузка. Основные действия загрузчика: загрузка программы, настройка ее на место, запуск выполнения.

Выполнение и отладка. Управление программой на этапе выполнения. Отладчик: основные возможности.

СПИСОК ЛИТЕРАТУРЫ

1.  Программирование на языке Ассемблера IBM PC. – М: Диалог-МИФИ, 2000.

2.  Архитектура IBM PC и язык Ассемблера: Учебное пособие. – М.: МФТИ, 2000.

3.  , Современные микропроцессоры. –

3-е изд., перераб. и доп. – СПб.: БХВ-Петербург, 2003.

4.  Assembler для DOS, Windows и UNIX. – М.: ДМК, 2003.

5.  Юров В.И. Assembler. Учебник для вузов. 2-е изд. – СПб.: ПИТЕР, 2008.

6.  Юров В.И. Assembler. Специальный справочник. 2-е изд. – СПб.: ПИТЕР, 2004.

Задания

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

Задание 1

(срок сдачи 30 марта–4 апреля)

1.  Системы счисления

1.  Как записываются числа в указанных системах счисления?

Двоичная	Десятичная	Шестнадцатеричная
101100
101.1
	90
	63
	101.1
		63
		ABF
		101.1

2.  Как записываются байтовые данные в указанных форматах?

Байт	Целое десятичное без знака	Целое десятичное со знаком	Символ ASCII
Двоичный	Шестнадцатеричный
	41
	61
		48
		122
			-128
			-1
				D
				9

3.  Как записываются указанные десятичные числа в указанных форматах? В каждой пустой клетке укажите соответствующее значение в виде шестнадцатеричной цифры:

Десятичное

Двоичное представление

Короткое

Длинное

Расширенное

–2.5

–0.5

0.0

0.333

0.5

2.5

4.  Как записываются следующие десятичные числа в BCD кодировке (неупакованной и упакованной)?

а) 1024, б) 512, в) 10, д) 56789.

2.  Директивы описания данных и сегментирования. Пересылки

1.  Пусть целая переменная-слово D описана в сегменте данных D1, а целая переменная-слово Е – в сегменте данных E1. Напишите программу, реализующую присваивание AX=D+E и выводящую на экран содержимое регистра AX.

2. Задан фрагмент программы:

С SEGMENT
ASSUME CS:C
X DW 1
BEG: MOV AX, Y
ADD AX, X
…
Y DW 2
С ENDS

При трансляции команды MOV Ассемблер зафиксирует ошибку, тогда как трансляция команды ADD пройдет без ошибки. В чем разница между этими двумя случаями? Как исправить ошибку в команде MOV? Напишите правильную программу с выводом результата сложения на экран.

3.  Арифметические команды

1.  Пусть Т - переменная размером в двойное слово, а Н, М и S –байтовые переменные. Считая, что прошло Т секунд (0<T<86400) от начала суток, определить, сколько полных часов (Н), минут (М) и секунд (S) прошло к этому моменту времени. Напишите программу, обеспечивающую ввод числа секунд T с клавиатуры и выводящую все четыре переменные

4.  Команды переходов и цикла. Ввод-вывод

1.  Напишите программу, которая по введенному с клавиатуры десятичному числу определяет, содержит запись числа цифру 5 или нет. Ответ (yes или no) вывести на экран.

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

3.  Напишите программу, которая по введенному с клавиатуры натуральному числу N вычисляет:

3.1. N-е число Фибоначчи (FN);

3.2. первое из чисел Фибоначчи, превосходящее 10000.

(Определение чисел Фибоначчи Fk: F0 = F1 = 1, Fk = Fk-1 + Fk-2).

4.  Напишите программу, которая по заданной последовательности символов (отличных от точки), за которой следует точка, определяет, сбалансирована ли эта последовательность по круглым скобкам. Ответ (yes или no) вывести на экран.

5.  Индексирование. Массивы. Структуры

1.  Напишите программу, которая в заданном массиве целых чисел находит наименьший элемент и выводит его на экран.

2.  Напишите программу, которая для заданного массива из 10 слов по 12 символов в каждом слове решает следующие задачи:

2.1.  определяет, упорядочены ли слова этого массива по алфавиту;

2.2.  определяет, есть ли в массиве хотя бы два одинаковых слова.

3.  Напишите программу, которая заданный массив целых чисел со знаком упорядочивает по неубыванию (X1£ X2£ X3£¼), используя один из следующих методов сортировки:

3.1.  сортировка выбором;

3.2.  сортировка обменом (метод пузырька);

3.3.  сортировка вставками.

4.  Описать структурный тип PERSON (человек) со следующими тремя полями: FAM (фамилия) – из 20 байтов, NAME (имя) – из 10 байтов и AGE (возраст) – 1 байт. Описать массив GR (группа) из 15 элементов типа PERSON. 14 элементов массива имеют инициализирующие значения полей, взятые из шаблона структуры, а 15-й элемент имеет инициализирующие значения, соответствующие Вашей фамилии, имени и возрасту. Написать программу, решающую следующую задачу:

4.1.  напечатать фамилию самого молодого человека из группы GR (любого, если таких людей несколько);

4.2.  определить, сколько людей из GR имеют то же имя, что и у Вас;

4.3.  определить, есть ли в GR хотя бы одна пара однофамильцев.

6.  Процедуры. Стек

1.  Напишите программу, которая определяет, какая из больших латинских букв чаще всего встречается в символьном массиве. Использовать дальнюю процедуру MAXLET, которой передается начальный адрес массива через регистр ВХ, а число элементов в нем – через регистр СХ (считать, что такая буква есть и она единственная). Свой ответ процедура должна вернуть через регистр AL. В своей работе процедура должна использовать вспомогательный массив счетчиков, отведя ему место в стеке.

2.  Напишите программу, которая должна обнулить те из пяти заданных переменных, значения которых положительны. Использовать дальнюю процедуру ZERO от 5 параметров, которые передаются через стек и каждый из которых (размером в слово) представляет собой адрес некоторой знаковой байтовой переменной из сегмента данных. Вывести на экран исходные значения переменных и их значения после вызова процедуры.

3.  Напишите программу, которая для введенной с клавиатуры последовательности символов, представляющая собой правильную запись формулы следующего вида:

<формула> ::= <цифра> | M(<формула>,<формула>) | m(<формула>,<формула>)

<цифра> ::= 0|1|2|3|4|5|6|7|8|9

(М трактуется как максимум (max), а m – как минимум (min)),

вычисляет ее значение (как число) и выводит его на экран. Использовать близкую рекурсивную процедуру без параметров, которая вводит эту формулу. Пример. Ввод: M(5,m(7,M(8,9))). Вывод: 7.

4.  Пусть в стек записано 10 слов. Напишите программу, которая реализует следующие операции:

4.1.  меняет местами два "верхних" слова стека, сохранив при этом значения всех регистров и не используя переменные;

4.2.  определяет, сколько среди этих слов нулевых;

4.3.  удаляет из стека нулевые слова, "сжав" остальные (дополнительный массив не использовать);

4.4.  определяет, есть ли в стеке хотя бы два одинаковых слова;

4.5.  рассматривая слова из стека как адреса (смещения) некоторых байтов сегмента данных, обнуляет все эти байты.

Задание 2

(срок сдачи 11–16 мая)

1.  Логические и сдвиговые команды. Упакованные данные

1.  Напишите программу, которая:

1.1.  подсчитывает число двоичных единиц в значении регистра АХ, записывает это число в регистр DH и выводит на экран;

1.2.  не используя команды деления, печатает значение регистра АХ в виде беззнакового двоичного числа без незначащих нулей;

1.3.  переворачивает содержимое регистра АХ;

1.4.  не используя команды умножения, вводит беззнаковое двоичное число и записывала его в регистр АХ (считать, что число задано без ошибок, содержит от 1 до 16 цифр и заканчивается пробелом).

2.  Заданы две типа записей:

DATE RECORD D:5, M:4, Y:7 ; дата в формате; "день-месяц-год (две последние цифры)" и

DATE1 RECORD Y1:7, Ml:4, Dl:5 ; дата в формате; "год-месяц-день" и две переменные

A DATE <8,3,6>

А1 DATE1 <>

Напишите программу, которая:

2.1.  выводит дату А на экран в виде dd. mm. yy (например: 08.03.06);

2.2.  присваивает переменной А1 ту же дату, что записана в переменной А и выводит ее на экран в виде yy.mm.dd.

3.  Задан тип запись

TR RECORD A:3,B:2,C:3 и переменная

R TR <8,3,3>

Напишите программу, реализующую следующие операции и выводящую результат на экран (все поля – из переменной R):

3.1. меняет местами значения полей А и С;

3.2. переходит на метку L, если значения полей А и В равны, где выдает об этом сообщение.

2.  Многомодульные программы. Связь с языками высокого уровня

1.  Напишите программу, состоящую из двух модулей. В головном модуле, написанном на языке С, заданы: массив целых чисел и массив вещественных чисел. Из модуля, написанного на языке Ассемблера, вызываются две функции: sum1, возвращающая значение суммы массива целых чисел, и функция sum2, возвращающая значение суммы массива вещественных чисел.

3.  Арифметический сопроцессор

1.  Для выражения a + b * c – d / ( a + b ) построить обратную польскую запись. Напишите программу, которая по заданным вещественными переменными a, b,c и d реализует вычисление значения данного выражения с помощью сопроцессора и запись результата в некоторую переменную z.

2.  Напишите программу возведения произвольного вещественного числа в произвольную степень x y, используя стандартные функции сопроцессора fyl2x (=y * log 2x, x ≥ 0 – в вершине стека, y – любое в регистре ST(1), результат – после очистки ST(0) и ST(1) в вершине стека), f2xm1 (= 2x – 1, –1 ≤ x ≤ 1) и fscale

(= 2x, x – целое со знаком).

4.  Макросредства

1.  Напишите программу, которая по введенному целому числу со знаком выводит его абсолютное значение. Имея в виду то, что последовательность команд ассемблера

met: neg ax

js met

реализует функцию abs(x) для любых значений аргумента, записанных в регистр аккумулятор, кроме значения 8000h, оформите её в виде соответствующего макроопределения absax и используйте его в программе.

2.  Напишите программу, которая по введенному целому числу со знаком выводит: -1, если x < 0; 0, если x = 0; 1, если x > 0. Написать и использовать макроопределение sign с одним параметром x, значением которого может быть либо имя регистра размером один или два байта, либо имя переменной длиной байт, слово или двойное слово.

3.  Напишите программу, выводящую на экран значений флагов CF, ZF, SF, OF. Написать и использовать макроопределение OUTF, вызов которого приводит к генерации последовательности команд, реализующих вывод четверки из 0 и 1 – значений флагов CF, ZF, SF, OF, и не изменяющего текущего значения регистров, в том числе и регистра флагов.

Индивидуальные задачи для программирования

Каждому студенту выдается свой вариант задания.

К 1-му заданию. Обработка символьных строк

Постановка задачи

Дан текст (последовательность символов), содержащий не более 100 элементов. Признаком конца текста считается символ с кодом 0.

Требуется:

·  Ввести текст с клавиатуры и записать его в память ЭВМ.

·  Определить, обладает ли этот текст заданным свойством, указанным в Вашем варианте задания.

·  Преобразовать текст по правилу 1 Вашего задания, если он обладает заданным свойством, и по правилу 2 в противном случае.

·  Вывести на экран исходный и преобразованный тексты, а также номер и формулировку примененного правила.

Варианты задания

Свойство исходного текста:

1.  Текст оканчивается заглавной латинской буквой, которая больше не встречается в тексте.

2.  Текст начинается цифрой и оканчивается цифрой, причем эти цифры различны.

3.  Текст начинается латинской буквой и оканчивается латинской буквой.

4.  Текст содержит не менее трех латинских букв.

5.  Текст содержит равное количество заглавных и строчных латинских букв.

6.  Текст не содержит иных символов, кроме цифр и латинских букв.

Правило 1 преобразования текста:

1.  Заменить каждую заглавную латинскую букву следующей по алфавиту (A→B, B→C,…, Z→A).

2.  Заменить каждую ненулевую цифру соответствующей ей по порядковому номеру строчной буквой латинского алфавита (1→a, 2→b и т. д.).

3.  Заменить каждую заглавную латинскую букву цифрой, числовое значение которой равно остатку от деления порядкового номера буквы в алфавите на десять.

4.  Заменить каждую строчную латинскую букву соответствующей заглавной буквой (a→A, b→B,…, z→Z).

5.  Заменить каждую заглавную латинскую букву соответствующей строчной буквой (A→a, B→b,…, Z→z).

6.  Заменить каждую заглавную латинскую букву «симметричной» в алфавите (A→Z, B→Y,…, Z→A).

Правило 2 преобразования текста:

1.  Перенести в начало текста все входящие в него цифры с сохранением порядка их следования.

2.  Перевернуть текст, не используя дополнительную память.

3.  Повторить каждый символ текста.

4.  Удалить из текста все повторные вхождения его первого символа.

5.  Оставить в тексте только те символы, которые входят в него ровно один раз.

6.  В каждой группе следующих подряд одинаковых символов оставить только один.

Требования к программе

1.  Вывод исходного текста должен быть выполнен сразу после ввода, до анализа и преобразования.

2.  Вывод преобразованного текста должен быть выполнен только после завершения преобразования.

3.  Алгоритмы преобразования по правилам 1 и 2 должны быть оформлены в виде подпрограмм.

4.  Программа должна сохранять работоспособность при любых входных данных.

Ко 2-му заданию. Динамические структуры данных

Постановка задачи

Дана последовательность от 1 до 20 слов, каждое из которых содержит от 1 до 8 заглавных латинских букв; соседние слова разделены запятой, за последним словом следует точка.

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

Варианты задания

Внутреннее представление последовательности слов:

1.  Список слов, упорядоченных по алфавиту.

2.  Двоичное дерево поиска (в нем слева от каждой вершины должны находиться только те слова, что предшествуют этому слову по алфавиту, справа – следующие за ним по алфавиту).

Какие слова, и в каком порядке, печатать:

1.  Все слова (с возможными повторениями).

2.  Все различные слова (без повторений).

3.  Все слова, входящие в последовательность более одного раза.

4.  Сначала все однобуквенные слова, затем все двухбуквенные слова и т. д.

5.  Сначала все различные однобуквенные слова, затем все различные двухбуквенные слова и т. д.

Замечание: в каждой группе слова печатать по алфавиту.

Дополнительная информация о слове

1.  Порядковый номер слова в исходной последовательности.

2.  Количество вхождений слова в последовательность.

Требования к программе

1.  В программе должна быть предусмотрена печать исходной последовательности слов.

2.  Для размещения звеньев списка (вершин дерева) выделить в памяти область подходящего размера – «кучу». Описать подпрограмму, которая при каждом обращении к ней выделяет из «кучи» свободную память под новое звено или вершину. (Замечание: основная программа обязана правильно работать при любом алгоритме выделения свободных ячеек из «кучи».)

3.  Описать в программе следующие подпрограммы:

§  чтение очередного слова, дополнение справа пробелами (до 8 символов) и запись его в память;

§  вставка нового слова в упорядоченный список (дерево);

§  просмотр списка (дерева) и печать нужных слов.

4.  Программа должна сохранять работоспособность при любых входных данных.

Методические указания

1.  Исходную последовательность слов следует сначала целиком ввести в память и лишь затем выделять из нее слова.

2.  Структуру и состав звеньев списков (вершин дерева) определить с учётом особенностей решаемой задачи.

Усл. печ. л. 1,0. Тираж 100 экз.