Буланкін В.Б - UCH_POS
Міністерство освіти України Володимирський державний університет
ПАРАЛЕЛЬНІ ОЧИСЮВАЛЬНІ СИСТЕМИ
В.Б. Буланкін Паралельні обчислювальні системи: Навчальний посібник/Владим. держ. ун-т. Володимир, 2003, 32 с.
Містять систематизований матеріал щодо застосування паралельних обчислювальних систем на основі цифрових інтеграторів для вирішення завдань у широкій сфері застосування. Включають узагальнений теоретичний матеріал, методику переходу до породжувальних систем диференціальних рівнянь К. Шеннона, математичні залежності чисельного інтегрування за Стілтьєсом та екстраполяції, що використовуються в ЦИМ, розрахункову частину на вибір порядку формул чисельного інтегрування, екстраполяції, довжини розрядної сітки змінних, видачі рішень на основі вимог, що пред'являються. Наведено приклади обчислення деяких математичних залежностей методами ЦІМ та проектування паралельних обчислювальних систем, що задовольняють заданим технічним характеристикам.
Навчальний посібник призначений для студентів спеціальностей 220100, 071900 та може бути використаний студентами суміжних спеціальностей для знайомства з принципами організації, проектування та використання обчислювальних систем на основі цифрових інтеграторів.
Табл. 4. Іл. 2. Бібліогр.: 3 назв.
Підвищення продуктивності обчислювальних систем (ВС) на етапі розвитку обчислювальної техніки досягається трьома основними шляхами:
1) підвищенням швидкодії елементів ПС. Однак тут існують певні фізичні межі насамперед технологічного характеру. Останніми роками тактова частота елементів ЦВМ різко зросла і досягла мікропроцесорів 166 - 1000 МГц;
2) удосконаленням математичногозабезпечення та схемотехнічної організації обчислювальних модулів, головним чином мікропроцесорів. Перехід до алгоритмів виконання операцій на основі порозрядної арифметики, широке впровадження паралелізму та принципу конвеєрної обробки на всіх рівнях ЗС збільшив кількість операцій реалізованих в одній команді процесора та скоротив час виконання команд
у програмах до одного – двох тактів;
3) переходом від однопроцесорних структур до мультипроцесорних та багатомашинних обчислювальних комплексів, що працюють паралельно.
Вихідні завдання, що описуються дискретним математичним апаратом, ефективно і просто реалізуються за допомогою набору як універсальних, так і спеціалізованих обчислювальних модулів ВС.
Спеціалізовані обчислювальні модулі мають обмежені набори команд, орієнтовані виконання одного чи кількох алгоритмів. Число команд у таких модулях не перевищує десяти, а в деяких складає лише одну операцію.
Апаратурно-спеціалізовані обчислювальні модулі, на відміну від універсальних, значно простіші та забезпечують побудову ВС різної конфігурації: послідовні, паралельно-послідовні, паралельні.
Однорідність одержуваних структур ЗС, що визначається однотипністю використовуваних елементів (процесорів) і зв'язків між ними, спрощує їх реалізацію в інтегральному виконанні у вигляді однієї або кількох ІС. Синтез інтегральних схем виявляється більш простим, забезпе-
печується велика щільність розміщення елементів і вище частота тактування проти неоднорідними структурами.
Актуальність проведення досліджень у галузі паралельних обчислювальних систем на базі спеціалізованих обчислювальних модулів визначається поряд, з кращим задоволенням так-тико-технічним вимогам, інтенсивним розвитком та широким поширенням інструментальних засобів з проектування пристроїв на базі замовних інтегральних схем, у тому числі ПЛІС (програмованих інтегральних схем).
Досить високий ступінь інтеграції ПЛІС, що становить понад 25 млн транзисторів на кристалі і тактова частота перемикання – 100 і більше мегагерц, доступність, відкритість внутрішньої структури висунули їх серед розробників у розряд найпопулярніших.
У вказівках розглядаються принципи побудови паралельних ЗС з урахуванням спеціалізованих обчислювальних модулів – цифрових інтеграторів. Досліджуються точнісні та динамічні характеристики ВС.
1. ОСНОВНІ ПРИНЦИПИ ПОБУДУВАННЯ СУЧАСНИХ ЦИФРОВИХ ІНТЕГРУЮЧИХ МАШИН
У ЦИМ відтворюється система рівнянь Шеннона [1], яку можна призвести до наступної симетричної форми:
dy pk = ∑ A pkj dz j, j = 1
dy qk = ∑ A qkj dz j, j = 1
dz k = y pk dy qk, dz 1 = dx,
y pk ( x 0 ) = y pk 0 ,
k = 2,3. N. Тут A pkj і A qkj (k = 1,2. N, j = 1,2. N)
є постійними коефі-
цієнтами, що приймають значення 0 або 1 в залежності від розв'язуваної задачі. Прямокутні матриці, складені з коефіцієнтів A pkj та
A qkj разом з вектором початкових умов y pk 0 ( k = 1,2. N ) повністю
задають систему рівнянь Шеннона (1.1) та програму комутації інтеграторів у ЦИМ.
До системи рівнянь Шеннона зводиться дуже широке коло завдань [1],
пов'язаних з розробкою та функціонуванням цифрових моделей та систем управління, а також з іншими проблемами. Сюди відносяться лінійні та нелінійні прості диференціальні рівняння та їх системи з початковими та граничними умовами; диференціальнірівняння у приватних похідних, що приводяться до звичайних диференціальних рівнянь; трансцендентні рівняння; завдання на обчислення різноманітних інтегралів, похідних, екстремумів і функцій однієї і багатьох змінних; операції перетворення координат; варіаційні завдання; завдання теорії оптимальних процесів, теорії диференціальних ігор та багато інших.
p align="justify"> Система рівнянь Шеннона (1.1) характерна тим, що в правій частині її використовуються лише операції підсумовування і множення і відсутні будь-які більш складні операції (розподіл, зведення в ступінь, функціональне перетворення і т. п.). Ця обставина призводить до суттєвого спрощення структури ЦИМ, тому що відпадає необхідність вводити в структуру ЦИМ складні функціональні перетворювачі.
Разом з тим, за чисельного інтегрування рівнянь Шеннона (1.1) виникає проблема обчислення інтеграла Стілтьєса
z k (i + 1) = ∫ y pk (x) dy qk (x),
який утворюється в результаті інтегрування рівнянь (1.1) на відрізку від x = xi до x = xi + 1 .
Детальне дослідження процесу чисельного інтегрування за Стілтьєсом дозволило отримати відповідні формули чисельного інтегрування різного порядку точності. У загальному випадку інтерполяційна формула чисельного інтегрування за Стілтьєсом n-го порядку точності може бути записана таким чином:
z k (i + 1) = y pki y qk (i + 1) + 1 2 y pk (i + 1) y qk (i + 1) +
+ ∑ ∑ α αβ n [ y qk ( i + 1 − α ) y qk ( i + 1 − β ) − y qk ( i + 1 − β ) y qk ( i + 1 − α ) ],
де n = 3,4,5, ..., α αβ n - постійні коефіцієнти [2].
Задаючи в (1.3) різні значення n, можна отримати конкретні формули чисельного інтегрування за Стілтьєсом, які можуть бути покладені в основу синтезу цифровихінтеграторів. Відмінною особливістю таких інтеграторів є те, що вони виробляють чисельне інтегрування не тільки незалежною змінною x , але і по будь-якій
залежною змінною y qk(x).
На входи цифрових інтеграторів інформація подається у вигляді прирощень підінтегральної функції y та змінної інтегрування
y qk (i + 1). Зазначені збільшення можуть бути обчислені, якщо проінтегрувати на інтервалі ( x i , x i + 1 ) перші два рівняння системи Шеннона (1.1):
= ∑ A pkj z j (i + 1),
= ∑ A qkj z j (i + 1),
Формула чисельного інтегрування (1.3) є інтерполяційною, т. е. вимагає обчислення прирощень інтеграла z k ( i + 1) вико-
вання прирощень y pk ( i + 1) та y qk ( i + 1) , які не можуть бути визначені
безпосередньо, оскільки відповідно до виразів (1.4) для цього необхідно мати у розпорядженні значення шуканих прирощень z k (i + 1) .
Щоб усунути зазначену скруту, можна скористатися екстраполяційними формулами чисельного інтегрування Стілтьєса. Але екстраполяційні формули, як показує докладне дослідження, виявляються значно складнішими і менш точними. Тому для чисельного інтегрування рівнянь Шеннона краще використовувати інтерполяційну формулу (1.3), а збільшення y pk ( i + 1) і y qk ( i + 1) напів-
чати шляхом екстраполяції прирощень y pki та y qki на один крок вперед. Точніше, слід екстраполювати на один крок уперед збільшення z ki , що досить просто здійснюється за допомогою виразу
Після екстраполяції прирощень
z ki неважко відповідно до
формулами (1.4) обчислити збільшення y pk ( i + 1) і y qk ( i + 1) :
= ∑ A pkj z * j (i + 1),
= ∑ A qkj z * j(i + 1),
Вираз (1.5) отримано з такою розрахунком, щоб похибка інтегрування збереглася незмінною.
Викладене показує, що в загальному випадку цифрова інтегрую-
ця машина повинна складатися з цифрових інтеграторів, в яких реалізується формула чисельного інтегрування за Стілтьєсом (1.3), екстраполяторів прирощень, в яких прирощення екстраполюються на один крок уперед відповідно до виразів (1.5) та суматорів, що здійснюють на основі формул (1.6) утворення прирощень підінтегральної функції та змінної інтегрування.
Перераховані операції та відповідні ним вирішальні блоки можуть бути об'єднані в один узагальнений універсальний цифровий інтегратор рис. 1.1.
Мал. 1.1. Універсальний цифровий інтегратор
Крім перерахованих блоків цифрові інтегруючі машини іноді вводяться для надання їм більшої гнучкості і для розширення можливостей додаткові вирішальні блоки: розмножувальні пристрої, цифрові функціональні перетворювачі, стежать інтегратори, індикатори рівності потоків прирощень, блоки поділу, логічні блоки та ін. Однак введення в
структуру ЦИМ перелічених додаткових вирішальних блоків у принципі необов'язково.
Загалом будь-яка цифрова машина, що інтегрує, реалізує різницеву схему інтегрування симетричної системи рівнянь Шеннона, яка утворюється в результаті об'єднання виразів (1.3), (1.5) і (1.6).
2. ОСНОВНІ ТИПИ І СТРУКТУРА ЦИФРОВИХ ІНТЕГРУЮЧИХ МАШИН
На основі різницевої СУШ можуть бути побудовані різні типи цифрових інтегруючих машин: екстраполяційні та інтерполяційні, послідовні та паралельні.
Екстраполяційні паралельні ЦИМ конструюються безпосередньо наоснові рівнянь різницевої СУШ та у загальному випадку складаються з N реальних цифрових інтеграторів, 2N суматорів та N екстраполяторів прирощень. Обчислювальні блоки в подібних ЦИМ працюють паралельно, в результаті чого процес інтегрування виявляється розгорнутим.
тим у просторі та швидкість інтегрування підвищується в порівнянні
з послідовними ЦИМ у N разів.
До структури паралельних ЦИМ входять: електронний комутуючий пристрій (КУ), пристрій керування, а також пристрої введення та виведення інформації.
Послідовна екстраполяційна ЦІМ складається в загальному випадку з одного інтегратора, двох суматорів і одного екстраполятора прирощень, а також іноді з деяких додаткових вирішальних блоків, які послідовно обробляють інформацію, що стосується N різних інтеграторів. В результаті процес інтегрування виявляється розгорнутим у часі.
Послідовна ЦИМ повинна містити пристрій, що запам'ятовує, в якому зберігаються вихідні і проміжні дані для кожного вирішального блоку, а також програма рішення задачі. Крім того до структури послідовної ЦИМ входять: прості пристрої введення та виведення інформації. (Окремі структурні компоненти послідовної ЦІМ використовуються в лабораторних роботах при моделюванні паралельної ПС.)
Послідовні ЦИМ вимагають менших витрат устаткування, ніж паралельні, а й швидкість роботи у N разів менше.
Поряд з екстраполяційними ЦІМ можуть бути сконструйовані паралельні та послідовні інтерполяційні ЦІМ з паралельним та послідовним способами обробки інформації в цифрових інтеграторах, що відрізняються точністю формул чисельного інтегрування, та інших вирішальних блоків, а також за способом утворення та використання прирощень або значеньприрощень.
3. ПЕРЕХІД ВІД ФУНКЦІЙ ДО РІВНЯННЯ ШЕННОНА, що породжує.
У [2] було обгрунтовано важливу можливість представлення функцій з допомогою рівнянь Шеннона, проте обгрунтування важливої можливості ще рівнозначно вказівку оптимального шляху переходу від заданих функцій до відповідних рівнянь. Оскільки проблема переходу від функціональних залежностей до еквівалентних рівнянь Шеннона має важливе значення під час програмування завдань ЦИМ, то цьому питанні слід зупинитися докладніше.
Розглянемо один з найбільш ефективних методів переходу від заданих функцій до систем рівнянь Шеннона, що породжує. Припустимо, що задана якась негіпертрансцендентна функція багатьох змінних
являє собою суперпозицію більш простих функцій, яку
необхідно подати у формі рівнянь Шеннона.
Таку функцію слід перш за все розчленувати на ряд елементів.