Лекція з курсу „Дослідження та проектування комп'ютерних систем та мереж” Універсальна SH-модель План Універсальність машини Тюрінга. Принципи організації комп'ютерів. Структура універсальної SH-моделі. 1. Універсальність машини Тюрінга. Машина Тюрінга (МТ) – це модель алгоритму. МТ складається з стрічки, головки, програми. Для виконання одного алгоритму необхідна одна машина Тюрінга. А якщо бути точніше, то – одна програма. Для більш чіткого розуміння функціонування МТ доцільно привести її структуру та прклад програми.
рис.1. Структура МТ q a q0 q1 … qN
a0 Pa1q1
a1
a2
…
aN
рис.2. Приклад програми МТ Кожний крок машини Тюрінга – це умовний перехід:
, де - декартове множення. Приклад декартового множення:
Роль однострічкової машини Тюрінга – уточнити поняття «алгоритм» (властивості, параметри, характеристики) . Щоб реалізувати інший алгоритм, потрібна інша програма та інша конфігурація (розміщення) даних відносно головки. Властивість масовості – це універсальність. Універсальність – здатність розв'язувати будь-яку задачу (арифметичну). Для цього потрібно змінювати програму, або потрібен набір програм і конфігурацій даних. Чи є реальним побудова універсальної МТ? Тобто, такої моделі алгоритму, яка охоплювала б деяку множину підзадач. Давайте, розглянемо це питання в аспекті проектування найпростішого RISC процесора. Весь процес проектування доцільно розбити на окремі детерміновані кроки. Для початку, визначемось з множиною операцій, що необхідно виконувати. Припускаємо, шо необхідно виконувати лише арифметичні операції: додавання, віднімання, множення, ділення, множина побітових операцій. Тобто кількість операцій приблизно рівна 20. В даному випадку, коли кажемо операція, маємо на увазі програма МТ. Виникає питання: чи є можливим об'єднання стрічок всіх програм універсальної МТ? Так, це можливо. В загальному випадку цілком достатньо лише однієї стрічки!
рис.3. Універсальна МТ з спільною стрічкою. Зауваження: 1) При розв'язку задач з кожною задачею набори вхідних даних змінюються. 2) Для визначення того, яку таблицю обрати, використовується символ коду алгоритму. Таким символом можуть бути арифметичні знаки +, -, х, логічні, пересилочні, символи перетворення та інші. Далі необхідно враховувати наступну вимогу: „будь-яка машина повинна діяти автоматично”. Дотриматись цієї вимоги можна представивши кожну програму окремою машиною Тюринга. Тоді універсальна МТ набуде наступного вигляду:
рис.4. Універсальна МТ Наступним кроком побудови універсальної машини Тюрінга є об'єднання всіх стрічок з записами програм в єдину стрічку з однією головкою. Тобто, дані зберігаються в одній, а програма в іншій стрічці.
рис.5. Універсальна МТ з розподіленими стрічками даних і програм Наступним кроком є об'єднання стрічок програм та даних в одну спільну. Ця стрічка буде розділена навпіл (з одного боку стрічка обмежена, з іншого – ні). В результаті цього об'єднання ми отримуємо універсальну однострічкову машину Тюрінга.
рис.6. Об'єднана стрічка МТ (дані та програми) Кожний символ, що використовується необхідно кодувати для того, щоб не виникло колізій в кроці запам'ятовування даних, додаткових символів та програм. Приведемо приклад системи кодування. символи керування: R – 101 L – 1001 S – 10001 символи зовнішнього алфавіту: a0 – 100001 a1 – 10000001 символи внутрішнього алфавіту: q0 – 1000001 q1 – 100000001
Крім того можна використовувати інші символи – допоміжні символи. Наприклад символи, що розділяють цифри символів. 0 – 10000001 1 – 1000000001 Результатом попередніх п'яти кроків нашої роботи є доведення теореми про існування універсальної машини Тюрінга. Висновки: Для створення універсальної машини Тюрінга потребує великої кількості комірок. Фон Нейман підрахував – на це потрібно 40 тисяч комірок. З дослідження універсальної машини Тюрінга випливають два фундаментальних принципи обчислювальних машин (фон Неймана): І - принцип виконання обчислень за програмою; II - принцип збережувальності програми. Питання, що ми обговорювали практичного значення не мають. Але теоретичне значення надзвичайно велике. Універсальна машина Тюрінга – започаткувала принципи обчислювальних машин. В нашому курсі універсальна машина Тюрінга має те значення, що за аналогією з нею ми будуватимемо універсальну модель обчислювальної машини, яка крім технічних характеристик має інформаційні характеристики, або характеристики штучного інтелекту . 2. Принципи організації комп'ютерів. Фон Нейман сформулював п'ять основних принципів організації комп'ютерів: принцип програмного управління; принцип збережувальної програми (програма зберігається разом з даними та проміжними даними); принцип умовного переходу; принцип кодування даних і програм; принцип ієрархічності пам'яті. Структура універсальної SH-моделі. Прикладом універсального обчислювача є мікропроцесор. Тобто це пристрій, що може забезпечити виконання будь-якої арифметичної задачі. Звісно, наше попереднє твердження не зовсім коректне, адже завжди можна знайти вийняток з будь-якого правила. Але в даному контексті вийнятки ми не розглядаємо. Для того, щоб зрозуміти яким чином пов'язані універсальний обчислювач та універсальна SH-модель доцільно ознайомитись з рис.7.
рис.7. Структурна схема універсального обчислювача (процесора) Як бачимо процесор, в даному випадку, представляється двома SH-моделями. Перша модель – функціональна, друга – модель керування. Давайте нагадаємо собі принципову відмінність між процесором і комп'ютером. Відмінність в тому, що комп'ютер має пам'ять. Тобто він здатний зберігати програму та дані для виконання певного алгоритму. Якщо враховувати цей факт і брати до уваги те, що SH-модель містить пам'ять – то в даному випадку ми утотожнюємо поняття універсальний обчислювач та комп'ютер. Яким чином пов'язані ці дві моделі? Чи є якась залежність між ними? І чим це спричинено? Відповіді на ці питання досить логічні і випливають з наступної аксіоми – „площа кристалу процесора є обжененою”. Тобто на певній площі ми повинні розмістити два функціональних вузла (насправді цихї вузлів набагато більше, але в розрізі даного питання ми їх не розглядаємо). Для збільшення продуктивності процесора нам необхідно збільшувати апаратну складність функціональної частини, і відповідно зменшувати – SHc. Давайте порівняємо процентні співвідношення цих частин для двох архітектур: CISC та RISC архітектури.
