Библиотечный каталог авторефератов Украины

веде A(P) у стан, в якому значення всіх комірок, крім нижньої стрічки, дорівнює нулеві, а нижня стрічка містить лише символи {0,1}, при цьому їх послідовність інтерпретується як сума всіх чисел, що були занесені в клітинний автомат.

Розглядається узагальнення негабінарної моделі на випадок наявності дефектів в клітинному просторі автомата. В модель дефектів введено певні обмеження. Не допускається двох  діагонально-сусідніх дефектів. Введення додаткового правила дозволило "стрибати" через дефекти.

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

Описано автоматизовану систему для імітаційного моделювання клітинних автоматів. Наведено структуру системи, синтаксис формулювання правил та введення даних, алгоритми роботи основних модулів та формальну мову взаємодії з системою. Приклади роботи системи проілюстровано в додатку 1. В додатку 2 подано акти впровадження системи.

ОСНОВНІ  РЕЗУЛЬТАТИ  ТА  ВИСНОВКИ

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

1. Обгрунтовано доцільність використання клітинних автоматів, тобто пристроїв з однорідною архітектурою, які працюють на основі простих правил підстановки на станах своїх елементів для виконання асинхронно-паралельних алгоритмів обробки інформації.
2. Запропоновано універсальну модель клітинного автомата для масових асинхронно-паралельних арифметичних обчислень, що дало можливість з єдиних позицій представити асинхронно-паралельні арифметичні обчислення на клітинних автоматах незалежно від системи кодування.
3. На основі введеної моделі знайдено такі універсальні конфігурації розміщень початкових даних в робочому просторі автомата, з яких реалізація кожної арифметичної операції виводиться як частковий випадок, що дало можливість використовувати одну і ту ж систему правил для виконання різних арифметико - логічних операцій.
4. В результаті порівняння різних систем кодування знайдено універсальну негабінарну систему представлення даних (-2)n/r, яка найбільш підходить для арифметичних обчислень на клітинних автоматах з дійсними та комплексними числами, дозволяє ввести правила клітинного автомата, які не залежать ні від знаку, ні від розрядності чисел, що зберігає принципи однорідності і нарощуваності. Це дає можливість мінімізувати пристрій, а також вести паралельні обчислення з числами довільної довжини, не змінюючи алгоритмів обробки і динамічно розподіляти ресурси “обробляючої пам’яті” між різними задачами.
5. Доведено коректність знайдених систем правил клітинного автомата для арифметичних обчислень з дійсними та комплексними числами, що підтвердило вірність гіпотези про можливість побітно - асинхронної обробки інформації в арифметичних обчисленнях.
6. Зроблено узагальнення моделі клітинного автомата на випадок дефектів в робочому полі та випадок континуальних станів кожної комірки, що дає можливість підвищити надійність таких пристроїв, а також підвищити їх ступінь інтеграції.
7. Створено автоматизовану систему для імітаційного моделювання процесів застосування правил клітинного автомата, яка дала можливість перевірити властивості систем правил, відпрацювати алгоритми асинхронної обробки інформації в рамках запропонованої моделі, оцінити ефективність обчислень на клітинних автоматах, а також створити асинхронно-паралельні алгоритми для вирішення інших задач, що дало можливість використати її в конкретних впровадженнях.

Публікації за темою дисертаційної роботи

