Векторні обчислення

Зміст.
Вступ.
1. Методи виконання векторних операцій.
2. Векторний співпроцесор IBM 3090.
3. Структура співпроцесора.
4.Висновок.
Список використаної літератури.



ВЕКТОРНІ ОБЧИСЛЕННЯ
Вступ.
Хоча продуктивність сучасних великих обчислювальних машин багаторазово зросла, існує клас задач, для яких їхні можливості як і раніше виявляються недостатніми. Ці задачі зв'язані з моделюванням реальних фізичних процесів у різних середовищах і вирішуються в таких галузях науки, як аеродинаміка, сейсмологія, метеорологія, ядерна фізика, фізика плазми і т.п. [WILS84].
Характерною рисою вищезгаданих задач є виконання одноманітних обчислювальних процедур з величезними масивами числових даних, що описують багатомірні фізичні поля, які змінюються динамічно. Для вирішення подібних задач розробляється окремий клас обчислювальних систем, що одержав назву суперкомп'ютерів. Такі системи повинні мати здатність виконувати сотні мільйонів арифметичних операцій у секунду над числами у форматі з плаваючою комою. Вартість існуючих систем цього класу досягає 10-15 млн. доларів. На відміну від великих обчислювальних машин (мейнфреймів), що проектуються в розрахунку на мультипрограмний режим роботи й інтенсивний обмін інформацією з периферійними пристроями, суперкомп'ютери оптимізовані з урахуванням особливостей числової обробки великих і надвеликих масивів даних.
Через велику вартість суперкомп'ютерів і їхньої спеціалізації на виконанні задач певного класу ринок таких систем досить обмежений. Їх застосовують тільки дуже потужні дослідницькі центри, що працюють, в основному, по урядових програмах. Незважаючи на величезні обчислювальні можливості сучасних суперкомп'ютерів, потреби наукових досліджень увесь час зростають.
У рамках цього напрямку розвивається клас комп'ютерів, орієнтованих на операції над векторами – так звані матричні процесори (array processor). Вони використовуються як співпроцесори для ефективної обробки векторизованих фрагментів програм.
1.Методи виконання векторних операцій
Нижче ми розповімо, у чому особливість операцій над векторними змінними і як ці операції виконуються в комп'ютерах різних класів. У комп'ютері загального призначення обробка векторів або масивів чисел у форматі з плаваючою комою організовується у вигляді циклічної процедури, причому в кожному циклі обробляється черговий елемент масиву. Розглянемо, наприклад, два вектори (одномірних числових масива) – А і В. Необхідно додати їх і помістити результат у вектор С. Для цього буде потрібно шість операцій додавання:
Як можна прискорити виконання подібних операцій? Необхідно впровадити паралелізм у тій або іншій формі.
Існує кілька підходів до впровадження ідей паралельного виконання операцій в обробку векторів. Найпростіше розглянути їх на конкретному прикладі перемножування квадратних матриць розміром . Формула для обчислення кожного елемента матриці результату має вигляд:
Тут , і – елементи матриць А, В і С.
Нижче представлений текст програми мовою FORTRAN, яку можна виконувати на будь-якому скалярному процесорі загального призначення.
DO 100 I=1,N DO 100 J=1,N C(I,J)= 0.0 DO 100 К=1,N
C(I,J)=C(I,J)+ A(I,K)*B(K,J) 100 CONTINUE
Один з методів підвищення продуктивності виконання подібних обчислень одержав назву векторної обробки. Цей метод припускає, що в програмі можна оперувати з одномірним вектором даних. Нижче представлена програма модифікованою мовою FORTRAN, у якому реалізована нова форма операторів, що дозволяє специфікувати операції над векторами.
DO 100 I=1,N C(I,J)= 0.0(J= 1,N) DO 100 К=1,N
C(I,J)=C(I,J)+ A(I,K)*B(K, J) (J=1,N) 100 CONTINUE
Член виду (J=1,N) означає, що операції над елементами з всіма індексами J у заданому інтервалі будуть виконуватися як єдина процедура. Про спосіб реалізації такого методу обчислень буде розказано нижче. У представленому тексті програми всі елементи в i-му рядку обчислюються паралельно. Кожен елемент у рядку являє собою суму, доданки якого обчислюються послідовно. Але навіть у цьому випадку потрібно тільки операцій векторного множення в порівнянні з операцій скалярного множення в попередньому варіанті.
Наступний варіант – паралельна обробка. Такий підхід припускає, що в нашому розпорядженні знаходиться N незалежних процесорів, що працюють паралельно. Для того щоб ефективно їх використовувати, потрібно якимось чином вказати, які обчислення повинні виконувати ці процесори. Для цього в мові програмування існує два типи директив. Директива FORK n указує, що паралельно виконувані процеси починаються в рядку програми з міткою n. Але вихідний процес продовжується оператором, що стоїть відразу за FORK. Кожне виконання директиви FORK породжує новий процес. Директива JOIN виконує роль, зворотну FORK. Вираз JOIN N вказує, що N незалежних процесів зливаються в один, котрий продовжується оператором, що стоїть відразу за JOIN. Координація такого злиття процесів покладається на операційну систему, і виконання загального процесу не відновляється доти, поки всі паралельні незалежні процеси не завершаться.
Нижче представлений текст програми паралельної обробки, що за формою мало відрізняється від першого з розглянутих варіантів тексту. Але в даному випадку кожний стовпець С обчислюється окремим процесом, і, отже, елементи певного рядка матриці обчислюються паралельно.
DO 50 J= 1,N
FORK 100 5 0 CONTINUE
J = N 100 DO 200 I = 1,N
C(I,J) = 0.0
DO 200 ДО = 1,N
C(I,J)= C(I,J)+A(I,K)*B(K,J) 200 CONTINUE JOIN N
Ми описали підходи до логічної організації векторних обчислень. Тепер розглянемо, яка повинна бути структура процесорів, здатних реалізувати ці підходи. Можна виділити три основних категорії:
процесор з конвеєрними АЛП;
процесор з паралельними АЛП;
паралельні процесори.
На рис. 6.1 представлені схеми двох перших варіантів. Конвеєрну організацію обробки машинних команд у процесорі ми вже розглядали в главі 11. На представленій схемі концепція конвеєра поширена і на організацію АЛП.
Оскільки арифметичні операції з числами у форматі з плаваючою комою досить складні, можна розбити кожну операцію на окремі фази і виконувати ці фази паралельно з різними числами (рис. 6.2,а). Операція додавання розділена на чотири фази – порівняння порядків (С), зсув мантиси одного з доданків (S), додавання мантис (А) і нормалізація суми (N), Послідовності чисел (вектори доданків) подаються на вхід блоку виконання першої фази. Надалі, у міру того як процес обробки просувається, у блоках виконання різних фаз виявляються чотири пари чисел – елементів сумованих векторів.
Очевидно, що така організація цілком підходить для обробки векторів. Щоб переконатися в цьому, згадайте опис методики конвеєрної обробки машинних команд у главі 11: процесор виконує повторювані операції зчитування й обробки команд із послідовних комірок пам'яті, і під час відсутності команд розгалуження конвеєр завжди заповнений. Точно так само і конвеєрний АЛП повинен увесь час заповнюватись даними – послідовними елементами оброблюваних векторів. Якщо буде виконуватися окрема арифметична операція, такий АЛП ніякого підвищення продуктивності не дасть. Завантаженням АЛП – передачею в нього елементів векторів – займається пристрій керування.
Можна удосконалити конвеєр – витягати елементи векторів з регістрів, а не з пам'яті. Саме це зображено на схемі, представленій на рис. 6.1,а. Елементи кожного операнду-вектора завантажуються єдиним блоком у векторний регістр, що являє собою не що інше, як великий набір однакових регістрів. Результат також поміщується у векторний регістр. Таким чином, більшість операцій включає тільки звертання до регістрів, а звертання до пам'яті відбувається винятково при виконанні команд завантаження і збереження.
Структуру, зображену на рис. 6.2, можна назвати внутріопераційним конвеєром. Цей конвеєр виконує єдину арифметичну операцію з двома векторними операндами (у даному випадку С = А + В) таким чином, що кілька елементів операндів-векторів обробляються паралельно. Внутріопераційний конвеєр можна доповнити міжопераційним конвеєром, що дозволяє прискорити виконання певної послідовності арифметичних операцій з векторними операндами. Один з методів організації міжопераційного конвеєра, що отримав назву зачеплення (chaining) векторних операцій, використовується в суперкомп'ютерах сімейства CRAY. Суть його в тому, що векторна операція може починатися, як тільки готові перші елементи пари векторів-операндів і функціональний елемент, що виконує операцію (додавання, віднімання, множення і т.п.), вільний. Тому результат, сформований одним функціональним вузлом, що побудований за схемою внутріопераційного конвеєра, негайно передається на вхід наступного функціонального вузла. При цьому як проміжні ланки ланцюга використовуються векторні регістри, і вся послідовність операцій виконується без збереження проміжних результатів у пам'яті.
Нехай, наприклад, потрібно обчислити С = (s хА) + В, де С, А и В – вектори, as – скаляр. У CRAY одночасно виконуються всі три операції: елементи, що завантажуються з пам'яті у векторні регістри операндів, негайно надходять у конвеєрний помножувач, результат передається в конвеєрний суматор, і елементи вектора суми передаються у векторний регістр результату відразу ж після їхнього обчислення.
Команди 2 і 3 можуть виконуватися паралельно, оскільки вони звертаються до різних регістрів і комірок пам'яті. Команді 4 необхідні результати виконання команд 2 і 3, і блок виконання цієї команди включається в ланцюжок після них. Як тільки перші елементи векторів будуть передані у векторні регістри VR2 і VR3, почнеться виконання команди 4.
Векторну обробку можна організувати і за допомогою багатьох АЛП в складі єдиного процесора, контрольованого одним пристроєм керування. У цьому варіанті пристрій керування направляє дані в блоки АЛП таким чином, що останні можуть працювати паралельно. У свою чергу, у кожному з паралельно працюючих АЛП можна використовувати конвеєр. На рис. 6.2,б зображено приклад такої схеми з чотирма АЛП, що працюють паралельно. При обробці векторів у такому процесорі пристрій керування направляє їхні елементи в блоки АЛП порціями, поки всі елементи не будуть передані на обробку.
І нарешті, третій метод організації обробки векторів – використання багатьох паралельно працюючих процесорів. У цьому випадку необхідно розділити задачу на багато окремих процесів, які можна було б виконувати паралельно. Використання такого варіанту має сенс тільки в тому випадку, якщо операційна система й апаратні засоби дозволяють чітко координувати паралельне виконання окремих підзадач. В даний час у цій області активно ведуться дослідження (див., наприклад, [GEHR88]).
Тепер ми можемо розширити класифікацію обчислювальних систем, приведену в розділі 1, і включити в неї описані вище структури (рис. 6.3). Можна розділити обчислювальні системи по ознаці наявності в складі системи одного або декількох пристроїв керування. Наявність багатьох пристроїв керування припускає наявність багатьох процесорів. Як випливає з наших міркувань, багато процесорів можуть спільно виконувати певну задачу, і в цьому випадку ми говоримо про паралельні процесори.
Хочу звернути увагу читачів на те, що в літературі часто зустрічаються не зовсім вдалі терміни, що стосуються мультипроцесорних систем. Термін векторний процесор (vector processor) часто позначає АЛП з конвеєрною організацією, хоча системи з паралельно працюючими АЛП точно так само використовуються для обробки векторів. Під терміном обробка масивів (array processing) також часто розуміється використання паралельних АЛП, у той час як усі три варіанти розглянутих структур прекрасно підходять для обробки масивів. Термін матричний процесор (array processor), як правило, позначає співпроцесор, що підключається до процесора загального призначення для виконання операцій над векторами.
В даний час на ринку суперкомп'ютерів домінують системи з конвеєрними АЛП, найбільш простими в порівнянні з двома іншими варіантами, розглянутими в цьому розділі. Конструкції пристроїв керування й операційних систем для них досить добре відпрацьовані і забезпечують ефективне використання наявних обчислювальних ресурсів. Нижче ми розглянемо конкретні реалізації обчислювальних систем для векторних обчислень.
2. Векторний співпроцесор IBM 3090
Гарним прикладом використання конвеєрного АЛП для обробки векторів є векторний співпроцесор IBM 3090, розроблений як один з компонентів сімейства IBM S/370 [PADE88], [TUCK87]. Багато в чому векторні функції IBM 3090 нагадують ті, що реалізовано в суперкомп'ютері CRAY.
У співпроцесорі широко використовуються векторні регістри. Кожний векторний регістр є набором скалярних регістрів. Для обчислення векторної суми С = А + В вектори А і В завантажуються в два векторних регістри. Не чекаючи завершення завантаження, дані з цих регістрів передаються в АЛП, а результат надходить у вихідний регістр. Накладення фаз операцій завантаження й обчислення істотно прискорює виконання всієї операції.
3. Структура співпроцесора.
Застосування конвеєрного АЛП для виконання операцій з векторами забезпечує підвищення швидкодії в порівнянні з циклічним виконанням скалярних арифметичних операцій, чому сприяють наступні умови.
Фіксована визначена структура векторних даних дозволяє замінити службові операції в тілі циклу більш швидкими внутрішніми операціями в співпроцесорі, що реалізуються апаратно або з допомогою мікропрограм.
Доступ до даних і власне обчислень можуть виконуватися паралельно.
Використання векторних регістрів для збереження проміжних результатів дозволяє уникнути додаткових звертань до пам'яті.
На рис. 6.4 представлена блок-схема векторного співпроцесора. Хоча співпроцесор і є окремим блоком, його архітектура вписується в загальну концепцію сімейства IBM S/370 і сумісна з нею. Інтеграція співпроцесора в IBM S/370 забезпечується в такий спосіб.
Для виконання всіх скалярних операцій у співпроцесорі використовується набір машинних команд IBM S/370.
Арифметичні операції з векторами в співпроцесорі формують результат точно в такому ж форматі, що і команди виконання скалярних операцій у IBM S/370. Наприклад, при проектуванні вузла виконання ділення розроблювачі повинні були вирішити, чи варто завжди домагатися точного результату, як це робиться в скалярному АЛП процесора IBM S/370, або можна пожертвувати точністю в молодших розрядах результату, збільшивши за рахунок цього швидкодію. Вибір був зроблений на користь збереження повної сумісності з архітектурою S/370, хоча це і трохи знизило продуктивність співпроцесора.
Команди виконання векторних операцій можуть перериватися, а потім відновлятися після обробки переривання точно так само, як і інші машинні команди S/370.
Набір виняткових ситуацій, зв'язаних з визначеними сполученнями значень операндів, при обробці векторів у співпроцесорі цілком дублює набір виняткових ситуацій у скалярному процесорі S/370. Для їхньої обробки використовуються ті ж підпрограми. Щоб досягти цього, індекс переривання формується таким чином, що вказує стан векторного регістра, у якому з'явилася виняткова ситуація (наприклад, переповнення).
Векторні дані знаходяться у віртуальній пам'яті, і переривання по відсутності сторінки для цих даних обробляється точно так само, як і для інших.
Рисунок 6.4 Блок-схема співпроцесора IBM 3090
Такий рівень сумісності має багато переваг. Існуючі операційні системи після мінімальної модифікації можуть працювати із співпроцесором. Раніше розроблені прикладні програми і компілятори можуть використовуватися в системі з співпроцесором без внесення яких-небудь змін.
4.Висновок.Якщо бажано, щоб раніше розроблені програми могли скористатися перевагами співпроцесора при виконанні обчислень, у них потрібно внести незначні зміни.Векторні команди, що обробляються співпроцесором, відносяться до типу "регістр-регістр", тобто і операнди і результат зберігаються в регістрах. Цей же підхід використовується й у суперкомп'ютері CRAY. У комп'ютерах фірми Control Data застосовується альтернативний підхід – операнди витягаються безпосередньо з пам'яті. Невелика незручність, створювана обов'язковим використанням регістрів, полягає лише в тому, що програміст або компілятор повинні враховувати особливості структури співпроцесора при підготовці машинної програми. Наприклад, допустимо, що довжина набору векторних регістрів – Kt а розмірність оброблюваних векторів – N>K. У цьому випадку необхідно організувати в програмі цикл, у якому обробляється вектор з К елементів, а кількість повторень цього циклу – N/K.
Який вплив робить на швидкодію співпроцесора використання регістрів, продемонструє приведений нижче приклад (приклад взятий з роботи [PADE88J). мовою FORTRAN програма перемножування двох комплексних векторів виглядає в такий спосіб:
DO 100 J=l,50
CR(J)=AR(J)*BR(J)-AI(J)*BI(J) 100 CI(J)=AR(J)*BI(J)-AI(J)*BR(J)
Програма перемножує вектори А и В і формує результуючий вектор С, причому усі вектори мають дійсну (AR, BR, CR) і уявну (AI, BI, CI) частини. Співпроцесор 3090 може протягом одного машинного циклу виконати одну операцію звертання до пам'яті (читання або запис) або дві операції читання й одну операцію запису в регістр. Крім того, протягом одного машинного циклу в АЛП виконується одна векторна команда.
При використанні для виконання цієї програми команд, що вибирають операнди з пам'яті і поміщають результати у пам'ять, кожний цикл обчислень буде займати 18 машинних циклів:
Операція "пам'ять-пам'ять" | К-сть циклів
AR(J)*BR(J)->T1(J) | 3
AI(J)*BI(J)->T2(J) | 3
T1(J)-T2(J)->CR(J) | 3
AR(J)*BI(J)->T3(J) | 3
AI(J)+BR(J)->T4(J) | 3
T3(J)+T4(J)->CI(J) | 3
Всього | 18
Якщо використовувати обчислювальні операції типу "регістр-пам'ять", процес обчислень буде виглядати в такий спосіб:

Список використаної літератури . ……………………………………………………………………
1 Catanzaro B. Multiprocessor System Architectyres. – Mountain View, CA: Sunsoft Press, 1994.
2 Hwang K. Advanced Computer Architecture. – New York : McGraw-Hill, 1993.
3 Lilja D. Cache Coherence in Large-Scale Shared-Memory Multiprocessors : Issues and Comparisons. – ACM Computing Surveys, September 1993.
Pfister G. In Search of Clusters. – Upper Saddle River, NJ : Prentice Hall, 1998.
Stone H. High-performance Computer Architecture. – Reading, MA : Addison-Wesley, 1993.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать