Організація паралельних обчислень в алгоритмах ШПФ на процесорі NM6403

Значна частина задач аналізу часових рядів зв'язана з перетворенням Фур'є і методами його ефективного обчислення. У цих задачах перетворення Фур'є відіграє важливу роль як необхідний проміжний крок у визначенні густини спектра потужності, крос-спектральних густин, передатних функцій, згорток, кореляційних функцій, а також у задачах інтерполяції значень. На практиці найбільш широке поширення одержали алгоритми ШПФ за основою 2 [1], де кожен функціональний вузол виконує базову операцію - двохвходового "метелика". Ці алгоритми орієнтовані, насамперед, на зведення до мінімуму числа операцій множення. Але з появою векторних процесорів цей критерій стає несуттєвим. Навпроти, число одночасно виконуваних множень головним чином визначає продуктивність процесора. Тому виникає питання про розпаралелюваня обчислень і реалізацію алгоритмів ШПФ із більш високими основами і їхніми можливими комбінаціями. Послідовність обчислень будь-якого ШПФ можна описати у вигляді графа, вузли якого виконують фактично звичайне дискретне перетворення, але з меншою розмірністю вхідних векторів (меншою основою). В залежності від вибору основи міняється як загальне число арифметичних операцій, так і кількість шарів графа.

Таблиця 7.2. Обчислювальна складність ШПФ

	Пряме обчислення ШПФ (основа N)	Обчислення ШПФ за основою 2	Обчислення ШПФ з комбінованими основами 2, 16, 32
Complex muls	Complex adds	Кількість шарів графу	Complex muls	Complex adds	Кількість шарів графу	Complex muls	Complex adds	Комбінація основ	Кількість шарів графу
N	N2	N2 -N		(N/2)log2N	Nlog2N
									16-16
									2-16-16
									32-32
									2-32-32

Complex muls - кількість комплексних множень

Complex adds - кількість комплексних додавань

В алгоритмах ШПФ за основою 2 кількість таких шарів максимальна (табл.7.2), тому при поетапному надходженні результатів обчислень від шару до шару відбувається більше нагромадження помилок округлення, ніж в алгоритмах з більш високими основами. І чим вища розмірність вектора вхідних даних, тим більша буде кількість шарів і в наслідок значніша помилка. Це особливо критично у випадках, коли обчислення проводяться в цілочисельній арифметиці (з фіксованою крапкою) чи при недостатньо широкій розрядності даних. Слід також зазначити, що в цьому випадку для запобігання переповнення проміжні результати після кожного чи після групи етапів множення (шарів графа) необхідно додатково нормалізувати, застосовуючи операцію зсуву вправо. Нормалізація крім зсуву може містити в собі процедуру округлення, що також вносить додаткові обчислювальні витрати. Можливим компромісним рішенням може виступати підхід, оснований на збільшенні основи в алгоритмах ШПФ. Нижче розглядається варіант ШПФ-256 за основою 16. Вибір такої основи з однієїсторони дає можливість для організації паралельних обчислень, а з іншої знижує кількість шарів графа до двох.

Дискретне 256-точкове перетворення Фур'є визначається формулою:

,де

Дана формула після тотожних перетворень приймає вид, що є опорним для побудови

ШПФ-256 за основою 16:

Кінцевий граф обчислення ШПФ-256 за основою-16 будується з цієї формули. Структура такого графа наведена на рис.7.3.

Рис.7.3 Узагальнений граф обчислення ШПФ-256 Рис.7.4. Розгорнута схема блоку 16-точкового

за основою 16. дискретного перетворення Фур'є

Граф складається з двох шарів по 16 блоків. Кожен блок графа має 16 комплексних входів і виходів. Як показано на рис.2 кожен блок графа являє собою 16-точкове дискретне перетворення Фур'є і відрізняється від інших блоків тільки комплексними коефіцієнтами W. Таким чином, распаралелювання алгоритму БПФ фактично зводиться до реалізації ефективного обчислення ДПФ-16, тобто до знаходження 16 скалярних добутків різних векторів [W] з одним вектором [x], що еквівалентно множенню матриці коефіцієнтів перетворення Фур'є -[W] розмірністю 16х16 на вхідний вектор [х].

Уявні і дійсні частини коефіцієнтів W зберігаються так само в упакованому виді, але в різних 64р. словах. Усі коефіцієнти W обчислюються заздалегідь і тому зберігаються усередині масиву в порядку зручному для наступних обчислень (рис.7.5).

Рис.7.5 Формат збереження вхідних даних і коефіцієнтів перетворення

Внаслідок такого представлення даних векторний помножувач працює в двох конфігураціях:

Рис.7.6 Еквівалентна схема помножувача векторного Рис.7.7 Еквівалентна схема помножувача векторного

співпроцесора NM6403 при розбитті матриці співпроцесора NM6403 при розбитті матриці

вагових коефіцієнтів - (2х32біти)/(8х8біт) вагових коефіцієнтів - (2х32біти)/(2х32біти)

По приведених двох варіантах розбивки матриці векторного помножувача виробляється повний процес скалярного множення двох комплексних векторів. Перша схема виконує 16 множень з нагромадженням за такт і служить для знаходження сум попарних добутків уявних і дійсних частин, друга виконує 4 множення з нагромадженням за такт, але фактично служить тільки для остаточного додавання отриманих часткових сум. Повна схема множення двох комплексних векторів довжиною 16 елементів відображена на рис.6. Тому що за один раз у матрицю вагових коефіцієнтів можна завантажити тільки 8 елементів вектора [х], завантаження усього вектора [х] відбуваються в два етапи.

Весь процес обчислення скалярного добутку складається з трьох етапів:

4. В матрицю вагових коефіцієнтів завантажуються 8 комплексних чисел x(0)..x(7).

На вхід помножувача X по черзі подаються спочатку вектор з 8-ми дійсних частин комплексних

коефіцієнтів W(0)..W(7) (тут ), а потім вектор з 8-ми уявних частин. Множення робиться відповідно до схеми на рис.4.

5. Далі з виходу помножувача результат добутку у виді двох 64р. слів безпосередньо надходить на підсумовуючий Y-вхід помножувача. При цьому в матрицю вагових коефіцієнтів завантажуються числа x(8)..x(15), а на вхід X помножувача аналогічно надходять і збільшуються нові коефіцієнти W(8)..W(15).

6. Для одержання остаточного результату -y(k), суми в лівих і правих частинах двох останніх результатів ("3-rd product" і "4-th poduct") необхідно перехресно скласти (з врахуванням знака "-"). Для цього, як показано на рис.6, в матрицю вагових коефіцієнтів завантажуються числа 0,1 і -1, а самі суми подаються на вхід X і Y і далі, працюючи за схемою на рис.5, векторний помножувача видає кінцевий результат для y(k).

Для наочності на рис.6 проілюстрований процес скалярного множення тільки двох векторів. В дійсності завантаження вхідних даних здійснюється пакетами по 32 64-розрядні слова, що дозволяє

максимально ефективно використовувати векторний співпроцесор. В результаті, з врахуванням часу передачі даних кожен крок множення (рис 4, рис 5) практично займає один процесорний такт, це досягається за рахунок одночасного використання двох шин даних - підкачування вхідних даних x(і) по одній шині суміщається з завантаженням коефіцієнтів W(і) чи вивантаженням результатів множення y(і) по іншій. Таким чином, реально вся процедура скалярного множення двох комплексних 16-мірних векторів у середньому по всьому ШПФ-256 складає 7 процесорних тактів.