Спосіб автоматичного формування зв’язків між компонентами обчислювального середовища

МП К . G 06 ^7/52 СПОСІБ АВТОМАТИЧНОГО ФОРМУВАННЯ ЗВ'ЯЗКІВ МІЖ КОМПОНЕНТАМИ ОБЧИСЛЮВАЛЬНОГО СЕРЕДОВИЩА Винахід відноситься до області цифрових обчислювальних машин для обробки інформації спеціального призначення з погляду конструкції обчислювального пристрою, може бути використаний при побудові спеціалізованих обчислювальних пристроїв для вирішення задач на мережах, організації принципів з'єднання компонент по різних класифікаційних ознаках (магістральний, радіальний, ланцюжковий, змішаний і т.д.) і для побудови лінійних погоджених цифрових відео-радіо частотних фільтрів для систем радіолокації, радіонавігації, телебачення, радіо-телекомунікації і провідного зв'язку з час-кодовим доступом. Відомий спосіб автоматичного формування зв'язків між компонентами обчислювального середовища, що використаний в ряді пристроїв (наприклад: а.с. № 717787, G 06 g 7 / 122, 29.10.79 р., БИПОиТЗ № 7, 25.02.80 р.; а.с. № 736121, G 06 g 7/ 122, 29.01.80 p., БИПОиТЗ № 19, 26.05.80 p.; a.c. № 636635, G 06 g 7/48, 16.08.78 p., БИПОиТЗ № 45, 15.12.78 p.; a. c. № 608169, G 06 g 7 / 122, 8.04.75 p., БИПОиТЗ № 19, 05.05.78 p.) і заснований на моделюванні фізичних змінних імпульсно-часовим методом (В.В.Васильев, А.Г.Додонов. "Гибридные модели задач оптимизации", из-во «Наукова Думка», 1974 р.). Суть такого способу моделювання полягає в представленні фізичних змінних числом імпульсів тактового генератора, що заносяться в елементи пам'яті, з наступним перетворенням цього числа імпульсів у часовий інтервал. Елементи пам'яті територіально розміщуються в кожній компоненті обчислювального середовища. У якості компонента виступає елементарний процесор, роль якого - відобразити модель віткі або вершини мережі, що моделюється. Часовий інтервал пропорційний розміру фізичної змінної визначається таким виразом: N - U. t. = ------------------- £ (і) fr - частота тактового генератора імпульсів; Ut- число імпульсів тактового генератора, виділене на представлення і-ої фізичної змінної. Обчислювальні пристрої, що використовують даний спосіб моделювання фізичних змінних, відносяться до класу цифрових аналогів, тобто обчислювальним пристроям з цифровою формою представлення інформації та аналоговим принципом виконання процесу обчислень. Процес обчислень включає подачу сигналу "Пуск" в обчислювальне середовище і фіксацію моменту його появи на виході середовища. У наданому середовищі сигнал, розповсюджуючись від однієї компоненти до іншої в залежності від конфігурації їх з'єднання, яка встановлюється зазделегіть, призводить до того, що кожна компонента, у яку він поступив, відтворює локальні властивості цільової функції. Конфігурація з'єднання компонент середовища визначена послідовністю відтворення локальних властивостей цільової функції на основі вхідних Ui змінних, що визначають її локальні значення. Така конфігурація з'єднань відображає мережу або взешанньш граф. Відомий спосіб автоматичного формування зв'язків між компонентами обчислювального середовища, число N яких задається обсягом розв'язуваної задачі і цільовою функцією, що полягає у виділенні необхідного моменту, обумовленого формуванням ознаки належності компоненти до заданої послідовності виконання операцій обчислення цільової функції, включення необхідної компоненти середовища в обчислювальний процес і ознаки безперервності виконання послідовності цих операцій шляхом обробки сигналу "Пуск", що подається в загальну лінію зв'язку і одночасно надходить в кожну компоненту середовища. Таким чином, як випливає з розглянутого способу моделювання фізичних змінних і способу автоматичного формування зв'язків між компонентами обчислювального середовища, загальний час - Т рішення будь-якої задачі на обчислювальних пристроях даного класу визначається таким виразом: Т= t P + Іаф (2) де tp- час відтворення ( обчислення ) локальних значень цільової функції, що визначає результат рішення задачі; Іаф - час, який втрачається на автоматичне формування зв'язків між компонентами обчислювального середовища ( елементарними процесорами ). Час tp - відтворення локальних значень цільової функції залежить тільки від значень величин Ui - фізичних змінних та їх числа, що визначається кількістю операцій у послідовності обчислень цієї функції. Час ta4>- автоматичного формування зв'язків між компонентами обчислювального середовища залежить від : 1) від числа компонент, що в загальному випадку визначається обсягом задачі, що вирішується; 2) від конфігурації з'єднань компонент у середовищі між собою в процесі обчислень у необхідну послідовність операцій з метою обчислювання результату рішення, обумовленого цільовою функцією; 3) від часу відновлення заданих значень ознаки належності до заданої послідовності операцій обчислень, що виконуються, і ознаки безперервності виконання цих операцій; 4) від числа ітерацій, що необхідно виконати в процесі вирішення задачі для визначення экстремума заданої цільової функції. Як витікає з вище викладеного, час автоматичного формування зв'язків між компонентами визначається як: 1 _ N(N-l)KiK 2 (3) fr де N - число компонент обчислювального середовища, обумовлене обсягом задачі, що вирішується, Кі - коефіцієнт, обумовлений числом можливих переривань для відтворення зв'язків між компонентами і залежний від конфігурації з'єднань компонент між собою, Кг - коефіцієнт, обумовлений можливим числом ітерацій при відтворенні локальних значень цільової функції для одержання результату вирішення задачі. 1 Пояснимо фізичний зміст виразу ( 3 ) Фізично час ----- N визначає відтворення тільки зв'язку fr однієї компоненти з усіма суміжними з нею, тобто одночасне відтворення значень однієї ознаки належності та ознаки безперервності Другий співмножник (N — 1) - визначає мінімальне необхідне число таких зв'язків, що існують між компонентами Наприклад, якщо задача, що вирішується, описується з'єднанням компонент між собою послідовністю у видгдяді ланцюжкового графа (найпростіший випадок ) з N = 100, то при £ = 10МГц і Кі = 1, Кг = 1 (для більшості задач Кл » 1, Кз= 2 -f 3 ) Іаф - — N = ~ І 0 с = 1 мс fr Для більшості задач Іаф складає хвилини і більше в залежності від виду цільової функції, від складності обмежень, що накладаються на неї Як очевидно з перерахованих факторів, час автоматичного формування зв'язків між компонентами обчислювального середовища значно перевершує час одержання безпосередньо результату вирішення задачі Крім того, час відтворення локальних властивостей цільової функції і час автоматичного формування зв'язків не можуть бути поєднані, що призводить до необхідності застосовувати дві серії тактових імпульсів, зсунутих відносно один до одного При цьому, при формуванні зв'язків обчислювальний процес зупиняється, тобто припиняється подача імпульсів генератора, які використовуються безпосередньо для відтворення локальних властивостей Ці фактори, взагалі кажучи, обмежують сферу використання даного класу обчислювальних пристроїв Метою даного винаходу є скорочення загального часу отримання результата вирішення задачі за рахунок значного зменшення часових витрат на автоматичне формування зв'язків між компонентами обчислювального середовища Ця мета досягається введенням операції автосинхронного виявлення і "скалярного перетинання", перша з яких полягає у виявленні сигналу "Пуск" шляхом затримки кожного імпульсу сигналу, що надходить, на час кратний періоду проходження імпульсів тактового генератора і порівняння його з наступним імпульсом цього сигналу, а друга - являє собою "Ш + 2" затримок, які послідовно виконуються, кожного з імпульсів сигналу, що надходять, на час кратний періоду следования імпульсів тактового генератора і такої ж кількості одночасно виконуваних з кожним тактом операцій порівнянь тривалості послідовності імпульсів сигналу "Пуск" з еталонною, причому сигнал "Пуск" відтворюється послідовністю, що включає дві пари імпульсів, перша і друга з яких відповідно визначає початок і кінець тривалості дії сигналу "Пуск", при цьому імпульси в парах зсунуті один щодо іншого на кратне число періодів надходження імпульсів тактового генератора, і імпульсів розташованих між цими парами і визначаючих "Ш" - у ознаку належності до заданого порядку виконання обчислювальних операцій, обумовлених цільовою функцією, що визначаються з т наступного виразу N = J] С$, де С^- число сполучень із "ЇЇ1" по "П", причому з кожним /7=1 імпульсом тактового генератора над послідовністю, що відтворює сигнал "Пуск" одночасно в кожній компоненті виконують дві групи операцій, перша з який містить послідовно виконувані операції автосинхронного виявлення і "скалярного перетинання", а друга з цих груп містить операцію "скалярного перетинання", при цьому у разі одночасного виконання зазначених груп операцій формується сигнал, що визначає момент початку відтворення локальних властивостей цільової функції, по закінченні виконання якої провадиться формування вихідного сигналу, що визначає ознаку безперервності виконання послідовності обчислювальних операцій і визначає результат одночасного виконання операцій другої групи та третьої, яка складається з послідовно виконанних операцій"скалярного перетинання " і затримку імпульсів, отриманнях у результаті виконання операції "скалярного перетинання", на час як і при виконанні операції автосинхронного виявлення, і відтворює вихідну послідовність імпульсів. Новими суттєвими ознаками пропонованного способу автоматичного формування зв'язків між компонентами обчислювального середовища становлять операції відображення сигналу "Пуск" послідовністю імпульсів, тривалість яких задана і постійна для задач однакового об'єму, операції автосинхронного виявлення сигналу, операції "скалярного перетинання" та операції затримки імпульсів послідовності на час кратний періоду проходження імпульсів тактового генератора, які виконуються в зазначенній раніш послідовності. Запровадження нових суттєвих ознак дозволяє в значній степені скоротити час автоматичного формування зв'язків між компонентами обчислювального середовища, що досягається за рахунок запроваджування залежністі наданного часу тільки від обсягу розв'язуваємої задачі. Крім цього, відтворювання локальних властивостей цільової функції не припиняється на час автоматичного формування зв'язків і використовувається в обчислювальних пристроях тільки одна серія імпульсів тактового генератора. Посвідчим це, В запропонованному способі час автоматичного формування зв'язків визначається таким співвідношенням ; — m (4), fi де значення ознаки "т" знаходять із співвідношення N= I C» (5) число сполучень з "т" по "п" . "т" - взагалі представляє собою коефіцієнт, що характеризує ступінь скорочення часу автоматичного формування зв'язків. З виразу ( 5 ) С у) т видно, що"ш"«К Для наведенного прикладу при N = 100, "т" = 7, так як 2 С^=С) + С ?2 +СІ + С* + С^ +С* +Щ = 7 + 2 1 + 3 5 +7+1 = 117 В наданому випадку ta-ф = — =7 10" с , або ta ф = 7 мкс. fi ta ф прото-па Виграш в порівнянні з прототипом складає TJ = -------------- = 0,143 103 = 143 ( раз.). ta-ф Суттєвисть запропонованного спосібу пояснювається рисунками ФІг. 1, Фіг. 2, Фіг. З . На Фіг. 1 наведена блок-схема алгоритмічної послідовності операцій, які виконуються кожною компонентою обчислювающего середовища, де 1 - операція автосинхронного виявлення , 2 - операція "скалярного перетину" , 3 - блок операцій, які реалізують локальні властивості цільової функції Операція автосинхронного виявлення 1 передбачає виконання таких дій, як затримку кожного імпульса вхідної послідовністі на час t кратний періоду следования імпульсів тактового генератора та порівняння його з наступним t' _ імпульсом цієї ж послідовністі На Фіг 1 ці дії відповідно визначени / —/ та П Такі дії можуть бути, на приклад, відповідно реалізовані на зсовувальному регістрі та елементі "И" (одиничне перетинання ) Відомо (А А Иванько,В И Гордиенко,В М Соловьев и др , "Цифровая обработка сигналов Опыт использования персональных ЭВМ", К/Техніка", 1991г), що операція "скалярного перетинання" передбочає виконання над кожним вхідним імпульсом послідовності таких дій, як затримку на час Ті та ( К + 2 ) порівнянь, виконуємих з кожним тактом генератора, з встановленням еталоном тривалості сигналу "Пуск", якій відображається періодом надходження Ґ імпульсів тактового генератора. Еталон тривалості Ті дії сигналу "Пуск", якій відображається періодом надходження імпульсів тактового к генератора, визначається співвідношенням Ті=^ ti, k — ПІ +2 , На Фіг 2г відображен еталон тривалістю Ті На Фіг 1 групи операцій і операції порівнянь, які необхідно виконувати одночасно з кожним імпульсом тактового генератора, позначені індексом "И", а операції , які виконуються послідовно позначені індексом "ИЛИ" Операції, які для виконання потребують значень еталонів, позначені індексами 1і,1і є N ^^^ т а ^ є Т і. На Фіг.2 сигнал "Пуск" відображен послідовністю імпульсів , де Фіг 2а — імпульси тактового генератора з періодом t , Фіг 26 — безпосередньо сигнал "Пуск" тривалості Ті, Фіг 2в — послідовність імпульсів, якою відображається сигнал "Пуск" Позначені цифрами 1,2 і 3,4 імпульси відповідно визначають початок і кінець дії сигнала "Пуск", а позначений цифрою 5 імпульс визначає ознаку, яка відповідає L порядковому номеру у послідовності виконання обчислювальних операцій цілівоі функції, де т Розглянемо результат дії операцій на послідовність імпульсів, що поступають на вхід (Фіг 1) Нехай цією послідовністю буде послідовність представлена на Фіг2в Нехай ця послідовність поступає з відповідним імпульсом генератора і черговість імпульсів наступна 1,2,5,3 і 4 Після виконання операції автосинхронного виявлення після необхідного числа тактових імпульсів одержимо послідовність імпульсів, що зображенана Фіг 2д, а після виконання операції "скалярного перетину " над цією послідовністю отримуємо результат, що наведений на Фіг 2е Слід зауважити , що еталонною послідовністю при виконанні цієї операції є послідовність, яка зображена на Фіг 2г Одночасно з цим над послідовністю ( 2в ) виконується операція " скалярного перетину" другої групи, в результаті якої отримаємо результат зображений на ФІг 2з Слід зауважити, що еталонною послідовністю при виконанні цієї операції є На Фіг.2 сигнал 'Тіуск" відображен послідовністю імпульсів , де Фіг.2а — імпульси тактового генератора з періодом t ; Фіг.26 — безпосередньо сигнал "Пуск" тривалості Ті; Фіг.2в — послідовність імпульсів, якою відображається сигнал "Пуск". Позначені цифрами 1,2 і 3,4 імпульси відповідно визначають початок і кінець дії сигнала "Пуск", а позначений цифрою 5 імпульс визначає ознаку, яка відповідає L порядковому номеру у послідовності виконання обчислювальних операцій цілівої функції, де т LeN= £ С"Л=і..... т. т Розглянемо результат дії операцій на послідовність імпульсів, що поступають на вхід (Фіг. 1). Нехай цією послідовністю буде послідовність представлена на Фіг.2в. Нехай ця послідовність поступає з відповідним імпульсом генератора і черговість імпульсів наступна : 1,2,5,3 і 4. Після виконання операції автосинхронного виявлення після необхідного числа тактових імпульсів одержимо послідовність імпульсів, що зображена на Фіг. 2д, а після виконання операції "скалярного перетину " над цією послідовністю отримуємо результат, що наведений на Фіг. 2е. Слід зауважити , що еталонною послідовністю при виконанні цієї операції є послідовність, яка зображена на Фіг.2г. Одночасно з цим над послідовністю ( 2в ) виконується операція " скалярного перетину" другої групи, в результаті якої отримаємо результат зображений на Фіг. 2з. Слід зауважити, що еталонною послідовністю при виконанні цієї операції є послідовність, яка зображена на Фіг, 2ж. Результат одночасного виконання операцій першої та другої груп зображен на Фіг.2и. Цей імпульс є сигналом початку відтворення локальних властивостей цільової функції, тобто початком виконання блока або групи операцій 3 ( Фіг. 1 ). На Фіг.З зображен процес формування ознаки безперервності виконання послідовності операцій. Тут еталонами для виконання операцій "скалярного перетину" другої і третьої груп є послідовністі , відповідно зображені на Фіг.Зе і Фіг.Зв. На Фіг.Зб зображений вихідний імпульс, що формується після відтворення локальних властивостей целевої функції ( блок 3, Фіг. 1 ) і на основі якого формується вихідна послідовність імпульсів , що визначає безперервність виконання послідовності операцій. Вона формується таким чином. Цей імпульс, після необхідного числа тактів генератора, в результаті яких повністю виконується операція "скалярного перетину" третьої групи, буде перетворений в послідовність імпульсів, зображену на Фіг.Зд. Ця послідовність поступить на вихід, що відображено на Фіг.Зз імпульсами 1 і 3. Після виконання операції затримки послідовності (Фіг.Зд) отримують послідовність, що зображена на Фіг. Зж. Вона також поступає на вихід, що зображено на Фіг. Зз імпульсами 2 і 4 . Одночасно з цим виконання операції "скалярного перетину" над імпульсом (Фіг.Зб) з участю еталону (Фіг.Зг ) одержимо імпульс, зображений на Фіг.Зе, який зсунутий відносно імпульса еталонної тривалості послідовності (Фіг.Зв). Він також поступає на вихід, що зображено на Фіг.Зз імпульсом 6. Отримана послідовність імпульсів ( Фіг.Зз ) має таку ж тривалість Ті, як і сигнал "Пуск" , але з іншою ознакою. Це свідчить про те , що кожна компонента обчислювального середовища незалежно від інших компонент обробляє послідовність імпульсів, яка відтворює сігнал "Пуск" , і формує такуж саму послідовність, але з іншою ознакою. СПОСІБ АВТОМАТИЧНОГО ФОРМУВАННЯ ЗВ'ЯЗКІВ МІЖ КОМПОНЕНТАМИ ОБЧИСЛЮВАЛЬНОГО СЕРЕДОВИЩА Вхід lieN tie Ті V 2 ФІГ.1 ▼ * * * • • •V V ▼ ЇЛИ или г V / . 2 / 2 Вихід Д у б р о в с к и й С . Є . Р г о м ш и н Р . І Ф е д о т о в М . В. СПОСІБ АВТОМАТИЧНОГО ФОРМУВАННЯ ЗВ'ЯЗКІВ МІЖ КОМПОНЕНТАМИ ОБЧИСЛЮВАЛЬНОГО СЕРЕДОВИЩА Ґ а) 11111111111111111111111 1 "Пуск" б) в) М 1 25 г) І И3 "Вхід" 4 Ъ~^\ Д) є) ж) з) и Ті Фіг, 2 Автори : Дубровский С.Є Рюмшин Р.І. Федотов М.В. СПОСІБ АВТОМАТИЧНОГО ФОРМУВАННЯ ЗВ'ЯЗКІВ МІЖ КОМПОНЕНТАМИ ОБЧИСЛЮВАЛЬНОГО СЕРЕДОВИЩА 1 H1 T,— 1 1 1 1 II а) H 1 1 > 1 II "ІІІІІИІІІНІИІНІ t * 6) в) г) ---------------- 1 -------------------► Д) UN e) ж) з) І І _______ І І І ___________ ^ 12 6 3 4 "Вихід Фіг.З Автори: Дубровский С Є Рюмшин Р І. Федотов М В.