Молодежь и наука - третье тысячелетие: Материалы студенческой научно-практической конференции с международным участием

3 П. А. Алексеев Факультет математики физики и информатики, III курс (очная форма обучения) Научный руководитель – И. Н. Балаба ПРИМЕНЕНИЕ РАСКРАСКИ ГРАФОВ В ЗАДАЧЕ О РАСПРЕДЕЛЕНИИ РЕГИСТРОВ ПРОЦЕССОРА Теория графов основана на трудах в знаменитого математика Леонарда Эйлера, когда тот в 1736 году предложил решение задачи о Кенигсбергских мостах. С тех пор данный раздел математики стал стремительно развиваться и уже в XX веке при помощи существенных достижений теории графов стало возможно появление ЭВМ и дальнейший прогресс в области вычислительной техники. Теория графов является мощным инструментом в решении различных задач, в том числе и многих задачах оптимизации. Самые распространенные задачи, использующие достижения теории графов – это:  компиляция программ (различные языки программирования);  моделирование и последующая оптимизация телекоммуникационных сетей;  трассировка печатных плат;  построение маршрутов на географической карте и т. д. Алгоритмы решения данных задач должны решаться с оптимальным коли- чеством ресурсов и давать положительный (дающий хотя бы приближенное ре- шение) результат. Каждая из этих задач является сложной технической пробле- мой, требующей значительного количества вычислительных ресурсов и времени на современных суперкомпьютерах. Поэтому на помощь приходят менее трудо- емкие, по сравнению с алгоритмами полного решения, эвристики, которые дают приближенные решения за меньшее время и экономят вычислительные ресурсы. Раскраска графов используется для следующих задач:  некоторые задачи о расписаниях;  задача о распределении регистров процессора;  задачи решения судоку и другие. Регистр процессора – это сверхбыстрая внутрипроцессорная память малого объема. Количество регистров ограничено и должно оптимально использоваться для наилучшего быстродействия компьютера. В данной памяти располагаются результаты некоторых вычислений. Распределение регистров происходит один раз – на момент компиляции программы и зависит только от полученного двоич- ного кода. Все используемые переменные и константы в процессе вычислений так или иначе попадают в данные регистры. Поэтому нужно контролировать, ка- кие переменные должны находиться в определенный момент времени в регистрах, чтобы программа работала быстро. Формализуем задачу: процессор имеет регистров. Требуется распределить регистры так, чтобы быстродействие полученной программы было максималь- ным, с учетом того, что процесс компиляции должен занимать сравнительно не- большое время.