Основы. Искусство управления сложностью. Системы счисления (тема 1)

1.

Организация
вычислительных систем
Иван Андреевич Сукин
Тема 1:
Основы

2.

Тема 1 :: Разделы
• Искусство управления сложностью
• Системы счисления
–
–
–
–
–
–
Двоичные числа
Шестнадцатеричные числа
Байты, биты, нибблы
Сложение
Представление чисел со знаком
Расширение чисел
Логические вентили
Логические уровни
КМОП транзисторы
Низкоуровневое представление вентилей
Энергопотребление
2
Организация вычислительных систем
Основы

3.

Тема 1: Основы
Искусство управления
сложностью

4.

Управление сложностью
• Как проектировать объекты, слишком
сложные для того, чтобы один человек мог
осмыслить их целиком?
• Абстракция
• Дисциплина
• Три «-ности»:
– Иерархичность
– Модульность
– Регулярность
4
Организация вычислительных систем
Основы

5.

Абстракция
Сокрытие ненужных
деталей
5
Организация вычислительных систем
Основы

6.

Дисциплина
• Сознательное ограничение множества
вариантов дизайна
• Пример: цифровая дисциплина
– Дискретные уровни напряжения вместо
непрерывных
– Дизайн цифровых систем проще чем у
аналоговых – можно разрабатывать более
сложные системы
– Цифровые системы замещают аналоговых
предшественников
6
Организация вычислительных систем
Основы

7.

Три «-ности»
• Иерархичность
– Система делится на подсистемы и далее
• Модульность
– Каждая подсистема имеет интерфейс
• Регулярность
– Общий подход к разработке модулей
(подсистем), так что их можно повторно
использовать
7
Организация вычислительных систем
Основы

8.

Цифровая абстракция
• Большинство физических величин
непрерывны
– Напряжение на участке цепи
– Частота колебаний
– Координаты тела
• Цифровая абстракция имеет дело с
дискретным подмножеством этих
значений
8
Организация вычислительных систем
Основы

9.

Цифровая дисциплина: биты
• Два дискретных значения:
– 1и0
– 1, ИСТИНА, HIGH
– 0, ЛОЖЬ, LOW
• 1 и 0: уровни напряжения или жидкости,
положения шестеренок и т.д.
• Цифровые схемы используют уровни
напряжения:
– 0: низкое напряжение (земля, GND)
– 1: высокое напряжение (VDD)
• Бит: двоичная цифра (Binary digit)
9
Организация вычислительных систем
Основы

10.

Тема 1: Основы
Системы счисления:
двоичные числа

11.

Системы счисления
• Десятичная
Единицы
Десятки
Сот ни
Тысячи
537410 = 5 * 103 + 3 * 102 + 7 * 101 + 4 * 100
Пять т ысяч
Три сотни
Семь
десятков
Чет ыре
единицы
• Двоичная
Единицы
Двойки
Чет вер ки
Во сьмерки
11012 = 1 × 23 + 1 × 22 + 0 × 21 + 1 × 20 = 1310
Одна
восьмерка
11
Одна
четверка
Организация вычислительных систем
Ноль двоек
Одна
единица
Основы

12.

Двоичный счет
Двоичная
0
1
10
11
100
101
…
12
Десятичная
0
1
2
3
4
5
Организация вычислительных систем
Основы

13.

Степени двойки
13
20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
25 = 32
26 = 64
27 = 128
28 = 256
29 = 512
210 = 1024
211 = 2048
212 = 4096
213 = 8192
214 = 16384
215 = 32768
Организация вычислительных систем
Основы
Полезно
запомнить

14.

Перевод чисел
• Из двоичной в десятичную:
– Перевести 100112 в десятичную систему
– 16×1 + 8×0 + 4×0 + 2×1 + 1×1 = 1910
• Из десятичной в двоичную:
– Перевести 4710 в двоичную систему
– 32×1 + 16×0 + 8×1 + 4×1 + 2×1 + 1×1 = 1011112
14
Организация вычислительных систем
Основы

15.

