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

Значний внесок у вирішення вказаних проблем внесли наступні вчені: О.Л. Бандман, Р. Беллман, В.В. Воєводін, В.М. Глушков, В.Ф. Євдокімов, Е.В. Євреінов, А.В. Каляєв, Д.О. Поспелов, І.В. Прангішвілі, Г.Е. Пухов, К.Г. Самофалов, К. Дж. Тербер, Ч. Хоар, Р. Хокні, К. Шеннон, J. Bhasker, W. Hackbusch, W. Miranker, U. Trottenberg та інші.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася відповідно до плану науково-дослідних робіт Сєвєродонецького технологічного інституту Східноукраїнського національного університету імені Володимира Даля в рамках держбюджетної теми "Автоматизація проектування та програмування комп'ютерних систем керування" (державний реєстраційний №0103U000415, обліковий №0206U000414).

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

Для досягнення поставленої мети вирішуються такі наукові завдання:

1. Обґрунтування і розробка методу алгоструктурного проектування обчислювальних моделей.

2. Розробка методу перетворень алгоструктурних моделей.

3. Розробка методу розпаралелення обчислень в алгоструктурах.

4. Розробка методу структурної реорганізації в проблемно-орієнтованих алгоструктурних конструкціях.

5. Розробка технології автоматизованого проектування алгоструктурних моделей.

6. Розробка інструментального програмного засобу та реалізація алгоструктурних моделей.

Об'єкт дослідження - процес структурно-алгоритмічного проектування моделей обчислювальних процесів для комп'ютерних систем.

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

Методи дослідження. Для розробки алгоструктурних моделей паралельних обчислювальних процесів використовувались: чисельні методи і обчислювальна математика, теорія різницевих схем, теорія мультипроцесорних обчислювальних систем, теорія цифрових автоматів, теорія обчислювальних середовищ, теорія обчислювальних структур, теорія адаптивних систем, теорія штучних нейромереж. Основні теоретичні положення перевірені шляхом комп'ютерного моделювання.

Наукова новизна одержаних результатів полягає в тому, що:

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

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

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

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

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

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

Розроблені в дисертації методи, моделі, технологія та програмно-технічні засоби впроваджено на підприємствах НВП "УНІКОНТ" (акт впровадження від 24.11.2006 р.), ПНВП "ВІКАН" (акт впровадження від 20.12.2006 р.), ТОВ НВП "Мікротерм" (акт впровадження від 22.10.2007 р.). Їх використання свідчить, що автоматизація структурно-алгоритмічного проектування моделей обчислювальних процесів для комп'ютерних систем дозволяє скоротити строки виконання робіт.

алгоструктурний паралельний обчислювальний процес

Результати виконаних в дисертації досліджень використовуються в навчальному процесі Технологічного інституту Східноукраїнського національного університету імені В. Даля (м. Сєвєродонецьк) (акт впровадження від 30.11.2006 р.), а саме у курсовому і дипломному проектуванні та в дисциплінах: "Цифрові ЕОМ", "Паралельні обчислювальні системи та середовища", "Комп'ютерні системи керування", "Обчислювальні і мікропроцесорні засоби в електронній апаратурі", "САПР", "Мікропроцесори та програмні засоби автоматизації".

Особистий внесок здобувача. Усі положення дисертації, які виносяться на захист, отримані автором самостійно і їх основний зміст викладено у роботах [1-20]. У роботах, написаних особисто та у співавторстві, здобувачу належать наступні результати: у роботах [2,14] - запропоновано метод алгоструктурного проектування обчислювальних моделей; у роботах [7,11,16] - обґрунтовано і розроблено бібліотечні алгоструктурні компоненти; у роботах [8,12] - запропоновано метод перетворень алгоструктурних моделей; у роботах [3,15, 19] - запропоновано та досліджено метод розпаралелення обчислень в алгоструктурах; у роботах [17,18, 20] - розроблено метод структурної реорганізації в проблемно-орієнтованих алгоструктурних конструкціях; у роботі [1,4,5,6] - отримала подальший розвиток технологія автоматизованого проектування алгоструктурних моделей; у роботах [9,10,13] - представлена розробка інструментального програмного засобу та реалізація за його допомогою алгоструктурних моделей.

Апробація результатів дисертації. Основні положення та окремі результати дисертаційної роботи доповідалися та обговорювалися на міжнародних науково-технічних, науково-практичних і науково-методичних конференціях, форумах та семінарах, а саме: 8-й міжнародній науково-технічній конференції "ИИСТ-2002" (м. Харків); науково-технічних конференціях "Університет і регіон” (м. Луганськ, 2002, 2004 р. р.); науково-практичній конференції фірми ALDEC INC США "Современные технологии проектирования систем на микросхемах программируемой логики” (м. Харків, 2003 р.); міжнародних молодіжних форумах "Радиоэлектроника и молодежь в 21 веке" (м. Харків, 2003-2007 р. р.); науково-практичних конференціях "Технологія” 2003-2007 (м. Сєвєродонецьк); міжнародній науково-методичній конференції "Математические методы и информационные технологии в управлении, образовании, науке и производстве" (м. Маріуполь 2005р.); міжнародних науково-практичних конференціях ISDMIT 2005-2007 (м. Херсон); міжнародних молодіжних форумах "Информационные технологии в 21 веке" (м. Дніпропетровськ, 2005-2007 р. р.); міжнародних науково-практичних конференціях "Інформаційні технології в наукових дослідженнях і навчальному процесі" (м. Луганськ, 2005-2007 р. р.); наукових семінарах науково-дослідницьких лабораторій "Резонанс” та "Альтернатива” (м. Сєвєродонецьк 2001-2002 р. р.).

Публікації. Основні результати дисертаційної роботи опубліковано в 34 друкованих працях, серед яких 10 наукових праць у виданнях, що включені до Переліку ВАК України з технічних наук, 24 - у матеріалах міжнародних та всеукраїнських наукових конференцій.

Структура і обсяг дисертації. Дисертація складається із вступу, чотирьох розділів, висновків, п'яти додатків та списку використаних джерел. Загальний обсяг роботи складає 204 сторінки, обсяг тексту основної частини - 140 сторінок. Робота містить 112 рисунків, 74 таблиць та посилання на 170 літературних джерела.

Зміст роботи

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

У першому розділі зроблені аналіз стану проблеми організації обчислень в комп'ютерних системах і постановка завдань дослідження.

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

В дисертації для цього запропоновано використовувати алгоструктури. Алгоструктури - це програмні моделі структур (1), що реалізують обчислювальні процеси. На їх підставі зручно складати моделі обчислювальних процесів. Їх можна представити у наступній формі:

AS={T; X; Y; Z; N; S (K,AS_i); P}, (1)

де АS - алгоструктура моделі обчислювального процесу; T - тип алгоструктури; X - вхідні змінні; Y - вихідні змінні; Z - зовнішні налагодження; N - внутрішні налагодження; S - структура алгопроекту; K - комутація; AS_{i -} інші алгоструктури, що використовуються в моделі, i=1,2,…; P - програма функціонування.

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

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

Під методом алгоструктурного проектування обчислювальних моделей розуміється процес складання моделей і компонент обчислювального процесу з алгоструктур, тобто AS={a_j,A_i}, де АS - алгоструктура, що проектується, та є алгопроектом; a_j - алгоелементи (найпростіші алгоструктури) з базової бібліотеки; А_i - алгоблоки (алгоструктури, які отримані з алгоелементів), які можуть бути залучені до складу бібліотек користувача; i, j - індекси. Запропоновано реалізовувати обчислювальні моделі, як деякі структури S^*, що отримані з інших структур S за рахунок певної комутації (K). Це здійснюється такими способами: S{ (a_ij) }>…>S^* (AS,K); (2)

S{ (A_i) }>…>S^* (AS (K),K); (3)

S{ (a_ij), (A_i) }>…>S^* (AS,AS (K),K). (4)

