Вход

Линейное программирование симплекс-методом Данцига

Реферат по программированию
Дата добавления: 06 сентября 2010
Язык реферата: Русский
Word, rtf, 1 Мб (архив zip, 121 кб)
Реферат можно скачать бесплатно
Скачать
Данная работа не подходит - план Б:
Создаете заказ
Выбираете исполнителя
Готовый результат
Исполнители предлагают свои условия
Автор работает
Заказать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу



Содержание


1. Постановка задачи

2. Форматы команд и их кодировка

3. Структурная схема процессора

4. Регистры

5. АЛУ

6. Формат микрокоманд

7. Микрокод

8. Кодировка микрокода

9. Примеры выполнения команд

10. Основные сигналы и регистры процессора

11. Примеры программ

12. Определение производительности



Постановка задачи


Синтезировать структуру простого магистрального процессора с одним АЛУ, выполняющего 8 заданных команд. Разработать формат команд, кодировку команд. Разработать структурную схему процессора, функциональные схемы всех блоков процессора, функциональную схему процессора в целом с указанием всех шин и управляющих сигналов.

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

Определить максимальную тактовую частоту процессора. Определить производительность процессора в операциях в секунду (IPS), а также выраженную в числе выполняемых тестовых программ в секунду. Указать способы повышения производительности процессора.

Характеристика процессора

Простой процессор магистрального типа с одноблочным универсальным АЛУ.

Разрядность регистров РОН и АЛУ процессора - 8 бит.

Число РОН - 4.

Адресуемая память - 256 слов.

Устройство управления - микропрограммное с ПЗУ микропрограмм.

Способ выполнения команд – последовательное выполнение или JMP или JC.

Адресация памяти - прямая.

Арифметика в дополнительном коде.

Вариант: 54 = «2 2 2 3»

Без использования непосредственной адресации.

3х-адресные команды.

Операции АЛУ: NOP, ADD + SHRA, NAND.

Состав команд: LD, ST, ADD, SHR + JC, DEC, SUB, NAND.


Форматы команд и их кодировка


Коды команд


КОП

Команда

Действие

000

ADD Rx,Ry,Rz

Rx=Ry+Rz

сложение

001

NAND Rx,Ry,Rz

Rx=!(Ry&Rz)

И-НЕ

010

SHR Rx,Ry

Rx=Ry/2

арифметический сдвиг вправо

011

JC address

jmp on carry

условный переход по переносу

100

DEC Rx,Ry

Rx=Ry-1

декремент (уменьшение на 1)

101

SUB Rx,Ry,Rz

Rx=Ry-Rz

вычитание

110

LD Rx,address

Rx=Mem(address)

загрузка из ОЗУ в регистр

111

ST Ry,address

Mem(address)=Rx

запись из регистра в ОЗУ


Формат команд


ADD Rx,Ry,Rz

КОП

Rx

Ry

Rz

не используется

0

0

0

x

x

y

y

z

z









NAND Rx,Ry,Rz

КОП

Rx

Ry

Rz

не используется

0

0

1

x

x

y

y

z

z









SHR Rx,Ry

КОП

Rx

Ry

не используется

0

1

0

x

x

y

y











JC address

КОП

не использ.

address

0

1

1






a

a

a

a

a

a

a

a




DEC Rx,Ry

КОП

Rx

Ry

не используется

1

0

0

x

x

y

y











SUB Rx,Ry,Rz

Сокращения:


КОП – код команды

Rx – регистр приемник

Ry – регистр источник 1

Rz – регистр источник 2

address – 8-битный адрес

КОП

Rx

Ry

Rz

не используется

1

0

1

x

x

y

y

z

z









LD Rx,address

КОП

Rx

не исп.

address

1

1

0

x

x




a

a

a

a

a

a

a

a


ST Rx,address

КОП

не исп

Ry


address

1

1

1



y

y


a

a

a

a

a

a

a

a


Структурная схема процессора

P

C



Регистры


Номер

При записи (по шине С)

При чтении (по шине A и B)

000

0

Rg0

программно-доступные регистры

Rg0

программно-доступные регистры

001

1

Rg1

Rg1

010

2

Rg2

Rg2

011

3

Rg3

Rg3

100

4

Temp0

Temp0

101

5

PC

PC

110

6

IR_HI (старшая часть IR)

IR

константа 1

111

7

IR_LO (младшая часть IR)

IR_LO


