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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Зміст

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

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

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


Регістри

Номер

Під час запису (по шині С)

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

000

0

Rg 0

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

Rg 0

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

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

Temp 0 = 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);

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

  • Застосувати конвейеризацию;

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

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
92.4кб. | скачати


Схожі роботи:
Лінійне програмування симплекс методом Данцига
Рішення задач лінійного програмування симплекс методом
Рішення задачі лінійного програмування симплекс методом
Розвязання задач графічним методом методом потенціалів методом множників Лангранжа та симплекс-методом
Рішення задач симплекс методом
Лінійне програмування 2
Лінійне програмування
Лінійне програмування
Лінійне та нелінійне програмування
© Усі права захищені
написати до нас