Згідно зі способом (2) алгопроект складається тільки з алгоелементів. Спосіб (3) передбачає використання алгоблоків. Спосіб (4) - є комбінацією способів (2) та (3). Проектування алгоструктур складається з породження одних алгоструктур на підставі інших, з базової бібліотеки або спроектованих користувачем. В базовій бібліотеці алгоструктур передбачені алгоелементы для структурування алгоритму або його частини (BLOCK), обчислювального типу (EXPRESSION) та розгалуження (IF), які забезпечують алгоритмічну універсальність. Певні набори алгоелементів становлять спеціалізовані бібліотеки алгоструктур, тобто {BLOCK, EXPRESSION, IF} > AS. З метою розширення можливостей алгоструктур та для спрощення складання з них алгопроектів доцільно залучити до бібліотеки: FOR - компонент для подання циклічних обчислень; PROGRAM - компонент для формування структурно-алгоритмічної форми подання обчислень на підставі можливостей мови програмування, яка використовується. Але обмежитися тільки найпростішими компонентами досить складно. З цією метою на підставі базових алгоструктур методами (2), (3), (4) розроблені спеціалізовані бібліотечні алгоелементи. Їх використання скорочує термін проектування моделей обчислювальних процесів не менш, ніж у 2-5 разів. Це свідчить про ефективність методу алгоструктурного проектування і можливість за його допомогою автоматизувати процес розробки алгоритмів та представити їх проблемно-орієнтованими моделями обчислювальних структур.

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

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

1. Проведення аналізу дій, які потрібно виконувати в проекті.

2. Виявлення в проекті залежних і незалежних змінних, їх сортування, групування і, якщо потрібно - введення нових змінних.

3. Структурування паралельних та послідовних процесів з урахуванням послідовності їх виконання.

Перетворення для компонент EXSPRESSION забезпечують виявлення в алгопроекті залежних і незалежних послідовних та паралельних обчислювальних процесів з метою їх структурування та розподілу. Перетворення для BLOCK, IF та FOR містять перегрупування та зменшення тієї сукупності з названих компонентів, які можуть бути використані в алгопроекті для наочності, а їх реалізація в моделі пов'язана з зайвими діями. Оскільки в компоненті PROGRAM використовуються типові елементи мов програмування, такі як операторні душки, обчислювальні вирази, розгалуження, цикли та інше, то перетворення полягає в наступному: PROGRAM{X,Y,Z,v₁,v₂,…,v_w} > AS{BLOCK (X,Y,Z), EXSPRESSION (X,Y,Z), IF (X,Y,Z) }, де X,Y,Z - входи, виходи, параметри налагоджування; v₁,v₂,…,v_{w -} допоміжні змінні. Розроблені перетворення використовують мінімальну сукупність алгоелементів та спрощують алгоструктуру задачі (табл.1).

Таблиця 1

Алгоструктурні перетворення

Розроблено метод розпаралелення обчислень в алгоструктурах, який передбачає:

1. Виявлення в алгопроекті паралельних та послідовних обчислювальних процесів.

2. Реалізацію способів розпаралелення обчислювальних процесів.

3. Генерацію алгоструктур із заданим паралелізмом обчислень.

Дійсно, якщо подивитись на структури, що реконфігуруються, як на автомати із програмованою логікою, котрі призначені для використання в якості обчислювальних пристроїв, їх можна представити такою сукупністю: <X,VS{K,DL,P},Y>, де: DL - сукупність дискретних логічних елементів; P - сукупність елементів, що програмує функціонування VS{K,DL,P}; K - комутація DL, яка визначає конфігурацію обчислювальної структури VS{K,DL,P}; X, Y - входи і виходи. Алгоструктура, що є віртуальною моделлю VS{K,DL,P}, вважається відомою, якщо задані <X,S{K,AS (F) },Y>. "Занурення" алгоструктур у структури, що реконфігуруються, пов'язане з процесом, в якому віртуальні компоненти S{K,AS (F) } будуть замінені відповідними компонентами в реальній структурі VS{K,DL,P}. Обчислювальні алгоритми задаються безлічами: <X,F,Y>, F - виконувана функція (ії) над X з метою одержання Y. F може містити операції, які виконуються послідовно, паралельно або паралельно - послідовно. Процес реалізації F в VS{K,DL,P} є обчислювальним процесом, для якого просторово - часову інтерпретацію всієї безлічі операцій f_ijF можна представити у вигляді матриці обчислювальних процесів. Залежно від особливостей задачі, що вирішується, деякі процеси f_ij, ir, jm можуть бути відсутніми. Тому, організація у структурах, що реконфігуруються, паралельних обчислювальних процесів пов'язана з тим, що потрібно на кожному j-ому, j (1,2,…,m) обчислювальному етапі, відповідно до f_ijF, підібрати такий набір процесів з f_ij, ir, jm, при якому обчислювальні можливості структур, що реконфігуруються, будуть використані найкраще. Реалізація f_ij, ir, jm для задачі, що вирішується, з урахуванням обраного структурного базису визначить набір обчислювальних структур, які цілком використовують певні ресурси структур, що реконфігуруються, та обумовлюють певний час обчислень. Таким чином проектування алгоструктур повинно відбуватися на основі оптимізаційних способів, наприклад, наступних.