При чтении старшей части регистра команд, на шину A или B поступает единичная константа (00000001). Это вполне допустимо, т.к. старшая часть регистра команд имеет свои выходы из блока регистров: (КОП, Rx, Ry, Rz). Младшая часть регистра команд поступает на шины A или B в неизменном виде, т.к. в некоторых командах процессора в младшей части регистра команд находиться 8-битный адрес. Единичная константа применяется при инкрементировании счетчика команд, а также для получения константы -1 = 11111111 (см. микрокод для команды DEC).

Разрядность РОН (регистры общего назначения) – 8 бит

Разрядность PC (program counter) – 8 бит

Разрядность IR (регистр команд) – 16 бит (доступно два регистра по 8 бит)




АЛУ



Структурная схема АЛУ и его связь с другими блоками машины показаны на рисунке. В состав АЛУ входят регистры Рг1 - Рг7, в которых обрабатывается информация , поступающая из оперативной или пассивной памяти N1, N2, ...NS; логические схемы, реализующие обработку слов по микрокомандам, поступающим из устройства управления.

Закон переработки информации задает микропрограмма , которая записывается в виде последовательности микрокоманд A1,A2, ..., Аn-1,An. При этом различают два вида микрокоманд: внешние, то есть такие микрокоманды, которые поступают в АЛУ от внешних источников и вызывают в нем те или иные преобразования информации (на рис. 1 микрокоманды A1,A2,..., Аn), и внутренние, которые генерируются в АЛУ и воздействуют на микропрограммное устройство, изменяя естественный порядок следования микрокоманд. Например, АЛУ может генерировать признаки в зависимости от результата вычислений: признак переполнения, признак отрицательного числа, признак равенства 0 всех разрядов числа др. На рис. 1 эти микрокоманды обозначены р1, p2,..., рm.

Результаты вычислений из АЛУ передаются по кодовым шинам записи у1, у2, ...,уs, в ОЗУ.

Функции регистров, входящих в АЛУ:

Рг1 - сумматор (или сумматоры) - основной регистр АЛУ, в котором образуется результат вычислений;

Рг2, РгЗ - регистры слагаемых, сомножителей, делимого или делителя (в зависимости от выполняемой операции);

Рг4 - адресный регистр (или адресные регистры), предназначен для запоминания (иногда и формирования) адреса операндов и результата;

Ргб - k индексных регистров, содержимое которых используется для формирования адресов;

Рг7 - i вспомогательных регистров, которые по желанию программиста могут быть аккумуляторами, индексными регистрами или использоваться для запоминания промежуточных результатов.


Формат микрокоманд


MIR – Microinstruction register – регистр микрокоманд (24 bit)

A

A MUX

B

B MUX

C

C MUX

RD

WR

ALU

COND

JMP ADDRESS


























A, B, C – номер регистра для осуществления чтения (A, B) или записи (C)

A MUX, B MUX, C MUX – откуда брать номер регистра

(0 – из команды IR, 1 – из микрокоманды MIR)

RD – чтение из ОЗУ

При этом адрес памяти берется с шины А, а результат подается на шину С

WR – запись в ОЗУ

При этом адрес памяти берется с шины А, а данные - с шины B

ALU – код операции АЛУ


КОП АЛУ

Операция АЛУ

00

NOP

01

ADD

10

SHRA

11

NAND


COND – условие для определения адреса следующей выполняемой микрокоманды


COND

Куда переходим

00

NEXT

на следующую микрокоманду

01

DECODE

декодирование команды, Address = [KOP]100

10

JMP

безусловный переход

11

JC

условный переход по переносу (Carry Flag)


JMP ADDRESS – адрес в памяти микропрограмм, куда осуществляется переход



Микрокод


Адрес

Микрокоманда

Пояснение

0

1

2

3

IR_HI = NOP(PC); READ

PC = ADD(PC, IR_HI)

IR_LO = NOP(PC); READ

DECODE

чтение старшего слова команды

переход к следующему слову (PC = PC + 1)

чтение младшего слова команды

декодирование считанной команды


ADD Rx, Ry, Rz


4

Rx = ADD(Ry, Rz); JMP 62

сложение содержимого регистров


NAND Rx, Ry, Rz


12

Rx = NAND(Ry,Rz); JMP 62

И-НЕ для содержимого регистров


SHR Rx, Ry


20

Rx = SHR(Ry); JMP 62

