1. У попередній статті ( «Світ ПК», № 2/02, с. 150 ) Ми детально розглянули машину Тьюринга (МТ)....
2. Операційний і керуючий блоки
3. Предикати і дії МТ
4. Таблиця переходів МТ
5. КА-машина: ПРО + УБ = (X + Y) + ТП
6. Паралельні властивості КА-машини
7. Про «спекуляціях» на прогнозі переходів
8. Мережева модель МКА: паралелізм безлічі машин Тьюринга
9. Приклад СМКА-моделі
10. Про недоліки і достоїнства МКА
11. Машина Тьюринга краще
12. література

У попередній статті ( «Світ ПК», № 2/02, с. 150 ) Ми детально розглянули машину Тьюринга (МТ). Там же, торкнувшись роботи з кількома голівками, що мають внутрішні стану, був намічений перспективний шлях розвитку МТ - паралельний. Саме йому і присвячена ця стаття.

Наше деловое партнерство www.banwar.org

Мама, дядько, який ходив
на одній нозі, - вже на двох.
Він собі виростив або йому приробили?
К. Чуковський. Від двох до п'яти

Отже, ми розглянемо, чому «потенціал паралелізму» у МТ вище, ніж у машини Посту (МП). Буде побудована паралельна машина, яка взяла багато від МТ, але все ж залишається окремою абстрактної машиною (АМ). Створюючи її, ми заодно визначимо і реалізацію МТ в результаті деталізації її структури. Тому можна буде «вживу» (правда, використовуючи нову машину і процедуру переходу до її програмами від МТ-програм), а не на папері, побачити результати роботи тьюрінгових програм.

"Чорний ящик"

Погляньмо на будь-яку абстрактну машину, а точніше, на її керуючий пристрій (КП), з позицій «чорного ящика». Перший його варіант - абстрактний «чорний ящик» (АЧЯ), що має по одному входу і виходу. Символи зовнішнього алфавіту надходять в АЧЯ через вхід, зазвичай званий вхідним алфавітом. А символи, які змінюють інформацію на стрічці, через вихід, іменований АЧЯ, видає вихідний алфавіт. Причому допускається, що обидва ці алфавіту можуть збігатися. Другий варіант, «структурний чорний ящик» (СЧЯ) має безліч таких каналів, і не виключено, коли число вхідних-вихідних каналів СЧЯ відповідає числу символів вхідного-вихідного алфавітів АЧЯ. Тоді «ящик» на структурному рівні вже становить основу моделі паралельних процесів.

Щоб відрізнити, яка з машин перебуває всередині «ящика», потрібно винести за його межі головки машин, якими слід керувати, видаючи їм відповідні символи. У кожної з машин вони, як правило, свої, хоча між ними часто можна ввести відповідність з точністю до перейменування. Символи, які визначаються специфікою машини, прийнято відносити до безлічі символів внутрішнього алфавіту машини: у машини Посту - це «стрілки», у машини Тьюринга - символи R і L. Безумовно, можна так визначити абстрактну машину (наприклад, шляхом об'єднання алфавітів), що символи внутрішнього алфавіту будуть видаватися через ті ж канали, що і зовнішнього, але все ж наочніше і зручніше вводити додаткові канали.

Поки ж винос головки за межі «ящика» ще не виявляє принципових відмінностей між машинами. Їх можливості в системі «ящик-головка» розрізняються лише набором тих символів внутрішнього алфавіту, які можна привести у відповідність простим перейменуванням. Істотними відмінності між ними стають тоді, коли враховується якесь внутрішнє стан «чорного ящика» (чя). При цьому стає видно, що машина Тьюринга має явну «вбудованим» властивістю відображати внутрішній стан чя, а машина Посту - немає.

А чи потрібно взагалі маніпулювати інформацією про такий внутрішній стан? Безумовно, адже, наприклад, від того, з яким «внутрішнім настроєм» потиснув вам сьогодні руку ваш начальник, може залежати багато! Здавалося б, звичайне, «стандартне» дію, настільки схоже на вчорашнє, але кінцевий результат може бути різним. Аналогічно і з програмами. У них внутрішній стан - це додатковий канал, не тільки стежить за її роботою, а й дає інформацію для управління їй. Саме тому і має сенс подавати інформацію про внутрішній стан машини і на вихід, і на вхід «ящика». Крім того, має бути ясно, що даними про стан можна оперувати паралельно з даними на інших каналах.

Було б зручно, якби символи внутрішніх станів абстрактної машини формували окреме безліч. Тоді можна було б вважати, що вихідний алфавіт СЧЯ - об'єднання множин символів внутрішніх станів і внутрішнього алфавіту машини (див. «Світ ПК» , № 2 - 3/02 ).

Таким чином, можна зробити висновок: СЧЯ більш зручний і гнучкий, ніж АЧЯ, а з двох формальних моделей внутрішнього устрою такого «ящика» найбільш природна модель типу МТ, т. Е. Та, яка відображає поняття внутрішнього стану «чорного ящика».

Операційний і керуючий блоки

Однак «ящик» ще потрібно «начинити». І тут, особливо для МТ, винаходити майже нічого не потрібно, так як структурно багато відпрацьовано на цифрових схемах. До речі, зовсім не обов'язково, щоб начинка «ящика» була «залізною». Але все ж краще введемо, з огляду на цю інформацію, ще один рівень деталізації структури «ящика». У практиці проектування дискретного пристрою прийнято виділяти його операційний (ПРО) і керуючий (УБ) блоки [1]: ПРО виконує всі дії по обробці інформації, а УБ реалізує алгоритм роботи машини в дискретному часі за допомогою елементів, що становлять ПРО.

Аналогічно можна поступити і на програмному рівні. Використовуємо звичайний прийом формального визначення програми у вигляді так званої схеми програми S, де S = трійка, M - безліч елементів пам'яті, або просто пам'ять, A - безліч операторів програми, G - управління програмою [2]. У цьому випадку пам'ять і оператори складають ПРО, управління - УБ. Якщо такий підхід поширити і на абстрактні машини, то М - стрічка, а все інше - керуючий пристрій цих машин.

Далі розберемо докладніше, що буде входити в відноситься до ПРО і УБ машину Тьюринга і відповідно МТ-програму. Розглянемо реалізацію цих блоків, взявши за основу відомі мови програмування, наприклад С ++. Ті ж операції поширимо по можливості і на програми для МП.

Предикати і дії МТ

Візьмемо спочатку операційний блок. На цьому рівні безліч операторів або блоків, складових ПРО, можна уявити двійкою, де X - безліч вузлів (блоків, функцій і / або підпрограм і т. П.), Які аналізують символи (якщо говорити про АМ), Y - безліч вузлів, що перетворюють символи. Ті функції, які входять в безліч X, назвемо предикатами, а ті, що містяться у великій кількості Y, - діями.

У разі реалізації елементів ПРО для МТ на мові Сі ++ її предикат може виглядати так:

bool xN () {sn == sj;},

де sn - поточний символ на стрічці; si - значення того символу, яким повинен відповідати символ на стрічці.

Якщо символи рівні, то предикат xN, де N - номер предиката і номер вхідного каналу СЧЯ, поверне значення «істина», а якщо немає - «брехня». Слід зауважити, це дуже важливо, що предикати за задумом не змінюють значення пам'яті, т. Е. Інформації на стрічці для розпаралелювання.

Функції-дії (далі - просто дії) не повертають значень, і цей факт можна підкреслити на Сі ++ типом значення, що повертається - void. У випадку з МТ дію, змінює поточний символ sn на sk, на Сі ++ матиме такий вигляд:

void yN () {sn = sk;},

а дія, що переміщує головку вправо, можна уявити так:

void yN () {R;}.

Предикати і дії для машини, адреса комірки стрічки, візьмуть вигляд:

bool xN () {s [i] == sj;}, void yN () {s [i] = sk;},

де i - індекс (адреса) осередки на стрічці, представленої масивом s.

Домовимося, що для дій, як і для предикатів, N - не тільки позначає їх номер в ПРО, але і номер вихідного каналу СЧЯ.

Предикати і дії дозволяють по-іншому визначити інструкції МТ, поставивши у відповідність будь-якого вхідного символу машини предикат, а будь-якого вихідного символу - дія. Причому сам перехід в наступний стан і виконання тієї чи іншої дії можливі тільки при істинному значенні відповідного предиката. Тепер все різноманіття видів інструкцій МТ можна звести до одного, а саме:

qi, xj, yk, ql,

де xj - предикат, що належить множині X;
yk - дія з безлічі Y;
qi, ql - поточний і наступний стану машини з безлічі її внутрішніх станів Q відповідно.

В результаті вийде код програми на Сі ++, що реалізує предикати і дії МТ, для функції І-НЕ (лістинг 1):

Це варіант програми для МТ, що має адресацію. Стрічка реалізована масивом цілих чисел, де нульовий і перший елементи масиву s містять вхідні значення функції, а другий елемент - вихідний.

Вище йшлося в основному про МТ, однак з точки зору ПРО тип розглянутої машини не настільки важливий. У разі машини Посту предикати і дії були б тільки простіше. У неї був би один предикат, що аналізує наявність або відсутність мітки на стрічці, і два або чотири дії (відповідно при наявності адресації і без неї). З яких, наприклад, два дії ставили б мітку і очищали осередок, а інші два переміщали б каретку.

Таблиця переходів МТ

На рівні ПРО відмінності між МТ і МП поки що не принципові. Інша річ при розгляді блоку УБ. Йому потрібно на якійсь мові задати алгоритм або програму роботи, щоб відповідно до неї він виконував запуск елементів, що становлять ПРО. У випадку з МТ це буде список інструкцій наведеного вище виду, а для МП його вид буде іншим.

Спочатку розглянемо програму УБ для МТ. Для задачі моделювання функції І-НЕ запис алгоритму роботи УБ машини Тьюринга буде наступною:

q 1, x1x2, y2, q 2 q 2, x3, y1, q 1 q 2, x4, y1, q 1

Це варіант для машини, адреси осередки пам'яті і має дві головки. Для програми, що використовує внутрішні стану, на місці дій потрібно поставити прочерки. І в цьому випадку ПРО буде складатися тільки з предикатів.

Тепер зрозуміло майже повну відповідність наведеної програми для УБ таблиці переходів (ТП) структурного кінцевого автомата (КА) Милі, що моделює таку ж функцію І-НЕ. При цьому в ТП одна інструкція УБ модифікованої МТ повністю відповідає одному рядку таблиці переходів КА. Зрозуміло також, чому модель КА абсолютно підходить в якості моделі УБ машини Тьюринга: перехід від програми Тьюринга до таблиці переходів КА майже очевидний і простий (він був розглянутий раніше).

Ми цілком можемо зменшити кількість предикатів, використовуючи їх заперечення. У цьому випадку програма, яка застосувала для індикації стану свого виходу внутрішні стану, може бути представлена ​​так:

q 1, x1x2, -, q 2 q 2, ^ x1, -, q 1 q 2, ^ x2, -, q 1

Тут в якості знака заперечення використаний символ (^).

Виникає питання: чи не можна для подальшого скорочення загальної кількості функцій ввести параметри для предикатів і дій? Безумовно, можна, але, як показала практика, краще змиритися з тим, що легко усунути, ніж погіршити ефективність реалізації і отримати проблеми з формальним визначенням і теорією самої абстрактної машини.

КА-машина: ПРО + УБ = (X + Y) + ТП

Наведемо повний лістинг програми, еквівалентної програмі Багатоголовочна машини Тьюринга, що використовує адресацію і внутрішні стану для відображення вихідного значення функції І-НЕ (лістинг 2).

Хоча форма вихідної програми МТ і її нова форма дуже близькі один одному, остання відповідає вже інший абстрактної машині, яку і ми назвемо КА-машиною (далі - МКА). Ця абстрактна машина структурно розділена на ПРО і УБ, де ПРО складається з двох множин - предикатів і дій, а моделлю УБ є модель КА. Відзначимо, що у МКА щодо кількості головок і відсутності адресації може бути та ж конструкція, що і у МТ, але все ж з безліччю головок і адресацією осередків на стрічці жити набагато легше. Крім того, без всіх цих головок було б складно побудувати паралельну модель. А як це можна зробити, використовуючи їх (по суті, кожна головка - окремий вхідний канал чя), стане ясно вже на прикладі побудови мережевої моделі МКА.

Паралельні властивості КА-машини

Для МКА майже очевидний паралелізм функцій, з яких складається ПРО. При цьому вказівка ​​про те, які функції можуть виконуватися паралельно, вже міститься в рядках таблиці переходів УБ. Але якщо розглядати якесь поточне внутрішній стан МКА, то паралельно можуть запускатися всі предикати, що навантажують переходи з нього в усі інші стани. І цілком можливо, так як вони не змінюють вміст стрічки. А при ситуації переходу в наступний стан настає черга паралельної роботи дій. Паралельно можуть виконуватися всі дії, що навантажують перехід в нове внутрішній стан.

Такий вид паралелізму МКА відповідає синхронного паралелізму паралельних мов. В цьому випадку запуск безлічі операторів в паралельну роботу відбувається одночасно, а сам момент закінчення їх роботи фіксується за останнім оператору, закінчив роботу (механізм, що задається операторами fork, join [3]).

Хоча це питання і дещо виходить за рамки поточної задачі, потрібно згадати і варіант подальшого розширення моделі МКА. При ієрархічній структурі будь-яке її дія може представляти, в свою чергу, одну або кілька МКА і т. Д. Але і в цьому випадку принцип синхронного паралелізму не повинен і не буде порушуватися, оскільки будь-який рівень ієрархії завершує свою роботу тільки після закінчення дій всіх вкладених рівнів.

Наступний тип паралелізму менш очевидний, але дуже ефективний при наявності асоціативної пам'яті (АП). Після паралельного виконання предикатів і формування поточної вхідний ситуації, обчисленої на основі отриманих від предикатів значень, можна приступити до паралельного аналізу всіх рядків поточного стану для знаходження єдиного рядка (так як автомат детермінований), що відповідає ситуації переходу.

Таким чином, у МКА можна виділити три рівня паралелізму: паралелізм предикатів, дій і аналізу дуг переходів поточного стану.

Про «спекуляціях» на прогнозі переходів

Передбачення команд - одна з найзагадковіших процедур, що виконуються сучасними процесорами. Якби не ця проблема, то реалізація програм була б багато ефективніше. І нинішні «спекулятивні обчислення» - один із наслідків безперервної боротьби з вирішенням проблеми переходів і причина різноманітних «спекуляцій» на цю тему. Але при існуючій архітектурі і від таких команд і від фактора їх випадкового розташування в тілі програми поки нікуди не дітися, а тому доводиться лише дивуватися, що ще щось вдається передбачати [4].

У зв'язку з цим не можна не відзначити, що робота, яка перетворює сучасний процесор в якусь подобу ворожки, в МКА виконується без всякого «містицизму». Легко видно, що безліч команд, які потрібно «передбачати» в сучасному процесорі, для МКА (в даному випадку це безліч предикатів і дій) обчислюються однозначно на основі аналізу таблиці переходів. При цьому чітко окреслено і обсяг визначається для виконання програмного коду: потрібно вибрати стільки операторів, скільки знаходиться в предиката або діях. У сучасному ж процесорі це число визначається числом інструкцій між операторами передачі управління. При невдалому «передбаченні» виконується зайва робота і, крім того, на саме пророкування також витрачається чимало часу.

А в МКА ж немає ніяких прогнозів - все може бути зроблено паралельно, швидко і однозначно.

Мережева модель МКА: паралелізм безлічі машин Тьюринга

Розглянутий вище синхронний паралелізм на рівні МКА - це лише перший крок на шляху розпаралелювання обчислювального процесу. Повним паралелізмом, універсальністю і адекватним відображенням структури володіє система, що складається з безлічі одночасно працюючих незалежних і / або взаємодіючих між собою блоків ( «чорних ящиків»). Така структура, звана мережею, добре описується безліччю абстрактних машин (МТ, МП, МКА і т. П.). У поширеній структурної класифікації паралельних систем мережева модель МКА (СМКА) відповідає безлічі процесорів над загальною пам'яттю або системам типу MIMD (Multiple Instruction - Multiple Data) або МКМД (множинний потік команд - множинний потік даних) [3]. І тому з структурної точки зору тут нічого нового немає. «Родзинка» криється в формальної математичної моделі, обраної для опису такої системи, в нашому випадку - в автоматної мережі з МКА.

Відмінних рис, які притаманні паралельної структурі, яка відповідає формальної моделі СМКА, не так вже й багато. Точніше, їх фактично три: дискретне час для окремої компоненти, єдине дискретне час для всіх паралельних компонент і можливість обміну інформацією про внутрішні стани окремих МКА між собою. Дискретне час окремої моделі відповідає моментам переходу моделі з одного стану в інший. Формально його реальна тривалість взагалі не має значення - важливо саме його наявність. Єдине дискретне час мережі передбачає синхронізацію дискретних тактів компонентних автоматів мережі, що приводить його поточне значення до поточного значення самого повільного компонентного автомата мережі.

Обмін інформацією про свої внутрішні стани між компонентами мережі не настільки обов'язкова умова, як два наведених вище, так як такою інформацією можна обмінюватися і через стрічку. Але цей вид обміну не тільки значно спрощує алгоритми системи, оскільки вводить відповідний тип синхронізації - через внутрішні стану, але і піддається гарному теоретичному опису (на цьому заснована алгебра кінцевих автоматів [5]).

Приклад СМКА-моделі

Зараз ми по суті повторимо опис автоматної паралельної моделі RS-тригера, наведеної в роботі [5], але вже в термінах моделей МКА і СМКА. Нагадаємо, що RS-тригер - це два елементи І-НЕ, з'єднаних зворотними зв'язками. Модель одного елемента І-НЕ, представленого моделлю МКА, ми вже розглянули. Граф моделі тригера, яка представлена ​​мережевою моделлю СМКА, що складається з двох моделей МКА, показаний на рис. 1. В даному випадку синхронізація процесів, що реалізують окремі елементи тригера, виконується через осередки пам'яті стрічки. Граф і структура моделі тригера, але з синхронізацією через стану, представлені на рис. 2.

Їх порівняння показує, що синхронізація з використанням внутрішніх станів спрощує модель. Швидше за все, друга модель і працювати буде швидше, оскільки немає операцій із зовнішньою пам'яттю. Правда, з'являються операції роботи з станами, але, по-перше, до них доступ здійснюється по окремих каналах, а по-друге, це спеціалізований і універсальний вид операцій, який може бути введений в систему команд і оптимізований по швидкодії на апаратному рівні.

Приклад з синхронізацією через стану переконує нас в тому, що в модель СМКА зручно ввести відповідну операцію доступу до внутрішнього стану окремих (компонентних) елементів мережі. Умовно позначимо цю операцію запиту станів компонентних автоматів мережі як State. Вона буде мати один параметр - ім'я компонентного автомата мережі - і повертати строкове значення - ім'я поточного стану. Програма (лістинг 2), що реалізує СМКА-модель RS-тригера, з урахуванням введеної операції може бути наступною (лістинг 3).

У цій програмі використано властивість моделі елемента І-НЕ перебувати тільки в одному з двох можливих станів. Це дає можливість обмежитися одним предикатом, які аналізують стан «сусіднього» елемента. Тут також використані:

• властивість предиката повертати два значення - справжнє і хибне;
• властивість таблиці переходів, що оперує кон'юнкції вхідних умов.

Як видно, у МП можна збільшити кількість функціональних блоків і налагодити управління ними, але лише МТ і МКА мають внутрішні стану, що дозволяють організувати синхронізацію безлічі паралельно працюючих машин. При цьому для СМКА можна створити зручну математичну теорію, а не спиратися на, здавалося б, інтуїтивно зручні механізми розпаралелювання і синхронізації для МП (нитки, потоки, семафори і т. П.), Які все ж важко піддаються якомусь математичному опису.

Ще раз підкреслимо, що поняття внутрішнього стану - це механізм, відсутній у машини Посту. І саме тому машина Тьюринга була обрана в якості основи для паралельної архітектури. Тільки МТ і модель кінцевого автомата створюють теоретично сувору, ефективно реалізовану і в той же час зручну паралельну модель. Машина Поста іноді «виграє» в простій послідовній роботі, але для більш досконалої паралельної вона малопридатна.

Про недоліки і достоїнства МКА

У програмах для МП тимчасової процес зміни внутрішніх станів програми прихований від програміста. Його існування слід хоча б з того факту, що будь-яка програма має час своєї роботи. Та й вважаючи роботу будь-якого оператора програми «миттєвої», ми все ж лукавим, оскільки і в цьому випадку знаємо, що потрібно спочатку проаналізувати змінні, виконати над ними операцію і тільки потім привласнити отриманий результат вихідної змінної. У тому, що це насправді так, легко переконатися, розглянувши асемблерний аналог програми або той же добре багатьом відомий приклад з оператором типу «++» в паралельній середовищі.

Так що якщо нас не цікавлять паралелізм і тимчасові характеристики програми, то мова МП буде навіть зручніше. В іншому випадку мова МП буде приховувати час і доведеться вдаватися до хитрощів для опису такого процесу, а це майже еквівалентно реалізації іншої моделі в рамках наявної. Подібна задача може бути дуже складною (наприклад, інтерпретація кінцевих автоматів в рамках звичайного процедурного мови).

Модель МКА відображає тимчасові властивості програм, які не можна не враховувати при реалізації паралельних процесів. І тут у МКА і відповідно породила її МТ незаперечні переваги перед МП. Тому, коли знаєш недоліки і переваги розглянутих машин, можна зробити висновок про бажаність і навіть необхідність їх «мирного» співіснування. Так, в рамках дій і предикатів, до яких цілком можна застосувати поняття «миттєвий», зручніше конструкція і модель машини Посту, а при реалізації самих процесів, коли час потрібно обов'язково враховувати, - машина Тьюринга або МКА. Таким чином, можна говорити про архітектуру з ієрархічно вкладеної структурою абстрактних машин.

Машина Тьюринга краще

Отже, якщо ми хочемо створити ефективну і універсальну паралельну модель і відповідну їй архітектуру процесора, то повинні взяти за основу машину Тьюринга і тісно пов'язану з нею модель кінцевого автомата. В цілому ми її розглянули, а в якихось деталях її можна вдосконалювати і навіть можна «відточувати» її теорію, але загальний підхід залишається тим самим: паралельна модель - це безліч машин Тьюринга, що працюють в єдиному дискретному часі із синхронізацією за допомогою внутрішніх станів. Вище - модель СМКА на рівні безлічі паралельних процесів і модель МКА на рівні окремих процесів (тут, ймовірно, навіть краще мати комбінацію МКА і МП).

Все викладене є не чисто теоретичні побудови, як це може здатися з-за оперування абстрактними поняттями, а формалізацію результатів тривалої практичної роботи. Паралельна модель, яка визначає кінцево-автоматну модель програм, а в підсумку і звичайно-автоматну технологію програмування, працює досить давно і успішно. Дана технологія показала свою ефективність, гнучкість, зручність і пристосованість (в сенсі реалізації на різних мовах і в різних операційних середовищах) при вирішенні найскладніших завдань, що вимагають опису безлічі паралельно працюють, взаємодіючих паралельних процесів.

На цьому практичні експерименти над абстрактними машинами можна завершити, а далі приступити до розгляду основ теорії паралельних процесів на базі розглянутої вище моделі СМКА, т. Е. Того, без чого будь-яка паралельна модель - набір блоків (як набір цифр в «касі» першокласника) . Але це буде темою вже наступного теоретичного експерименту.

література

1. Баранов С. І. Синтез мікропрограмних автоматів. Л .: Енергія, 1979. 232 с.
2. Короп PM, Міллер Р. Е. Паралельні схеми програм. // Кібернетичний збірник (нова сер.). Вип.13. М .: Світ, 1975. С. 5-61.
3. Вальковський В. А., Малишкін В.Е. Елементи сучасного програмування і суперЕОМ. Новосибірськ: Наука. Сиб. від., 1990. 143 с.
4. Шланскер М. С., Б. Рамакришна Рау. Явний паралелізм на рівні команд // Відкриті системи. 1999. № 11-12 .
5. Меліхов А. Н. Орієнтовані графи і кінцеві автомати. М .: Наука, 1971. 416 с.