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

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

скачати

Зміст
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
Скорочення:
КОП - код команди
Rx - регістр приймач
Ry - регістр джерело 1
Rz - регістр джерело 2
address - 8-бітний адресу
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

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

 
  P
C
Підпис: 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);
§ Перейти від мікропрограмного управління до управління на основі жорсткої логіки;
§ Застосувати конвейеризацию;
§ Що-небудь распараллеліть.
Додати в блог або на сайт

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

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


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