2.1 Розробка паралельно-ярусної форми

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

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

При побудові паралельно-ярусної форми користуємось наступними вимогами:

1. програма представляється у вигляді структури гілок;

2. стрілками показуються вхідні дані і результат обробки;

3. гілка позначається кружками з цифрами;

4. тривалість подається цифрою біля кружка;

5. вхідні гілки позначаються х, вихідні – y (х – мають нижні вхідні індекси, які позначають номери вхідних велечин, y – мають нижні і верхні індекси (верхні відповідають номеру гілки, а нижні – порядковому номеру результату).

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

Спочатку представимо вираз слідуючим чином:

Здійснимо відкривання дужок:

Виконаємо повне відкриття дужок:

Оскільки тип структурної організації являє собою багатоходову ОЗП, а кількість процесорних елементів 5. В такому випадку ми можемо зчитувати до 5 однакових даних (B,D,E) одночасно, без затримки у тактах.

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

Таким чином операції виконуються в основному паралельно, переміщаючись щоразу на новий щабель, званий ярусом.

Отже, ми отримаємо три паралельно-ярусні форми.

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

На рисунку 2 (додаток А) зображена друга паралельно ярусна форма, яку ми побудували на основі приклада (б). Суть цієї операції, із неповним відкриванням дужок, показала нам що такий приклад є ефективнішим, а саме як ми можемо спостерігати із рисунку 2, зменшилась кількість ярусів, і збільшився паралелізм гілок. За рахунок того, що ми можемо зчитувати такі дані як D,E паралельно, не втрачаючи затримки в тактах. Адже обрана система це багато входова ОЗП, це дані можуть зчитуватись паралельно без затримки в часі.

Оскільки це приносить ефективність, здійснимо повне відкривання дужок на прикладі (в).

На рисунку 3 (додаток А) зображена третя паралельно-ярусна форма, на основі прикладу (в). Повне відкривання дужок, значно спростило паралельно-ярусну форму, і кількість ярусів стала рівною трьом. Завдяки паралельному зчитуванню таких даних, як B,D,E. Тому можна сказати, що ми досягли набагато ефективнішої паралельно-ярусної форми розкриваючи дужки.