РОЗДІЛ 2
МАТЕМАТИЧНІ МОДЕЛІ ОБЧИСЛЮВАЛЬНИХ СТРУКТУР ДЛЯ
РЕАЛІЗАЦІЇ КОДУВАННЯ, ОБРОБКИ І ПЕРЕДАЧІ ІНФОРМАЦІЇ
2.1. Розробка моделей паралельно-ієрархічних структур для обробки і передачі
інформації
Паралелізм як магістральний напрямок розвитку архітектури ЕОМ приходить на
зміну "класичним" принципам побудови обчислювальних машин. Одновимірність,
лінійність алгоритмічної і схемотехнічної структури пам'яті, послідовність
доступу до даних - ці властивості лежали в основі розробки систем пам'яті
універсальних послідовних ЕОМ [44]. Паралелізм обробки даних висуває нові
вимоги до організації пам'яті. Вони пов'язані з необхідністю паралельного
доступу до множини елементів оброблюваних даних.
Проблема паралелізму не може бути ефективно вирішена простим дублюванням блоків
звичайної пам'яті, так як відмова від послідовного доступу до пам'яті спричиняє
за собою перегляд принципів її алгоритмічної і структурної організації.
Послідовна модель запам'ятовуючого середовища, яке використовувалося при
традиційному підході, вже не може бути основою побудови пам'яті. Послідовна
структура пам'яті [45], насправді, є дуже сильним обмеженням для ефективної
роботи з даними. При послідовному доступі питання про представлення
багатовимірних даних у пам'яті не обговорювалось, тому що не існувало ніякої
альтернативи. У паралельній пам'яті багатовимірність структур даних є природною
її властивістю. У зв'язку з цим необхідно встановити ряд нових закономірностей
у відображенні структур багатовимірних даних на послідовні структури їх
збереження в пам'яті.
Постає питання про розмірність доступу до даних, про форми організації
різноманітних сукупностей даних, які обираються, про їх адресацію, про
організацію ієрархічності при обробці багатовимірних даних і т.п. Все це
наповнює новим змістом задачі, які повинні вирішуватися в теорії структур даних
і теорії проектування структур пам'яті.
В численних прикладних задачах, зокрема, задачі розпізнавання образів
актуальним є зменшення об'єму оперативної пам'яті. Якщо впорядкувати якимось
чином дані, то зменшення об'єму пам'яті можна досягти за рахунок ущільнення,
яке отримаємо представляючи дані при записі в пам'ять, наприклад, системою
функцій. Цьому питанню в літературі приділено багато уваги [3,46]. Проте, за
останні роки ефективними методами стиску даних виявилися спектральні методи.
Для різноманітних базисних систем функцій (функцій Уолша, Хаара, Шаудера,
Крестенсона та ін.) [46] розроблені алгоритми швидких перетворень, які
дозволяють за допомогою простих обчислювальних процедур виконувати пряме й
обернене Фур'є-перетворення. В результаті, в пам'яті комп'ютера можна зберігати
спектральні коефіцієнти розкладання заданих систем функцій у ряди за тією або
іншою базисною системою функцій. Істинні дані відновлюються за допомогою
швидкого Фур'є-перетворення програмним або апаратним шляхом. В якості базисної
вибирається система функцій, яка забезпечує максимізацію кількості нульових
коефіцієнтів розкладання. Зменшення частки ненульових коефіцієнтів у масиві
коефіцієнтів унаслідок використання методів стиску даних призводить до
зменшення об'єму оперативної пам'яті.
У цьому зв'язку актуальною є задача опису даних за адаптивною системою базисних
функцій, формування яких залежить від структури даних, а це істотно покращує
характеристики перетворення [47].
Для проектування пам'яті із паралельно-ієрархічним і багатовимірним доступом до
даних необхідно розв’язати декілька ключових задач. Їх можна коротко
сформулювати в наступних трьох питаннях.
1. Як побудувати багатовимірне і паралельно-ієрархічне перетворювальне
середовище?
2. Як організувати паралельну й ієрархічну вибірку різноманітних підструктур
даних у цьому середовищі?
3. Як забезпечити адресацію даних у паралельно-ієрархічній пам'яті?
Пошук відповідей на ці питання і визначає зміст даного підрозділу.
Задача попередньої обробки даних у паралельному середовищі, яке запам'ятовує, є
ключовою. Розв’язок цієї задачі визначатиме як функціональні можливості
паралельної обробки інформації, так і складність її апаратурної реалізації. Як
наслідок, у роботах [48] про спеціалізовані системи аналізу і синтезу зображень
у структурах паралельної пам'яті досліджуються в оснсвному ті самі підходи, що
й у системах STARAN і BSP [49], незважаючи на специфічні вимоги предметної
області.
Однієї з перших робіт в цій області була робота П.Бадніка і Д.Кука (1971), у
якій досліджувалися можливості паралельного вибору даних у багатоблочному
середовищі, яке запам'ятовує. Подальший розвиток ця теорія одержала в роботах
Д.Лаурі (1975) і Г.Шапіро (1977) і стала основною для ряду досліджень в області
теорії паралельної пам'яті: Д.Ван Вооріс, Т.Моррін (1978), А.Деб (1980),
Б.Ребель, М.Гессель (1982), У.Бэнерджі, Д.Гэджискі, Д.Кук (1983), Х.Ширакава
(1983), Х.Вісхоф, Дж.Ван Лівен (1984), В.Джелбі, Дж.-М.Фрайланг, Дж.Ленфахт
(1984), Дж.Парк (1986), Е.А.Метлицький (1989), В.П.Кожем’яко, Л.І.Тимченко
(2002), Кайохару Айзава (2004) та ін.
В роботах усіх зазначених авторів розглядалися питання побудови паралельної
пам'яті, орієнтованої на збереження дво- або тривимірних масивів структур даних
- багатовимірних узагальнень лінійних списків. В останні роки теорія і методи
проектування розвивалися також у напрямку створення паралельної пам'яті і для
роботи з нелінійними структурами даних - деревами. У роботах М. Гес-
селя (1986), Р.Кройтцбурга (1996-1998), Х.Ширакава (2004) проектування
паралельної пам'яті для дерев розглядається як самостійна задача.
З огляду на ці результати і розвиваючи їх, у представленній роботі наведені
результати досліджень,
- Киев+380960830922