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.  Адаптація метода декомпозиції для розробленого способу представлення алгоритму керуючого автомата. Результатом вирішення цієї задачі є адаптація результатів метода декомпозиції до обраного способу моделювання алгоритму керуючого автомата, що дозволяє зображувати роботу автоматів після декомпозиції початкового алгоритму.


 

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

34097. Изъятие (выкуп) земельных участков для государственных и муниципальных нужд: основания, порядок 62.5 KB
  Следует иметь в виду что предполагаемое назначение объекта должно соответствовать полномочиям органа принимающего решение об изъятии земельного участка. Например решение об изъятии земельного участка для целей связанных с защитой Государственной границы России может быть принято только органами государственной власти Российской Федерации согласно п. Данное обстоятельство по сути означает что в случае возникновения судебного спора орган принявший решение об изъятии земельного участка должен будет представить суду убедительные...
34098. Право ограниченного пользования чужим земельным участком (сервитут). Обременения земельного участка 33 KB
  Обременения земельного участка. Однако возможно рассмотрение сервитута в качестве обременения земельного участка.С точки зрения собственника земельного участка который соседи используют для прохода к водоему сервитут является ограничением его права. Публичные сервитуты могут устанавливаться для:1 прохода или проезда через земельный участок;2 использования земельного участка для ремонта коммунальных инженерных электрических и других линий и сетей а также транспортной инфраструктуры;3 размещения на участке межевых и геодезических знаков...
34099. Право пользования земельным участком собственником недвижимости. Последствия утраты собственником недвижимости права пользования земельным участком 93 KB
  В случае когда земельные участки находящиеся в государственной или муниципальной собственности предоставляются за плату наряду с решением органа государственной власти или местного самоуправления о предоставлении земельного участка юридический состав образует также договор куплипродажи земельного участка. При наследовании земельного участка по наследству переходят также находящиеся в границах этого земельного участка поверхностный почвенный слой замкнутые водоемы находящиеся на нем лес и растения. Раздел земельного участка...
34100. Права и обязанности субъектов, использующих землю. Защита их прав 52.5 KB
  Взаимосвязанные между собой права и обязанности субъектов земельных правоотношений составляют суть содержания любого правоотношения. Права субъектов земельных правоотношений можно классифицировать на две основные группы: 1. Право на действия субъектов земельных правоотношений можно подразделить на: а виды действий. Право на бездействие субъектов земельных правоотношений можно подразделить на: а полное бездействие.
34101. онятие и особенности ответственности в области использования и охраны земель 25.5 KB
  Ответственность за земельные правонарушения. Ответственность нужно понимать в двояком смысле: юридическая ответственность как правовой институт в объективном смысле это совокупность юридических норм устанавливающих неблагоприятные последствия за совершение правонарушения в области использования и охраны земель и порядок их возложения на правонарушителя; в субъективном смысле юридическая ответственность это обязанность лица виновного в совершении правонарушения претерпеть неблагоприятные последствия предусмотренные законом...
34102. Земельно-правовая ответственность. Дисциплинарная ответственность в области использования и охраны земель 29 KB
  Специфической санкцией земельноправовой ответственности является земельного участка у собственника либо принудительное прекращение прав на земельный участок. 45 и 47 ЗК орган государственного земельного контроля налагает административное взыскание и одновременно выносит предупреждение о необходимости устранения нарушения; в этом предупреждении указывается допущенное правонарушение его содержание суть устанавливается срок для устранения допущенного правонарушения; разъясняются права земледельца землепользователя в случае...
34103. Гражданско-правовая ответственность за правонарушения в области использования и охраны земель 31.5 KB
  И хотя в настоящее время имущественная ответственность еще не нашла своего подобающего места среди других форм юридической ответственности будущее за ней неоспоримо так как ухудшение качества земель и всей окружающей среды влечет как правило имущественные последствия предполагающие возможность возмещения вреда восстановления земель и нарушенных экологических систем. Гражданским законодательством предусматривается ряд правил выработанных за тысячелетия: вред причиненный личности организации или имуществу подлежит возмещению в...
34104. Административная ответственность за правонарушения в области использования и охраны земель 37 KB
  АДМИНИСТРАТИВНАЯ ОТВЕТСТВЕННОСТЬ Согласно Кодексу РФ об административных правонарушениях КоАП от 30 декабря 2001 г. Кроме того в официальных кругах стала преобладать концепция отмирания социалистического государства и уменьшения административных принудительных средств воздействия на правонарушителей необходимости перехода к добровольному исполнению своих обязанностей перед обществом повышения моральных стимулов. Основным органом наложения административных взысканий стала административная комиссия при исполнительных комитетах...
34105. Уголовная ответственность за регистрацию незаконных сделок с землей (ст. 170 УК РФ) 22 KB
  Уголовная ответственность за регистрацию незаконных сделок с землей ст. 254 УК; государственная регистрация незаконных сделок. Государственная регистрация незаконных сделок с земельными участками ст.