Из десятичной в двоичную
• Два способа:
o Способ 1: Найти подходящую старшую степень
двойки, вычесть её и повторить процедуру
o Способ 2: Последовательно делить на 2,
записывая остатки справа налево
15
Организация вычислительных систем
Основы

16.

Из десятичной в двоичную
5310
Способ 1: Вычитать подходящую старшую степень двойки
5310
32×1
53-32 = 21
16×1
21-16 = 5
4×1
5-4 = 1
1×1
= 1101012
Способ 2: Последовательно делить на 2
5310 =
53/2 = 26 R1
26/2 = 13 R0
13/2 = 6 R1
6/2 = 3 R0
3/2 = 1 R1
1/2 = 0 R1
= 1101012
16
Организация вычислительных систем
Основы

17.

Двоичные числа
• Десятичное число из N цифр
– Сколько их? 10N
– Диапазон значений? [0, 10N - 1]
– Пример: десятичное число из 3 цифр:
• 103 = 1000 возможных значений
• Диапазон: [0, 999]
• Двоичное число из N цифр
– Сколько их? 2N
– Диапазон значений: [0, 2N - 1]
– Пример: двоичное число из 3 цифр:
• 23 = 8 возможных значений
• Диапазон: [0, 7] = [от 0002 до 1112]
17
Организация вычислительных систем
Основы

18.

Тема 1: Основы
Системы счисления:
шестнадцатеричные
числа

19.

Шестнадцатеричные числа
19
Hex
Десятичное
Двоичное
0
0
0000
1
1
0001
2
2
0010
3
3
0011
4
4
0100
5
5
0101
6
6
0110
7
7
0111
8
8
1000
9
9
1001
A
10
1010
B
11
1011
C
12
1100
D
13
1101
E
14
1110
F
15
1111
Организация вычислительных систем
Основы

20.

Шестнадцатеричные числа
• Основание системы счисления – 16
• Удобны для сокращенной записи
двоичных чисел
20
Организация вычислительных систем
Основы

21.

Переводы
• Из шестнадцатеричной в двоичную:
– Перевести 4AF16 (также 0x4AF) в двоичную
– 0100 1010 11112
• Из шестнадцатеричной в десятичную:
– Перевести 4AF16 в десятичную
– 162×4 + 161×10 + 160×15 = 119910
21
Организация вычислительных систем
Основы

22.

Префиксы
• Нижние индексы неудобны
• В некоторых ЯП используют префиксы:
• Шестнадцатеричный: 0x
• 0x23AB = 23AB16
• Двоичный: 0b
• 0b1101 = 11012
22
Организация вычислительных систем
Основы

23.

Тема 1: Основы
Системы счисления:
байты, нибблы и все
такое

24.

Биты, байты, нибблы
• Байт: 8 бит
– Всего _____ значений
– [__, ___]
• Ниббл: 4 бита
– Всего _____ значений
– [__, ___]
10010110
Старший
бит
Младший
бит
байт
10010110
Одна двоичная цифра – это __ бит
Одна hex цифра – это ___ бит или ___ нибблов
Две hex цифры – это ___ байт
Старший – слева
Младший – справа
24
Организация вычислительных систем
ниббл
CEBF9AD7
Старший
байт
Основы
Младший
байт

25.

Еще степени двойки
25
210 = 1 кило
220 = 1 мега
230 = 1 гига
240 = 1 тера
250 = 1 пета
260 = 1 экза
≈ 103 (1024)
≈ 106 (1,048,576)
≈ 109 (1,073,741,824)
≈ 1012
≈ 1015
≈ 1018
Организация вычислительных систем
Основы

26.

Оценки степеней двойки
• Чему равно 224?
24 × 220 ≈ 16 миллионов
• Насколько большое число можно
представить 32 битами?
22 × 230 ≈ 4 миллиарда
26
Организация вычислительных систем
Основы

27.

Тема 1: Основы
Системы счисления:
сложение

28.

Сложение
• Десятичное
• Двоичное
28
11
3734
+ 5168
8902
переносы
11
1011
+ 0011
1110
переносы
Организация вычислительных систем
Основы

29.

