ТАБЛИЦІ ПОШУКУ ДЛЯ ПІДВИЩЕННЯ ШВИДКОСТІ ОБЧИСЛЕНЬ У КОМП’ЮТЕРНІЙ ГРАФІЦІ ТА ЇХ ПЕРСПЕКТИВИ У МАЙБУТНЬОМУ



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

LOOKUP TABLES FOR INCREASING COMPUTING SPEED IN COMPUTER GRAPHICS AND THEIR PROSPECTS IN THE FUTURE

Goncharenko O.R., student of the NTUU «KPI»

Kyiv, Ukraine

This article describes look-up tables, whose use ofis one of the many methods of optimization, increasing productivity andperformance in actual computing. Examples of the usage of the most commonlookup tables are demonstrated in this article. Discussed prospects of thelookup tables in the future.

Key words: lookuptable, LUT, memristor.

Таблиці пошуку (англ. lookup table, LUT) – це структура даних, яка використовується для заміни обчислень на операції пошуку. Якщо отримання даних з таблиці пошуку буде швидшим ніж обчислення результатів з нуля, то використання таблиці дасть значний приріст в продуктивності [1]. Для таблиці обчислюються найбільш поширені вхідні данні. Для запитів, які потрапляють між прикладами з таблиці, алгоритм інтерполяції може генерувати прийнятні наближенні значення шляхом усереднення найближчих значень.

На рис. 1 зображено приклад таблиці пошуку. Кожна точка набору даних є показником вхідних значень конкретної величини таблиці пошуку. Масив даних таблиці служить в якості дискретного представлення функції, обчисленої в певній точці, яка є індексом даних [2].

Рис. 1. Приклад таблиці пошуку

Проте, використання таблиць пошуку у простих обчисленнях може призвести до погіршення роботи. Час запиту ресурсів з пам'яті і складність пам'яті можуть підвищити час виконання програми і складність системи. Можливість росту кеш-пам'яті також може стати проблемою. Запит даних у великих таблицях може призвести до промахів кешу. У деяких мовах програмування (наприклад, Java), звернення до таблиці пошуку може бути навіть більш «дорогим» через обов'язкові перевірки кордонів, що включає в себе додаткові порівняння та розгалуження для кожної операці пошуку. Розглянемо приклад використання таблиць пошуку у алгоритмі пошуку схожих зображень. Маємо систему з великою кількістю зображень і на вхід надходить команда «Знайти схожі зображення». Для цього потрібно проаналізувати кожне зображення, зменшити його (зазвичай роблять сітку 8х8), прибрати колір(привести зображення до градацій сірого), створити ланцюг біт, беручи 0 або 1 взалежності від середнього значення кольору в певній точці, перевести отримане значення до простого хешу, отримати таким самим чином хеш вхідного зображення,та на кінець порівняти кількість різних бітів. Час отримання результату пошуку буде помітно зростати з кожним новим зображенням. Але, якщо, мати таблицю пошуку з попередньо підрахованими значеннями хешу для кожного зображення, то швидкість формування масиву відповіді значно збільшитися. Окрім швидкого пошуку схожих зображень, можливо пришвидшити трансформацію зображення, а саме за рахунок таблиць пошуку оптимізувати приведення зображення до чорно-білого спектру. Потім розглянемо це більш детально.

Таблиці пошуку також широко використовуються в перетворенні (трансформації) зображень. В залежності від складності перетворення збільшення швидкості обчислень може бути здобуте саме за рахунок таблиць пошуку, аж до 15 разів або навіть більше для логарифмічних чи експоненціальних перетворень [3].

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

Рис. 2. Спеціально визначена таблицяпошуку та тривимірна таблиця пошуку

Рис. 2 показує спеціально визначену таблицю пошуку. Ця таблиця (рис. 2) повертає чорний колір для дуже яскравих та дуже темних зон, а для зон з середнім освітленням – білий. Таким чином палітру можна зменшити до двох рівнів сірого.

Якщо подивитися на це з математичної точки зору, то використання таблиць пошуку для перетворень уграницях сірого, означає, що деяка функція трансформування f(x) надана у вигляді таблиці, яка містить одну допоміжну точку функції для кожного можливого значення сірого кольору. Іншими словами таблиця містить певне значення для кожного значення відтінку сірого. Кольорові зображення також можуть бути трансформовані за допомогою таблиць пошуку, але для цього треба буде мати таблицю пошуку для кожного кольорового каналу і така таблиця пошуку називається тривимірною (3D). Прискорення відбувається за рахунок того, що не потрібно кожен раз обчислювати значення функції для певного параметру, це робиться один раз при першому запуску додатку.

