Существуют многочисленные практические приложения раскраски графов . Когда приложение моделируется как проблема с раскраской вершин графа, то вершины в каждом цветовом классе обычно представляют отдельные субъекты, которые не конкурируют или не конфликтуют друг с другом. Семь основных классов приложений, решаемых с помощью раскраски вершин (1—5) и рёбер (6—7) графов, следующие :

1) распределение радиочастот;

2) хранение химических веществ;

3) составление расписаний;

4) распределение регистров в микропроцессорах;

5) политическая картография;

6) окраска соединительных проводов;

7) минимизация расписаний.

Распределение частот

( англ. , англ. )

Термин «распределение частот» объединяет разные типы задач, которые зачастую имеют разные цели и модели .

• Планировку моделей распределения ( лицензирования , регулирования) радиочастот , максимизирующих использование всего .
• Учёт того, что надо отвести диапазоны и для мобильной , наземной ( англ. point-to-point ) и спутниковой связи , радио - и телетрансляций .
• Алгоритмы, динамически распределяющие частоты одной конкретной сети между пользователями. Особо интересна тут сотовая связь , в области которой проделан очень большой объём исследований.

Общее между задачами — это то, что они все производят оптимальное распределение ограниченного набора ресурсов между пользователями, количество коих в современных условиях всё время растёт. Два основных направления оптимизации :

• максимизация пропускной способности каналов при сохранении определённого минимального уровня интерференции (помех) ;
• минимизация интерференции для достижения фиксированной пропускной способности .

В ходе рассмотрения подходящих моделей, возникают задачи не намного сложнее T-раскраски ( англ. ) мультиграфа , ( англ. set T-coloring ) .

Результаты работы над реальной сотовой сетью были применены оператором в своей практической деятельности (проведено оператором E-Plus ( (англ.) ) — 3-м по величине в Германии (на 2010)) .

Составление расписаний

Вероятно, любому конкретному виду раскраски найдется применение в составлении расписаний:

• расписания для образовательных учреждений ;
• расписания в спорте ;
• планирование встреч, собраний, интервью;
• расписания транспорта, в том числе — авиатранспорта ;
• расписания для коммунальных служб ;
• прочие.

Распределение регистров в микропроцессорах

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

• регистрам процессора ,
• кэшу ,
• оперативной памяти ,
• прочим устройствам.

Далее рассмотрим оптимизации программ, связанные с распределением данных в этих устройствах.

Стандартный подход Хайтина

Считается, что первыми важными работами, заложившими основы применения метода раскраски графов в распределении регистров , были , , последующие же не добавили ничего революционного, внимание в них было сконцентрировано на ускорении работы алгоритма, уменьшении памяти, новых эвристиках по определению стоимости (введём определение ) и выбору регистров для откачки . Обзор этих методов можно найти в .

Приведём способ, предложенный в .

Распределение регистров ( англ. register allocation ) микропроцессора обычно производится на этапе компиляции.

На вход процедуры распределения подаётся некий внутренний код ( англ. IL , intermediate language , internal language ), который рассчитан на виртуальную машину с неограниченным числом регистров — будем называть их виртуальными регистрами.

На выходе процедуры обращения к виртуальнам регистрам переводятся либо в обращения к реальным регистрам процессора, либо, если первого нельзя сделать по причине того, что все регистры уже заняты, — в обращения к оперативной памяти путём введения дополнительного кода. Этот код называют кодом откачки ( англ. code ), а сам процесс — откачкой ( ). Отметим, что при обращении к оперативной памяти так же иногда используются реальные регистры (для тех команд процессора, которые в качестве аргумента не могут принимать адрес в памяти).

Для примера, количество регистров общего назначения в большей части процессоров Intel , соответствующих архитектуре:

• IA-32 — 8 шт.;
• Intel 64 — 16 шт.

(Однако, даже не все из них могут быть использованы в нашей процедуре распределения регистров, поскольку уже могут быть заняты — но это уже тонкие вопросы реализации.) Оперативная память же может хранить очень большое число — ограничения на её объём рассматривать не будем.

Перед выполнением самой процедуры распределения, стоит сделать:

• оптимизацию обращений к виртуальным регистрам;
• определение того, является ли переменная в данный момент «значимой», для каждого места программы. «Значима» переменная тогда, когда далее в программе происходит чтение записанного в ней в данный момент значения.

Сам алгоритм распределения регистров состоит из следующих шагов.

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

