Практическое применение раскраски графов

Практическое применение раскраски графов

Сразу укажем библиографию [Culberson04] как хороший источник ссылок на информацию по многим аспектам раскраски графов, в т.ч. её практическому применению. Есть ещё одна большая, хоть и на 2010 год уже очень давно не обновляемая – [Trick94] .

Постановку задачи различиных раскрасок здесь обсуждать почти не будем – посчитаем её известной.

Практические применения

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

Многочисленные применения раскраска находит в этой области:

• расписания для образовательных учереждений (обзор - [Qu06]);
• расписания в спорте (обзор – [Kendall09]);
• планирование встреч, собраний, интервью;
• расписания транспорта, в т.ч. – авиатранспорта (например, [Marx04]);
• расписания для коммунальных служб (например, [Roberts87]);
• и пр.

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

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

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

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

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

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

Как утверждается в [Боханко05], первыми важными работами, заложившими основы применения метода раскраски графов в распределении регистров, были [Chaitin81], [Chaitin82] - последующие же не добавили ничего революционного, внимание в них было сконцентрировано на ускорении работы алгоритма, уменьшении памяти, новых эвристиках по определению стоимости откачки регистров (введём определение далее) и выбору регистров для откачки; обзор этих методов можно найти в [Muchnick97].

Далее, рассмотрим способ, предложенный в [Chaitin82].

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

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

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

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

• IA-32 – 8 шт.,
• Intel 64 – 16 шт. ( [Intel09] )

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

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

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

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

• Построение графа – назовём его графом несовместимостей (interfernce graph, conflict graph).

Вершины данного графа – регистры. Вершины смежны, если соответствующие переменные «значимы» одновременно (по-другому: одна из переменных определена тогда, когда другая уже «значима»).

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

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

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

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

• [2] говорит о том, что в GCC версии 4.4 появился новый распределитель регистров - integrated register allocator, который применяет раскраску «Чейтина-Бриггса».
• [Dulong99], [Bharadwaj00] говорят о том, что раскраска «Чейтина-Бриггса» применяется и в (по крайней мере, его ранних версиях) компиляторе от Intel для архитектуры IA-64.

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

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

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

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

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

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

Достоинство этого метода – в том, что учитываются и размеры кэша, строки кэша, «блоков» кода, и ассоциотивность кэша. Метод удачно комбинируется с другими оптимизациями и inline-функциями [Hashemi97], [Aydin00]. Надо отметить, что он может реализовыаться реализовывается оптимизатором – но не оптимизатором компилятора, а оптимизатором компоновщика.

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

Хорошей работой, классифицирующей такие задачи и систематически излагающей их решения, является [Murphey99].

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

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

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

Два основных направления оптимизации тут:

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

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

Как пример работы над реальной сотовой сетью, результаты коей были далее применены оператором в своей практической деятельности – [Borndoerfer97], а оператор – E-Plus – 3-й по величине в Германии (на 2010).

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

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

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

• Факторизация Холецкого для метода предопределённых сопряжённых градиентов [Jones94].

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

• Другой итерационный метод решения СЛАУ – метод Гаусса-Зейделя в применении к разреженным матрицам.

Этот метод, в свою очередь, хорош, например, для расчёта энергораспределительных электросетей: такие сети могут быть представлены графами, вершины которых – это потребители и поставщики электроэнергии, а рёбра – линии электропередач; далее, строится СЛАУ, в матрице которой диагональным элементам соответствуют узлы вышеупомянутого графа, а ненулевым недиагональным – рёбра. [Koester94] Также, метод может служить сглаживателем для многосеточных методов конечных элементов. (multigrid methods of finite Element Problems). Оптимизация Гаусса-Зейделя с помощью sparse tiling для такого случая его использования рассмотрена в [Strout02] .

• Методы с использованием адаптивно уточняемой сетки (adaptive mesh refinement). [Jones97]

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

• Метод координатной релаксации. [Manne98]

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

• Предопределение (preconditioning) неполным LU- (ILU-, Incomplete LU-) разложением для решения СЛАУ с использованием подпространств Крылова. [Hysom00]

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

Вычисление матриц производных (якобианов и гессианов) в том случае, когда они разреженные, серьёзно можно ускорить с помощью раскраски графов. Существует проект “Graph Coloring for Computer Derivatives”, сайт - [3]. На сайте представлены публикации по теме, а также – программный пакет, в который оформили участники проекта свои достижения. Для введения в предмет можно посмотреть, одну из презентаций, относящихся к проекту – [Gebremedhin08].

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

procedure SparseCompute Вход: функция от вектора - F Выход: производная F – якобиан или гессиан 1. Исследуем структуру разреженности производной A ∊ ℝm x n. 2. Получим матрицу S ∊ {0; 1}n x q уменьшения количества столбцов A (seed matrix). 3. Вычислим значения уплотнённой B = A S ∊ ℝm x q . 4. Восстановим значения A по B (можно некими прямыми методами, можно - решением уравнений).

Место раскраски графа здесь – в вычислении S. В простых случаях надо вычислять обычную вершинную (distance-1), distance-2 раскраски (которая, в т.ч. сводится к distance-1 раскраске квадрата графа); в более сложных, требуются небольшие дополнительные ограничения:

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

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

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

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

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

Это важно, например, для установления источника их распространения нелегальным образом. Или же для подтверждения прав на данные, например – программное обеспечение систем на кристалле (system-on-chip).

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

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

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

Развитие и уточнение мыслей Qu и Potkonjak, попытки улучшения алгоритма происходит в работах [Myles03], [Collberg04], [Zhu06].

Отметим, что в [Myles03], [Collberg04] есть ссылки на программный пакет SandMark, в котором исполнены алгоритмы такого рода; доступен для скачивания на [4].

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

• Классическая задача о раскраске карт: вершины – страны; рёбра – общие границы. Такой граф, соответствующий карте, планарен, - а значит, по теореме о 4-х красках, всегда χ ≤ 4.
• Расчёт сетей ОКС-7 (некое обобщение телефонных сетей); а именно, раскраска мультиграфа с некоторыми ограничениями нужна при маршрутизации пакетов с учётом равномерной нагрузки [Самуйлов02]. Вообще, РУДН и в т.ч. вышеупомянутый К.Е. Самуйлов, работавший там, принимал активное участие в расчёте междугородной сети ОКС-7 России, что отражено даже в отраслевом стандарте [5] – что означает надёжность источника..
• Кластерный анализ (разделение объектов на т.н. кластеры; в рамках кластера объекты имеют похожие свойства и/или кластеры имеют отчётливое разделение) [Hansen97].
• Решение судоку: 9 цифр судоку – 9 цветов. Вершины графа несовместимости – клетки таблицы. Рёбра между и проводим тогда и только тогда, когда:
  • , или,
  • y=y, или,
  • и y/3.

• Конструирование устройств, где провода, соединённые в одном узле дожны для удобства различения иметь разные цвета.

Источники

• [Aydin00]

