Правила старшинства логических операций.

Правила старшинства логических операций.

1 Отрицание — логическое действие первой ступени.

2 Конъюнкция — логическое действие второй ступени.

3 Дизъюнкция — логическое действие третьей ступени.

 

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

 

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

 

 

Двоичная таблица сложения Двоичная таблица

умножения

 

0+0=0 0*0=0

0+1=1+0=1 0*1=1*0=0

1+1=10 1*1=1

1+1+1=11 1*1*1=1

Сложение в обратных кодах

А - положительное, а В — отрицательное, по модулю больше А.

В этом случае мы просто складываем числа А и В. Результат получаем, как обычно, в обратном коде:

13₁₀ = 0000 1101₂ (ПК/ОК)

−23₁₀ = 1001 0111₂ (ПК) = 1110 1000₂ (ОК)

(13 + (−23))₁₀ = 1111 0101₂ (ОК) = 1000 1010₂ (ПК) = −10₁₀

 

А — положительное, а В — отрицательное, по модулю меньше А.

На первый взгляд, кажется, что этот случай не отличается от рассмотренного выше второго, однако, давайте посмотрим, что же получится в итоге:

−13₁₀ = 1000 1101₂ (ПК) = 1111 0010₂ (ОК)

23₁₀ = 0001 0111₂ (ПК)

Обратите внимание на результат. У нас выходит, будто сумма — отрицательное число (ибо в знаковом разряде единица), причем, цифр также больше. И, даже если бы не будем учитывать знак, а просто переведем модуль, то получим 910, а не 1010, как должно быть.

Компьютер решает эту проблему, прибавляя получившуюся «лишнюю» единицу к получившемуся числу. Выглядит это следующим образом:

Как видите, в результате мы получили положительное число 0000 10102, переведя которое в десятичную систему счисления мы получим 1010. А это и есть правильный ответ.

 

А и В отрицательные числа.

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

Проверим:

−13₁₀ = 1000 1101₂ (ПК) = 1111 0010₂ (ОК)

−23₁₀ = 1001 0111₂ (ПК) = 1110 1000₂ (ОК)

Переведем получившийся обратный код в десятичное число: 1101 1011₂ (ОК) = 1010 0100₂ (ПК) = −36₁₀. Как мы видим, ответ получился верным.

Перевод чисел из одной с/с в другую (кому надо)

Перевод чисел из 8 с/с и 16 с/с в 2 с/с очень прост: достаточно каждую цифру заменить эквивалентной ей двоичной триадой (тройкой цифр) или тетрадой (четверкой цифр):

Например,

537,1₈=101 011 111,011₂

1A3,F₁₆=1 1010 0011,1111₂

 

Чтобы перевести число из 2с/с в 8с/с или 16с/с, нужно разбить влево и вправо от запятой на триады (для 8с/с) или тетрады (для 16с/с) и каждую такую группу заменить соответствующей 8-ричной или 16-ричной цифрой.

 

10101001,10111₂=10 101 001, 101 110₂=251,56₈

10101001,10111₂=1010 1001, 1011 1000₂=А9,В8₁₆

 

Регистровая адресация

Регистровая адресация (РА) напоминает прямую адресацию. Различие состоит в том, что адресное поле инструкции указывает не на ячейку памяти, а на регистр процессора. Идентификатор регистра в дальнейшем будем обозначать буквой R. Обычно размер адресного поля в данном случае составляет три или четыре бита, что позволяет указать соответственно на один па 8 или 16 регистров общего назначения (РОН).
Косвенная регистровая адресация

Косвенная регистровая адресация(КРА) представляет собой косвенную адресацию, где исполнительный адрес операнда хранится не в ячейке основной памяти, а в регистре процессора. Соответственно, адресное поле команды указывает не на ячейку памяти, а на регистр, как показано на рисунке 2.26.

Адресация со смещением

При адресации со смешением исполнительный адрес формируется в результате суммирования содержимого адресного поля команды с содержимым одного или нескольких регистров процессора.

Адресация со смещениемпредполагает, что адресная часть команды включает в себя как минимум одно поле (А_к). В нем содержится константа, смысл которой в разных вариантах адресации со смешением может меняться. Константа может представлять собой некий базовым адрес, к которому добавляется хранящееся в регистре смещение. Допустим и прямо противоположный подход: базовый адрес находится в регистре процессора, а в поле А_к указывается смещение относительно этого адреса. В некоторых процессорах для реализации определенных вариантов адресации со смешением предусмотрены специальные регистры, например базовый или индексный. Использование таких регистров предполагается по умолчанию, поэтому адресная часть команды содержит только поле А_к.

Если же составляющая адреса может располагаться в произвольном регистре общего назначения, то для указания конкретного регистра в команду включается дополнительное поле R (при составлении адреса более чем из двух составляющих в команде будет несколько таких полей). Еще одно поле Я может появиться в командах, где смещение перед вычислением исполнительного адреса умножается на масштабный коэффициент. Такой коэффициент заносится в один из РОН, на который и указывает это дополнительное поле. В наиболее общем случае адресация со смещением подразумевает наличие двух адресных полей: А_к и R. В рамках адресации со смещением имеется еще один вариант, при котором исполнительный адрес вычисляется не суммированием, а конкатенацией (присоединением) составляющих адреса. Здесь одна составляющая представляет собой старшую часть исполнительного адреса, а вторая – младшую.
Ниже рассматриваются основные способы адресации со смещением, каждый из которых, впрочем, имеет собственное название.
Базовая регистровая адресация