1. Вальковский В.А., Зербино Д.Д. Реализация арифметических вычислений в знакопеременных кодах на клеточных автоматах // Проблемы  управления  и  информатики.- № 2, 1997.- С. 49-64.
2. Вальковский В.А., Зербино Д.Д. К проблеме использования  клеточных  автоматов в качестве космических бортовых вычислительных устройств // Космічна наука і  технологія.- № 4, 1998.- C.49-54.
3. Фабри Л.П.,  Зербино Д.Д.  Об одном подходе к разработке диалоговых интерфейсов // Управляющие системы и машины.- 1986.- № 3.- С. 69-72.
4. Зербино Д.Д.  Перестановочная  модель обмена данными // Контрольно-измерительная техника.- 1988.- № 43.- С.80-82.
5. Вальковський В.О.,  Зербіно Д.Д.  Паралельні арифметичні обчислення на клітинних автоматах з дефектами // Комп'ютерна інженерія   та  інформаційні  технології: Вісник ДУ “Львівська політехніка”.- № 322.- 1997.- C. 20-24.
6. Зербіно Д.Д., Полєтаєв С.М. Алгебраїчні властивості правил перетворення клітинних автоматів // Комп'ютерна інженерія та інформаційні технології: Вісник ДУ “Львівська політехніка”.- № 349.- 1998.-  Т.1.- С. 147-153.
7. Вальковський В.О., Зербіно Д.Д. Організація асинхронного управління  процесом  розподіленої  обробки інформації // Волинський математичний вісник.-  Вип.2.-  Рівне,  1995.- С. 36-39.
8. Зербіно Д.Д.  Реалізація  двійкової арифметики засобами клітинних автоматів // Волинський математичний  вісник.- Вип.2.- Рівне, 1995.- С. 84-86.
9. Зербіно Д.Д.  Перспективи побудови обчислювальних систем на базі клітинних  автоматів // Збірник наукових праць “Комп’ютерні технології друкарства”.-  Львів.- 1998.- С. 173-178.
10. Зербіно Д.Д.  До вирішення проблеми  розробки  текстових процесорів на основі клітинних автоматів // Збірник наукових праць “Комп’ютерні технології друкарства”.- Львів.- 1998.- С.17-18.
11. Чабан В.Й., Зербино Д.Д. Условия вычисления матрицы леонодромии в электроэнергетических расчетах // Электрические цепи и системы.- Вып. 25.- 1990.- С. 46-48.
12. А.с. 1546972 МКИ G 06 F 7/52 Устройство для умножения-деления / Т.Г. Галамай, Д.Д. Зербино (СССР) № 4445726: заявлено 21.06.88, опубл. 28.02.90. Бюл. №8.- 3с.
13. Valkovskii V.A.,  Zerbino D.D.  Computation on Cellular Automata with Defects // Parallel Computing Technologies:  Proc. 4th Int. Conf. PaCT-97, Yaroslavl, Russia, 1997. (ed. V. Malyshkin), Springer, 1997, Lecture Notes in Computer Science.- V.1277. P. 136-144.
14. Зербино Д.Д.  Вычисления с комплексными числами на клеточных автоматах // Матер. Міжнар. наук. конф. “Сучасні проблеми механіки і математики”.- Львів, 1998.- С. 304-305.
15. Вальковський В.О., Зербіно Д.Д. До вирішення однієї комплексної проблеми обробки зображень на клітинних автоматах // Наукові  праці конф. “ДРУКОТЕХН-96”.-  Львів, 1996.- С. 22-23.
16. Грицык В.В., Вальковский В.А., Зербино Д.Д., Кисиль Б.В., Олексив Б.Я., Яджак М.С.  О некоторых направлениях исследований в области массовых параллельных вычислений // Наукові праці Першої Міжнар. наук.-техн. конф. з програмування “УкрПРОГ'98”.- Київ, 1998.- С. 286-295.
17. Вовчина З.М.,  Зербіно Д.Д. Реалізація представлення чисел у коді з від'ємними вагами // Наукові праці конф. “ДРУКОТЕХН-96”.- Львів, 1996.- C.94.
18. Дронюк І.М., Зербіно Д.Д., Цмоць І.Г. Перспективні структури процесорів цифрової обробки сигналів // Матер. міжнар. наук.-техн. конф. “Сучасні проблеми автоматизованої розробки і виробництва радіоелектронних засобів та підготовки інженерних кадрів”.- Львів, 1996.- Т.2.- С.193-194.
19. Зербіно Д.Д.  Про один засіб реалізації глобальних  операцій на клітинному автоматі // Тез. доп. 3-ї Української конф. з автоматичного  керування  “Автоматика-96”.- Севастополь, 1996.- Т.2.- С. 15-16.
20. Зербіно Д.Д.,  Цмоць І.Г.  Процесор сортування чисел на базі клітинних автоматів // Тез.  доп. 3-ї Української конф. з автоматичного керування “Автоматика-96”.- Севастополь, 1996.- Т.2.- С.177-180.
21. Вальковський В.О., Зербіно Д.Д. Моделювання однорідних обчислювальних  середовищ засобами клітинних автоматів // Тез. доп. 3-ї Української конф. з автоматичного керування “Автоматика-96”.-  Севастополь,  1996.- Т.2.- С. 7-8.
22. Фабри Л.П., Зербино Д.Д. Диалоговая информационная система на базе СМ-4 для анализа изменений в сосудистой системе человека на основании патогистологического исследования // Распараллеливание обработки информации: тез. докл. и сообщ. 5-й Всесоюз. школы-семинара.- Львов, 1985.- Ч.1.- С. 184-185.
23. Чабан В.Й., Билый Л.А., Кузьмяк Б.Д., Зербино Д.Д. Общий подход к анализу электрических машин // Тезисы  докладов Всесоюз. науч.-техн. конф. “Современные проблемы электромеханики”.- Ч.1.- Москва, 1989.- С. 121-122.