Тривимірні таблиці пошуку індексовані за трьома незалежними параметрами, якпоказано на рис. 2 [4].

Тоді як одновимірна таблиця містить тільки 4 елементи в 4-х однакових місцях по кожній осі, відповідна трьох вимірна таблиця пошуку містить 43, що дорівнює 64-м елементам. Тому розмірність 3D таблиці пошуку зростає з лінійною частотою дискретизації. Длятого щоб помістити в пам’ять 32х32х32 таблицю треба 393 КБ, 256х256х256 таблиця вимагає 200 МБ. Навіть якщо GPU має стільки доступних ресурсів, великі трьох-вимірні таблиці пошуку можуть швидко заповнити весь кеш текстурування, що може погіршити продуктивність. 3D таблиці пошуку є незамінною складовою у системах реального часу, задача яких - відтворювати потокове відео. Саме за рахунок таблиць пошуку відео може бути оптимізоване для перегляду без значного зниження fps шляхом використання певних фільтрів які корегують контраст, яскравість, тон та інші параметри зображення [5].

Розглянемо приклад лінійної кольорокорекції, зміни контрасту за допомогою лінійного розтягнення (як автоконтраст у Photoshop). Корекція – до зображення застосовуєтся перетворення яскравості, компенсуючи небажаний ефект:

\[{{f}^{-1}}\left(y \right)=x\]

де y – яскравість пікселя на вхідномузображенні, х – яскравість пікселя після корекції.

Компенсація вузького діапазону яскравості – лінійне розтягнення:

\[{{f}^{-1}}\left( y\right)=\left( y-{{y}_{\min }} \right)\cdot \frac{255}{{{y}_{\max }}-{{y}_{\min}}}\]

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

За підрахунками NVidia [4]таблиці пошуку підвищують продуктивність більше ніж у 100 разів і це не є межею. Недоліки, пов’язані з розміром таблиць пошуку, можуть бути усунені в майбутньому з використанням комп’ютерів нового покоління на базі мемристорів. Мемристор (рис. 3) – це пасивний елемент в мікроелектроніці, здатний змінюватисвій опір в залежності від заряду, що протікав в ньому. Основна перевага цього елементу в його енергонезалежності та надшвидкій передачі даних [6].

Рис. 3. 17 мемристорів

У даний час компанія Hewlett-Packard розробляє перший у світі суперкомп’ютер на базі мемристорів. Проекту дали кодову назву «The Machine». Комерціалізація технології очікується у 2020-х [7].

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

Наприклад, на рис. 4 ви можете побачити приблизну структуру такої таблиці пошуку для комп’ютерів на базі мемристорів. Структура таблиці пошуку проста: масив 3x3,кожен елемент якого містить в собі посилання на інші масиви (таблиці пошуку), які занадто великі щоб зберігати їх усі в кеш-пам’яті. Тому під час запиту до певного елементу буде завантажуватись до кешу певна область, яка необхідна для обчислень в даний момент (як LUT (0,2) замінює LUT (1,1) на рис. 4).

Рис. 4. Можливий варіант таблиці пошуку у системі на базі мемристорів

Заключення

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

Список використаних джерел

  1. Automated Memorization in C++[Електронний ресурс] – Режим доступу до ресурсу: http://pmcnamee.net/c++\-memoization.html

  2. Anatomyof a Lookup Table [Електронний ресурс] – Режим доступу до ресурсу:http://www.mathworks.com/help/simulink/ug/anatomy\-of\-a\-lookup\-table.html

  3. Christian Demant. Industrial Image Processing: VisualQuality Control in Manufacturing / Christian Demant, Bernd Streicher-Abel,Carsten Garnica, 1999. – 353 с.

  4. Matt Pharr. GPU Gems 2: Programming Techniques forHigh-Performance Graphics and General-Purpose Computation / Matt Pharr, 2005. –814 с.

  5. Benny Bing. Next-Generation Video Coding and Streaming/ Benny Bing, 2015. – 344 с.

  6. Гончаренко О. Р. Підходи до побудови пам’яті обчислювальних систем наоснові мемристорів / О. Р. Гончаренко, А. М. Волокита // Перспективні напрямкисучасної електроніки, інформаційних і комп’ютерних систем / Дніпропетровськ, 2015. – С. 129-131

  7. The Machine: A new kind of computer [Електронний ресурс] – Режим доступу до ресурсу: http://www.labs.hpe.com/research/themachine/
  • Рецензент: к.т.н., доц. каф. ОТ НТУУ "КПІ" Волокита А.М.
May 24, 2016