Практичне застосування розмальовки графів

Розмальовка графів практично застосовується (постановка завдання різних розмальовок тут не обговорюватиметься) для:

Зміст

розклади для освітніх установ (огляд - [1] );
розклади у спорті (огляд - [2] );
планування зустрічей, зборів, інтерв'ю;
розклад транспорту, в тому числі - авіатранспорту [3] ;
розклади для комунальних служб [4];
та інші.

Мабуть, будь-якому конкретному виду забарвлення знайдеться застосування у складанні розкладів.

Помітну роль швидкодії програм на комп'ютері грає час звернення мікропроцесора до даних. А саме, процесор може звертатися (перерахуємо пристрої в порядку зменшення швидкодії та збільшення обсягу) до:

Далі, розглянемо оптимізації програм, пов'язані з розподілом даних у цих пристроях.

Стандартний підхід Хайтіна

Першими [5] важливими роботами, що заклали основи застосування методу розмальовки графів у розподілі регістрів, були [6] , [7] — наступні ж не додали нічого революційного, увага була сконцентрована на прискоренні роботи алгоритму, зменшенні пам'яті, нових евристиках за визначенням вартості відкачування регістрів (введемо визначення далі) та вибору регістрів для відкачування; огляд цих методів можна знайти в [8].

Далі, розглянемо спосіб, запропонований у [7].

Розподіл регістрів (англ. register allocation) мікропроцесора зазвичай проводиться на етапі компіляції.

На вхід процедури розподілу подається якийсь внутрішній код (IL, intermediate language, internal language), який розрахований на віртуальну машину з необмеженим числом регістрів - називатимемо їх віртуальними регістрами.

Наприклад, кількість регістрів загальногопризначення переважно процесорів Intel, відповідних архітектурі:

(Однак, навіть не всі з них можуть бути використані в нашій процедурі розподілу регістрів, оскільки вже можуть бути зайняті — але це вже тонкі питання реалізації.) Оперативна пам'ять може зберігати дуже велику кількість «відкачаних» «регістрів» — обмеження на її обсяг розглядати не будемо.

Перед виконанням самої процедури розподілу варто зробити:

Оптимізацію звернень до віртуальних регістрів.
Визначення того, чи є змінна на даний момент «значною» для кожного місця програми. «Значима» змінна тоді, коли далі у програмі відбувається читання записаного у ній на даний момент значення.

Сам алгоритм розподілу регістрів складається з наступних кроків:

Побудова графа - назвемо його графом несумісностей (interfernce graph, conflict graph). Вершини цього графа - регістри. Вершини суміжні, якщо відповідні змінні «значущі» одночасно (по-іншому: одна із змінних визначена тоді, коли інша вже «значима»).
«Склеювання» змінних (subsumption, variable propagation): якщо до копіювання однієї змінної в іншу, 2-а ще не «значима», а 1-а не «значима» після копіювання — ми можемо опустити непотрібну операцію переміщення і стягнути («склеїти» ») відповідні даним змінним вузли графа.
І, нарешті, найцікавіший для нас етап: знаходження n-розмальовки графа, де n — кількість вищезгаданих реальних змінних. Розв'язанням цього завдання розмальовки є оптимальне розподіл регістрів. Розфарбовуватимемо так:

Для вершин зі ступенем меншим за n — призначимо колір, якщо можна.
Для нерозфарбованих вершин (або їх ступінь не менше n, або кольорузакінчилися) - «відкачуємо» змінні; видаляємо ці вершини із графа. Відповідно, у сусідніх їм вершин ступінь зменшується - і має сенс знову зробити крок 1. (Не варто забувати, що при відкачуванні також можливе введення нової змінної - її треба додати до графа.)

Практика показує, що алгоритм сходиться досить швидко.

Розмальовка графа застосовується у багатьох відомих компіляторах, наприклад:

У GCC версії 4.4 з'явився новий розподільник регістрів [www 2] - англ. integrated register allocator, який застосовує т.з. забарвлення «Хайтіна-Бріггса».
Розмальовка "Хайтіна-Бріггса" застосовується і в (принаймні, його ранніх версіях) компіляторі від Intel для архітектури IA-64. [www 1][9]

Облік паралелізму лише на рівні команд

Процесори, здатні одночасно і незалежно виконувати кілька команд, знаходять все ширше застосування; про них кажуть, що підтримують паралелізм лише на рівні команд (англ. Instruction-level parallelism , ILP ). Назвемо їх ILP-процесорами. Клас ILP-процесорів включає у тому числі процесори з дуже довгим командним словом - VLIW (Very Large Instruction Word, до яких належать, зокрема, багато моделей цифрових процесорів обробки сигналів (ЦПОС). Найвідомішою комерційно успішною реалізацією концепції паралелізму на рівні окремих Інструкцією є сімейство мікропроцесорів Itanium компанії Intel, також варто відзначити архітектуру E2K, розроблену українською компанією МЦСТ.

Для реального використання високої продуктивності ILP-процесорів необхідні компілятори високого рівня мов, здатні генерувати ефективний код; у тому числі, важлива та оптимізація розподілу регістрів. Введення ILP вимагає серйозної переробки методуХайтіна у частині побудови графа несумісності; в [5] запропоновано доопрацьований варіант.

Розподіл коду, що виконується по кешу

Було запропоновано також алгоритм для розподілу часто використовуваних областей коду в кеші [10] — т. зв. англ. cache line coloring.

Граф несумісності тут такий: вершини — деякі блоки коду (можна, наприклад, брати процедури), ребра існують тоді, коли з одного блоку викликається інший. Як видно, ми концентруємось на т.з. конфліктах першого покоління (first-generation cache conflicts) — між «блоком» та її викликаючим/викликаним. Але варто зазначити, що завдання розмальовки вирішується не алгоритмами загального призначення, а спеціальним евристичним, який, до того ж, дає рішення, яке задовольняє додаткові умови.

Достоїнство цього методу в тому, що враховуються і розміри кешу, рядки кешу, блоків коду, і асоціативність кешу. Метод вдало комбінується з іншими оптимізаціями та inline-функціями [10] [11] . Слід зазначити, що може реалізовуватися оптимізатором — але з оптимізатором компілятора, а оптимізатором компоновщика.

Хорошою роботою, що класифікує такі завдання та систематично викладає їх рішення, є [12] .

Термін «розподіл частот» поєднує різні типи завдань, які часто мають різні цілі та моделі. Ці завдання включають:

Планування моделей розподілу (ліцензування, регулювання) радіочастот, що максимізують використання всього радіоспектру.
Врахування того, що треба відвести діапазони і для мобільного, наземного (англ. point-to-point) і супутникового зв'язку, радіо- і телетрансляцій.
Алгоритми, що динамічно розподіляють частоти однієї конкретної мережі між користувачами. Особливо цікавий тут стільниковий зв'язок,в області якої виконано дуже великий обсяг досліджень.

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

Два основні напрями оптимізації тут:

максимізація пропускної спроможності каналів за збереження певного мінімального рівня інтерференції (перешкод);
мінімізація інтерференції задля досягнення фіксованої пропускної спроможності.

У ході розгляду відповідних моделей, у [12] виникають завдання не набагато складніше T-розмальовки (англ. T-coloring) мультиграфа, спискового T-розмальовки (англ. set T-coloring).

Як приклад роботи над реальною стільниковою мережею, результати якої були далі застосовані оператором у своїй практичній діяльності - [13] (Проведено оператором E-Plus (англ. en:E-Plus) - 3-м за величиною в Німеччині (на 2010 рік) )).

Узагальнено представимо завдання так: об'єкти - деякі обчислення, між якими треба розділити обчислювальні ресурси (процесори, комп'ютери ...), що можуть працювати паралельно один до одного. Якісь обчислення можуть виконуватися в паралелі один одному, якісь ні. Відповідно, вершинна розмальовка графа несумісності обчислень і є потрібним розподілом.

