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


 

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

82483. Социальная политика государства. Источники доходов населения. Система социальной защиты 30.8 KB
  Источники доходов населения. Доходы населения это совокупность средств и затрат в натуральном выражении для поддержания физического морального экономического и интеллектуального состояния человека. Формирования денежных доходов осуществляется за счет оплаты труда работников выплат из социальных фондов социальных трансфертов предпринимательских доходов Социальная защита населения это одно из важнейших направлений социальной политики государства заключающееся в установлении и поддержании общественно необходимого материального и...
82484. Государственное регулирование экономики: социальное неравенство, измерение распределения доходов. Черта бедности. Кривая Лоренца, коэффициент Джини 55.12 KB
  ГОСУДАРСТВЕННОЕ РЕГУЛИРОВАНИЕ ЭКОНОМИКИ одна из основных форм участия государства в экономике состоящая в его воздействии на распределение ресурсов и доходов на уровень и темпы экономического развития и благосостояние населения страны. К числу наиболее распространенных индикаторов дифференциации доходов населения относят коэффициент концентрации доходов индекс Джини и кривую Лоренца характеризующие степень удаления от состояния равенства в распределении доходов. Степень неравенства в распределении доходов в западной экономической...
82485. Теория сравнительных преимуществ и протекционизм. Международная торговля и распределение доходов 33.02 KB
  Она исходит из наличия двух стран и двух товаров; издержек производства только в виде заработной платы которая к тому же одинакова для всех профессий; игнорирования различий в уровне заработной платы между странами; отсутствия транспортных издержек и наличия свободной торговли. увеличению производства в отраслях ориентированных на экспорт и сокращению производства в отраслях конкурирующих с импортом. Теория ХекшераОлинадает возможность оценить последствия развития внешней торговли для владельцев различных факторов производства рабочих...
82486. Теории международной торговли (А. Смита, Д. Риккардо, Э. Хекшера, Б. Олина) 34.21 KB
  В своем труде Исследование о природе и причинах богатства народов в полемике с меркантилистами Смит сформулировал идею о том что страны заинтересованы в свободном развитии международной торговли поскольку могут выиграть от нее независимо от того являются они экспортерами или импортерами. Каждая страна должна специализироваться на производстве того товара где она обладает абсолютным преимуществом – выгодой основанной на разной величине затрат на производство в отдельных странах – участницах внешней торговли. При анализе направлений...
82487. Мировое хозяйство, понятие и эволюция. Интеграция в мировой экономике 32.42 KB
  Интеграция в мировой экономике Мировое хозяйство – совокупность национальногосударственных и негосударственных структур а также их взаимодействий на основе международного разделения труда и политических контактов. В данной трактовке мировое хозяйство представляет собой единое экономическое пространство мегаэкономику в котором субъектами хозяйственных отношений выступают: национальные экономики стран мира; субъекты мирового бизнеса – транснациональные корпорации и их альянсы; институты мирового хозяйства – международные экономические...
82488. Международная торговля: свобода торговли и протекционизм 33.52 KB
  Сторонники свободной торговли считают что международная торговля должна развиваться на основе рыночных сил спроса и предложения т. Экономические аргументы в защиту протекционистских мер: с помощью импортных пошлин страна может достичь улучшения условий торговли и увеличения экономического выигрыша; поддержка национальной промышленности на этапе ее зарождения и становления; повышение уровня занятости национальных ресурсов; смягчение кризиса в отраслях испытывающих экономические трудности; ограждение национальной экономики от мировых...
82489. Международная валютная система 30.96 KB
  Основной задачей мировой валютной системы МВС является регулирование сферы международных расчетов для обеспечения устойчивого экономического роста и поддержания равновесия во внешнеторговом обмене. Мировая валютная система представляет собой: определенный набор международных платежных средств; режим обмена валют включая валютные курсы; условия конвертируемости механизм обеспечения валютноплатежными средствами международного оборота; регламентацию форм международных расчетов; режим международных рынков валюты и золота; статус...
82490. Объект и предмет экономической теории. Методология экономической науки 35.64 KB
  Методология экономической науки. Первый раздел имеет методологическое фундаментальное значение так как служит основным средством исследования двух следующих разделов микроэкономики и макроэкономики. Это привело к появлению множества методов исследования экономической теории: Метод научной абстракции Отвлечение в процессе познания от внешних явлений не экономических сторон выделение более глубокой сущности предмета или экономического явления Метод функционального анализа Используется зависимость функцияаргумент для проведения...
82491. Основные направления и школы в экономической теории. Экономические законы и категории 34.86 KB
  Экономические законы и категории. Экономические законы и категории. Различают специфические общие и особенные экономические законы. Специфические экономические законы действуют в пределах исторически определенных форм хозяйствования.