39130

АНАЛІЗ ІСНУЮЧИХ СПОСОБІВ ПРЕДСТАВЛЕННЯ СХЕМ МІКРОПРОГРАМ ТА ІСНУЮЧИХ МЕТОДІВ ДЕКОМПОЗИЦІЇ ЦИХ СХЕМ

Курсовая

Информатика, кибернетика и программирование

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

Украинкский

2013-10-01

469.5 KB

1 чел.

1 АНАЛІЗ ІСНУЮЧИХ СПОСОБІВ ПРЕДСТАВЛЕННЯ СХЕМ МІКРОПРОГРАМ ТА ІСНУЮЧИХ МЕТОДІВ ДЕКОМПОЗИЦІЇ ЦИХ СХЕМ

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

1.1 Аналіз існуючих способів представлення схем мікропрограм

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

Результатами роботи метода декомпозиції є система пов’язаних автоматів, тому розроблюваний спосіб представлення алгоритму повинен дозволяти моделювання роботи декількох автоматів.

1.1.1 Мова логічних схем. Операторний метод

Робота над питанням про взаємовідношення можливостей обчислювальної машини й мислення почалася в радянській кібернетиці з розробок і доповідей Ляпунова А. А. [1]. Наукова діяльність Ляпунова почалася зі створення операторного методу програмування. Так був названий метод, що сполучав у собі визначення мови програмування - мови логічних схем й опис прийомів програмування на цій мові.

В основі операторного методу лежить принципово новий підхід до опису алгоритму. Відзначалося, що традиційні мови теорії алгоритмів, такі, як машини Тюрінга [2], нормальні алгоритми Маркова, рекурсивні функції, гарні для дослідження природи обчислюваності, але непридатні для опису алгоритму у формі, що зручна для рішення практичних завдань. В операторному методі знайшла реалізацію ідея "великоблочного" опису алгоритму, що відкриває шлях формалізації поняття алгоритм. Завдання строгого опису нової формалізації, яке б супроводжувалося доказом її адекватності традиційним мовам теорії алгоритмів, Ляпунов поставив перед своїм аспірантом А. П. Єршовим, і вона була вирішена в його кандидатській дисертації.

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

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

Логічні схеми Ляпунова використовувалися подвійно - для опису однієї конкретної програми й для опису цілого класу програм, що мають загальну структуру. Із введенням поняття програми основним стає завдання розробки  їх еквівалентних перетворень. Але оскільки формалізація програми зрівнює її з іншими формалізаціями алгоритму, проблема розпізнавання того, чи виконують дві програми ту й саму функцію, здобуває статус нерозв'язної. Виникає завдання моделювання програм об'єктами, що дозволяють розв’язувати еквівалентність. У якості таких і були взяті ті ж логічні схеми, але кожна з них тепер трактувалася як клас програм з однаковою структурою. Еквівалентність двох схем визначалася вимогою: яким би не була припустима спільна інтерпретація схем як програм, вона приводить до функціонально еквівалентних програм. Еквівалентні перетворення схем залишаються еквівалентними й для програм, що представлені схемами. Використання схем у другому змісті закріпило за ними назву схем Янова.

1.1.2 Схеми Янова

     Перед Ю.І. Яновим були поставлені завдання:

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

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

Для доказу повноти перетворень Яновим був успішно застосований апарат теорії логічних вирахувань, при якому правило перетворення трактується як аксіома.

Схеми Янова були введені в літературу в 1958 р. [3]. Ця робота стала класичною завдяки своїй повноті й закінченості: всі основні компоненти теорії перетворень програм у ній були явно сформульовані й у рамках побудованої системи понять майже до кінця пророблені.

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

Схема Янова являє собою лінійну послідовність операторів A1,...,An і розпізнавачів, що мають вид довільних булевських функцій від змінних p1,..., pk. Для схеми задається так називаний розподіл зрушень, що складає в зіставленні кожному операторові зрушення деякої підмножини змінних p1,...,pk. Змінні, що входять в зрушення деякого оператора, інтерпретуються як його результати.

У якості реалізації схем розглядається послідовність виконуваних операторів при проходженні за схемою від початку до кінця. Дві схеми вважаються еквівалентними, якщо збігаються їхні безлічі реалізацій. Яновим був знайдений алгоритм розпізнавання еквівалентності будь-яких двох схем і побудована повна схема перетворень, що містить 14 аксіом і 3 правила виводу. У роботі [4] теорія схем Янова була перенесена на мову графів. На рис. 1.1 представлена граф-схема програми, а на рис. 1.2 - схема Янова для цієї програми.

Виявилося, що нове визначення є більш адекватним розглянутій проблемі. Це знайшло своє відбиття, по-перше, у спрощенні аксіоматики перетворень: 14 аксіомам відповідало тільки шість аксіом. Крім того, новий апарат дозволив створити більш ефективне правило виводу, що використовує поняття логічної підпорядкованості. 

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

Схеми Янова були першою вдалою спробою формалізувати алгоритм програми й тому мали ряд істотних недоліків:

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

Рисунок 1.1 - Граф-схема алгоритму

Рисунок 1.2 - Схема Янова   

1.1.3 Схеми Мартинюка

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

Для схем Мартинюка була досліджена й практично повністю вирішена одна важлива методична проблема. Теорія схем програм стає істотно більш простою, якщо будь-який ланцюжок у деякій схемі програми є припустимим, тобто існує така інтерпретація, що реалізує цей ланцюжок. У той же час на практиці частіше зустрічаються програми, у яких реалізуються не всі послідовності команд, що допускають керуючим графом. Тому виникає наступна проблема: нехай деякими засобами, зовнішніми стосовно топології схеми G, описані обмеження на безліч ланцюжків схеми. Потрібно побудувати іншу схему G′, повна безліч ланцюжків якої збігається з безліччю ланцюжків схеми G, що відповідають зазначеним обмеженням. Виникає завдання знаходження найбільш загальної мови для опису обмежень на ланцюжки, а також методики побудови схеми G′. Перші кроки в рішенні цієї проблеми зведення були початі Смирновим, потім досить загальний результат було отримано Мартинюком [5].

Схеми Мартинюка виявилися зручною моделлю для опису ряду алгоритмів побудови транзитивних замикань бінарних відносин між вершинами і їхніх декомпозицій. Ці алгоритми мають велике значення для оптимізації програм. На рис. 1.3 наведена схема Мартинюка для розглянутої раніше граф-схеми на рис. 1.1.

Рисунок 1.3 - Схема Мартинюка


1.1.4 Схеми Лаврова

Схеми Лаврова були введені в літературу в 1961 р. у зв'язку з завданням економії пам'яті й зараз є найбільш уживаною моделлю для рішення прикладних завдань теорії програмування – головним чином для алгоритмів оптимізації програм. У схемах Лаврова досліджуються інформаційні зв'язки між операторами в умовах незмінності логічної структури програм. Формально вони визначаються в такий спосіб: береться схема Мартинюка, у якій кожному операторові приписується деяке число інформаційних входів і виходів (можна вважати, що оператор має не більше одного виходу). Входам і виходам довільним образом зіставляються символи змінних величин або комірок пам'яті.

Загальна теорія схем Лаврова ще не розроблена, всі конкретні роботи базуються на деяких допущеннях або обмеженнях, що грають роль достатніх умов, що забезпечують потрібну авторові еквівалентність. Фактично роль історії в схемах Лаврова грає інформаційно-логічний граф. Є й інший підхід для визначення інваріантів схем Лаврова. Інформаційний граф являє собою сукупність всіх інформаційних зв'язків, що реалізовані деякою конкретною операційно-логічною історією. У ряді випадків можна розглядати для завдань інформаційного зв'язку між операторами A й B безліч всіх шляхів у схемі від A до B, що реалізують цей зв'язок. Такі шляхи називаються маршрутами інформаційного зв'язку. Безліч всіх маршрутів всіх інформаційних зв'язків схеми Лаврова є більш вузьким інваріантом, чим сукупність інформаційно-логічних графів.

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

Єршов розглянув варіант схем Лаврова, у яких інформаційні зв'язки між входами й виходами операторів задаються не за допомогою імен змінних, а явно у вигляді додаткового інформаційного графа схеми. Це дозволяє побудувати теорію, що не залежить від різних варіантів розподілу пам'яті. Корисність такого підходу виявилася в завданнях оптимізації програм й у паралельному програмуванні. Схема Лаврова для розглянутої раніше граф-схеми (рис. 1.1) наведена на рис. 1.4.