Двоичное сложение
• Сложите два
четырехбитовых
числа
1
1001
+ 0101
1110
• Сложите два
четырехбитовых
числа
111
1011
+ 0110
10001
29
Организация вычислительных систем
Основы

30.

Переполнение
• Цифровые систем оперируют с заданным
количеством бит
• Переполнение: когда результат слишком
содержит больше бит, чем возможно
сохранить
• Второй пример на предыдущем слайде
30
Организация вычислительных систем
Основы

31.

Тема 1: Основы
Системы счисления:
числа со знаком

32.

Двоичные числа со знаком
• Прямой код
• Дополнительный код
32
Организация вычислительных систем
Основы

33.

Прямой код
• 1 знаковый бит, N-1 бит самого числа
• Знаковый бит – старший
– Положительное: знак = 0
– Отрицательное: знак = 1
• Пример, 4-битовое представление ± 6:
+6 = 0110
- 6 = 1110
• Диапазон N-битового числа в прямом коде:
[-(2N-1-1), 2N-1-1]
33
Организация вычислительных систем
Основы

34.

Прямой код
Проблемы:
• Не работает сложение, например -6 + 6:
1110
+ 0110
10100 (неправильно!)
• Два представления нуля 0 (± 0):
1000
0000
34
Организация вычислительных систем
Основы

35.

Дополнительный код
• Проблемы прямого кода отсутствуют:
– Сложение работает
– Ноль имеет единственное представление
35
Организация вычислительных систем
Основы

36.

Дополнительный код
• Старший бит имеет вес -2N-1
+
• Самое большое число из 4 бит: 0111
• Самое маленькое число из 4 бит: 1000
• Старший бит по-прежнему определяет знак
(1 = отрицательный, 0 = положительный)
• Диапазон N-битовых чисел в доп. коде:
[-(2N-1), 2N-1-1]
36
Организация вычислительных систем
Основы

37.

Смена знака
• Как поменять знак числа в
дополнительном коде?
• Способ:
1. Инвертировать все биты
2. Добавить 1
• Пример: изменить знак числа 310 = 00112
1. 1100
2. + 1
1101 = -310
37
Организация вычислительных систем
Основы

38.

Примеры доп. кода
• Изменить знак числа 610 = 01102
1. 1001
2. + 1
10102 = -610
• Перевести 10012 из дополнительного
кода в десятичную систему
1. 0110
2. + 1
01112 = 710, поэтому 10012 = -710
38
Организация вычислительных систем
Основы

39.

Сложение в доп. коде
• Сложим 6 + (-6) в доп. коде
111
0110
+ 1010
10000
• Сложим -2 + 3 в доп. коде
111
1110
+ 0011
10001
39
Организация вычислительных систем
Основы

40.

Вычитание
• Вычитание сводится к замене знака и
сложению
• Пример: 3 – 5 = 3 + (-5)
0011
+ 1011
1110
40
Организация вычислительных систем
3
-5
-2
Основы

41.

Сравнение числовых систем
Система
Диапазон
Беззнаковая
[0, 2N-1]
Прямой код
[-(2N-1-1), 2N-1-1]
Доп. код
[-2N-1, 2N-1-1]
Например, для четырех битов:
-8
-7
-6
-5
-4
-3
-2
-1
Беззнаковая
0
1
2
3
4
5
6
7
8
9
41
11
12
13
14
15
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111
1111 1110 1101 1100 1011 1010 1001
10
0000
1000
0001 0010 0011 0100 0101 0110 0111
Организация вычислительных систем
Основы
Доп. код
Прямой код

42.

Тема 1: Основы
Системы счисления:
расширение

43.

Расширение чисел
Расширение представления числа из N в M
бит (M > N) :
– Знаковое расширение для чисел в
дополнительном коде
– Расширение нулями для беззнаковых чисел
43
Организация вычислительных систем
Основы

44.

Знаковое расширение
• Бит знака копируется во все старшие
разряды
• Величина числа остается прежней
• Пример 1:
–
–
4-битовое представление 3:
8-битовое представление:
0011
00000011
• Пример 2:
–
–
44
4-битовое представление -5:
8-битовое представление:
Организация вычислительных систем
1011
11111011
Основы

