WWW.UK.X-PDF.RU

БЕЗКОШТОВНА ЕЛЕКТРОННА БІБЛІОТЕКА - Книги, видання, автореферати

 
<< HOME
CONTACTS




Продажа зелёных и сухих саженцев столовых сортов Винограда (по Украине)
Тел.: (050)697-98-00, (067)176-69-25, (063)846-28-10
Розовые сорта
Белые сорта
Чёрные сорта
Вегетирующие зелёные саженцы

Продажа зелёных и сухих саженцев столовых сортов Винограда (по Украине)
Тел.: (050)697-98-00, (067)176-69-25, (063)846-28-10
Розовые сорта
Белые сорта
Чёрные сорта
Вегетирующие зелёные саженцы

«УДК 004.21 В.М. Грига Національний університет ”Львівська політехніка”, кафедра електронних обчислювальних машин ПОБУДОВА ТА АНАЛІЗ РЕКУРСИВНИХ ПРОСТОРОВО-ЧАСОВИХ ГРАФІВ © Грига В.М., ...»

УДК 004.21

В.М. Грига

Національний університет ”Львівська політехніка”,

кафедра електронних обчислювальних машин

ПОБУДОВА ТА АНАЛІЗ

РЕКУРСИВНИХ ПРОСТОРОВО-ЧАСОВИХ ГРАФІВ

© Грига В.М., 2007

Розглянуто особливості побудови рекурсивного просторово-часового графу на

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

затрати обладнання та побудовано часову матрицю суміжностей.

They consider pecularities of recursive space-time graph drawing parallel multiplication algorithm on example. Timeng parameters and computational burden has been analyzes of the build timeng dependency matrix.

Вступ. Математичною основою для проектування універсальних обчислювальних машин стала теорія абстрактних автоматів (Мілі та Мура) [1], фундаментальним поняттям яких є поняття стану. Це поняття відповідає унікальним діям машини протягом визначеного проміжку часу (синхротакту роботи), а сам абстрактний автомат покликаний забезпечити послідовність у часі переходів з одного стану до іншого для реалізації заданого алгоритму. Фундаментальним механізмом для реалізації часової послідовності станів є використання комірок пам’яті, які дають змогу фіксувати поточний стан і на основі функцій переходів визначати до якого наступного стану необхідно перейти. Також, окрім попереднього стану, на визначення наступного стану впливають вхідні дані.

Математичною основою для проектування спеціалізованих процесорів стала теорія потокових графів (або графів потоків сигналів), у якій вершинам графів відповідають обчислювальні операції, а дугам – лінії передачі даних для обробки. Необхідно зазначити, що потокові графи дають змогу проектувати спеціалізовані пристрої для класу алгоритмів, структура яких не залежить від вхідних даних (алгоритми без галужень [2] або інваріантні до зсуву алгоритми [3]). У випадку галужень необхідно використовувати графи станів (абстрактних автоматів), які широко використовуються для проектувань керівних пристроїв.

Хоча потокові графи майже повністю відображають структуру обчислювального пристрою, проте у багатьох випадках з погляду апаратних ресурсів (розміру кристала інтегральної схеми) або некритичних часових параметрів доцільно реалізувати обчислення декількох операцій (вершин) за допомогою одного обчислювального елемента. Такий процес оптимізації апаратних затрат може відповідати зменшенню ступеня паралелізму або виконанню послідовних у часі операцій за допомогою одного елемента (рекурсія).

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

Саме для формалізації такого процесу проектування оптимізованих за апаратними затратами спеціалізованих пристроїв було запропоновано методику нового класу просторово-часових графів [4].

Просторово-часові графи характеризуються трьома типами об’єктів: вершинами, дугами та вузлами. Оскільки більшість операцій не є унарними і для них використовують більше одного вхідного оперенда, необхідно вміти відрізнити незалежні входи заданої вершини від послідовних надходжень вхідних даних. З цією метою введені поняття вхідних та вихідних вузлів вершини графу. Під вузлом вершини графу розуміють незалежні входи (або виходи) цієї вершини, послідовність входів (або виходів) гілок до яких однозначно визначає послідовність передавання даних.

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

Просторово-часове перетворення вибраного алгоритму. Як паралельний алгоритм множення вибрано дерево Уоллеса [5]. На рис. 1 зображено структурну схему двійкового підсумовування часткових добутків за допомогою дерева Уоллеса для чотирирозрядних чисел.

Рис. 1. Структурна схема дерева Уоллеса

На цьому рисунку СМ – операція повного двійкового підсумовування, а НС – операція неповного двійкового підсумовування.