Рисунок 1.4 - Схема Лаврова

Порівняльну характеристику розглянутих схем програм надано в табл.1.1.

Для порівняння використовувалися наступні важливі характеристики схем:

  •  використання графічної форма зображення схем;
  •  стандартизованість схеми;
  •  можливість використання схем лише для одного типу керуючих автоматів;
  •  об’єктно орієнтований підхід до моделювання.

Операторний метод та схеми Мартинюка, Лаврова були першими спробами переходу від текстового опису програм до графічного, тому мають багато недоліків. Р-схема та граф-схема були першими вдалими спробами стандартизувати зображення алгоритму програми. Р-схема дозволяла більш компактно зображувати алгоритм, але використовувала нестандартні позначення.  “Графсет  та  мережа  Петрі  більш  придатні  для опису  складних

Таблиця 1.1 – Порівняння розглянутих способів представлення схем програм

Назва

Графічна форма

Стандарт

Опис тільки одного типу КА

ООМ

Операторний метод

   +

Схема Янова

Схема Мартинюка

   +

Схема Лаврова

   +

Р-схема

   +

+

+

Граф-схема

   +

+

Мережа Петрі

   +

+

Графсет

   +

+

SDL

   +

+

+

+

UML

   +

+

+

паралельних   процесів, але можуть використовуватися і для зображення алгоритму програми. Слід зазначити, що стандарти “Графсет” та SDL є безкоштовними, але програми, що надають графічний інтерфейс та засоби моделювання, перевірки схем є платними. Для порівняння також було розглянуто мову UML, що є стандартизованою мовою моделювання та дозволяє зображувати алгоритм програми, використовуючи стандартні, прості та зрозумілі графічні позначення. UML використовує об’єктно орієнтований підхід до моделювання, що дозволяє зображувати структуру системи, її поведінку та динаміку, що неможливо в розглянутих способах представлення схем програм, окрім SDL. Кожна з розглянутих схем має власні достоїнства та недоліки, тому необхідно розробити спосіб представлення алгоритму мікропрограми, що  використовує прості та зрозумілі графічні позначення, дозволяє моделювати автомата обох типів, дозволяє моделювати роботу декількох автоматів та має формалізовану семантику. З розглянутих способів представлення схем програм UML відповідає цим вимогам, але UML є уніфікованою мовою моделювання тому іноді дозволяє використовувати для моделювання декілька підходів, наприклад, використання складних сторожових умов або простих сторожових умов разом з елементом “Рішення”. Використовуючи нотацію UML необхідно розробити нотацію, що не містить неоднозначностей.

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

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

Висновки

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

  1.  виконати аналіз підмножини уніфікованої мови моделювання, що дозволяє моделювати керуючі автомати. На основі цієї семантики  розробити семантику, що дозволяє представляти алгоритм роботи керуючого автомата у простій та зрозумілій формі. Результатом рішення цієї задачі є формалізована семантика, що дозволяє представляти алгоритм керуючого автомата.
  2.  Розробити метод декомпозиції алгоритму керуючого автомата для його реалізації на заданій кількості пристроїв. Розроблюваний метод зважає на технічні можливості сучасних апаратних пристроїв та перспективні варіанти розвитку у даній області. Результатом вирішення цієї задачі є отримання гнучкого та розширюваного методу, який може використовуватися як незалежно, так і в межах інших систем і сам, в свою чергу, може інтегрувати інші методи.
  3.  Адаптація метода декомпозиції для розробленого способу представлення алгоритму керуючого автомата. Результатом вирішення цієї задачі є адаптація результатів метода декомпозиції до обраного способу моделювання алгоритму керуючого автомата, що дозволяє зображувати роботу автоматів після декомпозиції початкового алгоритму.


 

А также другие работы, которые могут Вас заинтересовать

24997. Основные этапы становления информационного общества. Информационные ресурсы государства, их структура. Образовательные информационные ресурсы 75.5 KB
  Информационные ресурсы государства их структура. Образовательные информационные ресурсы. Развитие новых информационных технологий и их быстрое проникновение во все сферы жизни породило новое направление в современной информатике социальная информатика включающее в себя следующую проблематику: информационные ресурсы как фактор социальноэкономического и культурного развития общества; закономерности и проблемы становления информационного общества; развитие личности в информационном обществе; информационная культура; информационная...