45.

Расширение нулями
• Во все старшие разряды копируется ноль
• Значение отрицательных чисел меняется
• Пример 1:
–
–
4-битовое представление: 0011 = 310
8-битовое представление: 00000011 = 310
• Пример 2:
–
–
45
4-битовое представление: 1011 = -510
8-битовое представление: 00001011 = 1110
Организация вычислительных систем
Основы

46.

Тема 1: Основы
Логические вентили

47.

Логические вентили
• Выполняют логические операции:
– НЕ, И, ИЛИ, НЕ-И, НЕ-ИЛИ, …
• С одним входом:
– Инвертор (НЕ), буфер
• С двумя входами:
– И, ИЛИ, НЕ-И, НЕ-ИЛИ, исключающее ИЛИ
(XOR)
• С несколькими входами
47
Организация вычислительных систем
Основы

48.

Вентили с одним входом
НЕ
BUF
A
Y
Y=A
A
0
1
48
A
Y
Y=A
Y
1
0
Организация вычислительных систем
A
0
1
Основы
Y
0
1

49.

Вентили с двумя входами
И
A
B
ИЛИ
Y
A
B
Y = AB
A
0
0
1
1
49
B
0
1
0
1
Y
Y=A+ B
Y
0
0
0
1
Организация вычислительных систем
A
0
0
1
1
B
0
1
0
1
Основы
Y
0
1
1
1

50.

Вентили с двумя входами
НЕ-И
XOR
A
B
A
B
Y
Y=A+ B
A
0
0
1
1
50
B
0
1
0
1
НЕ-ИЛИ
Y
Y = AB
Y
0
1
1
0
A
0
0
1
1
B
0
1
0
1
A
B
XNOR
Y
Y=A+ B
Y
1
1
1
0
Организация вычислительных систем
A
0
0
1
1
B
0
1
0
1
Основы
A
B
Y
Y=A+ B
Y
1
0
0
0
A
0
0
1
1
B
0
1
0
1
Y
1
0
0
1

51.

Вентили с многими входами
НЕ-И-3
A
B
C
ИЛИ-3
Y
Y = A+B+C
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
Y
1
0
0
0
0
0
0
0
A
B
C
Y
Y = ABC
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
Y
0
0
0
0
0
0
0
1
•XOR с многими входами: проверка четности
51
Организация вычислительных систем
Основы

52.

Описание на SystemVerilog
module gates(input logic a, b, c,
output logic y1, y2, y3, y4, y5);
not g1(y1,
and g2(y2,
or
g3(y3,
nand g4(y4,
xor g5(y5,
endmodule
52
a);
a, b);
a, b, c);
b, c);
a, c);
Организация вычислительных систем
Основы

53.

Тема 1: Основы
Логические уровни

54.

Логические уровни
• Дискретные напряжения определяют 1 и 0
• Например:
– 0 = земля (GND) или 0 вольт
– 1 = VDD иди 5 вольт
• Как насчет 4.99 вольт? Это 0 или 1?
• А как насчет 3.2 вольт?
54
Организация вычислительных систем
Основы

55.

Логические уровни
• Диапазон напряжений для 1 и 0
• Разные диапазоны для входных и
выходных уровней для учета влияния
шума
55
Организация вычислительных систем
Основы

56.

Что такое шум?
• То, что приводит к ухудшению сигнала
– Сопротивления, наводки, помехи…
• Пример: вентиль выдает 5 В, но
сопротивление снижает это
напряжение до 4.5 В
Шум
Отправитель
5В
56
Организация вычислительных систем
Получатель
4.5 В
Основы

57.

Статическая дисциплина
• Для любых допустимых значений
входов любой элемент цепи должен
гарантировать правильное значение на
выходе
• Нужно использовать ограниченные
диапазоны напряжений для
представления логических уровней
57
Организация вычислительных систем
Основы

58.

Запасы помехоустойчивости
Отправитель
Получатель
Выходные характеристики
Входные характеристики
VDD
Уровень HIGH
VO H
Уровень HIGH
NMH
Запрещенная
зона
VO L
VIH
VIL
NML
Уровень LOW
Уровень LOW
GND
58
Организация вычислительных систем
Основы

