Практически приложения на оцветяването на графики

Оцветяването на графиката се използва практически (изложението на проблема с различните оцветявания няма да се обсъжда тук) за:

Съдържание

разписания на учебните заведения (преглед - [1]);
графици в спорта (преглед - [2]);
планиране на срещи, срещи, интервюта;
транспортни разписания, включително въздушен транспорт [3];
графици за комунални услуги [4] ;
и други.

Вероятно всеки конкретен тип оцветяване ще бъде използван при планирането.

Значителна роля в скоростта на програмите на компютъра играе времето, през което микропроцесорът осъществява достъп до данни. А именно, процесорът има достъп (изброяваме устройствата в низходящ ред на скорост и увеличаване на обема) до:

След това разглеждаме програмните оптимизации, свързани с разпространението на данни в тези устройства.

Стандартният подход на Khaitin

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

След това разгледайте метода, предложен в [7] .

Разпределението на регистъра на микропроцесор обикновено се извършва по време на компилиране.

Процедурата за разпространение се въвежда с някакъв вътрешен код (англ. IL, междинен език, вътрешен език), който е предназначен за виртуална машина с неограничен брой регистри - ще ги наричаме виртуални регистри.

Например общия брой регистриназначения в повечето от процесорите на Intel, съответстващи на архитектурата:

(Въпреки това, дори не всички от тях могат да бъдат използвани в нашата процедура за разпределяне на регистър, тъй като те вече могат да бъдат заети - но това вече са фини проблеми с изпълнението.) RAM може да съхранява много голям брой "изпомпани" "регистри" - ние няма да разглеждаме ограничения за неговия размер.

Преди да извършите самата процедура за разпространение, струва си да направите:

Оптимизиране на разговори към виртуални регистри.
Определяне дали дадена променлива в момента е "значима" за всяко място в програмата. Една променлива е „значима“, когато програмата прочете стойността, която текущо се съхранява в нея.

Самият алгоритъм за разпределение на регистъра се състои от следните стъпки:

Изграждане на графика – нека я наречем графа на несъвместимост (англ. interfernce graph, context graph). Върховете на този граф са регистри. Върховете са съседни, ако съответните променливи са "значими" по едно и също време (с други думи: една от променливите е дефинирана, когато другата вече е "значима").
„слепване“ на променливи (включване, разпространение на променлива): ако преди копирането на една променлива в друга, втората все още не е „значима“, а първата не е „значима“ след копирането, можем да пропуснем ненужната операция по преместване и да издърпаме („залепим“) възлите на графиката, съответстващи на тези променливи.
И накрая, най-интересният етап за нас: намиране на n-оцветяването на графиката, където n е броят на горните реални променливи. Решението на този проблем с оцветяването е оптималното разпределение на регистрите. Нека го оцветим така:

За върхове със степен по-малка от n, задайте цвят, ако е възможно.
За неоцветени върхове (или тяхната степен е поне n, или цветоветеприключи) - "изпомпване" на променливите; премахнете тези върхове от графиката. Съответно, степента на съседните върхове намалява - и има смисъл да се предприеме отново стъпка 1. (Не забравяйте, че при изпомпване е възможно също да се въведе нова променлива - тя трябва да се добави към графиката.)

Практиката показва, че алгоритъмът се сближава доста бързо.

Оцветяването на графики се използва в много известни компилатори, например:

GCC версия 4.4 въведе нов разпределител на регистър [www 2] - англ. интегриран регистров разпределител , който използва т.нар. оцветяване "Хейтин-Бригс".
Оцветяването на Haitin-Briggs също се използва (поне в ранните му версии) на компилатора от Intel за архитектурата IA-64. [www 1][9]

Отчитане на паралелизма на ниво инструкция

Процесорите, способни да изпълняват множество инструкции едновременно и независимо, стават все по-широко използвани; те се казва, че поддържат паралелизъм на ниво инструкция, ILP. Нека ги наречем ILP процесори. Класът ILP процесори включва и процесори с много дълга инструкционна дума - VLIW (Very Large Instruction Word), които включват по-специално много модели цифрови сигнални процесори (DSP).Най-известната търговска успешна реализация на концепцията за паралелизъм на ниво индивидуални инструкции е фамилията микропроцесори Itanium на Intel.Заслужава да се отбележи и E2K архитектурата, разработена от българската компания MCST.

Реалното използване на високата производителност на ILP процесорите изисква езикови компилатори на високо ниво, способни да генерират ефективен код; включително оптимизирането на разпределението на регистъра също е важно. Въвеждането на ILP изисква основна ревизия на методаKhaitin относно изграждането на графиката на несъвместимостта; в [5] е предложена преработена версия.

Разпределение на кеша на изпълним код

Предложен е и алгоритъм за разпределяне на често използвани кодови области в кеша [10] – т.нар. Английски оцветяване на кеш линията.

Графиката на несъвместимост тук е следната: върховете са някои „блокове“ от код (можете например да вземете процедури), ръбовете съществуват, когато друг се извика от един „блок“. Както виждате, ние се концентрираме върху т.нар. конфликти от първо поколение ( първо поколение кеш конфликти ) - между "блока" и неговия извикващ / извиквания. Но си струва да се отбележи, че проблемът с оцветяването не се решава от алгоритми с общо предназначение, а от специална евристика, която освен това дава решение, което отговаря на определени допълнителни условия.

Предимството на този метод е, че взема предвид размера на кеша, редовете на кеша, "блоковете" на кода и асоциативността на кеша. Методът се комбинира успешно с други оптимизации и инлайн функции [10] [11] . Трябва да се отбележи, че може да се реализира от оптимизатора - но не от оптимизатора на компилатора, а от оптимизатора на линкера.