Особистий внесок. Положення, які складають суть дисертації, були сформульовані і вирішені автором самостійно:

1. Розробка системи правил функціонування клітинного автомата для реалізації арифметичних операцій з додатніми числами в двійковій системі кодування [2,8,16,19].
2. Розробка системи правил функціонування клітинного автомата для реалізації арифметичних операцій над дійсними числами в негабінарній системі кодування першого порядку [1,9].
3. Розробка системи правил функціонування клітинного автомата для реалізації арифметичних операцій та виразів над комплексними числами в негабінарній системі другого порядку [14].
4. Розробка системи правил функціонування клітинного автомата для обчислень над дійсними числами при наявності дефектів робочого простору автомата [5,13].
5. Доведення коректності асинхронних обчислень на клітинних автоматах в двійковій та негабінарній системах кодування [1,2].
6. Властивості операцій композиції та варіації правил перетворення станів автоматного простору [6].
7. Узагальнення моделі клітинного автомата на випадок дійсних значень комірок [10,15].
8. Розробка принципів функціонування автоматизованої системи для моделювання асинхронних алгоритмів [3,4,7,21,22].
9. Перевірка алгоритмів асинхронної обробки інформації [11,12,18,20,23].

Зербіно Д.Д. Паралельні арифметичні обчислення на клітинних автоматах. Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - Автоматизовані  системи управління та прогресивні інформаційні технології. Державний науково-дослідний інститут інформаційної інфраструктури, Львів, 1999.

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

Ключові слова: клітинний автомат, паралельна обробка, арифметичні обчислення, імітаційне моделювання, алгоритм паралельних підстановок.

Зербино Д.Д. Параллельные арифметические вычисления на клеточных автоматах. Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности  05.13.06 - Автоматизированные системы управления и прогрессивные информационные технологии. Государственный научно-исследовательский институт информационной инфраструктуры, Львов, 1999.

Диссертация посвящена решению комплекса проблем, связанных с реализацией арифметических вычислений на клеточных автоматах. Выполнен анализ исследований по параллельной обработке информации и определено место клеточных автоматов среди всех моделей параллельной обработки. Разработаны теоретические основы исследуемой модели в ориентации на арифметические вычисления. Введено и формально обосновано несколько систем правил преобразований для выполнения арифметических и логических операций, а также для реализации сложных выражений и массовых вычислений. Исследована их корректность и минимальность. Введен и изучен ряд обобщений клеточных автоматов. Описана реализованная автором система моделирования клеточных вычислений.

В первом разделе проведен анализ работ по параллельной обработке информации. Предложена классификация работ в области однородных вычислительных моделей. На основе анализа источников литературы определено место модели клеточных автоматов среди других однородных вычислительных моделей. Осуществлен сравнительный анализ известных моделей клеточных автоматов в различных областях знаний - физике, математике, биологии. Выделены общие особенности этих моделей и разработана классификация типов клеточных автоматов.

