andrey

Путь к Файлу: /Организация ЭВМ / Лекции ВМ-91 / Архипов Нерет - Глава 2(2.1, 2.2).doc

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   0
Пользователь:   andrey
Добавлен:   13.01.2015
Размер:   472.0 КБ
СКАЧАТЬ

«ОСНОВЫ (BASICS)» Глава 2

 

 

 

 

 

2.1. Аппаратная модель.

 

Изучение архитектуры компьютера без расчета стоимости его реализации и длины критических линий связи большое заблуждение. Это все равно, что делать покупки, не смотря на ценник. В данной главе указывается и анализируется аппаратная часть модели MP95. Данная модель, по крайней мере, дает примерное представление о возможных затратах.

 

2.1.1. Компоненты.

 

В данной модели существуют 5 основных компонентов: шлюзы, триггеры, драйверы, ОЗУ и ПЗУ. Стоимость и задержка основных компонентов указана в таблице 2.1. Они приведены в виде сравнения со стоимостью и временем срабатывания простого инвертора. Для основных компонентов используются условные обозначения (рис. 2.1.).

 

 

Стоимость

Задержка

НЕ

1

1

И-НЕ, ИЛИ-НЕ

2

1

И, ИЛИ

2

1

XOR, XNOR

4

2

МUX

3

2

Триггер

8

4

Управляемый ключ (3-state driver)

5

2

Ячейка (элемент) ОЗУ

2

-

Ячейка (элемент) ПЗУ

0.25

-

Табл.2.1. Количество переходов и задержка основных элементов.

 

Инвертор

Логическое “И”

Логическое “ИЛИ-НЕ”

Архипов Нерет - Глава 2(2.1, 2.2)

Архипов Нерет - Глава 2(2.1, 2.2)

Архипов Нерет - Глава 2(2.1, 2.2)

MUX

XOR

Элемент логическое “И-НЕ”

Архипов Нерет - Глава 2(2.1, 2.2)

Архипов Нерет - Глава 2(2.1, 2.2)

Архипов Нерет - Глава 2(2.1, 2.2)

Axd ОЗУ

3-state driver

XNOR

Архипов Нерет - Глава 2(2.1, 2.2)

Архипов Нерет - Глава 2(2.1, 2.2)

Архипов Нерет - Глава 2(2.1, 2.2)

Логическое “ИЛИ”

Триггер

Axd ПЗУ

Архипов Нерет - Глава 2(2.1, 2.2)

Архипов Нерет - Глава 2(2.1, 2.2)

Архипов Нерет - Глава 2(2.1, 2.2)

Рис.2.1. Символические обозначения основных компонентов.

 

Архипов Нерет - Глава 2(2.1, 2.2)

Рис.2.2. Схема полного сумматора FA

 

Разрешающие сигналы CE триггеров и регистров, выходные разрешающие сигналы OE драйверов и сигналы записи в ОЗУ – W всегда имеют высокий активный уровень (ур. логич. “1”).

ОЗУ с A-количеством адресов и с d-битными данными имеет стоимость:

Cram(A, d) = CRAMcell * (A + 3) * (d + log log d)

и задержку:

Архипов Нерет - Глава 2(2.1, 2.2)

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

Стоимость и задержка таким мультипортовых ОЗУ:

Cram3 (A,d) = 1.6 * Cram(A, d)

Dram3(A, d) = 1.5 * Dram(A, d)

 

            Пример 2.1. Схема на рисунке 2.2 имеет цену CFA и задержку DFA, где

Архипов Нерет - Глава 2(2.1, 2.2)

 

2.1.2. Время циклов.

 

            При подсчете времени циклов мы делали замеры задержек указанных в таблице 2.2 во время чтения и записи в регистры и ОЗУ. Необходимо заметить, что мы начинали и заканчивали подсчет циклов в момент времени, когда на выходе регистров появляются новые значения. Константа «сигма» берется равной 1.

 

Регистр

ОЗУ

Чтение

0

Архипов Нерет - Глава 2(2.1, 2.2)

Запись

Архипов Нерет - Глава 2(2.1, 2.2)

Архипов Нерет - Глава 2(2.1, 2.2)

Табл.2.2. Время операции чтения и записи регистров и ОЗУ

           

Пример 2.2. Предположим схема S имеет задержку ds и ОЗУ - R имеет время доступа dram. Четыре схемы на рисунке 2.3 тогда имеют время циклов:

Архипов Нерет - Глава 2(2.1, 2.2)

 

Архипов Нерет - Глава 2(2.1, 2.2)Архипов Нерет - Глава 2(2.1, 2.2)Архипов Нерет - Глава 2(2.1, 2.2)Архипов Нерет - Глава 2(2.1, 2.2)

 

Рис.2.3. Четыре типа передачи данных между регистрами и ОЗУ.

 

2.1.3. Иерархические схемы.

 