В случае базовой регистровой адресации(БРА) регистр, называемый базовым, содержит полноразрядный адрес, а подполе А_С, - смешение относительно этого адреса. Ссылка на базовый регистр может быть явной или неявной. В некоторых ЭВМ имеется специальным базовый регистр и его использование является неявным, то есть подполе R в команде отсутствует.
Базовую регистровую адресацию обычно используют для доступа к элементам массива, положение которого в памяти в процессе вычислений может меняться. В базовый регистр заносится начальный адрес массива, а адрес элемента массива указывается в подполе А_Скоманды в виде смещения относительно печатного адреса массива. Достоинство данного способа адресации в том, что смещение имеет меньшую длину, чем полный адрес, и это позволяет сократить длину адресного поля команды. Короткое смешение расширяется до полной длины исполнительного адреса путем добавления слева битов, совпадающих со значением знакового разряда смешения.

Индексная адресация

При индексной адресации(ИА) подполе А_С содержит адрес ячейки памяти, а регистр (указанный явно или неявно) – смещение относительно этого адреса. Как видно, этот способ адресации похож на базовую регистровую адресацию. Поскольку при индексной адресации в поле А_Снаходится полноразрядный адрес ячейки памяти, играющий роль базы, длина этого поля больше, чем при базовой регистровой адресации. Тем не менее вычисление исполнительного адреса операнда производится идентично.
Блочная адресация

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

11. Законы Амдала и Густафсона.

DOP (Degree Of Parallelism)

Степень параллелизма программы – D(t) – число процессоров, участвующих в исполнении рограммы в момент времени t

DOP зависит от алгоритма программы, эффективности компиляции и доступных ресурсов при исполнении

График D(t) – профиль параллелизма программы

 

T(n) – время исполнения программы на n процессорах

T(n)<T(1), если параллельная версия алгоритма эффективна

T(n)>T(1), если накладные расходы (издержки) реализации параллельной версии алгоритма чрезмерно велики

Speedup

Ускорение за счёт параллельного выполнения

S(n) = T(1) / T(n)

Efficiency

Эффективность системы из n процессоров

E(n) = S(n) / n

Случай S(n)=n – линейное ускорение – масштабируемость (Scalability) алгоритма (возможность ускорения вычислений пропорционально числу процессоров)

Случай S(n)>n – суперлинейное ускорение (например, из-за большего коэффициента кеш-попаданий)

 

Закон Амдала

Gene Amdahl (1967)

f – доля последовательной части программы

1-f – доля распараллеливаемой части программы

 

 

Практические ограничения ускорения

Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений:

«В случае, когда задача разделяется на несколько частей, суммарное время ее выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». Если разделяемая часть кода f может быть равномерно формально распределена по n процессорам, то закономерность может быть записана, как представлено на рис. 1.

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

 

Закон Густафсона

Единственная известная гипотеза о возможности преодоления описанных ограничений была высказана в 1988 году Джоном Густафсоном, но она не распространяется на подмножество фиксированных задач. На основании полученного опыта Густафсон пришел к выводу, что при построении более мощных систем пользователи стремятся не сократить время работы текущей версии задачи, а перейти к новой версии, обеспечивающей более высокое качество решения:

 

S(P)= P – l(P – 1), где P – число процессоров, S – ускорение, l – часть кода, не поддающаяся распараллеливанию.

 

Закон масштабируемого ускорения (Scaled Speedup):

 

Допустим, некоторую конструкцию можно рассчитать методом конечных элементов, и в таком случае, чем меньшим берется размер элемента, тем выше будет точность. Сегодня идеи Густафсона, связанные с совершенствованием методов коммуникации между узлами, реализуются в компании Massively Parallel Technologies (MPT), где, кстати, работает и сам Амдал. Допустимо сказать, что эти методы позволяют преодолеть ограничения закона, названного его именем, но только косвенно.

 

Принцип замены простых задач более сложными, предложенный Густафсоном, скорее экзотика, чем повседневная практика, поэтому в массовых приложениях, на которые рассчитываются многоядерные процессоры, действует закон Амдала.

 

Правила старшинства логических операций.

1 Отрицание — логическое действие первой ступени.

2 Конъюнкция — логическое действие второй ступени.

3 Дизъюнкция — логическое действие третьей ступени.

 

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

 

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

 

 

Двоичная таблица сложения Двоичная таблица

умножения

 

0+0=0 0*0=0

0+1=1+0=1 0*1=1*0=0

1+1=10 1*1=1

1+1+1=11 1*1*1=1

Сложение в обратных кодах

А - положительное, а В — отрицательное, по модулю больше А.

В этом случае мы просто складываем числа А и В. Результат получаем, как обычно, в обратном коде:

13₁₀ = 0000 1101₂ (ПК/ОК)

−23₁₀ = 1001 0111₂ (ПК) = 1110 1000₂ (ОК)

(13 + (−23))₁₀ = 1111 0101₂ (ОК) = 1000 1010₂ (ПК) = −10₁₀