Во втором разделе даны теоретические основы вычислений на клеточных автоматах. Для формального определения понятия автоматного правила и условий его применения введено понятие клеточного шаблона. Правилом преобразования P на множестве Z2×Q, где Q - множество состояний ячеек, называется подстановка следующего вида:

P:    lM  → rM,

которая указывает, что множество состояний lM одномоментно заменяется на множество состояний rM на некотором шаблоне M.  Далее в разделе доказана теорема, состоящая из 12-ти частных утверждений. Они выражают условия выполнимости законов ассоциативности и коммутативности при различных вариантах применения правил. В разделе введены такие основополагающие понятия, как абстрактный клеточный автомат, однозначный клеточный автомат, минимальные по числу подстановок и по объему системы правил, завершающаяся система правил.

Третий раздел связан с реализацией арифметических и логических операций и с обоснованием их корректности. Клеточный автомат является корректным, если он однозначный, и его система правил для всех возможных начальных состояний завершающаяся. Доказаны теоремы о корректности систем правил для арифметических вычислений в двоичной и негабинарной системах кодирования. Сделан вывод о том, что для выполнения операций над действительными и комплексными числами необходимо использовать негабинарную систему кодирования с весами разрядов: (-2)(x+y)/k. Для действительных чисел k=1, а для комплексных k=2. В негабинарной системе 2-го порядка каждое комплексное число можно представить как сумму весов разрядов: {..., 4c, 4,-2c, -2, c, 1, -0.5c, -0.5, 0.25c, 0.25,... }, где с = - комплексная составляющая. Для вычислений над комплексными числами также введена система правил, состоящая из 8 правил, и доказана теорема, аналогичная теоремам для действительных чисел. На основе введених в теоремах правил рассмотрены примеры преобразования двоичного кода в негабинарный код 1-го порядка и пример построения многослойной структуры из отдельных двухмерных клеточных автоматов для реализации умножения матриц.

В четвертом разделе сделано обобщение модели клеточного автомата на случай, когда каждое значение ячейки представляет собой действительное число. В частности, доказана теорема относительно корректности и однозначности введеной системы правил. Рассмотрено обобщение негабинарной модели на случай появления дефектов в рабочем пространстве клеточного автомата. На модель дефектов наложены некоторые ограничения. В частности, не допускается появление двух диагонально-соседних дефектов. В разделе проанализирована эффективность вычислений на клеточных автоматах, установлена зависимость количества шагов вычислений от размера рабочей области, заполненной единицами. В разделе также описывается автоматизированная система для имитационного моделирования клеточных автоматов. Приводится структура системы, синтаксис языка описания правил и исходных данных, алгоритмы работы основных модулей и диалог с пользователем. Примеры работы системы проиллюстрированы в приложении.

Ключевые слова: клеточный автомат, параллельная обработка, арифметические вычисления, имитационное моделирование, алгоритм параллельных подстановок.

Zerbino D.D. Parallel Arithmetic Computations on Cellular Automata. Manuscript.

Thesis for Degree of Candidate of Technical Sciences in speciality 05.13.06 - Automatic Control Systems and Progressive Information Technologies. State Scientific Institute of Information Infrastructure, Lviv, 1999.

The dissertation is devoted to the solution of the complex problems connected with realization of arithmetic computations on cellular automata. The analysis of achievements in parallel information processing is fulfilled and the place of cellular automata between all parallel processing models is determined. Theoretical base of investigated model oriented on arithmetical computations is developed. Systems of replacement rules for realizing logical and arithmetical operations as well as for evaluating the complex expressions and massive computations are introduced and formally grounded. Their correctness and minimality are investigated. A number of generalizations of cellular automata is introduced and studied. Realized by the author system for simulation of cellular computations is described and realized.

Keywords: cellular automata, parallel processing, arithmetical computations, simulations, parallel substitutions algorithm.