Уже стало нормой рисование схем в иерархическом или в рекурсивном виде. Так же не является проблемой описание стоимости или задержки иерархических схем при помощи системы уравнений. Для рекурсивных схем необходимо составлять рекурсивные системы дифференциальных уравнений.

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

 

2.1.4. Примечания для Формулы Задержки

 

Примем S за схему с I входами и O выходами, как показано на схеме 2.4. Очень часто это удобно для анализа задержки DS(I1; O1) от подмножества I1 входов к подмножеству выходов O1. Это максимальная задержка пути P от входа I1 к выходу O1. Используются аббревиатуры:

DS(I1; O) = Ds(I1)

DS(I; O1) = Ds(O1)

DS = DS(I; O)

           

Схемы S не изолированы: их входы и выходы соединены с регистрами или ОЗУ, возможно даже через длинные линии связи. Примем за AS(I1; O1) максимальную задержку пути, который начинается в регистре или в ОЗУ, входит в S через вход I1 и выходит из S  через выход O1. Мы называем AS(I1; O1) суммарной задержкой. Если все входы I1 напрямую соединены с регистрами, то получается:

AS(I1; O1) = DS(I1; O1)

Аналогично обозначим за TS(I1; O1) максимальное время цикла необходимое для корректного прохождения данных от I1 к O1.

Архипов Нерет - Глава 2(2.1, 2.2)

 

Рис.2.4. Варианты прохода сигнала через цепь S.

I’ – подмножество входов I, а O’ – подмножество выходов O.

 

Пример 2.3. Схема Sc на рисунке 2.5 включает 3 цикла:

- выход из схемы S1 через выход d3;

- вход в схему S2 через вход d1;

- вход в схему S2 через вход d2.

Временной цикл Sc может быть записан как:

Архипов Нерет - Глава 2(2.1, 2.2), где

 

Архипов Нерет - Глава 2(2.1, 2.2)

 

Архипов Нерет - Глава 2(2.1, 2.2)

Рис.2.5. Схема Sc.

 


2.2. Числовое представление и основные цепи

 

2.2.1. Натуральные числа

 

Для битов Архипов Нерет - Глава 2(2.1, 2.2) и натуральных чисел n, обозначенных за xn строка состоит из совокупности n чисел x. Обычно счет битов строки Архипов Нерет - Глава 2(2.1, 2.2)n ведется справа налево цифрами от 0 до n-1. Хотя запись может выглядеть так: a = an-1 … a0 или a = a[n-1:0].

Для строк a = an-1 … a0 Архипов Нерет - Глава 2(2.1, 2.2), обозначенных как

Архипов Нерет - Глава 2(2.1, 2.2)

натуральное число в двоичном представлении a. Очевидно, мы имеем:

Архипов Нерет - Глава 2(2.1, 2.2)

Примем за Архипов Нерет - Глава 2(2.1, 2.2) диапазон чисел, которые имеют двоичное представление длинной n. Для Архипов Нерет - Глава 2(2.1, 2.2) и Архипов Нерет - Глава 2(2.1, 2.2) c x = < a >, обозначим:

Архипов Нерет - Глава 2(2.1, 2.2)

n-разрядное представление x. Двоичное число – это строка, которая интерпретируется как двоичное представление числа.

Из определения можно сделать вывод, что для любого Архипов Нерет - Глава 2(2.1, 2.2)

Архипов Нерет - Глава 2(2.1, 2.2)

 

Сложение

 

Записи в таблице 2.3 явно удовлетворяют

Архипов Нерет - Глава 2(2.1, 2.2)                                                (2.1)

Это стандартный алгоритм нахождения двоичного представления суммы трех битов. Для сложения двух n-разрядных чисел a[n-1:0] и b[n-1:0], первое обнаруживает, что:

Архипов Нерет - Глава 2(2.1, 2.2)

a

b

c

c’

s

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

0

0

1

0

1

1

1

0

1

1

0

1

0

0

1

Табл.2.3. Нахождение двоичного представления <c’s> суммы битов a,b,c.

 

Хотя, даже “сумма + 1” может быть представлена с помощью n+1 битов. Стандартный алгоритм для сложения двоичных чисел a[n-1:0] и b[n-1:0] одинаков и для Архипов Нерет - Глава 2(2.1, 2.2) :

Архипов Нерет - Глава 2(2.1, 2.2)                                              (2.2)

для Архипов Нерет - Глава 2(2.1, 2.2). Бит si называется битом суммы в позиции i, а ci называется битом переноса из позиции i в позицию i+1. Следующая теорема подтверждает верность алгоритма:

Теорема 2.1.Архипов Нерет - Глава 2(2.1, 2.2)                               

 

 

Доказательство.

Для n=0, это следует непосредственно из определения алгоритма. От n до n+1 первый заканчивается равенством 2.1 и следствием гипотезы:

Архипов Нерет - Глава 2(2.1, 2.2)

 

2.2.2. Целые числа.

 

Для строк a[n-1:0] используем обозначение, Архипов Нерет - Глава 2(2.1, 2.2)например Архипов Нерет - Глава 2(2.1, 2.2)=01111, и обозначим за