Наведемо такі приклади чисельних методів, які можна розпаралелити:

Розкладання Холецького для методу сполучених градієнтів із приреченням

[14] Цей метод є одним із кращих ітераційних методів для вирішення систем лінійних рівнянь алгебри (СЛАУ) з великими, розрідженими, симетричними, позитивно визначеними матрицями.

Метод Зейделя у застосуванні до розріджених матриць

Теж ітераційний метод вирішення СЛАУ.

Цей, у свою чергу, хороший, наприклад, для розрахунку енергорозподільчих електромереж: такі мережі можуть бути представлені графами, вершини яких це споживачі та джерела електроенергії, а ребра лінії електропередач; далі, будується СЛАУ, у матриці якої діагональним елементам відповідають вузли вищезгаданого графа, а ненульовим недіагональним - ребра. [15]

Також, метод може бути т.зв. згладжувачем (англ. iterative smoother) для багатосіточних методів вирішення задач методом кінцевих елементів. (англ. Multigrid методів finite element problems). Оптимізація методу Зейделя, що використовується у згладжуванні, за допомогою т.з. англ. sparse tiling для такого випадку його використання розглянуто у [16] .

Методи з використанням адаптивно уточнюваної сітки

[17] Вони, своєю чергою, корисні у вирішенні диференціальних рівнянь у приватних похідних (ДУЧП). Принцип уточнення тут такий: у місцях, де очікується найбільша локальна похибка, де рішення змінюється найшвидше, щільність сітки вибирається більшою.

Метод координатної релаксації

(англ. Method of coordinate relaxation)

[18] Вдало застосовується у знаходженні екстремальних власних значень дуже великих розріджених симетричних матриць. Іноді таких великих, що їх практичніше генерувати на льоту, ніж зберігати у пам'яті. Такі завдання часто постають у квантовій механіці.

Призначення неповним LU-розкладанням

Для простого випадку, коли «ущільнення» похідної обмежується зменшенням кількості стовпців, наведемо алгоритм:

Вхід: функція від вектора - F

Місце розмальовки графа тут - у обчисленні S . У найпростіших випадках треба обчислюватизвичайну вершинну (англ. distance-1); distance-2 забарвлення (яке, в тому числі зводиться до distance-1 забарвлення square graph); більш складних, потрібні невеликі додаткові обмеження:

зоряна розмальовка (star coloring) - вершинна distance-1, але з додатковим обмеженням: для будь-якого шляху з 4-х вершин використовується не менше 3-х кольорів;
ациклічна розмальовка (acyclic coloring) - вершинна distance-1 + кожен цикл використовує не менше 3-х кольорів.

У рамках вищезгаданого проекту було проведено обчислення для технічних виробничих завдань:

процес хромотографічного поділу (з галузі хімії, хімічної технології) за допомогою техніки англ. Simulated Moving Bed;
вирішення задачі оптимального енергетичного потоку (optimal power flow) (електроенергетика).

Це важливо, наприклад, для встановлення джерела їхнього поширення нелегальним чином. Або для підтвердження прав на дані, наприклад — програмне забезпечення систем на кристалі (system-on-chip).

Повідомлення можна закодувати навіть у графі. Одну з таких технік запропонували Qu і Potkonjak (тому її іноді називають QP-алгоритмом) [21] .

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

Витягти його можна шляхом порівняння отриманого графа з вихідним; існують і способи переконатися в тому,чи було якесь повідомлення закодовано у графі без використання вихідного — докладніше витяг описано, наприклад, [22] .

Розвиток і уточнення думок Qu і Potkonjak, спроби покращення алгоритму відбувається в роботах [23], [24], [22].

Зазначимо, що у [23] , [24] є посилання програмний пакет SandMark, у якому виконані алгоритми такого роду; доступний для завантаження на [www 4] .