Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Арифметика ЕОМ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2009
Тип роботи:
Інші
Предмет:
Інформаційні технології
Група:
КН-30
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ УКРАНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
ІНСТИТУТ КОМП’ЮТЕРНИХ НАУК ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
Курсове проектування
На тему:
Арифметика ЕОМ
Зміст
Розділ І: Розробка структури операційного автомату на основі заданих алгоритмів…………………………………………….……………..……………….3
Операційний автомат АЛП – опис дії для заданої структури…...…………3
Мікропрограми ділення……………………………………………...……….6
2.1. Структура і мікропрограми АЛП для ділення чисел з фіксованою крапкою…………………………...……………………………………………...6
2.2 Ділення з нерухомим діленим і зсуваючим вправо дільником…..……7
2.3 Ділення з нерухомим дільником і зсувом вліво діленого……………...7
2.4 Алгоритм ділення з нерухомим дільником з відновленням залишку……………………………………………………………………………....7
2.5 Алгоритм ділення з нерухомим дільником без відновлення залишку…………………………………………………………………………..…...9
Розділ ІІ: Управляючі автомати……………………………………………….......11
Автомат з жорсткою логікою, граф автомата Мура та його функціональна схема………………………………………………………11
Автомати з програмованою логікою, структура мікропрограм, адресація…………………………………………………………………....15
Мікропрограмний автомат з природною адресацією, поле мікрооперацій, коди…………………………………………………….....17
3.1. Природна адресація…………………………………………………...17
3.2. Кодування та поле мікро операцій…………………………………..19
Структурна схема керуючого автомату………………………………….21
Розробити модель інтелектуального агента на основі операційного автомату, що лежить в основі Internet………………………………........24
5.1. Технологія інтелектуальних агентів в INTERNET…………………24
Розділ І: Розробка структури операційного автомату на основі заданих алгоритмів
Операційний автомат АЛП – опис дії для заданої структури.
Сутність обробки інформації у цифровій формі полягає у виконанні заданої послідовності найпростіших арифметичних і логічних операцій над числами. У цифровій апаратурі основним пристроєм, у якому безпосередньо виконується обробка, є процесорний пристрій. Процесорний пристрій (як і будь-який інший складний цифровий пристрій) синтезується у вигляді поєднання двох пристроїв: операційного (арифметико-логічного) і керуючого. Структура процесорного пристрою показана на рис. 1.
Арифметико-логічний пристрій (АЛП) призначений для виконання арифметичних і логічних операцій над числами (словами), що надходять до нього, за сигналами з пристрою керування. Основні операції, що виконує АЛП – це додавання та множення.
Пристрій керування призначений для організації процесу обчислень. Він координує дії АЛП, генеруючі у визначеній часовій послідовності керуючі сигнали, під дією яких у вузлах АЛП виконуються необхідні операції.
Формування керуючих сигналів y1,…,yn (див. рис. 1) для виконання визначених мікрокоманд може залежати від стана вузлів АЛП, обумовленого сигналами x1,…,xn, які передаються по відповідних колах з виходів АЛП на входи керуючого пристрою. Керуючі сигнали y1,…,yn можуть залежати також від зовнішніх сигналів x+1,…,xL.…
Результати обробки, виконані у АЛП, знімають з його виходів z1,…,zm...
АЛП будують на основі багаторозрядного двійкового суматору, що виконує арифметичні операції, і регістрів для зберігання операндів (даних, що беруть участь в операціях) і результатів виконання арифметичних операцій. У якості додаткових елементів АЛП містить у собі канали (шини) для передавання інформації, мультиплексори для комутації каналів, шифратори і дешифратори, лічильники, а також логічні елементи різних типів для виконання необхідних логічних операцій. Двійковий суматор у сукупності з деякими додатковими логічними елементами часто називають арифметико-логічним колом або операційним пристроєм. АЛК, за принципом побудови, є комбінаційним пристроєм, тому що воно не має в своєму складі власних запам’ятовуючих пристроїв.
Рис.1. Схема процесорного пристрою.
Спрощена блок-схема АЛП подана на рис. 2.
Рис. 2. Спрощена схема АЛП.
Всі дані в арифметико-логічне коло і накопичувальний регістр (акумулятор) надсилаються через регістр даних. Накопичувальний регістр має розмір, що відповідає довжині машинного слова. Для того, щоб скласти два двійкових числа, одне число запам'ятовується у накопичувальному регістрі, а інше - запам'ятовується у регістрі даних. Після додавання сума двох чисел надходить у накопичувальний регістр, замінюючи вихідне двійкове число - операнд.
Процес функціонування АЛП розпадається на певну послідовність елементарних дій у його вузлах. Перелік таких елементарних дій містить у собі:
встановлення регістру в деякий стан;
інвертування вмісту розрядів регістру;
пересилку вмісту одного вузла в інший вузол (наприклад, пересилку числа з регістра в регістр);
зсув вмісту вузла (регістра) ліворуч або праворуч;
рахування, при якому число у лічильнику збільшується або зменшується на одиницю;
додавання;
перевірка на рівність вмісту регістра деякому числу (у разі виконання умов рівності результатом є логічна одиниця, у випадку невиконання - логічний нуль).
деякі логічні дії (порозрядна диз'юнкція, кон’юнкция і т.д.).
Кожна елементарна дія, виконувана у одному із вузлів АЛП протягом одного тактового періоду, називається мікрокомандою, а весь набір мікрокоманд, призначений для розв'язання визначеної задачі, - мікропрограмою.
Таким чином, якщо в АЛП передбачається можливість виконання n різних мікрооперацій, то з пристрою керування виходять n керуючих кіл, кожне з яких відповідає визначеній мікрооперації. І якщо в АЛП необхідно виконати деяку мікрооперацію, то досить із керуючого пристрою по певному керуючому колу подати в АЛП сигнал (наприклад, рівень логічної 1). Внаслідок того, що керуючий пристрій визначає мікропрограму, тобто які і у якій часовій послідовності повинні виконуватися мікрооперації, він одержав назву мікропрограмний автомат.
Існує два принципово різних підходи до проектування мікропрограмного автомату (керуючого пристрою): використання принципу схемної логіки або принципу програмованої логіки. Іноді ці принципи називають апаратною або програмною реалізацією цифрового автомату. У першому випадку, тобто при використанні принципу схемної логіки, у процесі проектування підбирається деякий набір цифрових мікросхем (частіше за все малого і середнього ступеню інтеграції) і визначається така схема з'єднання їх виводів, котра забезпечує необхідне функціонування. Пристрої, побудовані за таким принципом, здатні забезпечувати найвищу швидкодію при заданому типі технології елементів, однак такі пристрої завжди виходять вузькоспеціалізованими.
Використання принципу програмованої логіки припускає побудову деякого універсального пристрою на одній або на кількох мікросхемах великого ступеню інтеграції (ВІС). Необхідний алгоритм функціонування пристрою тут забезпечується розміщенням у його пам'яті деякої певної програми (або мікропрограми).
Якщо у пристрої, побудованому за принципом схемної логіки, усяка зміна або розширення набору виконуваних функцій тягне за собою його демонтаж і монтаж за новою схемою, то при використанні програмованої логіки така зміна досягається лише заміною програми, що зберігається у пам'яті, на нову. Тому в останні два десятиліття реалізація складних цифрових автоматів з програмованою логікою мала переважне поширення.
Мікропрограми ділення
2.1. Структура і мікропрограми АЛП для ділення чисел з фіксованою крапкою (Каган ст. 211, 213-219)
Ділення в ЕОМ звичайно зводиться до виконання послідовності віднімання дільника спочатку з діленого, а потім з часткових залишків, що утворилися в процесі ділення і зсуву часткових залишків.
Реалізувати ділення можна двома основними способами:
2.2 Ділення з нерухомим діленим і зсуваючим вправо дільником.
Цей спосіб ділення заснований на прямому копіюванні дій при ручному діленні. Структура АЛП для ділення має вигляд, який зображений у Додатку 1.
Початкове ділене X заноситься в PгX, а дільник Y – в старші розряди Pг1Y. Дільник зсувається вправо шляхом косої передачі з Pг1Y в Pг2Y і прямої передачі з Pг2Y в Pг1Y. Віднімання дільника виконується підсумувуванням додаткового коду дільника. Цифри частки залишків, які визначають по знаку часткових залишків, фіксується в регістрі Pг1Z шляхом послідовного занесення їх в молодший розряд Pг1Z і зсуву вмісту Pг1Z з допомогою косої передачі в Pг2Z і прямої з Pг2Z в Pг1Z.
Недоліком такого АЛП є подвійна довжина суматора і його регістрів.
2.3 Ділення з нерухомим дільником і зсувом вліво діленого.
Цей спосіб дозволяє будувати АЛП з суматором одиночної довжини (Додаток 2).
Тут нерухомий дільник Y зберігається в PгY, а ділене X, зсуваючись вліво відносно Y, знаходиться в двох регістрах: старші розряди X – в Pг1X, а молодші – в Pг2X. Ділення починається з зсуву вліво діленого X шляхом косої передачі його в PгCm і Pг3X і відповідних прямих передач в Pг1X. Далі на вхід суматора подається зсунуте вліво ділене, утворюється частковий залишок шляхом підсумовуванням додаткового коду дільника, і наступна цифра частки заноситься в звільнений при зсуві X розряд Pг2X.
Арифметично-логічний пристрій розглянутого типу широко застосовується для ділення.
2.4 Алгоритм ділення з нерухомим дільником з відновленням залишку.
1. Берутся модулі від діленого і дільника.
2. Початкове значення часткового залишку покладається рівним старшим розрядам діленого.
3. Частковий залишок подвоюється шляхом зсуву на один розряд вліво. При цьому в звільнений при зсуві молодший розряд часткового залишку заноситься наступна цифра діленого.
4. З зсунутого часткового залишку віднімається дільник і аналізується знак результату віднімання.
5. Наступна цифра модуля частки рівна 1, якщо результат віднімання додатній, і 0, якщо від’ємний. В останньому випадку значення остачі відновлюється до того, яке було до віднімання.
6. Пункти 3, 4 і 5 послідовно виконуються для одержання всіх цифр модуля частки.
7. Знак частки плюс, якщо знаки діленого і дільника однакові, в іншому випадку – мінус.
Розглянемо тепер більш детально ділення в АЛП з нерухомим дільником. Структурна схема АЛП дана у Додатку 3.
Схема містить: суматор Cm; вхідний регістр Pг1 для збереження дільника; вхідний регістр суматора PгA, в який поступає прямий або зворотній код дільника; вихідний регістр суматора PгCm, в якому утворюється частковий залишок; регістри діленого PгB (старші розряди) і Pг2 (молодші розряди); допоміжний регістр Pг2’ для зсуву діленого, тригери знаків діленого і дільника ТгЗн1 і ТгЗн2; лічильник циклів СчЦ для підрахунку числа одержаних цифр частки. Одержані в процесі ділення цифри частки заносяться в звільнені розряди Pг2’.
Мікропрограма ділення для випадку додатніх чисел приведена у Додатку 4. Пояснемо процедуру відновлення остачі.
Якщо віднімання дає від’ємний результат (См[0] = 1), то попередній частковий залишок, який зберігається в PгB, передається в PгCm, для чого попередньо обнулюється PгA. В PгCm прийом здійснюється з зсувом вліво на 1 розряд. Це забезпечує відновлення попереднього часткового залишку і зміщення його відносно дільника перед наступним відніманням.
Мікропрограма, яку ми розглядаємо, призначена для обробки додатніх чисел. А також її можна легко перетворити для обробки чисел з любими знаками, які представленні в прямому коді. Для цього треба внести такі зміни: після прийому операндів в PгB, Pг2 і Pг1 значення знакових розрядів X і Y передаються в тригер знака – відповідно ТгЗн1 і ТгЗн2. Потім в PгB [0] і Pг1 [0] заноситься 0, тобто виконується перехід до модулів X і Y. Розряд знаку частки встановлюється в 0 при ТгЗн1 = ТгЗн2 і в 1 в протилежному випадку.
Розглянутий метод ділення носить назву ділення з відновленням залишку. Недоліком цього методу є необхідність введення спеціального такту для відновлення залишку.
Звичайно в ЕОМ для ділення використовується другий метод – ділення без відновлення залишку.
2.5 Алгоритм ділення з нерухомим дільником без відновлення залишку. Пункти 1-3 співпадають з алгоритмом ділення з відновленням залишку.
4. З зсунутого часткового залишку віднімається дільник, якщо залишок додатній, і до зсунутого часткового залишку додається дільник, якщо залишок від’ємний.
5. Наступна цифра модуля частки рівна 1, якщо результат віднімання додатній, і 0, якщо від’ємний.
Пункти 6, 7 співпадають з попереднім алгоритмом.
Можна показати, що часткові залишки після виконання додавання при діленні без відновлення залишку одержуються такі самі, як і залишки після зсуву відновленого залишку при діленні з відновленням залишку.
Дійсно, оскільки зсув часткового залишку на один розряд вліво є еквівалентом множення його на два, одержимо: 2*a – b = 2*(a – b) + b, (6-5), де a – частковий залишок; b – дільник.
Аналогічно
2na = {…{[(a – b)*2 + b] + b}*2 + … + b}. (6-6)
Ділення без відновлення залишку завжди потребує для одержання одної цифри частки тільки додавання або віднімання з зсуву часткового залишку.
Мікропрограма ділення цілих додатніх чисел без відновлення залишку у своїй початковій частині співпадає з мікропрограмою ділення без відновлення залишку. Різниця з’являєтья після формування знаку частки. У Додатку 5 приведена частина мікропрограми ділення без відновлення залишку після мікрокоманди фіксації знаку частки.
Блок-схема показує, що поки невизначені всі цифри частки (СчЦ <> 0), в залежності від знаку часткового залишку або підсумовується Y (при См [0] = 1), або віднімається Y (при См [0] = 0). В одержаному новому частковому залишку аналізується знак і в ньому визначається цифра частки. Після завершення всіх циклів ділення (СчЦ = 0) видається реультат. При цьому якщо залишок від’ємний, то він відновлюється шляхом підсумуванням Y.
Ділення чисел, що представленні в залежності від знаку прямим доповнюючим кодом, можна зробити не переходячи до модулів. При цьому алгоритм ділення є подібним до розглянутих.
Відмінності заключаються в наступному (для випадку ділення без відновлення залишку):
1. Так як ділене і дільник можуть мати різні знаки, то дія з частковим залишком (додавання або віднімання Y) залежать від знаку залишку і дільника і визначаються наступною таблицею.
Знак залишку
Знак дільника
Дія
+
+
Віднімання Y
+
-
Додавання Y
-
+
Додавання Y
-
-
Віднімання Y
(Каган стр. 219)
Якщо знак залишку співпадає з знаком дільника, то zi = 1, інакше zi = 0.
2. Якщо X > 0 і Y < 0, то частку необхідно збільшити на одиницю.
Якщо X < 0 і Y > 0, то частку необхідно збільшити на одиницю у випадку залишку від ділення, яке не дорівнює нулю.
Якщо X < 0 і Y < 0, то частку необхідно збільшити на одиницю у випадку залишку від ділення, яка рівна нулю.
Ділення правильних дробів виконується так, як і ділення цілих. Різниця заключається тільки у тому, що ділене має, як правило, таку ж довжину, як дільник. Але можна допустити, що ділене має ще n молодших розрядів, які рівні нулю. Тоді стає ясно, що алгоритм ділення дробів нічим не відрізняється від алгоритму ділення цілих.
Розділ ІІ: Управляючі автомати
Автомат з жорсткою логікою, граф автомата Мура та його функціональна схема
Для організації роботи ЕОМ, як одна з її складових, необхідний керуючий автомат. У його функції входить формування керуючих сигналів, на основі деякого алгоритму для операційної частини ЕОМ.
Алгоритм управління системи задається кодом управління, що надходить в КА із зовнішнього середовища. Алгоритм управління ОА називається мікропрограмою і реалізується керуючим автоматом. Однією з основних проблем при створенні спеціалізованої ЕОМ є пошук компромісу між швидкодією, вартістю і універсальністю КА. Також важливим є час проектування і реалізації схеми КА.
Як відомо, КА з жорсткою логікою виграють за швидкодією перед автоматами з програмованою логікою, але мають жорстку структуру і не можуть бути змінені. ПЛІС дозволяють замінити весь пристрій конфігурований на мікросхему. Таким чином з'являється можливість створювати перепрограмовані КА з жорсткою логікою.
При синтезі керуючих автоматів на підставі графу мікропрограми будується граф абстрактного автомату. Його синтез здійснюється за допомогою формалізованих методів.
Є дві абстрактних моделі керуючих автоматів:
- Абстрактна модель автомату Мілі
Q[t+1]=X(Q[t],x[t])
Y[t+1]=б(Q[t],x[t])
Q[0]=Q0
- Абстрактна модель автомату Мура
Q[t+1]=X(Q[t],X[t])
Y[t+1]=б(Q[t])
Q[0]=Q0
функція переходів
функція виходів
визначення початкового стану
Якщо порівнювати ці дві моделі, то виявиться, що автомат Мілі більш економніший у апаратних затратах. Проте наявність ефекту перегонів при функціонуванні, це може призводити до збоїв. Автомат Мура, натомість, свою роботу не пов’язує з перегонами. Методика синтезу автомату є формалізована і може виконуватися комп’ютерною програмою.
Тому для подальшого синтезу надійного КА я буду використовувати модель автомату Мура. Для цього, насамперед, потрібно відобразити граф автомату.
граф автомату Мура (граф має стільки вершин, скільки станів автомат)
початкова і кінцева вершина об’єднується
на ребрах автомату простягаються дозволяючи сигнали:
Z – сигнал запису автомату
Х1 – повідомляючий сигнал, який надходить від ОБ
в інших вершин крім початкової і кінцевої простягаються номери станів і вихідні сигнали (Y1-Y3).
Стани автомату кодуються двійковим кодом, коди яких повинні відрвзнітися один від одного. Способів кодування є дуже багато. Проте є загальне правило, яке твердить, що число бітів повинне бути не менше, ніж мінімальне значення кількості станів. А саме:
N ≥ log2n
Де
N – число бітів;
n – число станів автомату;
Кожному біту коду стану відповідає тригер пам’яті.
Таблиця кодування
станів автомата Мура
Стан
Код станів
Q1
Q2
Q3
a1
0
0
0
a2
1
0
0
a3
1
0
1
a4
1
1
0
ЦА можна реалізувати на принципі «жорсткої логіки». Тобто, особливості станів автомату – за допомогою елементів пам’яті тригерів, функції переходів входів/виходів – за допомогою логічних елементів.
Властивості автоматів з жорсткою логікою:
максимально можлива швидкодія;
жорстка структура яка не передбачає внесення змін, потребує індивідуальної побудови для кожного варіанту закону функціонування. Ця властивість виступає як великий недолік.
Замалюємо абстрактну функціональну схему КА Мура:
де Q, X, Y і δ — відповідають визначенню автомату Мілі, а μ являється відображенням виду: μ : S → Y. Особливістю автомату Мура є те, що символ y(t) в присутній у ься у стані вихідному каналі увесь той час, поки автомат знаходисуществует все время пока автомат находится в состоянии Q(t).
Автомати з програмованою логікою, структура мікропрограм, адресація
Ще один підхід щодо реалізації ЦА базується на використанні пристроїв управління з програмованою логікою.
Властивості пристрою управління з програмованою логікою:
гнучкість і універсальність застосування, схема пристрою є постійною не змінюється при заміні мікропрограм, заміна мікропрограм передбачає лише перепрограмування пам’яті.
Швидкодія пристрою програмованої логіки суттєво поступається швидкодії пристроям з жорсткою логікою.
Зарисуємо узагальнену структуру.
МПУ – мікропроцесорний пристрій управління;
ОБ – операційний блок;
ПМК – пам'ять мікрокоманд;
Мікропрограми записуються в пам'ять в прямому вигляді, де слово відповідає одній мікрокоманді. В кожен такт виконується одна мікрокоманда. Будується на основі автомату Мура.
РГМК – регістр мікрокоманд, в якому відбувається зчитування;
КМК – код мікрокоманди в операційній частині;
А – адреса мікрокоманди;
ДМК – дешифратор мікрокоманд. На виході формуються символи управління y, які подаються на операційний блок;
ОБ – операційний блок. Він формує повідомлення сигналів х – сигналів про особливості проміжних результатів. Вони є вхідними для МПУ;
ПФАМК – пристрій формування адрес мікрокоманд. В кожен тактовий момент формує адресу наступної команди. Вона подається на РгАМК;
БКС – блок синхронізації, що синхронізує роботуМПУ;
КК – код команди;
Розглядаючи загальну структуру пристрою управління з програмованою логікою важливо не оминути таких фактів як адресація та структура мікропрограм.
Отже, найчастіше використовується природній спосіб формування адрес мікрокоманди. Основним елементом ПФАМК є лічильник, що формує адресу за допомогою інкременту.
У випадку переходів наступна адреса буде залежати від адресної частоти попередньої мікрокоманди, сигналів х операційного блоку і коду команди (КК).
Задачею автоматів управління є формування, розподілення в часі послідовностей сигналів управління, під дією яких в операційному автоматі виконуються операції:
Елементарний неділимий акт обробки інформації в операційному автоматі, що проходить на протязі одного такту, називається мікрооперацією. Прикладами мікрооперацій можуть бути “Зсув інформації”, “+1”,”-1” і т.д. Коли в операційному автоматі одночасно реалізуються декілька мікрооперацій, то така множина мікрооперацій називається мікрокомандою. Мікрооперації генеруються вхідними сигналами автомату управління, а їх послідовність в часі визначається функціями переходу. Сукупність мікрокоманд і функцій переходу утворюють мікропрограму.
Отже, першим кроком синтезу є запис мікропрограми у вигляді графу. Граф складається з вершин і ребер, що з’єднують їх. Є 4 типи вершин:
1). Початкова – з неї виходить одна дуга. Завершення функції автомата приводить до першої вершини.
2). Кінцева – присутня довільна кількість входів.
3). Операторна – відповідає виконаній мікрокоманді. Входить довільна кількість дуг, виходить лише одна дуга.
4). Умовна – на вхід подається довільне число дуг, на вихід – дві.
Зарисуємо фрагмент графу мікропрограми на основі моделі автомату Мура (Додаток 6).
На графі представлені три мікрокоманди, які показані мітками Y1, Y2, Y3. Кожній команді буде відповідати стан автомату. Q1, Q2, Q3 одночасно відображають вихідний сигнал.
Мікропрограмний автомат з природною адресацією, поле мікрооперацій, коди
3.1. Природна адресація
Отже, є автомати з різними типами адресації, а саме:
- з примусовою;
- з природною;
- з комбінованою;
Проте детально я хотіла б зупинитись на автоматі з природною адресацією.
При природній адресації микрокоманд існує три формата МК (мал. 3.1.).
Мал. Формати м(крокоманд автомата з природною адресац((ю..
Тут формат ОМК відповідає операторн(й вершині, УМК1-умовній, а УМК2-вершині безумовного переходу. При подачі сигналу “пуск" лічильник ЛАМК обнуляється, і за сигналом СІ відбувається запис МК до регістра. СФМО формує відповідні МО при П=1 або видає на всіх виходах нулі при П=0. СФА в залежності від П і вм(сту поля FX, формує сигнали Z1 і Z2. Сигнал Z1 дозволяє проходження синхро(мпульс(в на л(чильний вхід ЛАМК, а Z2 дозволяє запис до лічильника адреси наступної МК з приходом синхро(мпульсу.
Визначимо розрядн(сть полів. l=]log2(L+1)[, де L-число умовних вершин. L=6, l=3
m=]log2T[ Т- число наборів м(крооперац(й, що використовуються в ГСА, в нашому випадку Т=17, m=5.
r=]log2 Q[, Q - кількість м(крокоманд.
У автоматі з природною адресац(єю (Додаток 7) при істинності(помилковість) логічної умови перехід здійснюється до вершини з адресою на одиницю великим, а при (помилковість)істинності ЛУ перехід відбувається за адресою, записаною в полі FA. У нашому випадку будемо додавати одиницю при істинності ЛУ або при переході з операторной вершини. Якщо в одній точці сходиться декілька переходів по “1" або з операторно( вершини, то всі вершини з яких здійснювався перехід, повинні були б мати однакову (на одиницю меншу ) адресу, н(ж наступна команда. Але це неможливо.
Для виключення подібних ситуацій вводять спеціальну вершину безумовного перходу Дані вершини дода(мо таким чином, щоб в одній точці сходилася будь-яка кількість переходів по “0" і тільки один по “1" або з операторно( вершини.
Вершина безумовного переходу
3.2. Кодування та поле мікрооперацій
Відмітимо, що спосіб кодування впливає на правильність формування керуючих сигналів і складність автомата. Можливість формування сигналів, не передбачених графом автомата при неоптимальному кодуванні станів обумовлена появою “гонок”, що пов'язано з розкидом часу переключення окремих тригерів автомата. Наприклад, при переході автомата зі стану 10 у стан 10 під час переключення тригерів можлива поява станів 00 або 11 (в залежності від того, який із тригерів раніш переключається). Ці проміжні стани при використанні тригерів із внутрішньою затримкою не впливають на правильність переключення автомата, однак можуть привести до появи короткочасних помилкових керуючих сигналів.
Для усунення цього недоліку можна використовувати протигоночне сусіднє кодування. При сусідньому кодуванні перехід автомата з одного в будь-який інший припустимий для даного автомата стан здійснюється переключенням тільки одного тригера, внаслідок чого ”гонки” не виникають. В автоматах, що не допускають сусіднього кодування, необхідно вводити додаткові стани.
Усі мікрокоманди, що присутні у мікропрограмі керування, кодуються за допомогою позиційного коду МК. Це максимально скорочує довжину формату слів керування, а, отже, і ємність КП. При застосуванні цього методу оптимізації операційної частини мікропрограмних пристроїв керування максимально скорочуються апаратні витрати при реалізації блоку керуючої пам’яті, але збільшуються апаратні витрати при реалізації схеми формування мікрооперацій (СФМО), а швидкодія функціонування пристрою керування є найменшою серед усіх трьох методів оптимізації.
Метод кодування полів сумісних мікрооперацій заснований на тому, що найчастіше у мікропрограмах керування у окремих станах автомата необхідно формувати далеко не усі мікрооперації, що присутні у алгоритмі керування. Тому мікрооперації, що не використовуються разом в жодній мікрокоманді у алгоритмі керування, можна об’єднати у одне поле (такі мікрооперації є сумісними) та формувати у окремому стані автомата тільки одну мікрооперацію з окремого поля. Мікрооперації у окремому полі кодуються за допомогою позиційного коду мікрооперацій. Цей метод оптимізації операційної частини мікропрограмних пристроїв керування є середнім за показниками апаратних витрат та швидкодії між методами унітарного кодування мікрооперацій та максимального кодування наборів мікрооперацій. Довжина формату слів керування у керуючій пам’яті скорочується у порівнянні із методом унітарного кодування мікрооперацій, а, отже, скорочуються і апаратурні витрати при реалізації блоку КП. Окремі поля сумісних мікро операцій реалізуються у вигляді дешифраторів полів у складі схеми формування мікрооперацій. Ці дешифратори, як правило, містять менше еквівалентних вентилів, аніж дешифратор коду мікрокоманд у методі максимального кодування наборів мікрооперацій. Це зменшує апаратні витрати при реалізації схеми формування мікрооперацій та зменшує часову затримку у блоці СФМО у порівнянні з методом максимального кодування наборів мікрооперацій. При застосуванні методу кодування полів сумісних мікрооперацій виникає необхідність оптимального розподілення сумісних мікрооперацій по окремим полям. Розроблено ряд алгоритмів розподілення сумісних мікрооперацій по окремим полям, що мають свої переваги та недоліки. Для того, щоб оцінити ефективність використання можливостей окремого поля, пропонується ввести коефіцієнт наповненості окремого поля.
Більша частина інформації, що обробляється мікропроцесором є текстовою, яка представлена у вигляді стрічок символів певного алфавіту. Окремий символ (буква, цифра, знак) кодується 7 і 8-ми бітними кодами. Рядок символів при 8-ми бітному кодуванні являє собою послідовність байтів наступного виду:
1 8 1 8 1 8
S1 S2 … Sn
S – 8-ми бітний двійковий код символу. Таким чином, рядок символів відображається полем змінної довжини. Зазвичай довжина поля може змінюватися від 1 до 256 байт.
Для кодування символів використовуються спеціальні коди. Найбільш розповсюдженими є 7 і 8-ми бітні двійкові коди. Логічні значення, відповідно, приймають одне із 2-ох результатів: «істина» або «хиба» і кодується цифрами «1» і «0». Дії над ними можна робити лише з допомогою логічних операцій. Це може бути набір мулевих векторів і матриць.
Для запису індикації адресів і даних застосовується зручна і компактна вісімкова і шістнадцяткова система числення. Наприклад, якщо б поле коду становило 4 біти, можна було б закодувати 16 різних операцій, а кожен з адресів складав би 12 біт. Таким чином можна було б адресувати 4 Кбайт пам’яті. Тоді загальна довжина команди складала б 40 біт. Звісно, з такою командою процесору буде складно працювати, оскільки він оперує 8-ми і 16-ти бітними словами. Тому, частина інформації, що необхідна процесору повинна здаватися неявно і не залежати від властивостей кожної окремої команди.
4. Структурна схема керуючого автомату
Замалюємо узагальнену структуру ЦА.
КС – комбінаційна схема;
П – пам'ять;
x – вхідні сигнали;
y – вихідні сигнали;
V – сигнали збудження, які забезпечують перемикання елементів пам’яті;
Q – вихідні сигнали елементів пам’яті, що відображають стани автомату;
C – сигнали синхронізації.
Автомат складається з двох частин:
комбінаційна частина автомата реалізує функції алгебри логіки, може будуватись на основі логічних елементів.
Пам'ять автомату фіксує множину станів Q може будуватися на тригерах або регістрах пам’яті.
Загалом реалізація може здійснюватись на елементах ПЛІС.
На вхід комбінаційної схеми надходить множина повідомляючи сигналів х, які формуються операційним блоком, а також сигнали Q від пам’яті які відображають стан автомату в момент часу Т. Комбінаційна частина формує вихідні сигнали у, які сигналами управління і подаються на операційний блок а також сигнали збудження V, які забезпечують перехід в наступний стан автомату. Алгоритм синтезу може бути повністю автоматизованими.
В даному випадку автомат розглядається як декомпозиція елементарних автоматів (тригерів).
Автомат містить комбінаційну схему (КС) і пам'ять (П), що складається з тригерів Тi. Входами КС є виходи Q1,...,Qm тригерів і вхідні сигнали (логічні умови) х1,...,хk, що формуються в операційному пристрої. КС виробляє керуючі сигнали y1,...,yp для операційного пристрою і функції збудження тригерів q1,...,qm, що визначають перехід автомата з одного стану в інший. Кожній з безлічі станів {а1,...,аm} відповідає визначений набір значень Qi.
Якщо вихідні сигнали залежать тільки від стану, в якому знаходиться автомат, його називають автоматом Мура. Закон функціонування такого автомата визначається виразами
,
,
де
s=0, 1, 2,...– моменти автоматного (дискретного) часу;
( – функція переходів;
( – функція виходів;
a ( {a1, a2, ..., am} – стан автомата;
х={х1, х2 , ..., хk} – вектор значень вхідних сигналів;
у={у1, у2, ..., уp} – вектор вихідних сигналів автомата.
Розробити модель інтелектуального агента на основі операційного автомату, що лежить в основі Internet
Особливості функціонування спеціалізованого інтелектуального агента визначаються його
інтересом – вектором оцінок бажаності можливих станів агента.
Для опису інтересу агента, за допомогою якого він розрізняє стани довколишнього світу та
позиціонує себе у ньому, застосовується функція корисності, котра є числовою оцінкою його бажаності для агента. Корисності об’єднуються з імовірностями дій для визначення очікуваної корисності кожної дії.
5.1. Технологія інтелектуальних агентів в INTERNET.
Сьогодні перед користувачем постає задача шукати потрібну інформацію в невідомому і постійно наростаючому віртуальному інформаційному просторі. Якщо потрібно розв’язати яку-небудь складну, нетривіальну задачу, що зв’язано з використанням цілком екзотичних математичних методів, про які користувач має слабке уявлення, або ж вияснити який небудь маловідомий історичний факт (наприклад походження батьків відомої людини), або ж знайти та використати деяке програмне забезпечення, тоді подальші дії повинні проходити по такому сценарію (звичайно, якщо розвиток мережі піде в даному напрямку). Користувач активізує програму - агента на своєму комп’ютері і достатньо вільній формі описує задачу. Потім агент з’єднується з іншими агентами, щоб вияснити, що їм відомо про розв’язання поставленої задачі. Якщо знаходиться агент, якому відоме вирішення, тоді агент користувача відфільтровує знайдену інформацію з метою ідентифікації потрібних розв’язків і відсіює непотрібні дані. Якщо розв’язок не знайдено або ж є неповним, кожен з агентів звертається до сусідніх агентів, щоб взнати можливі адреси інформаційних сховищ і (або) професійних “розв’язувачів“ даних задач. Цей процес продовжується до попередньо обумовленого користувачем терміну. Якщо за даний час не отримано позитивного результату – комп’ютер повідомляє, що розв’язок поставленої задачі сучасній науці невідомий. Приведений сценарій передбачає ряд процедур, таких як евристичний пошук, інтелектуальні взаємодії, нагромадження та узагальнення інформації, розпізнавання і класифікацію.
Найважливішими проблемами для створення інтелектуальних агентів є:
· розробка стандартної мови спілкування агентів;
· розробка методів ефективної обробки знань, класифікації та розпізнавання;
· розробка “живого“ користувацького інтерфейсу (“природна мова“).
Головною серед цих проблем є розробка стандартів обміну знаннями в процесі спілкування агентів. Зараз існує щонайменше два подібні стандарти в цій галузі: Knowledge Query Manipulation Language та Knowledge Interchange Format, які до цього часу мають масу недоробок. Те саме можна сказати і відносно другої проблеми. Дійсно ефективних методів, що здатні стати базою побудови промислової технології світового масштабу, на сьогодні немає. Відносно останньої проблеми варто підкреслити, що саме проблема створення інтерфейсу, близького до природної мови, зруйнувала проект ESPRIT, який передбачав створення комп’ютера п’ятого покоління до 90-тих років. Проте зрушення в цьому напрямку є.
Сьогодні Push – технології, а завтра інтелектуальні агенти будуть спрямовані для якнайкращого використання інформації і ефективної взаємодії між людьми через глобальні інформаційні мережі.
Список літератури
Букреев И.Н., Мансуров В.М., Горячев В.И. Микроэлектронные схемы цифровых устройств.– М.: Сов. радио, 1975. – 368 с.
Майоров С.А., Новиков Г.И. Принципы организации цифровых машин. Л.: Машиностроение, 1977. – 432 с.
Самофалов К.Г., Романкевич А.М., Валуйский В.Н., Каневский Ю.С., Пиневич М.М. Прикладная теория цифровых автоматов.– К.: Вища школа, 1987. – 375 с.
Самофалов К.Г., Корнейчук В.И., Тарасенко В.П., Жабин В.И. Цифровые ЭВМ. Практикум. – К.: Вища школа, 1990. – 215 с.
Наукові праці ДонНТУсерія "Інформатика, кібернетика та обчислювальна техніка" випуск 10 (153)
http://masters.donntu.edu.ua
7. Методичні вказівки до лабораторної роботи №3
З курсу “Комп’ютери та мікропроцесорні системи”, Львів 2000.
8. http://ru.wikipedia.org/
Додатки
Додаток 1 (Каган стр. 214)
Y
X
Додаток 2 (Каган стр. 214)
Додаток 3 (Каган стр. 215)
Додаток 4 (Каган стр. 217)
Додаток 5 (Каган стр. 219)
Додаток 6
Рис. Фрагмент граф-схеми закодованого мікроалгоритму автомата Мура
Рис. Граф-схема закодованого мікроалгоритму автомата Мура
Додаток 7
Структурна схема автомата з природною адресац(єю
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора