КЛ_АВС

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

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

Наиболее привычным базисом является следующий набор функций: инверсия, дизъюнкция и конъюнкция.

Законы алгебры логики:

Если:

xV1=1; x*0=0; xVx=1; x*x=0; xV0=x; x*1=x;

1.Закон коммутативный: x1*x2 = x2+x1

2.Закон ассоциативный: (x1*x2)x3=(x1*x3)*x2=x1*(x2*x3)

3.Закон дистрибутивный: x1(x2Vx3)=x1*x2Vx1x3

x1Vx2x3=(x1Vx2) (x1Vx3)

4.Закон поглощения: в дизъюнктивной форме конъюнкция меньшего ранга поглощает все конъюнкции большего ранга:

21

Техническая интерпретация логических функций.

По логическим выражениям проектируются схемы ЭВМ. При этом следует придерживаться следующей последовательности действий:

1.Словесное описание работы схемы;

2.Формальное описание работы схемы (таблица истинности, таблица Карно);

3.Запись логических функций в нормально-дизъюнктивной (конъюнктивной) совершенной нормализованной форме по таблице истинности;

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

5.Построение схемы устройств.

6.Проверка работоспособности полученной схемы.

22

2. Функциональная организация компьютеров.

Машина Тьюринга

Основы построения электронных вычислительных машин в их современном понимании были заложены в 30-е – 40-е годы прошлого века видными учеными: английским математиком Аланом Тьюрингом и американцем венгерского происхождения Джоном (Яношом) Нейманом.

В1936 году А. Тьюринг сформулировал понятие абстрактной вычислительной машины. Одновременно с ним, хотя и не в столь явной форме, это же сделал Э. Пост (США). Хотя машина Тьюринга (МТ) не стала реально существующим устройством, она до настоящего времени постоянно используется в качестве основной модели для выяснения сущности таких понятий, как “вычислительный процесс”, “алгоритм”, а также для выяснения связи между алгоритмом и вычислительными машинами.

Основные положения машины Тьюринга

1.Машина Тьюринга (рис.1.1) имеет конечное число знаков si, образующих внешний алфавит, в котором кодируются сведения, подаваемые

вМТ, а также вырабатываемые в ней. Среди знаков имеется пустой знак

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

Взависимости от поданной начальной информации (содержащихся на ленте знаков) возможны два случая:

после конечного числа тактов машина останавливается (имея

информацию ), подавая сигнал об остановке. В этом случае МТ применима к информации и перерабатывает ее в информацию ;

остановка никогда не наступает. В этом случае МТ не применима к начальной информации .

Внешняя память

2. В каждый момент обозревается лишь одна ячейка ленты (памяти). Переход может осуществляться лишь к соседней ячейке (R – вправо, L – влево, N – нет перехода (остаться)). Переход к произвольной ячейке производится путем последовательного перебора всех ячеек, разделяющих текущую и необходимую ячейки.

На каждом отдельном такте команда предписывает только замену единственного знака si, хранящегося в обозреваемой ячейке, каким-либо другим знаком sj.

3. Логический блок МТ имеет конечное число состояний {qi} i=1…m. Знаки R, L, N, q1,…,qm – внутренний алфавит машины.

Переработанный знак sj и операция перехода P(t+1) являются функцией si

и qk :

si(t+1)=f(si (t), qk). P(t+1)= (si(t), qk)

Программа для МТ определяется тройкой {si,P,q}t+1.

Пример вычисления логической функции y=x y

Перед началом работы машина Тьюринга находится в состоянии q1 считывания первого операнда.

Данная МТ применима к исходной информации. Останов – состояние q4. Значение si в ячейке y не меняется (сохраняется результат).

Если программа для МТ будет определена таблицей переходов

то данная МТ будет не применима к исходной информации. В состоянии q4 значение si в ячейке y постоянно меняется на противоположное.

Автомат Неймана

По принципу обработки информации вычислительное устройство, предложенное Нейманом (автомат Неймана – АН), существенно отличается от машины Тьюринга.

24

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

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

В автомате Неймана число одновременно обрабатываемых ячеек может неограниченно расти, оставаясь в каждый момент конечным.

Элемент Неймана (ЭН) – это устройство, которое на каждом такте пребывает в одном из конечного числа состояний ri R, образующих его алфавит. ЭН имеет два входных канала: левый и правый; по каждому из них на такте t также поступает по одному состоянию из R (рис.).

rm

ri rj

Элемент Неймана

Элемент реализует функцию zt+1 = (ri, rj, rm)t, то есть в такте t+1 переходит в состояние z.

Состояние называется спокойным, если выполняется условие (r, r, r) = r, то есть ЭН, пребывающий в состоянии покоя, может быть выведен из него только при условии, что хотя бы по одному каналу поступает возбуждающее состояние.

Впредь полагается, что среди R существует специально выделенное состояние покоя Ф.

Состояния ЭН в момент времени t определяют конфигурацию АН (рис) в момент t: K(t).

Структура автомата Неймана

Функционирование АН – это переход от состояния К(t) к состояниям

K(t+1), K(t+2), …

За один такт состояние может менять большое число ЭН, что фактически приводит к параллельной обработке информации.

Принципы построения современных ЭВМ

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

25

учеными - американским математиком и физиком Джоном фон Нейманом и советским инженером и ученым Сергеем Лебедевым.

Сущность этих принципов состояла в следующем:

1.Двоичная система счисления - компьютеры на электронных элементах должны работать не в десятичной, а в двоичной системе счисления;

2.Принцип программного управления и хранимой в памяти программы - программа должна размещаться в одном из блоков компьютера - в запоминающем устройстве (первоначально программа задавалась путем установки перемычек на коммутационной панели); Это обстоятельство приводит к следующим важным последствиям:

a)промежуточные результаты вычислений, константы и другие числа могут размещаться в том же ЗУ, что и программа;

b)числовая форма записи программы позволяет машине производить операции над величинами, которыми закодированы команды программы.

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

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

организации памяти, а доступ к командам и данным осуществляется по адресу (принцип адресности);

5.Арифметическое устройство компьютера конструируется на основе схем, выполняющих операцию сложения.

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

Самой важной отличительной чертой модели фон Неймана был и остается принцип единой линейной памяти, которая адресуется последовательными адресами и в которой команды неотличимы от

данных.

26

3. Структурная организация классической ЭВМ

Основные функции компьютера заключаются в обработке, хранении и передаче информации. Поэтому функциональная структура ЭВМ состоит из процессора (центральное процессорное устройство - ЦПУ), памяти, устройств ввода-вывода и подсистем управления и связи между всеми отдельными модулями ЭВМ (интерфейсы).

ЦПУ

ЕАЛУ

СИСТЕМНЫЙ ИНТЕРФЕЙС

Рисунок 1 - Структура ЭВМ

Центральное процессорное устройство – мозг компьютера, его задача выполнять программы (выполнять алгоритм решения задачи, согласно программе вычислений).

Процессор состоит из нескольких частей:

Устройство Управления – отвечает за вызов команды из памяти, определение типа команды и реализацию микропрограммного исполнения команды;

27

Арифметико Логическое Устройство – выполняет все операции по обработке всех видов данных в том числе арифметические и логические операции;

Внутримашинный интерфейс (интерфейс) – осуществляет связь и регулирует трафик внутри процессора;

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

Внастоящее время все эти модули удается сделать в виде единой интегральной микросхемы – микропроцессора

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

УУформирует адреса операндов и управляющие сигналы для их чтения из ЗУ и передачи в арифметико-логическое устройство. После считывания операндов устройство управления по коду операции, содержащемуся в команде, выдает в АЛУ сигналы на выполнение операции. Полученный результат записывается в ЗУ по адресу приемника результата под управлением сигналов записи. Признаки результата (знак, наличие переполнения, признак нуля и так далее) поступают в устройство управления, где записываются в специальный регистр признаков. Эта информация может использоваться при выполнении следующих команд программы, например команд условного перехода.

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

Устройства вывода представляют результаты обработки информации в форме, удобной для восприятия (индикаторы, печатающие устройства, графопостроители, экран дисплея и т.п.)

28

Память хранит информацию, передаваемую из других устройств, в том числе поступающую извне через устройство ввода. Память машины, обычно, состоит из двух частей: быстродействующей основной или оперативной памяти (ОП) и сравнительно медленной, но способной хранить большой объем информации внешней памяти (ВП). Непосредственно в вычислительном процессе участвует только ОП, только после окончания отдельных этапов обработки информации и переходе к следующей стадии вычислений из внешней памяти в ОП передается очередная порция информации. ОП обладает сложной иерархической структурой – несколько уровней КЭШ-памяти (более быстродействующей чем ОП, но меньшей по объему), сама ОП, интерфейсы памяти. Ячейки оперативной памяти нумеруются числами 0, 1, 2,......, называемыми адресом ячеек. Если необходимо записать в память слово, следует подать на шину адреса памяти сигналы соответствующие адресу нужной ячейки, и подать само слово на шину записи. Для того чтобы получить содержимое хранимого в ячейке слова, в память посылается адрес и она выдает по шине чтения копию слова. Центральный процессор взаимодействует с ОЗУ посредством 3-х шин: шина адреса, по которой передается адрес нужной ячейки памяти; шина чтения, предназначенная для передачи данных из выбранной ячейки в CPU; шина записи, предназначенная для передачи данных из CPU и записи их в выбранную ячейку памяти.

Физический адрес памяти (есть еще логический, но об это позже), который процессор выдает на шину адреса всегда считается адресом байта. Такое представление памяти называется адресным пространством. Следовательно, с точки зрения процессора память имеет очень простую организацию, показанную ниже. Здесь ОЗУ содержит 4096 ячеек памяти, каждая из которых занимает по 20 разрядов (бит).

Рисунок 2 - Структура памяти простейшего компьютера Из этих 20-ти разрядов 12 используются для представления адреса, а

оставшиеся 8 (байт) – для хранения данных (понятно, что в этом случае шина данных должна иметь 8 линий, разрядов). Следовательно, объем памяти

29

(адресное пространство) этого ОЗУ равен 4096 * байт = 4096 байт = 4 Кбайт. Конечно этого очень мало для современного микропроцессора. В общем случае минимальный адрес равен 0, а максимальный N – 1, число N определяется разрядностью шины адреса (ширина, количество проводников шины). Таким образом, адресное пространство равно 2N, например для процессора Pentium с N = 32 составляет 4 Гбайт. Если шина данных процессора имеет 16 или 32 линии, то за одно обращение к памяти можно передать два или четыре байта данных, что существенно увеличивает производительность процессора.

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

Особенности современных ЭВМ

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

Индексные регистры. Позволяют формировать адреса памяти добавлением содержимого указанного регистра к содержимому поля команды.

Этот принцип впервые реализован в 1949г. в ЭВМ Манчестерского университета и использован в 1953г. фирмой Electro Data Corporation при производстве ЭВМ Datatron.

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

Pegasus фирмы Ferranti (1956г.).

Представление данных в форме с плавающей точкой. Представление данных в виде мантиссы и порядка и выполнение операций над ними было реализовано в 1954г. в вычислительных машинах NORC и 704 фирмы IBM.

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

выполнением прерванной команды, запоминается в определенной области. Этот принцип впервые был применен в 1954г. в машине Univac1103.

30