• для вершин со степенью меньше n — назначим , если можно;
• для нераскрашенных вершин (либо их степень не меньше n, либо — закончились) — ; удаляем эти вершины из графа. Соответствнно, у соседних им вершин степень уменьшается — и имеет смысл снова сделать шаг 1. (Не стоит забывать, что при также возможно введение новой переменной — её надо добавить в граф.)

Практика показывает, что алгоритм сходится довольно быстро.

Раскраска графа применяется во многих известных компиляторах, например:

• в GCC версии 4.4 появился новый распределитель регистров — англ. integrated register allocator , который применяет т. н. раскраску « Хайтина -Бриггса»;
• раскраска « Хайтина -Бриггса» применяется и в (по крайней мере, его ранних версиях) компиляторе от Intel для архитектуры IA-64 .

Учёт параллелизма на уровне команд

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

Для реального использования высокой производительности ILP-процессоров необходимы компиляторы языков высокого уровня, способные генерировать эффективный код; в том числе, важна и оптимизация . Введение ILP требует серьёзной переработки в части построения графа несовместимости. Имеется доработанный вариант .

Распределение исполняемого кода по кэшу

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

здесь такой: вершины — некие «блоки» кода (можно, например, брать процедуры ), рёбра существуют тогда, когда из одного «блока» ввызывается другой. Как видно, мы концентрируемся на т. н. конфликтах первого поколения ( first-generation cache conflicts ) — между «блоком» и её вызывающим или вызываемым. Но задача раскраски решается не алгоритмами общего назначения, а специальным эвристическим, который, к тому же, даёт решение, которое удовлетворяет неким дополнительным условиям.

Достоинство этого метода — в том, что учитываются и размеры кэша, строки кэша, «блоков» кода, и . Метод удачно комбинируется с другими оптимизациями и . Он может реализовываться оптимизатором — но не оптимизатором компилятора, а оптимизатором компоновщика .

Распараллеливание численных методов

Обобщённо представим задачу так: объекты — некие вычисления, между которыми надо разделить вычислительные ресурсы (процессоры, компьютеры…), могущие работать параллельно друг другу. Какие-то вычисления могут выполняться в параллели друг другу, какие-то — нет. Соответственно, вычислений и представляет собой искомое распределение.

Приведём следующие примеры численных методов , которые таким образом можно распараллелить:

Разложение Холецкого для метода сопряжённых градиентов с предопределением

Этот метод является одним из лучших для решения систем линейных алгебраических уравнений (СЛАУ) с большими, разреженными , симметричными , положительно определёнными матрицами .

Метод Зейделя в применении к разреженным матрицам

Тоже решения СЛАУ .

Этот, в свою очередь, хорош, например, для расчёта энергораспределительных электросетей : такие сети могут быть представлены графами, вершины которых — это потребители и источники электроэнергии, а рёбра — линии электропередач ; далее, строится СЛАУ , в матрице которой диагональным элементам соответствуют узлы вышеупомянутого графа, а ненулевым недиагональным — рёбра .

Также метод может служить т. н. сглаживателем ( англ. iterative smoother ) для многосеточных методов решения задач методом конечных элементов . ( англ. of ). Имеется оптимизация метода Зейделя , используемого в сглаживании, с помощью т. н. англ. sparse tiling для такого случая его использования .

Методы с использованием

( англ. )

Они, в свою очередь, полезны в решении дифференциальных уравнений в частных производных (ДУЧП) . Принцип уточнения здесь такой: в местах, где ожидается наибольшая локальная погрешность — где решение меняется быстрее всего, плотность сетки выбирается большей .

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

( англ. Method of coordinate relaxation )

Удачно применяется в нахождении экстремальных собственных значений очень больших разреженных симметричных матриц. Иногда таких больших, что их практичнее генерировать на лету, чем хранить в памяти. Такие задачи часто встают в квантовой механике .

Предопределение неполным LU-разложением

( by )

Для решения СЛАУ с использованием подпространств Крылова .

Вычисление производных

Вычисление матриц производных ( якобианов и гессианов ) в том случае, когда они разреженные , можно серьёзно ускорить с помощью раскраски графов. Существует проект «Graph Coloring for Computer Derivatives». На его сайте представлены публикации по теме, а также — программный пакет, в который оформили участники проекта свои достижения . Для введения в предмет имеются презентации, относящихся к проекту .

Для простого случая, когда «уплотнение» производной ограничивается уменьшением количества столбцов, приведём алгоритм.