арифметич. сдвиг содержимого регистра


JC address


28

29

30

Temp0 = NOP(Temp0); JC 30

JMP 62

PC = NOP(IR_LO); JMP 0

организация условного перехода

если условие не выполнилось, то завершить

иначе записать в PC новый адрес из IR_LO


DEC Rx, Ry


36

37

38

Temp0 = SHR(IR_HI)

Temp0 = NAND(Temp0, Temp0)

Rx = ADD(Ry,Temp0); JMP 62

Temp0 = 0 (00000001  00000000)

Temp0 = -1 (11111111)

Rx = Ry + Temp0 = Ry + (-1)


SUB Rx, Ry, Rz


44

45

46

47

48

Temp0 = SHR(IR_HI)

Temp0 = ADD(Temp0, Rz)

Temp0 = NAND(Temp0, Temp0)

Temp0 = ADD(Temp0, IR_HI)

Rx = ADD(Ry, Temp0); JMP 62

Temp0 = 0 (00000001  00000000)

Temp0 = 0 + Rz = Rz

инвертировать Temp0 = Rz

Temp0 = ( ! Rz) + 1

Rx = Ry + (-Rz)


LD Rx, address


52

Rx = NOP(IR_LO); READ; JMP 62

чтение из ОЗУ (шина A – адрес)


ST Ry, address


60

61


Temp0 = NOP(Ry)

Temp0 = NOP(IR_LO, Temp0); WRITE; JMP 62

Temp0 = Ry (данные на шину B)

запись в ОЗУ

(шина A – адрес, шина B - данные)

End:



62

PC = ADD(PC, IR_HI); JMP 0

увеличение счетчика команд (PC=PC+1)


Кодировка микрокода


DEPTH = 64; % количество слов %

WIDTH = 24; % размер слова в битах %


ADDRESS_RADIX = DEC; % система счисления для адреса %

DATA_RADIX = BIN; % система счисления для данных %


CONTENT

BEGIN

[0..63] : 0; % по умолчанию везде нули %


% Инициализация %

0: 101100011101100000000000; % IR_HI = NOP(PC); READ %

1: 101111011011000100000000; % PC = ADD(PC, IR_HI) %

2: 101100011111100000000000; % IR_LO = NOP(PC); READ %

3: 000100011001000001000000; % DECODE %


% ADD Rx, Ry, Rz %

4: 000000000000000110111110; % Rx = ADD(Ry, Rz); JMP 62 %

% NAND Rx, Ry, Rz %

12: 000000000000001110111110; % Rx = NAND(Ry,Rz); JMP 62 %

% SHR Rx, Ry %

20: 000000000000001010111110; % Rx = SHR(Ry); JMP 62 %


% JC address %

28: 100110011001000011011110; % Temp0 = NOP(Temp0); JC 30 %

29: 100110011001000010111110; % JMP 62 %

30: 111110011011000010000000; % PC = NOP(IR_LO); JMP 0 %


% DEC Rx, Ry %

36: 110100011001001000000000; % Temp0 = SHR(IR_HI) %

37: 100110011001001100000000; % Temp0 = NAND(Temp0, Temp0) %

38: 000010010000000110111110; % Rx = ADD(Ry,Temp0); JMP 62 %


% SUB Rx, Ry, Rz %

44: 110100011001001000000000; % Temp0 = SHR(IR_HI) %

45: 100100001001000100000000; % Temp0 = ADD(Temp0, Rz) %

46: 100110011001001100000000; % Temp0 = NAND(Temp0, Temp0) %

47: 100111011001000100000000; % Temp0 = ADD(Temp0, IR_HI) %

48: 000010010000000110111110; % Rx = ADD(Ry, Temp0); JMP 62 %


% LD Rx, address %

52: 111100010000100010111110; % Rx = NOP(IR_LO); READ; JMP 62%


% ST Ry, address %

60: 000000011001000000000000; % Temp0 = NOP(Ry) %

61: 111110011001010010111110; % Temp0 = NOP(IR_LO, Temp0);

WRITE; JMP 62 %


62: 101111011011000110000000; % PC = ADD(PC, IR_HI); JMP 0 %


END ;



Примеры выполнения команд


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


Основные сигналы и регистры

Сокращение

Примечание

CLOCK

синхронизирующий сигнал

C_SEL[2..0]

номер регистра выбранного в качестве приемника

A_SEL[2..0]

номер регистра выбранного в качестве источника 1

