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

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

1) распределение радиочастот;
2) хранение химических веществ;
3) составление расписаний;
4) распределение регистров в микропроцессорах;
5) политическая картография;
6) окраска соединительных проводов;
7) минимизация расписаний.

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

(англ. Spectrum management, англ. frequency allocation)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для примера, количество регистров общего назначения в большей части процессоров 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][12].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Методы с использованием адаптивно уточняемой сетки

(англ. Adaptive mesh refinement)

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

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

(англ. Method of coordinate relaxation)

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

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

(Preconditioning by ILU, Incomplete LU-factorization)

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

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

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

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

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

Выход: производная  — якобиан или гессиан

1. Исследуем структуру разреженности производной (саму производную вычислять не будем).

2. Составим матрицу уменьшения количества столбцов  — англ. seed matrix; составим так, чтобы стало наименьшим.

3. Вычислим значения уплотнённой ; вычислять будем не по этой формуле, а иным способом. Тут видно, что уменьшенное раньше  — количество столбцов

4. И теперь, восстановим значения по (можно некими прямыми методами, можно — решением уравнений).

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

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

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

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

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

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

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

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

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

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

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

Литература

  1. Gross J. L., Yellen J. Graph theory and its applications. Second edition. Boca Raton—London—New York: Chapman & Hall/CRC, 2006. P. 371–416.
  2. Murphey, Robert A.; Panos M. Pardalos, Mauricio, Mauricio G.C. Resende (1999). «Frequency Assignment Problems». Handbook of Combinatorial Optimization: 295–377, Kluwer Academic Publishers.
  3. Borndörfer, Ralf; Andreas Eisenblätter, Martin Grötschel, Alexander Martin (1997). «Frequency assignment in cellular phone networks». In International Symposium on Mathematical Programming: 24–29.
  4. Rong Qu, Edmund Burke, Barry McCollum, Liam T.G. Merlot, Sau Y. Lee. A Survey of Search Methodologies and Automated Approaches for Examination Timetabling (англ.) : journal. — 2006.
  5. Kendall, Graham; Sigrid Knust, Celso C Ribeiro, Sebastián Urrutia. Scheduling in sports: An annotated bibliography (англ.) // Comput. Oper. Res. : journal. — Oxford, UK, UK: Elsevier Science Ltd., 2009. ISSN 0305-0548. doi:10.1016/j.cor.2009.05.013.
  6. Marx, Daniel (2004). «Graph Coloring Problems and Their Applications in Scheduling». in Proc. John von Neumann PhD Students Conference: 1–2.
  7. Roberts, Fred S. Graph theory and its applications to problems of society (англ.). — Society for Industrial Mathematics, 1987.
  8. Chaitin, Gregory J.; Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, Peter W. Markstein. Register Allocation Via Coloring (англ.) // Comput. Lang. : journal. — 1981. Vol. 6, no. 1. P. 47—57.
  9. Chaitin, Gregory J. (1982). «Register Allocation & Spilling via Graph Coloring». SIGPLAN Symposium on Compiler Construction: 98-105. DOI:10.1145/800230.806984.
  10. Боханко, А. С; А. Ю Дроздов, С. В Новиков, С. Л Шлыков. Распределение регистров методом раскраски графа несовместимости для VLIW-архитектур // High-performance computer systems and microprocessors: Collected papers of the Institute of Microprocessor Computing Systems, Russian Academy of Science : журнал. — 2005. Т. 8.
  11. Muchnick, Steven. Advanced Compiler Design and Implementation (англ.). — San Diego: Morgan Kaufmann, 1997. — ISBN 1558603204.
  12. Bharadwaj, Jay; William Y Chen, Weihaw Chuang, Gerolf Hoflehner, Kishore Menezes, Kalyan Muthukumar, Jim Pierce. The Intel IA-64 Compiler Code Generator (англ.) // IEEE Micro : journal. — Los Alamitos, CA, USA: IEEE Computer Society Press, 2000. Vol. 20, no. 5. P. 44—53. ISSN 0272-1732. doi:10.1109/40.877949.
  13. Hashemi, Amir H; David R Kaeli, Brad Calder (1997). «Efficient procedure mapping using cache line coloring». PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation: 171–182, New York, NY, USA: ACM. DOI:10.1145/258915.258931.
  14. Hakan Aydin, David R. Kaeli. Using cache line coloring to perform aggressive procedure inlining (англ.) // ACM SIGARCH Computer Architecture News : journal. — New York, NY, USA: ACM, 2000. Vol. 28, no. 1. P. 62—71. ISSN 0163-5964. doi:10.1145/346023.346046.
  15. Jones, Mark T.; Paul E. Plassmann. Scalable Iterative Solution of Sparse Linear Systems (англ.) // Parallel Computing : journal. — 1994. Vol. 20, no. 5. P. 753—773.
  16. Koester, D. P; S. Ranka, G. C Fox (1994). «A parallel Gauss-Seidel algorithm for sparse power system matrices».: 184–193, Washington, D.C., United States: IEEE Computer Society Press. Дата обращения: 30 January 2010.
  17. Strout, Michelle Mills; Larry Carter, Jeanne Ferrante, Jonathan Freeman, Barbara Kreaseck (2002). «Combining Performance Aspects of Irregular Gauss-Seidel Via Sparse Tiling». LCPC: 90-110. DOI:10.1007/11596110_7.
  18. Jones, Mark T.; Paul E. Plassmann. Parallel Algorithms for Adaptive Mesh Refinement (англ.) // SIAM Journal on Scientific Computing : journal. — SIAM, 1997. Vol. 18, no. 3. P. 686—708. doi:10.1137/S106482759528065X. (недоступная ссылка)
  19. Manne, Fredrik (1998). «A parallel algorithm for computing the extremal eigenvalues of very large sparse matrices (Extended Abstract)». proceedings of Para98, Workshop on Applied Parallel Computing in Large scale scientific and Industrial Problems 1541: 332–336, Lecture Notes in Computer Science, Springer. Дата обращения: 30 January 2010.
  20. Hysom, David; Alex Pothen. A Scalable Parallel Algorithm for Incomplete Factor Preconditioning (англ.) // SIAM J. Sci. Comput : journal. — 2000. Vol. 22. P. 2194—2215. doi:10.1.1.38.7293.
  21. Gebremedhin, A. (10 June 2008). «Graph Coloring in Parallel Processing and Scientic Computing». CSCAPES Workshop 2008. Дата обращения: 23 January 2010. Архивная копия от 9 июня 2010 на Wayback Machine
  22. Qu, Gang; Miodrag Potkonjak (1998). «Analysis of watermarking techniques for graph coloring problem». ICCAD: 190-193. DOI:10.1145/288548.288607.
  23. Zhu, William; Clark Thomborson (2006). «Recognition in software watermarking». MCPS '06: Proceedings of the 4th ACM international workshop on Contents protection and security: 29–36, New York, NY, USA: ACM. DOI:10.1145/1178766.1178776.
  24. Myles, Ginger; Christian S. Collberg (2003). «Software Watermarking Through Register Allocation: Implementation, Analysis, and Attacks». ICISC: 274-293. DOI:10.1007/b96249.
  25. Collberg, Christian; Clark Thomborson, Gregg M. Townsend. Dynamic Graph-Based Software Watermarking (англ.) : journal. — 2004.
  26. Самуйлов, К. Е. Методы анализа и расчета сетей ОКС 6. — Москва, Издательство Российского университета дружбы народов, 2002.
  27. Основные положения системы сигнализации ОКС № 7 для сети связи Российской Федерации : журнал. — ЦНТИ "Информсвязь", 2004. — 11 октября.
  28. Hansen, Pierre; Brigitte Jaumard. Cluster analysis and mathematical programming (англ.) // Math. Program. : journal. — 1997. Vol. 79. P. 191—215.