Архипов Нерет - Глава 2(2.1, 2.2)целым числом с двумя дополнительными представлениями a. Очевидно, мы получаем

Архипов Нерет - Глава 2(2.1, 2.2)

Обозначим за Архипов Нерет - Глава 2(2.1, 2.2) диапазон чисел, которые образованы двумя составными представлениями длины n. Для Архипов Нерет - Глава 2(2.1, 2.2) и Архипов Нерет - Глава 2(2.1, 2.2) с x=[a], обозначим:

twon(x) = a

n-разрядное второе дополнительное представление числа x. Второе дополнительное число – строка, которая интерпретируется как второе дополнительное представление числа. Очевидно,

Архипов Нерет - Глава 2(2.1, 2.2)

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

 

Основные свойства вторичных дополнительных чисел/

Лемма: пусть a=a[n-1:0], тогда

Архипов Нерет - Глава 2(2.1, 2.2)

Доказательство. Первые два равенства очевидны. Самый простой подсчет показывает, что

<a> - [a] = an-12n

 

это аргумент третьего равенства.

Архипов Нерет - Глава 2(2.1, 2.2)

Это аргумент четвертого равенства.

Архипов Нерет - Глава 2(2.1, 2.2)

Это аргумент последнего равенства.

 

 

 

 

 

 

Вычитание.

 

Основной алгоритм вычитания для n-разрядных двоичных чисел a и b в случае когда результат не отрицательный действует следующим образом:

1. Сложение двоичных чисел Архипов Нерет - Глава 2(2.1, 2.2) и 1.

2. Отбрасывание ведущего (первого) бита результата.

 

Пример 2.4. Мы хотим осуществить вычитание <110> - <0101> = 12 – 5 =7. Выполним следующие действия:

1. <1100> - <0101> = <110> + <1010> + 1 = <1100> + <1011> = <10111>

2. Отбрасываем первый бит и получаем результат: <0111> = 7.

Это действует, но не доказывает ничего. Для того, чтобы увидеть как же работает алгоритм, заметьте, что Архипов Нерет - Глава 2(2.1, 2.2) подразумевает Архипов Нерет - Глава 2(2.1, 2.2). Хотя, достаточно подсчитать результат модуля 2n, т.е. отбрасывание первого бита не приносит вреда. Правильность алгоритма следует из теоремы:

Теорема 2.3. Пусть a = a[n-1:0] и b = b[n-1:0], тогда Архипов Нерет - Глава 2(2.1, 2.2)

Доказательство:

Архипов Нерет - Глава 2(2.1, 2.2)

Существенным, в отношении вторичного дополнительного числа является то, что алгоритмы сложения для сложения n-разрядных двоичных чисел работают только при n-разрядности вторичных дополнительных чисел до тех пор, пока результат сложения остается в пределах диапазона Tn. Это не удивительно, ведь последние n-1 бит n-разрядных дополнительных чисел представляется в виде двоичных чисел. Следующая теорема уточняет ряд моментов:

Теорема 2.4. Пусть a = a[n – 1:0], b = b[n – 1:0] и пусть Архипов Нерет - Глава 2(2.1, 2.2). Пусть <s[n : 0]> = <a[n – 1:0]> + <b[n – 1:0] + cin  и  пусть биты ci и si будут определены по основному алгоритму сложения для двоичных чисел. Тогда получим:

· Архипов Нерет - Глава 2(2.1, 2.2)

· если Архипов Нерет - Глава 2(2.1, 2.2), тогда [a] + [b] + cin = [s[n - 1:0]]

Доказательство:

Архипов Нерет - Глава 2(2.1, 2.2)

 

Архипов Нерет - Глава 2(2.1, 2.2)

 

Заметьте, что для a = a[n – 1 : 0] и b = b[n – 1 : 0] мы имеем [a] + [b] + cin Архипов Нерет - Глава 2(2.1, 2.2)

Хотя, если мы выполним двоичное сложение:

Архипов Нерет - Глава 2(2.1, 2.2)

в результате всегда получим:

Архипов Нерет - Глава 2(2.1, 2.2)

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

Наш сайт представляет собой Сервис, где студенты самых различных специальностей могут делиться своей учебой. Для удобства организован онлайн просмотр содержимого самых разных форматов файлов с возможностью их скачивания. У нас можно найти курсовые и лабораторные работы, дипломные работы и диссертации, лекции и шпаргалки, учебники, чертежи, инструкции, пособия и методички - можно найти любые учебные материалы. Наш полезный сервис предназначен прежде всего для помощи студентам в учёбе, ведь разобраться с любым предметом всегда быстрее когда можно посмотреть примеры, ознакомится более углубленно по той или иной теме. Все материалы на сайте представлены для ознакомления и загружены самими пользователями. Учитесь с нами, учитесь на пятерки и становитесь самыми грамотными специалистами своей профессии.

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика