|
Національне агентство з питань інформатизації
при Президентові України
Державний науково-дослідний інститут
інформаційної інфраструктури
ЗЕРБІНО Дмитро Дмитрович
УДК 681.513
ПАРАЛЕЛЬНІ АРИФМЕТИЧНІ ОБЧИСЛЕННЯ
НА КЛІТИННИХ АВТОМАТАХ
05.13.06 - Автоматизовані системи управління
та прогресивні інформаційні технології
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Львів-1999
Дисертацією є рукопис.
Робота виконана в Державному університеті "Львівська політехніка"
Міністерства освіти України.
Науковий керівник: доктор фізико-математичних наук, професор,
Вальковський Володимир Олександрович,
завідуючий відділом Державного науково-дослідного інституту інформаційної інфра-структури
Офіційні опоненти: доктор технічних наук, старший науковий співр.
Русин Богдан Павлович,
завідуючий відділом Фізико-механічного інституту ім. Г.В.Карпенка НАН України
кандидат технічних наук
Опотяк Юрій Володимирович,
старший науковий співробітник Державного науково-дослідного інституту інформаційної інфраструктури
Провідна установа: Інститут кібернетики ім. В.М.Глушкова НАН
України, відділ керуючих машин і систем, м. Київ.
Захист відбудеться "15"_липня_ 1999 року о 16 год. на засіданні спеціалізованої вченої ради Д 35.813.01 в Державному науково-дослідному інституті інформаційної інфраструктури (290601, м.Львів, вул. Наукова, 5а).
З дисертацією можна ознайомитись у бібліотеці Державного науково-дослідного інституту інформаційної інфраструктури (290601, м.Львів, вул.Наукова,5а).
Автореферат розісланий "14"травня1999 р.
Вчений секретар
спеціалізованої вченої ради
доктор технічних наук, ст.наук.сп._________________ Бунь Р.А.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність проблеми. В даний час намітилися три основні тенденції розвитку обчислювальної техніки. Це підвищення обчислювальної потужності; зниження собівартості біту інформації; наближення до користувача або до приладів та процесів, які використовують інформацію. Дана дисертаційна робота має відношення до перших двох тенденцій.
Більшість сучасних комп'ютерів структурно розділені на активний елемент - центральний процесор і пасивну пам'ять. Тому, при збільшенні об'єму пам'яті використання кожного її біту зменшується. З цього випливає, що підвищення обчислювальної потужності для задач з великими об'ємами даних в значній мірі пов'язане з розвитком методів розпаралелювання обчислень.
Масові паралельні обчислення стають все більш необхідними для створення та аналізу моделей складних систем, а також для обробки сигналів і об'ємних зображень. Також потрібними є моделі пристроїв та алгоритми, які дозволять дешево та просто виконувати масово-паралельні обчислення. Зменшення собівартості на всіх стадіях проектування та виробництва за рахунок високого ступеня стандартизації та однотипності є можливим, якщо вдається розбити схему на однакові фрагменти, зв'язки між якими повторюються при переході від одного фрагменту до іншого. Властивість регулярності структури притаманна моделі клітинних автоматів, яка серед інших моделей однорідних систем характеризується тим, що в ній відсутні засоби комутації між елементами. Це дає можливість спростити її апаратну реалізацію і методи синтезу програм.
Аналіз публікацій підтвердив, що немає математичної моделі клітинного автомата для виконання всіх арифметичних операцій та виразів. Створення такої моделі стало б поштовхом до розвитку широкого класу моделей стохастичного паралелізму при обробці інформації, оскільки арифметико-логічні операції є базовими. Таким чином, дослідження елементарних однорідних обчислювальних структур, зокрема структур без засобів комутації між елементами - так званих клітинних автоматів, доцільні як з теоретичної, так і з практичної точок зору.
Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалася в рамках завдання Державної науково-технічної програми “Перспективні засоби обчислювальної техніки. Аналітичне приладобудування. Телекомунікації.” Міністерства України у справах науки і технологій, яка виконується в Державному університеті “Львівська політехніка”.
Мета і задачі дослідження. Метою роботи є дослідження можливості застосування клітинних автоматів для реалізації паралельних арифметичних та логічних обчислень. Для її досягнення були поставлені наступні задачі.
- Розробити модель клітинного автомата, що може бути використана для побудови паралельних пристроїв та програм, в основу яких покладено алгоритми розпаралелювання логічних та арифметичних операцій на рівні окремих бітів даних.
- Дослідити і порівняти різні системи правил функціонування таких моделей в класичній і знакозмінній системі кодування чисел, визначити алгебраїчні властивості правил.
- Визначити оптимальну систему кодування та систему правил функціонування клітинного автомата для виконання паралельних арифметичних обчислень за наступними критеріями оптимальності: а) мінімальна кількість правил; б) максимальна швидкість досягнення результату; в) функціональна повнота в класі чотирьох арифметичних операцій - додавання, віднімання, множення та ділення.
- Розробити та обгрунтувати алгоритми реалізації логічних та арифметичних операцій над дійсними та комплексними числами.
- Створити автоматизовану систему для імітаційного моделювання клітинниих автоматів з довільною системою правил.
Наукова новизна одержаних результатів. В дисертаційній роботі вперше розроблено теорію побудови клітинного автомата для виконання паралельних обчислень з дійсними та комплексними числами та векторами на рівні окремих біт даних, а саме:
- введено нову модель клітинного автомата для арифметичних обчислень з дійсними та комплексними числами;
- вперше використано негабінарну систему кодування дійсних та комплексних чисел для клітинних автоматів;
- запропоновано новий метод асинхронних побітних обчислень дійсних та комплесних виразів;
- вперше розглянуто систему правил клітинного автомата для роботи при наявності дефектних комірок;
- розглянуто нові клітинні алгоритми для перетворення чисел з двійкової системи представлення в негабінарну;
- вперше розглянуто правила еквівалентного перетворення автоматного простору на випадок контінуальності стану кожної комірки;
- знайдено принципи побудови автоматизованої системи для імітаційного моделювання клітинних автоматів.
Практичне значення одержаних результатів. Теорія, методи, алгоритми і програми, які були розроблені в дисертаційній роботі, дозволяють:
- проектувати дешеві пристрої з однорідною структурою у вигляді здатних до переналаштування мікросхем “обробляючої пам'яті” для виконання масових паралельних обчислень в деякому класі задач;
- підвищувати надійність вказаних пристроїв за рахунок їх працездатності при виникненні дефектних комірок;
- застосовувати та відлагоджувати асинхронні алгоритми обробки інформації, які можуть бути реалізовані вказаними пристроями;
- моделювати та прогнозувати хід розвитку різних процесів, які представляються асинхронними правилами підстановки станів, зокрема, процесів асинхронних арифметичних обчислень.
Впровадження результатів роботи. Результати роботи були використані та впроваджені в наступних організаціях: Львівські міські електричні мережі - алгоритм масштабування електричних схем із збереженням надписів та позначень; Інститут прикладних проблем механіки і математики ім. Я.С.Підстригача НАН України, м. Львів - експерементальна оцінка правильності асинхронних алгоритмів; Карпатське відділення інституту геофізики ім. С.І.Субботіна НАН України, м. Львів - клітинна модель розповсюдження селевого потоку; Білоруський державний університет, м. Мінськ - впровадження в навчальний процес на факультеті прикладної математики та інформатики; Державний університет “Львівська політехніка” - впровадження в навчальний процес на факультеті комп’ютерних та інформаційних технологій; Українська академія друкарства - алгоритми фільтрації зображень, виділення контурів та середньої лінії рукописних шрифтів.
Апробація роботи. Основні положення і результати дисертаційних досліджень доповідались, обговорювались і отримали схвалення на щорічних науково-технічніх конференціях професорсько-викладацького складу Державного університету “Львівська політехніка”, а також на наступних конференціях: школі-семінарі “Распараллеливание обработки информации” (1985р.); Всесоюзній науково-технічній конференції “Современные проблемы электромеханики” (1989р.); 3-й Українській конференції з автоматичного керування “Автоматика-96” (1996р.); Школі-семінарі “Прикладні проблеми математики та інформатики” (1996р.); Міжнародній конференції “ДРУКОТЕХН” (1996р., 1998р.); Міжнародній науково-технічній конференції “Сучасні проблеми автоматизованої розробки і виробництва радіоелектронних засобів та підготовки інженерних кадрів” (1996р.); Міжнародній конференції “Parallel Computing Technologies-97” (1997р.); Міжнародній науковій конференції “Сучасні проблеми механіки і математики” (1998р.); Першій Міжнародній науково-технічній конференції з програмування УКРПРОГ'98 (1998р.).
Публікації. Основний зміст дисертаційної роботи викладено в 23 друкованих працях (в тому числі 11 статей, з них 6 в періодичних фахових виданнях, авторське свідоцтво).
Структура і обсяг роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, списку використаних літературних джерел із 149 найменувань і додатків. Робота викладена на 170 сторінках.
ОСНОВНИЙ ЗМІСТ РОБОТИ
Вступ містить обгрунтування актуальності вирішуваної проблеми. Наведено перелік задач, вирішення яких стає неможливим без засобів паралельної обробки і масового паралелізму. Описуються переваги застосування паралельних однорідних структур та їх типи. Клітинні автомати охарактеризовані як однорідні структури, які не мають засобів комутації між своїми елементами, а лише описуються правилами підстановки їх станів. Це дає можливість суттєво спростити і стандартизувати пристрої паралельної обробки інформації.
Перший розділ присвячено аналізові досліджень з паралельної обробки інформації. Здійснено класифікацію робіт в напрямку однорідних обчислювальних моделей. В результаті аналізу літературних джерел визначено місце моделі клітинних автоматів серед інших однорідних обчислювальних моделей. Проведено порівняльний аналіз відомих моделей клітинних автоматів з різних галузей знань - фізики, математики, біології. Виділено загальні особливості цих моделей та розроблено класифікацію типів моделей клітинних автоматів. Зроблено висновок, що теорія обчислень на бітовому рівні на однорідних структурах без засобів комутації між елементами лише починає розвиватись і вимагає комплексного підходу.
Подібна модель обчислень на макрорівні створює інший підхід до програмування. Так, в розділі вводиться поняття програми, що складається з наступних частин:
Preacts - частина, де описуються розбиття клітинного простору на регістри та аргументи арифметичного виразу, який необхідно обчислити;
Inacts - частина, в якій надаються початкові значення деяким областям - аргументам;
Comacts - частина, яка задає правила перетворення даних в комірках робочого простору та регістрах;
Outacts - частина, що вказує координати області результату обчислень.
Процес обчислення арифметичного виразу закінчується тоді, коли жодне правило перетворення даних не може бути виконано.
В другому розділі закладено теоретичні основи клітинних автоматів. Модель паралельних обчислень без засобів комутації між елементами розглянуто на основі поняття підстановок станів деякої впорядкованої множини. Для формального визначення правила та умови його застосування введено поняття клітинного шаблону. Клітинним шаблоном M називається скінченна підмножина множини Z2 вигляду:
M = {(0,0), (i1,j1), ..., (im,jm)},
де ik,jk ∈ Z. Шаблон M(i,j), який утворюється зсувом шаблону M на вектор (і,j), розглядається як (i,j)-варіація M(i,j) шаблону M:
M(i,j) = {(i,j), (i1+i,j1+j), ..., (im+i,jm+j)}.
Коли будемо говорити про застосовність правила, то під (i,j) будемо розуміти координати шаблону на автоматній площині. З поняттям застосовності правила пов'язане поняття розмітки шаблону M, де кожній його комірці відповідає одне значення з деякої множини станів Q:
lM={((0,0),q0), ((i1,j1),q1), ..., ((im,jm),qm)}.
Правилом перетворення P на множині Z2×Q називається підстановка наступного вигляду:
P: lM → rM, (1)
яка вказує, що множина станів lM одномоментно замінюється на множину станів rM на деякому шаблоні M.
Застосуванням правила P (або перетворенням P) в комірці (i,j) будемо вважати його (i,j)-варіацію, яка може бути виражена через перетворення варіації шаблону наступним чином:
P(i,j): lM(i,j) → rM(i,j). (2)
Для кожного правила (1) природнім чином визначається обернене до нього правило:
P-1: rM → lM.
Для варіації (2) також існує обернене перетворення:
P(i,j)-1: rM(i,j) → lM(i,j).
Відносно (i,j)-варіацій операція обернення зберігає "своєрідну" комутативність, оскільки від заміни місцями правої і лівої частини правила поняття (i,j)-варіації не залежить:
(P(i,j))-1 = P-1(i,j).
Якщо в автоматній площині послідовно виконується два правила P1(i1,j1) і P2(i2,j2), то ми будемо позначати цей факт як композицію варіацій:
P3(i1,j1) = P1(i1,j1) * P2(i2,j2).
Відповідно, P3(i1,j1) будемо розглядати як варіацію правила P3, яке утворилося в результаті композиції
P3 = P1 * P2(i2-i1, j2-j1),
оскільки композиція варіацій правил еквівалентна варіації їх композиції:
P(i,j) * R(i,j) = (P * R)(i,j).
Обернення композиції варіацій в загальному вигляді:
(P(i,j)*R(k,n))-1 = R-1(k,n)*P-1(i,j).
Правило R виразне в системі P={P1, P2,..., Pn}, якщо
∃(is,js)(R = Pk1(i1,j1)*Pk2(i2,j2)*...*Pkm(im,jm)),
де Pks∈P, s=1,...,m. Далі в розділі доведено теорему, яка складається з 12-ти тверджень. Вони виражають умови виконання законів асоціативності та комутативності при різних варіантах застосування правил та їх варіацій.
Абстрактним клітинним автоматом A на площині Z2 називається трійка:
A = (S,Q,P),
де S ⊆ Z2 - робоче поле автомату; Q - деяка множина станів, які можуть приймати комірки робочого поля S; P={P1, P2,..., Pn}, - деяка множина правил перетворення станів робочого поля.
Однозначний клітинний автомат можна розглядати як функцію:
A(P): QS → QR, (3)
де R ⊆ S називається областю результату обчислень.
Система правил P={P1, P2, ..., Pn} автомату A мінімальна по кількості правил, якщо для довільного Pi ∈ P система P\{Pi} реалізує функцію, яка відрізняється від (3). Система P мінімальна по кількості правил тоді і тільки тоді, коли жодне правило Pi не можна виразити в системі P\{Pi}. Таким чином, в мінімальній по кількості правил системі немає "зайвих" правил.
Система правил P мінімальна по об'єму правил, якщо не існує такого правила Pj з шаблоном Mj, який строго включається в шаблон Mi одного з правил Pi ∈ P, і заміна Pi на Pj в системі P не приведе до порушення функції (3). Цей варіант мінімальності говорить про те, що не можна зменшити шаблон жодного з правил.
Під загальним поняттям мінімальної системи правил буде розумітись система, що мінімальна як по кількості, так і по об’єму правил одночасно.
Завершувальність системи правил, за звичай, означає, що не існує нескінченної послідовності застосувань правил, які належать даній системі.
Третій розділ присвячено питанням реалізації арифметичних операцій на клітинних автоматах. Обгрунтовано коректність арифметичних та логічних операцій. Клітинний автомат A(P) є коректним, якщо він однозначний та його система правил для всіх можливих початкових станів QS є завершувальною.
Якщо стан QR довільної області R ⊆ S в клітинному просторі автомата інтерпретувати як деяке число, то коректні клітинні автомати можна використовувати для арифметичних обчислень. Доведено наступні теореми про коректність автоматів з системами правил для арифметичних обчислень в двійковій та негабінарній системах кодування.
ТЕОРЕМА 1. Для обчислення арифметичних виразів вигляду
f = (a1+a2+...+ak)*b /(2n-c)+d1+d2+...+dm
асинхронний клітинний автомат з системою правил {B1, B2, P0}:
є коректним і мінімальним для додатніх чисел в двійковій системі кодування.
Значення {r, x, s} під виразами правил належать регістру, дані в якому доступні для кожної комірки робочого простору автомата. Значеннями xi={0,1} позначені біти чисел. Число b=xkxk-1 ...xm і додатковий код xnxn-1...x0 числа c заноситься в проміжок між символами r і s в регістр.
Зроблено висновок, що для здійснення операцій над дійсними та комплексними числами необхідно використовувати негабінарну систему кодування з вагою розрядів: (-2)(i+j)/k. Для дійсних чисел k=1, а для комплексних k=2. За таких умов має місце наступна теорема:
ТЕОРЕМА 2. Для обчислення арифметичних виразів виду
f = (a1 ± a2 ± ... ± ak)*b /(-c) ± d1 ± d2 ± ... ± dm
з дійсними числами в негабінарній системі кодування 1-го порядку, асинхронний клітинний автомат з системою правил {B1, V1, V2 , P1 }:
і станами {0,1} є коректним і мінімальним.
В негабінарній системі 2-го порядку кожне комплексне число можна представити як суму ваг розрядів:
{..., 4c, 4,-2c, -2, c, 1, -0.5c, -0.5, 0.25c, 0.25,... },
де с = - комплексна складова. Для обчислень з комплексними числами також введено систему з восьми правил та доведено теорему, яка є аналогічною до теорем 1 і 2.
На основі введених у теоремах правил розглянуті приклади перетворення двійкового коду в негабінарний код 1-го порядку та приклад побудови багатошарової структури з окремих двохвимірних клітинних автоматів для реалізації множення матриць.
В четвертому розділі узагальнено моделі клітинного автомату. Зокрема, зроблено узагальнення моделі клітинних автоматів, коли кожне значення комірки являє собою дійсне число. При цьому додатково введено правила R1-R3 і доведено теорему.
ТЕОРЕМА 3. Послідовність застосувань правил {B1,V1,V2, R1-R3}:
| 