Математичною основою для представлення обчислювальної структури дерева Уоллеса є потоковий граф. Виявити паралелізм і навіть керувати ним, забезпечуючи тим самим можливість знаходження компромісних просторово-часових співвідношень, що є основним для вибору структури обчислювального пристрою, можна за допомогою зображення потокового графу алгоритму в ярусно-паралельній формі [6, 7].

Ярусно-паралельна форма потокового графу(ЯПФ ПГ) – це такий граф, у якого всі вершини розділені на яруси так, що в межах одного ярусу між вершинами потокового графу немає зв’язків. У ЯПФ ПГ усі вершини одного ярусу залежать від результатів попереднього ярусу і не залежать від вершин наступних ярусів. Ярусно-паралельна форма визначає ступінь паралелізму графу (максимальна кількість вершин на одному ярусі), а також мінімально можливий час обчислення цього алгоритму (кількість ярусів).

Застосувавши операцію ранжування до ЯПФ ПГ, яка дає змогу на всіх дугах, які перетинають яруси, ставити елемент затримки, що дорівнює одному такту, отримаємо ранжовану ЯПФ ПГ.

Треба зазначити, що подальший перехід до просторово-часових графів здійснюється на основі ранжованої ЯПФ ПГ, до якої застосовуються операції стиску за висотою та шириною. Розрізняють послідовні, паралельні та рекурсивні просторово-часові графи. Розглянемо часові параметри цих графів, які характеризують швидкодію алгоритму – це пропускна здатність та часова затримка.

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

Часова затримка – це час, протягом якого обробляються дані, починаючи від першого вхідного числа до часу отримання на виході повного результату.

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

Стискаючи усі вершини ранжованої ЯПФ ПГ до однієї, отримаємо рекурсивний просторовочасовий граф, в якому всі операції виконуються однією вершиною за допомогою зворотних зв’язків. На рис. 2. зображено рекурсивний просторово-часовий граф дерева Уоллеса. З метою ефективного виконання операції множення на цьому графі множене і множник попарно розділені на старші і молодші розряди, які надходять на елементи затримки.

–  –  –

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

Біля елементів затримки записані числа за такої формулою:

M ( N ( Z )), (1) де M – номер вихідної дуги з елемента затримки; N – номер вхідного числа; Z – затримка на потрібну кількість тактів.

Біля дуг, які надходять на вхідні та вихідні вузли, записані номери тактів, під час яких проходять необхідні дані. Часова затримка та пропускна здатність для рекурсивного просторовочасового графу збігаються і становлять 15 тактів.

Маючи рекурсивний ПЧГ дерева Уоллеса, можна побудувати структуру рекурсивного обчислювального пристрою.

Затрати обладнання рекурсивного обчислювального пристрою визначаються за формулою:

WЗО = 72Reg + 2 Mux2 + 1Mux3 + 1Mux6 + 2 Mux6 + 2 Mux8 + 2 Mux9 + 2 Demux12 + WОБ, (2) де Re g – регістр; Muxn – мультиплексор ( n – кількість входів); Demux m – демультиплексор ( m – кількість виходів); WОБ – затрати обладнання на операцйний блок.

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


Купить саженцы и черенки винограда

Более 140 сортов столового винограда.


Для формального опису просторово-часових графів можна використати матрицю суміжностей, у якій по вертикалі будуть представлені вхідні, а по горизонталі – вихідні “точки” схеми, а також вхідні та вихідні точки кожної вершини. У кожній комірці aij можна вказати номери тактів, під час яких під’єднуватимуться ті або інші входи та виходи.

Так, для рекурсивного просторово-часового графу матриця суміжностей матиме такий вигляд:

–  –  –

Рис. 3. Часова матриця суміжностей рекусивного просторово-часового графу Часова матриця суміжностей рекурсивного просторово-часового графу складається з 9 вхідних та 3 вихідних точок вершини. У комірках матриці вказані номери тактів, під час яких спрацьовують необхідні входи та виходи.

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

1. Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз, 1962. 2. Кун С. Матричные процессоры на СБИС. – М.: Мир, 1991. 3. Мельник А.О. Спеціалізовані комп’ютерні системи реального часу. – Львів, 1996. – 53 с. 4. Ерметов Ю.О. Проектування обчислювальних структур на основі просторовочасових графів // Вісн. Хмельницьк. нац. ун-ту. – 2005. – № 2. 5. Цилькер Б.Я.,Орлов С.А. Организация ЭВМ и систем: Учеб. для вузов. – СПб:. Питер, 2006. – 668 с. 6. Поспєлов Д.А. Введение в вычислительные системы. – М.: Сов. радио, 1972. 7. Дунець Р.Б: Аналіз та синтез топологій комп’ютерних видавничополіграфічних систем: Монографія. – Львів: НВФ “Українські технології”, 2003. – 192 с.

–  –  –

ПІДВИЩЕННЯ РІВНЯ ІНТЕЛЕКТУ ПРОЦЕСОРНИХ КОМПЛЕКСІВ

КОНТРОЛЮ ТА ДІАГНОСТИКИ ЕНЕРГООБ’ЄКТІВ

© Дороніна О.М., Хомич С.В., 2007.

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

This paper presents intellectualization principles of the control and diagnostic tools of power objects. The features of transferring from the level of measure procedures hardcoded multifunctional tools to levels of noniterative and iterative adaptive tools are investigated.

Вступ. Успішне вирішення проблеми енергозбереження неможливе без підвищення рівня структурно-алгоритмічного синтезу комплексів контролю та діагностики енергооб’єктів (ККДЕ), що передбачає насамперед поліпшення метрологічних характеристик результатів вимірювань параметрів електроенергії за оптимального ступеня реалізації потенційної точності вимірювальних перетворень та забезпечення функціональної повноти контролю. Підвищення метрологічної якості вимірювальних перетворень, а також розширення функціональних можливостей сучасних процесорних ККДЕ тісно пов’язані з їхньою інтелектуалізацією, яка залежить від комплексного використання апаратних та програмно-алгоритмічних можливостей на основі апріорної (банку знань та банку даних) та поточної інформації про мету та умови вимірювань.

Огляд літературних джерел З огляду на [1], метрологічний рівень результатів вимірювань параметрів електроенергії залежить, насамперед від забезпечення таких властивостей вимірювальних процедур, як:

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

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



Похожие работы:

«УДК 006.91:62 ©Мартинов А.П., Тріщ Р.М.АНАЛІЗ СУЧАСНОГО СТАНУ НОРМУВАННЯ ТОЧНОСТІ ГЕОМЕТРИЧНИХ ПАРАМЕТРІВ ВИРОБІВ У МАШИНОБУДУВАННІ 1. Постановка задачі Вступ України до Світової організації торгівлі (СОТ) має покращити, перш за все, структуру експорту на користь високотехнологічної конкурентоспроможної машинобудівної продукції з високим рівнем якості. Поняття якості для виробників машинобудівної продукції пов'язане, в першу чергу, з забезпеченням геометричної взаємозамінності складанних...»

«ІВАНО-ФРАНКІВСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ НАФТИ І ГАЗУ На правах рукопису АШИКОВА Евеліна Ібрагимівна УДК 353.1: 502/504 МЕХАНІЗМИ РЕАЛІЗАЦІЇ ДЕРЖАВНОЇ ЕКОЛОГІЧНОЇ ПОЛІТИКИ НА РЕГІОНАЛЬНОМУ РІВНІ Спеціальність 25.00.02 – механізми державного управління Дисертація на здобуття наукового ступеня кандидата наук з державного управління Науковий керівник – Грицяк Ігор Андрійович, доктор наук з державного управління, професор, заслужений діяч науки і техніки України Івано-Франківськ – 2014...»

«ЗАТВЕРДЖУЮ Директор Свалявського професійного будівельного ліцею _ М.І.Гулович ПЛАН роботи учнівської ради Свалявського професійного будівельного ліцею на 2013-2014 навчальний рік У 2012-2013 н.р. робота Учнівської Ради органу учнівського самоврядування Свалявського професійного будівельного ліцею була спрямована на формування в учнів активної життєвої позиції, їх соціальної підготовки до активної участі в демократичному управлінні суспільством. Відповідно до основних положень Концепції...»