59.

Запасы помехоустойчивости
Отправитель
Получатель
Выходные характеристики
Входные характеристики
VDD
Уровень HIGH
VO H
Уровень HIGH
NMH
Запрещенная
зона
VO L
VIH
VIL
NML
Уровень LOW
Уровень LOW
GND
59
Верхний запас:
NMH = VOH – VIH
Нижний запас:
NML = VIL – VOL
Организация вычислительных систем
Основы

60.

Передаточные характеристики
Идеальный буфер:
V(Y)
A
Реальный буфер:
Y
V(Y)
VDD
VOH
VOH VDD
Единичный
гейн
Наклон = 1
VOL
VOL 0
V(A)
VDD / 2
VDD
V(A)
0
VIL VIH
VDD
VIL, VIH
NMH = NML = VDD/2
60
Организация вычислительных систем
NMH, NML < VDD/2
Основы

61.

Передаточные характеристики
A
Y
V(Y)
Выходные характеристики Входные характеристики
VDD
VDD
VOH
VO H
NMH
Запрещенная
зона
Единичный
гейн
Наклон = 1
VOL
VO L
V(A)
0
VIL VIH
61
NML
VDD
Организация вычислительных систем
GND
Основы
VIH
VIL

62.

Уровень VDD
• В 1970-х и 1980-х, VDD = 5 В
• Уровень VDD снизился
– Транзисторы могут сгореть
– Нужно низкое энергопотребление
• 3.3 В, 2.5 В, 1.8 В, 1.5 В, 1.2 В, 1.0 В, …
– Нужно быть аккуратным, соединяя схемы с
разным уровнем напряжения питания
62
Организация вычислительных систем
Основы

63.

Логические семейства
Семейство
VDD
VIL
VIH
VOL
VOH
ТТЛ
5 (4.75 - 5.25)
0.8
2.0
0.4
2.4
КМОП
5 (4.5 - 6)
1.35
3.15
0.33
3.84
НВТТЛ
3.3 (3 - 3.6)
0.8
2.0
0.4
2.4
НВКМОП
3.3 (3 - 3.6)
0.9
1.8
0.36
2.7
63
Организация вычислительных систем
Основы

64.

Тема 1: Основы
КМОП транзисторы

65.

Транзисторы
• Вентили построены на транзисторах
• Транзистор – управляемый ключ
– 2 соединены в зависимости от напряжения на
третьем
– d и s соединены (ON) если g = 1
d
g=0
g=1
d
d
g
s
65
ON
OFF
s
Организация вычислительных систем
s
Основы

66.

Кремний
• Транзисторы сделаны из кремния
• Чистый кремний – плохой проводник
• Кремний с примесями – хороший проводник
– n-тип (свободные электроны, negative)
– p-type (свободные дырки, positive)
Свободный электрон
Si
Si
Si
Si
Si
Si
Si
Si
Si
Si
Si
Si
Si
Атомная решетка
66
Свободная дырка
Si
Si
Si
As
Si
Si
B
Si
Si
Si
Si
+
n-тип
Организация вычислительных систем
+
-
p-тип
Основы
Si
Si
Si

67.

МОП транзисторы
• Металл-оксидполупроводник (МОП)
транзисторы:
– Поликремниевый (в
прошлом металлический)
затвор
– Оксидный (диоксид Si)
изолятор
– Легированный
полупроводник
67
Организация вычислительных систем
Основы

68.

Транзисторы: нМОП
68
Затвор = 0
Затвор = 1
OFF (сток и исток не
связаны)
ON (сток и исток
связаны)
Организация вычислительных систем
Основы

69.

Транзисторы: пМОП
пМОП транзисторы
противоположны нМОП
– ON когда Gate = 0
– OFF когда Gate = 1
69
Организация вычислительных систем
Основы

70.

Транзисторы
d
нМОП
пМОП
g=1
d
d
OFF
g
ON
s
s
s
s
s
s
g
OFF
ON
d
70
g=0
Организация вычислительных систем
d
Основы
d