Примечания

  • [www 5] — хороший источник ссылок на информацию по многим аспектам применения
  • [www 6], хоть и на 2010 год уже очень давно не обновляемая.
  1. Dulong, Carole; Rakesh Krishnaiyer, Dattatraya Kulkarni. An Overview of the Intel IA-64 Compiler (англ.) (1999). doi:10.1.1.14.1435. Дата обращения: 21 марта 2011. Архивировано 20 апреля 2012 года.
  2. GCC 4.4 Release Series: Changes, New Features, and Fixes (англ.) (2010). Дата обращения: 23 января 2010. Архивировано 20 апреля 2012 года.
  3. Graph Coloring for Computing Derivatives - Home Page (англ.). CSCAPES Institute. Дата обращения: 5 января 2020.
  4. Collberg, Christian SandMark: A Tool for the Study of Software Protection Algorithms - homepage (англ.) (недоступная ссылка). Department of Computer Science, The University of Arizona. Дата обращения: 30 января 2010. Архивировано 20 апреля 2012 года.
  5. Culberson, Joseph Graph Coloring Bibliography (англ.). Canada: Department of Computing Science, University of Alberta (21 сентября 2004). Дата обращения: 24 января 2010. Архивировано 20 апреля 2012 года.
  6. Trick, Michael annotated bibliography for cliques and coloring (англ.) (1994). Дата обращения: 24 января 2010. Архивировано 20 апреля 2012 года.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.