«МІЖРЕГІОНАЛЬНА АКАДЕМІЯ УПРАВЛІННЯ ПЕРСОНАЛОМ МЕТОДИЧНІ РЕКОМЕНДАЦІЇ ЩОДО ЗАБЕЗПЕЧЕННЯСАМОСТІЙНОЇ РОБОТИ СТУДЕНТІВ здисципліни “ІНСТИТУТ ПРЕЗИДЕНСТВА” (длябакалаврів) Київ 200 Підготовлено доцентом кафедри політології М.А.Остапенко Затверджено на засіданні кафедри політології (протокол № 1 від 07.09.07) СхваленоВченоюрадоюМіжрегіональноїАкадеміїуправлінняперсоналом ОстапенкоМ.А.Методичні рекомендації щодо забезпечення самостійної роботи студентів з дисципліни “Інститут президенства” (для...»

«Вісник ОНУ Том 8, випуск 9,2003 УДК 316.77 Т. Є. Мосійчук, асист. Одеський національний університет ім. 1.1. Мечникова, Інститут соціальних наук, відділення соціології СОЦІАЛЬНА РЕАБІЛІТАЦІЯ ЯК МЕХАНІЗМ ВІДНОВЛЕННЯ СОЦІАЛЬНИХ зв'язків у соціумі В основу статті поставлені питання вивчення механізмів соціальної реабілітації. У роботі представлені основні підходи до розуміння влаштування суспільства, на підставі яких автор виявляє механізми суб'єктно-об'єктної реабілітаційної діяльності. Механізми...»

«Економічні науки Література 1. Ареф`єва О.В., Герасимчук Н.А. Управління формуванням підприємництва. – К.:Корпорація, 2006. -227 с.2. Ареф`єва О.В., Шнипко О.С. Суперечності розвитку як основне джерело загрози безпеці рівноваги економічних систем // Актуальні проблеми економіки. – 2006. – №3 – С. 57-62.3. Заруба В.Я. Концепция ценностей в управлении социально-экономическими системами // Проблеми та перспективи формування національної гуманітарно-технічної еліти: Збірник наукових праць: Вип....»

«НАЦІОНАЛЬНИЙ ІНСТИТУТ СТРАТЕГІЧНИХ ДОСЛІДЖЕНЬ МЕХАНІЗМИ ФОРМУВАННЯ РЕГІОНАЛЬНИХ ПРІОРИТЕТІВ РОЗВИТКУ аналітична доповідь КИЇВ – 2013 Механізми формування регіональних пріоритетів розвитку. – К.: НІСД, 2013. – 88 с.Автори: Біла С.О., д. держ. упр., проф., засл. економіст України (керівник авторського колективу) (вступ, 1.1; 2.4; 3.2;3.4;4; рекомендації) Шевченко О.В., к. е. н, с.н.с. (1.1; 1.2; 4; рекомендації, додатки) Жук В.І. (1.2; рекомендації, додатки) Романова В.В., к.політ.н....»

«Chychyrko Sergey, Associate Professor of Constitutional and Administrative Law of the National Transport University, e-mail: nataw@i.ua, tel. +30442805327, Ukraine, 01010, Kyiv, Suvorova str., 1, of. 415. Denysyuk Elena, Researcher, Assistant Professor of Constitutional and Administrative Law of the National Transport University, e-mail: yurd2010@mail.ru, tel. +30442805327, Ukraine, 01010, Kyiv, Suvorova str., 1, of. 415.РЕЦЕНЗЕНТИ: Воркут Тетяна Анатоліївна, доктор технічних наук, професор,...»

«ПАТ «ЗАВОД «ЛЬВІВСІЛЬМАШ» КОСАРКА НАВІСНА КН-2, ПОСІБНИК ПО ЕКСПЛУАТАЦІЇ КН-2,1 1. ВСТУП 1.1 Цей посібник по експлуатації містить основні відомості з будови, монтажу та експлуатації косарки КН-2, 1 1.2 Косарка КН-2, 1 призначена для скошування високоврожайних і польових трав на підвищених поступальних швидкостях і укладання скошеної маси в покіс. Машина застосовується у всіх зонах країни 1.3 Косарка агрегатується з тракторами класу 0,9-1,4 т. 2. ТЕХНІЧНІ ДАНІ 2.1 Технічні дані косарки...»

«НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ЛЬВІВСЬКА ПОЛІТЕХНІКА ТУРИЦЯ Віктор Володимирович УДК 547.583.5’261:547.814:547.391’26 ЗАСТОСУВАННЯ РЕАКЦІЙ орто-АЛКОКСИКАРБОНІЛАРЕНДІАЗОНІЙ ГАЛОГЕНІДІВ З НЕНАСИЧЕНИМИ СПОЛУКАМИ У СИНТЕЗІ ІЗОКУМАРИНІВ 02.00.03 – органічна хімія Автореферат дисертації на здобуття наукового ступеня кандидата хімічних наук Львів-2010 Дисертацією є рукопис. Робота виконана на кафедрі органічної хімії Львівського національного університету імені Івана Франка Міністерства освіти і науки...»




Продажа зелёных и сухих саженцев столовых сортов Винограда (по Украине)
Тел.: (050)697-98-00, (067)176-69-25, (063)846-28-10
Розовые сорта
Белые сорта
Чёрные сорта
Вегетирующие зелёные саженцы


 
2013 www.uk.x-pdf.ru - «Безкоштовна електронна бібліотека»