МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Організація паралельних обчислень в алгоритмах ШПФ на процесорі NM6403Значна частина задач аналізу часових рядів зв'язана з перетворенням Фур'є і методами його ефективного обчислення. У цих задачах перетворення Фур'є відіграє важливу роль як необхідний проміжний крок у визначенні густини спектра потужності, крос-спектральних густин, передатних функцій, згорток, кореляційних функцій, а також у задачах інтерполяції значень. На практиці найбільш широке поширення одержали алгоритми ШПФ за основою 2 [1], де кожен функціональний вузол виконує базову операцію - двохвходового "метелика". Ці алгоритми орієнтовані, насамперед , на зведення до мінімуму числа операцій множення. Але з появою векторних процесорів цей критерій стає несуттєвим. Навпроти, число одночасно виконуваних множень головним чином визначає продуктивність процесора. Тому виникає питання про розпаралелюваня обчислень і реалізацію алгоритмів ШПФ із більш високими основами і їхніми можливими комбінаціями. Послідовність обчислень будь-якого ШПФ можна описати у вигляді графа, вузли якого виконують фактично звичайне дискретне перетворення, але з меншою розмірністю вхідних векторів (меншою основою). В залежності від вибору основи міняється як загальне число арифметичних операцій, так і кількість шарів графа. Таблиця 7.2. Обчислювальна складність ШПФ
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 елементів вектора [х], завантаження усього вектора [х] відбуваються в два етапи. Весь процес обчислення скалярного добуткускладається з трьох етапів: 1. В матрицю вагових коефіцієнтів завантажуються 8 комплексних чисел x(0)..x(7). На вхід помножувача X по черзі подаються спочатку вектор з 8-ми дійсних частин комплексних коефіцієнтів W(0)..W(7) (тут ), а потім вектор з 8-ми уявних частин. Множення робиться відповідно до схеми на рис.4. 2. Далі з виходу помножувача результат добутку у виді двох 64р. слів безпосередньо надходить на підсумовуючий Y-вхід помножувача . При цьому в матрицю вагових коефіцієнтів завантажуються числа x(8)..x(15), а на вхід X помножувача аналогічно надходять і збільшуються нові коефіцієнти W(8)..W(15). 3. Для одержання остаточного результату -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 процесорних тактів. Читайте також:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|