24998. Клавиатура (Keyboard) 31.69 KB
  Принцип действия клавиатуры Основным элементом клавиатуры являются клавиши. Сигнал при нажатии клавиши регистрируется контроллером клавиатуры и передается в виде так называемого скэнкода на материнскую плату. На материнской плате ПК для подключения клавиатуры также используется специальный контроллер. Когда скэнкод поступает в контроллер клавиатуры инициализируется аппаратное прерывание процессор прекращает свою работу и выполняет процедуру анализирующую скэнкод.
24999. Принцип работы модемов 62.47 KB
  Современные модемы обеспечивают гораздо большую скорость передачи данных. Применяемые в них протоколы передачи данных и коррекции ошибок обеспечивают надежную связь даже на не очень хороших телефонных линиях. В процессе передачи компьютерных данных по большинству линий связи выполняется двойное их ' преобразование: поток данных из компьютера побайтно преобразуется в последовательность отдельных бит которая далее превращается в сигнал при годный для передачи по телефонным линиям. Принимаемые данные претерпевают обратное преобразование: из...
25000. О мониторах - подробнее 131 KB
  Количество точек по горизонтали и по вертикали которые могут изображаться на экране монитора называется его разрешением. Принцип работы электроннолучевого монитора стеклянная колба сигналы управления лучом электронная пушка покрытие из люминофора электронный луч же монитора может меняться за счет объединения соседних триад. Количество раз которое сменится изображение на экране электроннолучевого монитора за 1 секунду называется частотой кадровой развертки.
25001. Манипуляторы 37.71 KB
  Наиболее распространенным из них является так называемая Мышь Она служит для ввода данных или одиночных команд выбираемых из меню ли текстограмм графических оболочек выведенных на экран монитора. Мышь представляет собой небольшую коробочку с двумя или тремя клавишами и утопленным свободно вращающимся в любом направлении шариком на нижней поверхности. Для работы с мышью необходима плоская поверхность с этой целью используют резиновые коврики Mouse Pad. Так как с помощью мыши нельзя вводить в компьютер серии команд поэтому мышь и...
25002. Текстовый редактор. Назначение и основные возможности 59.21 KB
  Обычно текстовыми редакторами принято называть программы выполняющие простейшие операции по редактированию текста а процессорами программы обладающие расширенными по сравнению с редакторами средствами для компьютерной обработки текста. В процессе подготовки текстовых документов можно выделить следующие этапы: набор текста; редактирование; форматирование текста разметка страниц; печать просмотр перед печатью текста на экране печать на бумаге. Основные функции текстовых процессоров: создание документов; редактирование документов...
25003. ПОЧЕМУ РАБОТА ЗА КОМПЬЮТЕРОМ ЧАСТО ПРИВОДИТ К БОЛИ 82.5 KB
  Выплачиваемые компенсации достигают астрономических размеров а некоторым пострадавшим от работы за компьютерам приходится расплачиваться жестокими болями в течение всей жизни. Недавние исследования показали что примерно 20 нарушений здоровья связанных с работой за компьютером вызваны не вредностью компьютера как такового а незнанием основных правил работы с ним а также неправильной организацией рабочего места. В 1996 году Государственный комитет санитарноэпидемиологического надзора утвердил Гигиенические требования к видеодисплейным...
25004. Понятие информации. Информационные процессы 48.19 KB
  Мы говорим: я получил важную информацию у меня недостаточно информации для принятия решения кто владеет информацией правит миром не особенно задумываясь о том что же такое информация. В этом заключена одна из особенностей понятия информации: оно относится к числу базовых понятий таких как число в математике которые можно пояснять уточнять использовать но нельзя однозначно определить. Юристы например используют определение из закона Об информации информатизации и защите информации: информация сведения о лицах предметах...
25005. Принтер — основное устройство для вывода инфор 48.5 KB
  Во время печати на его поверхность подается высокое напряжение которое распределяет статический заряд по поверхности барабана. У цветных лазерных принтеров соответствующие и стоимость и скорость печати. Поскольку лазер формирует прообраз изображения целиком на барабане то к моменту печати он уже полностью должен быть в памяти принтера. Большой объем памяти требуется при печати большого потока документов.