B_SEL[2..0]

номер регистра выбранного в качестве источника 2

Rx[2..0]

номер регистра приемника из IR (регистра команд)

Ry[2..0]

номер регистра источника 1 из IR (регистра команд)

Rz[2..0]

номер регистра источника 2 из IR (регистра команд)

MIR_A[2..0]

номер регистра приемника из MIR (р-ра микрокоманд)

MIR_B[2..0]

номер регистра источника 1 из MIR (р-ра микрокоманд)

MIR_C[2..0]

номер регистра источника 2 из MIR (р-ра микрокоманд)

AMUX

Откуда брать номер регистра (0 – из IR, 1 – из MIR)

Эти сигналы управляют соответствующими мультиплексорами.

BMUX

CMUX

A_bus[7..0]

Данные на шинах источниках, выходящих из блока регистров

B_bus[7..0]

C_ALU[7..0]

Результат выходящий из АЛУ

C_RAM[7..0]

Данные, считанные из ОЗУ

C_bus[7..0]

Выбранные данные для записи (С_ALU или C_RAM)

RD

сигнал чтения из ОЗУ

WR

сигнал записи в ОЗУ

KOP_ALU[1..0]

код операции АЛУ (поступает из MIR)

COND[1..0]

определение следующей микрокоманды (из MIR)

CBL_SEL[1..0]

результат работы Control Branch Logic (логика управления ветвлением) – определяет следующую микрокоманду

CF

флаг переноса, поступающий из АЛУ в Control Branch Logic

JMP_ADR[5..0]

адрес следующей микрокоманды (из MIR)

MIR[23..0]

полное значение регистра микрокоманд (24 бит)

PC

программный счетчик (адрес в ОЗУ)



Примеры программ


ПРИМЕР 1


DEPTH = 256; % Memory depth and width are required %

WIDTH = 8; % Enter a decimal number %


ADDRESS_RADIX = DEC; % Address and value radixes are optional %

DATA_RADIX = BIN; % Enter BIN, DEC, HEX, or OCT; unless %


CONTENT

BEGIN

%-------------------%

0: 11001000; % LD Rg1, [6] %

1: 00000110;


2: 11010000; % LD Rg2, [7] %

3: 00000111;


4: 00011011; % ADD Rg3, Rg1, Rg2 %

5: 00000000;


6: 00010110; % const 22 (DEC) %

7: 00100001; % const 33 (DEC) %

END ;



ПРИМЕР 2


DEPTH = 256; % Memory depth and width are required %

WIDTH = 8; % Enter a decimal number %


ADDRESS_RADIX = DEC; % Address and value radixes are optional %

DATA_RADIX = BIN; % Enter BIN, DEC, HEX, or OCT; unless %


CONTENT

BEGIN

%-----------------%

0: 11001000; % LD Rg1, [10] %

1: 00001010;


2: 01010010; % SHR Rg2, Rg1 %

3: 00000111;


4: 01100000; % JC 8 %

5: 00001000;


6: 10010010; % DEC Rg2, Rg1 %

7: 00000000;


8: 11100010; % ST Rg1, [10] %

9: 00001010;


10: 00000001; % const = 1 %

END ;


Значения основных сигналов и содержимое основных регистров на каждом такте выполнения данных примеров программ приведены в виде временных диаграмм на электронном носителе.


Определение производительности

Среднее количество микрокоманд при выполнении команды процессора можно приблизительно оценить как 4 + 17/8 + 1 = 7 микрокоманд на команду процессора. Таким образом, при максимальной тактовой частоте в 33,3 МГц средняя производительность процессора составит 4, 7 MOPS (или 33,3 М ?ops / сек).


Тестовая программа

Количество команд процессора

Количество микрокоманд

Время выполнения, нс

N / сек

ПРИМЕР 1

3

18

540

1851851

ПРИМЕР 2

5

34

1020

980398



Повысить производительность процессора можно одним из следующих способов:

  • Увеличить разрядность шины-приемника с 8 до 16 бит, и считывать команду из ОЗУ не за три такта, а за один;

  • Увеличить функциональность АЛУ, при этом можно будет сократить длину микрокода для некоторых команд (особенно для SUB и DEC);

  • Перейти от микропрограммного управления к управлению на основе жесткой логики;

  • Применить конвейеризацию;

  • Что-нибудь распараллелить.

© Рефератбанк, 2002 - 2017