71.

Транзисторы
• нМОП: пропускают 0, подключать к GND
• пМОП: пропускают 1, подключать к VDD
пМОП
сеть
входы
выход
нМОП
сеть
71
Организация вычислительных систем
Основы

72.

Тема 1: Основы
Вентили и
транзисторы

73.

КМОП вентили: НЕ
НЕ
VDD
A
Y
A
Y=A
A
0
1
73
Y
1
0
P1
Y
N1
GND
A
P1
N1
Y
0
ON
OFF
1
1
OFF
ON
0
Организация вычислительных систем
Основы

74.

КМОП вентили: НЕ-И
NAND
A
B
P2
Y
P1
Y
Y = AB
A
0
0
1
1
B
0
1
0
1
Y
1
1
1
0
A B P1
0 0 ON
P2
ON
A
N1
B
N2
N1
N2
Y
OFF OFF 1
0 1 ON OFF OFF ON 1
1 0 OFF ON ON OFF 1
1 1 OFF OFF ON ON 0
74
Организация вычислительных систем
Основы

75.

Структура КМОП вентиля
пМОП
сеть
входы
выход
нМОП
сеть
75
Организация вычислительных систем
Основы

76.

Вентиль НЕ-И-3
Как построить вентиль НЕ-И-3?
A
B
C
Y
76
Организация вычислительных систем
Основы

77.

Вентиль И
Как построить вентиль И?
A
B
77
Организация вычислительных систем
Y
Основы

78.

Закон Мура
78
Организация вычислительных систем
Основы

79.

Тема 1: Основы
Энергопотребление

80.

Энергопотребление
Мощность = Энергия, потребляемая в
единицу времени
• Динамическое энергопотребление
• Статическое энергопотребление
80
Организация вычислительных систем
Основы

81.

Динамическое потребление
• Мощность для зарядки емкостей
– Энергия для зарядки емкости C до напряжения
VDD равна CVDD2
– Схема работает на частоте f
– Емкость заряжается a раз за цикл (разрядка не
тратит энергию)
• Динамическое энергопотребление:
Pdynamic = aCVDD2f
81
Организация вычислительных систем
Основы

82.

Коэффициент активности a
• a это доля цикла, потраченная на зарядку
– Сигнал часов
– Изменение раз в цикл
– Случайный сигнал
– Типичный сигнал
82
Организация вычислительных систем
a=1
a = 0.5
a = 0.25
a = 0.1
Основы

83.

Статическое потребление
• Энергия, потребляемая, когда значения
на вентилях не меняются
• Вызвано токами утечки IDD
• Статическое энергопотребление:
Pstatic = IDDVDD
83
Организация вычислительных систем
Основы

84.

Единицы измерения
• Схемы имеют маленькие емкости,
низкие токи и высокие частоты.
84
Префикс
Обозначение
Величина
Тера
Т
1012
Гига
Г
109
Мега
М
106
Кило
к
103
Милли
м
10-3
Микро
мк
10-6
Нано
н
10-9
Пико
п
10-12
Фемто
ф
10-15
Организация вычислительных систем
Основы

85.

Пример
• Оценить энергопотребление смартфона во
время работы мобильной игры
–
–
–
–
–
VDD = 0.8 В
C = 5 нФ
f = 2 ГГц
a = 0.1
IDD = 100 мА
P = aCVDD2f + IDDVDD
= (0.1)(5 нФ)(0.8 В)2(2 ГГц) + (100 мА)(0.8 В)
= (0.64 + 0.08) Вт ≈ 0.72 Вт
85
Организация вычислительных систем
Основы

86.

Пример
• Если у батарея телефона имеет емкость
4000 мАч, сколько времени она проживет в
режиме ожидания?
– VDD = 0.8 В
– IDD = 100 мА
Pstatic = IDDVDD = 0.08 Вт
Время работы = (Емкость/1000) * VDD / Потребление
= (4000 мАч / 1000) * 0.8 В/ (0.08 Вт)
= 40 часов
86
Организация вычислительных систем
Основы