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


 

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

66066. Национальные и региональные инвестиционные проекты РФ. Инвестиционные программы Омска 45.83 KB
  Согласно действующему законодательству инвестиционная деятельность на территории РФ может финансировать за счет: собственных финансовых ресурсов и внутрихозяйственных резервов инвестора (прибыль, амортизационные отчисления, денежные накопления и сбережения граждан и юридических лиц...
66067. Всемирный банк 38.27 KB
  В настоящее время под Всемирным банком фактически понимают две организации: Международный банк реконструкции и развития Международная ассоциация развития В разное время к ним присоединились созданные для решения задач Всемирного банка ещё три организации...
66068. Бюджетный дефицит в период до 1990 года 34.5 KB
  Падение объема производства естественно привело к сокращению доходной базы бюджета. Уклонение от налогов в условиях несовершенства налогового законодательства и существующего в обществе отношения к обязательности налоговых платежей...
66069. Бюджетный дефицит в зарубежных странах 32.5 KB
  Бюджетный дефицит в США Дефицит федерального бюджета США в 20112012 финансовом году завершившемся 30 сентября с. По сравнению с прошлым финансовым годом дефицит бюджета сократился на 16 в 2010-2011 финансовом году он составлял 1299 трлн долл.
66070. Инвестиционные и кредитные рейтинги РФ и регионов 161 KB
  Распределение российских регионов по рейтингу инвестиционного климата в 2010-2011 годах: Максимальный потенциал минимальный риск 1 10 Московская область 29 г.Санкт-Петербург 32 Краснодарский край Средний потенциал минимальный риск 2 1 Белгородская область...
66072. Негосударственный пенсионный фонд (НПФ) 40 KB
  Негосударственный пенсионный фонд (НПФ) — особая организационно-правовая форма некоммерческой организации социального обеспечения, исключительными видами деятельности которой являются...
66073. Ипотека. Ипотека с государственной поддержкой 66 KB
  Его обязательством перед кредитором является погашение кредита а обеспечивает исполнение этого обязательства залог недвижимости. Недвижимость приобретенная с помощью ипотеки является собственностью заемщика кредита с момента приобретения.
66074. Глобализация финансов 124.69 KB
  Вследствие финансовой глобализации национальные экономики становятся особенно уязвимы к потрясениям мировой финансовой системы основанной на необеспеченных реальными активами долларах США. Кроме того монетаристская основа денежной политики финансовых властей...