Спосіб 1 - розподіл структурних ресурсів. Нехай g_i - кількість структурних ресурсів, необхідних для реалізації i-го процесу; n_i - кількість процесів i-го типу; k - припустима кількість всіх процесів на кожному обчислювальному етапі; G - граничний структурний ресурс (кількість компонентів, яку можна використовувати); N - гранична кількість процесів i-го типу. На підставі наявних можливостей доцільно організувати розподіл структурних ресурсів наступним чином:

(5)

Спосіб 2 - розподіл ресурсів часу обчислень. Нехай _i - тривалість виконання i-го процесу; n_i - кількість процесів i-го типу; k - припустима кількість всіх процесів на кожному обчислювальному етапі; T - граничний ресурс часу виконання всіх процесів на обчислювальному етапі; N - гранична кількість процесів i-го типу. На підставі наявних можливостей доцільно організувати розподіл ресурсів часу обчислень наступним чином:

(6)

Приклад розподілу ресурсів наведено у табл.2.

Таблиця 2

Розподіл ресурсів в алгоструктурах

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

Отже, у разі застосування методу розпаралелення обчислень в алгоструктурах для організації паралельних обчислювальних процесів буде здійснюватись конфігурування з урахуванням особливостей S{K,AS (F) } та VS{K,DL,P}. В такому разі кожний обчислювальний етап передбачає наступне: аналіз обчислювальних алгоритмів та побудову f_ijF; рішення (5) або (6) й оптимізацію кількості реалізуємих на обчислювальному етапі f_ij, ir, jm; генерацію алгоструктур із заданим паралелізмом обчислень. Отримані таким чином алгоструктури мають потрібній обчислювальний паралелізм і забезпечують найкраще використання наданих ресурсів, що підтверджено експериментально.

У третьому розділі розроблено метод структурної реорганізації проблемно-орієнтованих алгоструктурних конструкцій.

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

Розроблено метод структурної реорганізації проблемно-орієнтованих алгоструктурних конструкцій, який передбачає:

1. Розподіл обчислень та визначення потрібного кількісного і якісного набору алгоелементів, які забезпечують виконання алгоритму.

2. Компоновку алгоелементів в алгопроекті.

3. Налагодження формул в алгоелементах в відповідності до алгоритму.

4. Формування необхідних зв'язків між алгоелементами.

Метод дозволяє з алгоелементів складати алгоструктурні конструкції - як структурні форми подання процедури деякого обчислення ASK=<K, AS (F) >.

В багатьох моделях передбачається виконання операцій інтегрування. Відомо, що найпростіші формули для паралельного інтегрування дають велику похибку, а більш точні - мають досить складний обчислювальний процес на початковій ділянці і це не завжди є прийнятним. Було запропоновано такий спосіб організації обчислень, який дозволяє обійтися без ускладнення на початковій ділянці та мати прийнятну точність. У способі обчислення ведуться по формулі прямокутників. Інтегрування повторюється двічі, з одинарним кроком, а потім подвоєним. Як наслідок, без втрати швидкодії загальна похибка обчислень для лінійних задач зменшується приблизно в 10 разів, а для нелінійних задач - в 2-3 рази. Спосіб інтегрування має високу швидкість, потребує всього кілька операцій арифметичного типу та поліпшує точність обчислень. Реорганізація цієї алгоструктурної конструкції здійснюється за рахунок визначення кількості потрібних інтеграторів та їх пере комутації і забезпечує потрібний обчислювальний паралелізм.

Зазначено, що нейромережеві та точкові обчислювачі дозволяють виконувати перетворення Q=F (U) та U=F^-1 (Q), що називають зворотними і тому, їх використання є доцільним для вирішення задач ідентифікації і крайових задач, де: U, Q - входи і виходи. У зв'язку із цим розглянута задача проектування обчислювальних нейромережних структур (NS) та точкових структур (TS) на підставі алгоструктурної технології. Комп'ютерна модель NS вважається відомою, якщо задані <U,S{K, N (F) },Q>, де: N (F) - сукупність нейронів, кожний з яких реалізує задану функцію перетворення F; K - матриця комутації нейронів, що визначає структуру S нейромережі. Модель TS вважається відомою, якщо задані <U, S{K, TО (F) }, Q>, де: TО (F) - сукупність точкових обчислювачів, котрі реалізують задану функцію F; K - матриця комутації, що визначає структуру S моделі для точкових обчислень. Алгоструктура вважається відомою, якщо задані <X, S{K, AS (F) }, Y>, де: AS (F) - сукупність алгоелементів і алгоблоків, кожний з яких реалізує задану функцію F; K - матриця комутації алгоелементів і алгоблоків, що визначає конфігурацію S алгоструктури; X, Y - входи і виходи.