Добра работа, класифицираща такива проблеми и систематично представяйки техните решения, е [12].

Терминът "разпределение на честотата" обхваща различни типове задачи, които често имат различни цели и модели. Тези задачи включват:

Планиране на модели на разпределение (лицензиране, регулиране) на радиочестоти, които максимизират използването на целия радиоспектър.
Като се има предвид фактът, че е необходимо да се разпределят обхвати за мобилни, наземни (на английски точка до точка) и сателитни комуникации, радио и телевизионни предавания.
Алгоритми, които динамично разпределят честотите на една конкретна мрежа между потребителите. От особен интерес тук е клетъчната комуникация,в който са направени много изследвания.

Общото между задачите е, че всички те произвеждат оптимално разпределение на ограничен набор от радиочестотни ресурси между потребителите, чийто брой непрекъснато нараства в съвременните условия.

Тук има две основни области на оптимизация:

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

В хода на разглеждане на подходящи модели, в [12] възникват задачи, които не са много по-сложни от Т-оцветяване (англ. T-coloring ) на мултиграф, Т-оцветяване на списък (англ. set T-coloring ).

Като пример за работа върху реална клетъчна мрежа, чиито резултати бяха допълнително приложени от оператора в техните практически дейности - [13] (Провежда се от оператора E-Plus ((английски) en: E-Plus) - 3-тият по големина оператор в Германия (за 2010 г.)).

Нека обобщим задачата по следния начин: обектите са някои изчисления, между които е необходимо да се споделят изчислителни ресурси (процесори, компютри ...), които могат да работят паралелно един с друг. Някои изчисления могат да се извършват паралелно едно на друго, други не. Съответно оцветяването на върховете на графиката за несъвместимост на изчисленията е желаното разпределение.

Даваме следните примери за числени методи, които могат да бъдат паралелизирани по този начин:

Декомпозиция на Холецки за метода на спрегнатите градиенти с предварително определяне

[14] Този метод е един от най-добрите итеративни методи за решаване на системи от линейни алгебрични уравнения (SLAE) с големи, редки, симетрични, положително определени матрици.

Методът на Зайдел, приложен към разредени матрици

Също итеративен метод за решаване на SLAE.

Това от своя страна е добре, например, за изчисляване на електроразпределителните мрежи: такива мрежи могат да бъдат представени чрез графики, чиито върхове са потребители и източници на електроенергия, а краищата са електропроводи; освен това се конструира SLAE, в чиято матрица диагоналните елементи съответстват на възлите на горната графика, а ненулевите извъндиагонални елементи съответстват на ръбовете. [15]

Също така методът може да служи като т.нар. сглажител (англ. iterative smoother) за многомрежови методи за решаване на задачи по метода на крайните елементи. (Английски многомрежови методи на проблеми с крайни елементи). Оптимизиране на метода на Seidel, използван при изглаждане, чрез използване на т.нар. Английски разреденото подреждане за този случай на употреба се обсъжда в [16] .

Методи, използващи адаптивно прецизирана мрежа

[17] Те от своя страна са полезни при решаването на частични диференциални уравнения (PDE). Принципът на усъвършенстване тук е следният: на местата, където се очаква най-голямата локална грешка - където решението се променя най-бързо, плътността на мрежата се избира да бъде по-голяма.

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

(англ. Метод на координирана релаксация)

[18] Използва се успешно при намиране на екстремни собствени стойности на много големи редки симетрични матрици. Понякога толкова големи, че е по-практично да се генерират в движение, отколкото да се съхраняват в паметта. Такива проблеми често възникват в квантовата механика.

Предварително определяне чрез непълно разлагане на LU

За прост случай, когато "компресията" на производната е ограничена до намаляване на броя на колоните, представяме алгоритъма:

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

Мястото на оцветяването на графиката тук е в изчисляването на S . В прости случаи е необходимо да се изчислиправилен връх ( англ. distance-1 ); разстояние-2 оцветяване (което, наред с други неща, намалява до разстояние-1 оцветяване на квадратна графика); в по-сложните се изискват малки допълнителни ограничения:

звездно оцветяване - vertex distance-1 , но с допълнително ограничение: за всеки път от 4 върха се използват поне 3 цвята;
ациклично оцветяване - vertex distance-1 + всеки цикъл използва поне 3 цвята.

В рамките на горния проект бяха извършени изчисления за технически производствени задачи:

процесът на хроматографско разделяне (от областта на химията, химическата технология) с помощта на техниката на английски Simulated Moving Bed;
решение на проблема за оптималния поток на енергия (оптимален поток на енергия) (енергетика).

Това е важно, например, за да се установи източникът на незаконното им разпространение. Или за потвърждаване на права върху данни, например - софтуерни системи на чип (system-on-chip).

Съобщението може да бъде кодирано и в графика. Една такава техника беше предложена от Qu и Potkonjak (поради което понякога се нарича QP алгоритъм) в [21].

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

Можете да го извлечете, като сравните получената графика с оригиналната; Има начини да се уверитедали определено съобщение е кодирано в графиката, без да се използва оригиналното - извличането е описано по-подробно, например в [22] .

Развитието и усъвършенстването на мислите на Qu и Potkonjak, опитите за подобряване на алгоритъма се срещат в произведенията [23] , [24] , [22] .

Имайте предвид, че в [23], [24] има препратки към софтуерния пакет SandMark, в който се изпълняват алгоритми от този вид; достъпен за изтегляне на [www 4] .