Вход : функция от вектора — ${\displaystyle F}$ Выход : производная ${\displaystyle F}$ — якобиан или гессиан 1. Исследуем структуру разреженности производной ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ (саму производную вычислять не будем). 2. Составим матрицу ${\displaystyle S\in \lbrace 0;1\rbrace ^{n\times q}}$ уменьшения количества столбцов ${\displaystyle A}$ — англ. seed matrix ; составим так, чтобы ${\displaystyle q}$ стало наименьшим. 3. Вычислим значения уплотнённой ${\displaystyle B=AS\in \mathbb {R} ^{m\times q}}$ ; вычислять будем не по этой формуле, а иным способом. Тут видно, что уменьшенное раньше ${\displaystyle q}$ — количество столбцов ${\displaystyle B}$ 4. И теперь, восстановим значения ${\displaystyle A}$ по ${\displaystyle B}$ (можно некими прямыми методами, можно — решением уравнений).

Место раскраски графа здесь — в вычислении ${\displaystyle S}$ . В простых случаях надо вычислять обычную вершинную ( англ. distance-1 ); distance-2 раскраску (которая, в том числе сводится к distance-1 раскраске square graph ). В более сложных, требуются небольшие дополнительные ограничения:

• звёздная раскраска (star coloring) — вершинная distance-1 , но с дополнительным ограничением: для любого пути из 4 вершин используется не менее 3 цветов;
• ациклическая раскраска (acyclic coloring) — вершинная distance-1 + каждый цикл использует не менее 3 цветов.

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

• процесс хромотографического разделения (из области химии, химической технологии) посредством техники ;
• решение задачи оптимального энергетического потока ( ) ( электроэнергетика ).

Цифровые водяные знаки

Технология цифровых водяных знаков ( англ. ) позволяет вместе с данными (будь то медиафайлы , исполняемые файлы и прочие) передать некое скрытое сообщение (« водяной знак », ). Такое скрытое сообщение может быть применено в защите авторских прав для идентификации владельца данных.

Это важно, например, для установления источника их распространения нелегальным образом. Или же для подтверждения прав на данные, например — программное обеспечение систем на кристалле ( ). Сообщение можно закодировать в том числе и в графе. Одну из таких техник предложили Qu и Potkonjak (поэтому её иногда называют QP-алгоритмом) .

Состоит она вот в чём: допустим, у нас есть граф G, раскраска которого используется в программе — причём, используется так, что допустимо поменять содержимое графа с небольшим увеличением его хроматического числа . Что важно, одним из таких примеров является граф несовместимости — а значит, мы сможем закодировать послание в программном продукте с помощью распределения регистров.

Извлечь его можно путём сравнения полученного графа с исходным; существуют и способы удостовериться в том, было ли некое сообщение закодировано в графе без использования исходного .

Имеется развитие, уточнение Qu и Potkonjak , попытки улучшения алгоритма , , .

Отметим, что имеется программный пакет SandMark, в котором исполнены алгоритмы такого рода , . Он доступен для скачивания .

Прочие применения

• Классическая задача о раскраске карт: вершины — страны; рёбра — общие границы. Такой граф, соответствующий карте, планарен, — а значит, по теореме о 4 красках , всегда χ ≤ 4.
• Расчёт сетей ОКС-7 (некое обобщение телефонных сетей); а именно, раскраска мультиграфа с некоторыми ограничениями нужна при маршрутизации пакетов с учётом равномерной нагрузки . РУДН , в том числе его сотрудник Самуйлов, принимал активное участие в расчёте междугородной сети ОКС-7 России .
• Кластерный анализ (разделение объектов на т. н. кластеры ; в рамках кластера объекты имеют похожие свойства и/или кластеры имеют отчётливые различия) .
• Решение судоку : 9 цифр судоку — 9 цветов. Вершины — клетки таблицы. Рёбра между ${\displaystyle (x,y)}$ и ${\displaystyle (x',y')}$ проводим тогда и только тогда, когда:
  • ${\displaystyle x=x'}$ , или,
  • ${\displaystyle y=y'}$ , или,
  • ${\displaystyle \lceil x/3\rceil =\lceil x'/3\rceil }$ и ${\displaystyle \lceil y/3\rceil =\lceil y'/3\rceil }$ .
• Конструирование устройств, где провода, соединённые в одном узле, должны для удобства различения иметь разные цвета.

Литература

Примечания

• — хороший источник ссылок на информацию по многим аспектам применения
• , хоть и на 2010 год уже очень давно не обновляемая.

Ссылки