Подібність подання N (F) і AS (F) та TO (F) і AS (F) забезпечує схожість моделей NS, TS та алгоструктур і робить можливим використання алгоструктур для проектування моделей нейромережних та точкових обчислювачів в формі NS=<K,N (F) >, TS=<K,TО (F) >, як певних алгоструктурних конструкцій. Цей підхід дозволив отримати різноманітні моделі NS, TS. Формули для TО (F) вперше запропонували академік Г. Є. Пухов та професор Ю.В. Чернухін. В дисертації вони отримали подальший розвиток. З метою поліпшення швидкодії TS в алгоструктурних моделях запропоновано і досліджено використання багатокрокової апроксимації. Реорганізація зазначених алгоструктурних конструкцій здійснюється за рахунок визначення потрібної кількості N (F) і TО (F) та їх перекомутації і забезпечує потрібний обчислювальний паралелізм. Комп'ютерне моделювання підтвердило ефективність такої структурної реорганізації.

Алгоструктурам притаманні такі властивості як програмованість та змінність структури. Це дає можливість на їх підставі автоматизовано проектувати велике різноманіття моделей обчислювальних структур для комп'ютерних систем керування (КСК) з автоналагодженням параметрів, зі змінною структурою, адаптивних. Фрагменти проектування алгоструктурних конструкцій КСК наведені в табл. 3. Реорганізація цих конструкцій здійснюється за рахунок визначення потрібної кількості проблемно-орієнтованих алгоструктур та їх пере комутацій і забезпечує потрібний обчислювальний паралелізм.

Таблиця 3

Проблемно-орієнтовані алгоструктурні конструкції для КСК

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

У четвертому розділі запропонована технологія автоматизованого проектування алгоструктурних моделей, яка втілена в інструментальному програмному засобі - AlgoCAD.

Для задачі, що вирішується, технологія дозволяє з бібліотечних алгоелементів (AS) та алгоструктурних конструкцій (ASK) складати алгоструктурні моделі (ASM), як структурні форми подання обчислень, яких достатньо для рішення задачі ASM = <K, ASK, AS (F) >. Технологія містить:

1. Аналіз задачі та визначення кількісного і якісного набору алгоелементів, що забезпечує її вирішення.

2. Вибір з бібліотеки потрібних компонентів та проблемно-орієнтованих алгоструктурних конструкцій або їх розробка.

3. Компоновка алгоелементів та встановлення між ними за допомогою комутації необхідних зв'язків.

4. Реалізація в алгоелементах формул у відповідності до алгоритму рішення задачі.

5. Налагодження алгоструктурної моделі.

6. Визначення в алгоструктурній моделі паралельних та послідовних обчислювальних процесів та перевірка ступеня їх розпаралелення.

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

8. Реорганізація та структурування алгоструктурної моделі на підставі перерозподілу обчислень.

9. Генерація алгоструктурної моделі із заданим паралелізмом обчислень з урахуванням наявних ресурсів.

10. Моделювання і документування алгоструктурної моделі.

Методи, що представлені у попередніх розділах, і послідовність проектування алгоструктурних моделей втілені в інструментальному програмному засобі, який названо - AlgoCAD. На підставі запропонованої послідовності за допомогою AlgoCAD були розроблені й досліджені алгоструктурні моделі, що використовують: звичайні диференційні рівняння, звичайні диференційні рівняння з крайовими умовами, диференційні рівняння з частковими похідними, оптимізацію, інтерполяцію. Розроблені алгоструктури забезпечують високу продуктивність, максимально розпаралелюють обчислювальний процес і ефективно використовують наявні ресурси. Але, якщо наявних ресурсів не достатньо, то конфігурація алгоструктурних моделей зміниться автоматично.

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

Основні результати і висновки