Лекции по "Программированию"

Очередь FIFO. Создается очередь запросов «первый пришел – первый ушел», однако сохраняется проблема арбитража между почти одновременными запросами, а также возникает необходимость поддержания очереди запросов достаточной длины. Преимуществом данного алгоритма является возможность достижения максимальной пропускной способности шины.

Простые коммутаторы  с пространственным разделением. Простые коммутаторы с пространственным разделением позволяют одновременно соединять любой вход с любым одним выходом (ординарные) или несколькими выходами (неординарные). Такие коммутаторы представляют собой совокупность мультиплексоров, количество которых соответствует количеству выходов коммутатора, при этом каждый вход коммутатора должен быть заведен на все мультиплексоры. Структура этих коммутаторов показана на рисунке 16.

Достоинства:

• возможность одновременного контакта со всеми устройствами;
• минимальная задержка;

Недостатки:

• высокая сложность порядка n x m, где n – количество входов, m – количество выходов;
• сложность обеспечения надежности.

Коммуникационных средах вычислительных систем, в частности  коммутатор Клоза и баньян-сети, распределенные составные коммутаторы и графы межмодульных связей систем SPP-1000, МВС-100 и МВС-1000.

Составные коммутаторы. Простые коммутаторы имеют ограничения на число входов и выходов, а также могут требовать большого количества оборудования при увеличении этого числа (в случае пространственных коммутаторов). Поэтому для построения коммутаторов с большим количеством входов и выходов используют совокупность простых коммутаторов, объединенных с помощью линий "точка-точка".

 
Рисунок 2 - Простой коммуникатор с пространственным разделением

 

Составные коммутаторы имеют задержку, пропорциональную количеству простых коммутаторов, через которые проходит сигнал от входа до выхода, т.е. числу каскадов. Однако объем оборудования составного коммутатора меньше, чем простого с тем же количеством входов и выходов. Чаще всего составные коммутаторы строятся из прямоугольных коммутаторов 2 х 2 с двумя входами и выходами. Они имеют два состояния: прямое пропускание входов на соответствующие выходы и перекрестное пропускание. Коммутатор 2 х 2 состоит из собственно блока коммутации данных и блока управления. Блок управления в зависимости от поступающих на него управляющих сигналов определяет, какой тип соединения следует осуществить в блоке коммутации - прямой или перекрестный. При этом если оба входа хотят соединиться с одним выходом, то коммутатор разрешает конфликт и связывает с данным выходом только один вход, а запрос на соединение со стороны второго блокируется или отвергается.

Коммутатор Клоза может быть построен в качестве альтернативы для прямоугольного коммутатора с (m x d) входами и (m x d) выходами. Он формируется из трех каскадов коммутаторов: m коммутаторов (d x d) во входном каскаде, m коммутаторов (d x d) в выходном и d промежуточных коммутаторов (m x m).

 

 
Рисунок 3 -  Коммутатор Клоза 3 x 4

 

Соединения внутри коммутатора  устроены следующим образом:

• j-й выход i-ого коммутатора входного каскада соединен с i-ым входом j-ого промежуточного коммутатора;
• j-й вход k-ого коммутатора выходного каскада соединен с k-ым выходом j-ого промежуточного коммутатора.

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

 

 

Лекция № 8. Арифметические основы вычислительных систем. Системы счисления. Позиционные и непозиционные системы счисления.  Основания систем счисления

Система счисления –  это совокупность приемов и правил для записи чисел цифровыми знаками. Система счисления должна обеспечивать:

1. Возможность представления каждого числа в рассматриваемом диапазоне величин;
2. Единственность представления;
3. Простоту оперирования чисел.

Системы счисления делятся  на позиционные и непозиционные.

В непозиционной системе  счисления значение символа не зависит  от его положения в числе. Для  образования чисел используются операции: «+» и « - ».

В позиционной системе  счисления значение символа определяется ее положением в числе.

Для позиционной СС справедливо  равенство:

 

(78,12)₁₀ = 7*10¹ + 8*10⁰ + 1*10 ^–1 + 2*10^-2

a_i – символы системы счисления, q – основание СС.

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

 

10	2	8	16
0	0000	000(0)	0
1	0001	001(1)	1
2	0010	010(2)	2
3	0011	011(3)	3
4	0100	100(4)	4
5	0101	101(5)	5
6	0110	110(6)	6
7	0111	111(7)	7
8	1000	1000(10)	8
9	1001	1001(11)	9
10	1010	1010(12)	A
11	1011	1011(13)	B
12	1100	1100(14)	C
13	1101	1101(15)	D
14	1110	1110(16)	E
15	1111	1111(17)	F

 

(0111)₂ = 1*2² + 1*2¹ + 1*2⁰= 4 + 2 + 1 = 7

 

Лекция № 9. Перевод чисел из одной системы счисления в другую. Аналитический способ перевода. Перевод чисел путем подбора коэффициентов нового ряда. Табличный способ перевода. Перевод с использованием промежуточной системы счисления

 

 

1. перевод чисел путем подбора коэффициентов нового ряда.