Aydin, H. & Kaeli, D. (2000), "Using cache line coloring to perform aggressive procedure inlining", SIGARCH Comput. Archit. News. New York, NY, USA Vol. 28(#1), pp. 62-71. ACM.

DOI: http://doi.acm.org/10.1145/346023.346046

• [Bharadwaj00]

Bharadwaj, J., Chen, W.Y., Chuang, W., Hoflehner, G., Menezes, K., Muthukumar, K. & Pierce, J. (2000), "The Intel IA-64 Compiler Code Generator", IEEE Micro. Los Alamitos, CA, USA Vol. 20(#5), pp. 44-53. IEEE Computer Society Press.

doi:10.1109/40.877949

• [Borndoerfer97]

Borndörfer, R., Eisenblätter, A., Grötschel, M. & Martin, A. (1997), "Frequency assignment in cellular phone networks", In In International Symposium on Mathematical Programming., pp. 24-29.

• [Chaitin82]

Chaitin, G.J. (1982), "Register Allocation & Spilling via Graph Coloring", In SIGPLAN Symposium on Compiler Construction., pp. 98-105.

doi:10.1145/800230.806984

• [Chaitin81]

Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E. & Markstein, P.W. (1981), "Register Allocation Via Coloring", Comput. Lang.. Vol. 6(#1), pp. 47-57.

• [4]

Collberg, C., "SandMark: A Tool for the Study of Software Protection Algorithms - homepage"

URL: http://www.cs.arizona.edu/sandmark

• [Collberg04]

Collberg, C., Thomborson, C. & Townsend, G.M. (2004), "Dynamic Graph-Based Software Watermarking"

URL: ftp://ftp.cs.arizona.edu/reports/2004/TR04-08.pdf

• [Culberson04]

URL: http://webdocs.cs.ualberta.ca/~joe/Coloring/

• [Dulong99]

Dulong, C., Krishnaiyer, R. & Kulkarni, D. (1999), "An Overview of the Intel IA-64 Compiler"

doi:10.1.1.14.1435 [download.intel.com/technology/itj/q41999/pdf/compiler.pdf URL: download.intel.com/technology/itj/q41999/pdf/compiler.pdf]

• [Gebremedhin08]

Gebremedhin, A. (2008), "Graph Coloring in Parallel Processing and Scientic Computing", In CSCAPES Workshop 2008. Santa Fe, NM, jun 10-13, 2008.

URL: http://www.cs.sandia.gov/CSRI/Workshops/2008/CSCAPES/presentations/gebremedhin_coloring-cscapes08.pdf

• [Hansen97]

Hansen, P. & Jaumard, B. (1997), "Cluster analysis and mathematical programming", Math. Program.. Vol. 79, pp. 191-215.

• [Hashemi97]

Hashemi, A.H., Kaeli, D.R. & Calder, B. (1997), "Efficient procedure mapping using cache line coloring", In PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation. New York, NY, USA, pp. 171-182. ACM.

DOI: http://doi.acm.org/10.1145/258915.258931

• [Hysom00]

Hysom, D. & Pothen, A. (2000), "A Scalable Parallel Algorithm for Incomplete Factor Preconditioning", SIAM J. Sci. Comput. Vol. 22, pp. 2194-2215.

doi:10.1.1.38.7293 URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.7293&rep=rep1&type=url&i=0

• [Jones97]

Jones, M.T. & Plassmann, P.E. (1997), "Parallel Algorithms for Adaptive Mesh Refinement", SIAM Journal on Scientific Computing. Vol. 18(#3), pp. 686-708. SIAM.

doi:10.1137/S106482759528065X URL: http://link.aip.org/link/?SCE/18/686/1

• [Jones94]

Jones, M.T. & Plassmann, P.E. (1994), "Scalable Iterative Solution of Sparse Linear Systems", Parallel Computing. Vol. 20(#5), pp. 753-773.

• [Kendall09]

Kendall, G., Knust, S., Ribeiro, C.C. & Urrutia, S. (2009), "Scheduling in sports: An annotated bibliography", Comput. Oper. Res.. Oxford, UK, UK Elsevier Science Ltd..

doi:10.1016/j.cor.2009.05.013 URL: http://www.cs.nott.ac.uk/~gxk/papers/corsportsbib.pdf

• [Koester94]

Koester, D.P., Ranka, S. & Fox, G.C. (1994), "A parallel Gauss-Seidel algorithm for sparse power system matrices", In Supercomputing '94: Proceedings of the 1994 conference on Supercomputing. Los Alamitos, CA, USA, pp. 184-193. IEEE Computer Society Press.

URL: http://www.new-npac.org/users/fox/pdftotal/sccs-0630.pdf

• [Manne98]

Manne, F. (1998), "A parallel algorithm for computing the extremal eigenvalues of very large sparse matrices (Extended Abstract)", In proceedings of Para98, Workshop on Applied Parallel Computing in Large scale scientific and Industrial Problems. Vol. 1541, pp. 332-336. Lecture Notes in Computer Science, Springer.

URL: http://www.ii.uib.no/~fredrikm/fredrik/papers/relax.ps

• [Marx04]

Marx, D. (2004), "Graph Coloring Problems and Their Applications in Scheduling", In in Proc. John von Neumann PhD Students Conference., pp. 1-2.

• [Matz]

Matz, M., "Design and Implementation of a Graph Coloring Register Allocator for GCC"

• [Muchnick97]

Muchnick, S. (1997), "Advanced Compiler Design and Implementation" San Diego Morgan Kaufmann.

• [Murphey99]

Murphey, R.A., Pardalos, P.M., Mauricio & Resende, M.G. (1999), "Frequency Assignment Problems", In Handbook of Combinatorial Optimization., pp. 295-377. Kluwer Academic Publishers.

• [Myles03]

Myles, G. & Collberg, C.S. (2003), "Software Watermarking Through Register Allocation: Implementation, Analysis, and Attacks", In ICISC., pp. 274-293.

• [Qu98]

Qu, G. & Potkonjak, M. (1998), "Analysis of watermarking techniques for graph coloring problem", In ICCAD., pp. 190-193.

doi:10.1145/288548.288607

• [Qu06]

Qu, R., Burke, E.K., Mccollum, B., Merlot, L.T.G. & Lee, S.Y. (2006), "A Survey of Search Methodologies and Automated Approaches for Examination Timetabling"

• [Roberts87]

Roberts, F.S. (1987), "Graph theory and its applications to problems of society" Society for Industrial Mathematics.

• [Singh99]

Singh, A. & Marek-Sadowska, M. (1999), "Circuit clustering using graph coloring", In ISPD '99: Proceedings of the 1999 international symposium on Physical design. New York, NY, USA, pp. 164-169. ACM.

DOI: http://doi.acm.org/10.1145/299996.300055 URL: http://www.cecs.uci.edu/~papers/compendium94-03/papers/1999/ispd99/pdffiles/2_4_5.pdf

• [Strout02]

Strout, M.M., Carter, L., Ferrante, J., Freeman, J. & Kreaseck, B. (2002), "Combining Performance Aspects of Irregular Gauss-Seidel Via Sparse Tiling", In LCPC., pp. 90-110.

doi:10.1007/11596110_7

• [Trick94]

Trick, M. (1994), "annotated bibliography for cliques and coloring"

URL: http://mat.gsia.cmu.edu/COLOR/color.html

• [Zhu06]

Zhu, W. & Thomborson, C. (2006), "Recognition in software watermarking", In MCPS '06: Proceedings of the 4th ACM international workshop on Contents protection and security. New York, NY, USA, pp. 29-36. ACM.

DOI: http://doi.acm.org/10.1145/1178766.1178776

• [Боханко05]

Боханко, А., Дроздов, А., Новиков, С. & Шлыков, С. (2005), “Распределение регистров методом раскраски графа несовместимости для VLIW-архитектур”, High-performance computer systems and microprocessors: Collected papers of the Institute of Microprocessor Computing Systems, Russian Academy of Science. Vol. 8

• [Самуйлов02]

Самуйлов, К. (2002), "Методы анализа и расчета сетей ОКС 7" Москва, Издательство Российского университета дружбы народов.

• [3]

"Graph Coloring for Computing Derivatives - Home Page"

URL: http://www.cscapes.org/coloringpage/index.htm

• [2]

"GCC 4.4 Release Series: Changes, New Features, and Fixes"

URL: http://gcc.gnu.org/gcc-4.4/changes.html

• [5]

"Основные положения системы сигнализации ОКС № 7 для сети связи Российской Федерации"ЛОНИИС, ЦНИИС

URL: http://www.complexdoc.ru/ntdtext/547175/