(101001)₂ = 1*2⁵ + 1*2³ + 1*2⁰ =  41

2)Аналитический способ перевода, при этом способе перевода целые и дробные числа переводятся разными способами.

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

78/2 = 39/2 = 19/2 = 9/2 = 4/2 = 2/2 = 1

0           1           1       1       0        0

78₁₀ = 1001110₂

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

0,12*2=                            (78,12)₁₀ = 1001110,000111                        

0,24

0,48

0,96

1,92

1,84

1,68

  3) табличный метод перевода.

Для перевода используются таблицы

4) перевод с использованием промежуточной системы счисления. Этот способ применяется при переводе из десятичной системы счисления в двоичную и наоборот

(312)₁₀ ® (х₁)₈ ® (х₂)₂

312/8 = 39/8 = 4  = 470                                х₁ = 100 111 000

  0            7                                                              4     7    0

      Перевод чисел из СС с основанием 2 в СС с основанием 2ⁿ и обратно. Перевод целых чисел.Если основание СС является степенью числа 2, то перевод чисел из этой СС в двоичную и обратно можно проводить по более простым правилам. Для того чтобы целое двоичное число записать в СС с основанием q=2ⁿ, нужно:

1. двоичное число разбить справа налево на группы по n цифр в каждой.
2. если в последней группе окажется меньше n разрядов, то ее надо дополнить нулями до нужного числа разрядов.
3. рассмотреть каждую группу как n-разрядное двоичное число и записать ее соответствующей цифрой в системе счисления с основанием q=2ⁿ.

Пример. Число 101100001000110010₂ переведем в восьмеричную СС.

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

101	100	001	000	110	010
5	4	1	0	6	2

Получаем восьмеричное представление исходного числа: 541062₈.

Перевод дробных чисел. Для того чтобы дробное двоичное число записать в СС с основанием q=2ⁿ, нужно:

1. двоичное число разбить слева направо на группы по n цифр в каждой
2. если в последней правой группе окажется меньше n разрядов, то ее надо дополнить справа нулями до нужного числа разрядов.
3. рассмотреть каждую группу как n-разрядное двоичное число n и записать ее соответствующей цифрой в СС с основанием q=2ⁿ.

Пример. Число 0,1011001₂ переведем в восьмеричную СС.

Разбиваем число слева  направо на триады и под каждой из них записываем соответствующую  восьмеричную цифру

0,	101	100	010
0,	5	4	2

  Получаем восьмеричное  представление исходного числа  0,542₈.

Перевод чисел  из СС с основанием q=2ⁿ в двоичную систему.

Для того, чтобы произвольное число, записанное в СС с основанием q=2ⁿ, перевести в двоичную СС, нужно каждую цифру этого числа заменить ее n-значным эквивалентом в двоичной СС.

Пример. Переведем шестнадцатеричное  число 4АС35₁₆ в двоичную СС.

В соответствии с алгоритмом:

4	А	С	3	5
0100	1010	1100	0011	0101

 Получаем: 0100101011000110101

Лекция 10. Арифметические основы ЭВМ. Формы представления чисел в  ЭВМ. Естественная форма представления (с фиксированной запятой или фиксированной точкой). Нормальная форма представления (с плавающей запятой или с плавающей точкой). Правила нормализации. Представление отрицательных чисел. Правила нормализации. Прямой, обратный и дополнительный коды чисел

 

В ЭВМ используются 3 формы  представления символов. Для записи числовой информации используются 2 формы:

- естественная 

- нормальная 

3-я форма используется  для записи алфавитно-цифровой  информации.

1. естественная форма представления (с фиксированной запятой или фиксированной точкой ) (ФЗ (ФТ))

Если число целое, то «,» или «.» ставится после младшего разряда.

Если число дробное  старший разряд отводится под  знак, (.) находится перед старшим  разрядом, а веса располагаются как  выделено на рис. курсивом

0 £ х £ (2ⁿ-1) диапазон для целых чисел

0 £ х £ 1-2^-n для дробных чисел

При представлении целых  чисел используются 2 формата:

• полуслово (n=16 разрядам)
• слово (n=32 разрядам)

 

 зн    2³⁰    2²⁹                  2⁰

|x₀|   x₁|  x₂|  ...|  |   | x₃₁

               2^-1       2^-2                   2^-31

Знак числа 

Под знак отводится один разряд, в этот разряд записывается:

    0, если число  + (положительное)

    1, если число  – (отрицательное)

2. Нормальная форма представления (с плавающей запятой или с плавающей точкой) ПЗ (ПТ)

    При записи  числа с ПЗ число делится  на два поля: поле для записи порядка и поле для записи мантиссы

А=М*q^p

0,002=2*10^-3 

2- мантисса

3- порядок 

10- основание систем  счисления

       знч   знп      порядок

x0

y0

y1

…

y6

x1

X2

…

xn

                                                М

Знч – знак числа

Знп – знак порядка

М – мантиса

Р – порядок

Для записи чисел с  ПЗ используется два формата:

• слово (если разряд =32)
• двойное слово (64 разряда)