Сила прикладной математики проявляется в достижениях инженерных и других наук. Однако часто математические задачи, используемые в этих приложениях, включают сложные вычисления, которые выходят за рамки возможностей современных компьютеров с точки зрения времени и ресурсов. Так обстоит дело с задачами комбинаторной оптимизации.
Комбинаторная оптимизация заключается в нахождении оптимального объекта или решения в конечном множестве возможных. Такие проблемы повсеместно проявляются в реальном мире в разных областях. Например, задачи комбинаторной оптимизации проявляются в финансах как оптимизация портфеля, в логистике как хорошо известная «задача коммивояжера», в машинном обучении и в открытии новых лекарств. Однако современные компьютеры не могут справиться с этими проблемами при большом количестве переменных.
К счастью, группа исследователей из Токийского технологического института в сотрудничестве с лабораторией Hitachi Hokkaido University и Токийским университетом разработала новую архитектуру процессора, специально предназначенную для решения задач комбинаторной оптимизации, выраженных в форме модели Изинга. Изначально модель Изинга использовалась для описания магнитных состояний атомов (спинов) в магнитных материалах. Однако эту модель можно использовать в качестве абстракции для решения задач комбинаторной оптимизации, поскольку эволюция спинов, которая стремится достичь так называемого состояния с наименьшей энергией, отражает то, как алгоритм оптимизации ищет лучшее решение.
Фактически, состояние спинов в состоянии с наименьшей энергией может быть напрямую отображено на решение задачи комбинаторной оптимизации.
Предлагаемая архитектура процессора, получившая название STATICA, принципиально отличается от существующих процессоров, которые рассчитывают модели Изинга, называемые отжигателями. Одним из ограничений большинства описанных отжигателей является то, что они рассматривают только спиновые взаимодействия между соседними частицами.
Это позволяет ускорить расчет, но ограничивает их возможные применения. Напротив, STATICA полностью связана, и все спин-спиновые взаимодействия учитываются.
Хотя скорость обработки STATICA ниже, чем у аналогичных отжигателей, схема расчета лучше: используется параллельное обновление.
В большинстве отжигателей эволюция спинов (обновление) рассчитывается итеративно. Этот процесс по своей сути является последовательным, что означает, что переключения спинов вычисляются одно за другим, потому что переключение одного спина влияет на все остальные в той же итерации.
В STATICA процесс обновления выполняется параллельно с использованием так называемых стохастических клеточных автоматов. Вместо вычисления спиновых состояний с использованием самих спинов, STATICA создает копии спинов, и используются взаимодействия спин-реплика, что позволяет проводить параллельные вычисления.
Это экономит огромное количество времени из-за меньшего количества необходимых шагов. «Мы доказали, что традиционные подходы и STATICA дают одно и то же решение при определенных условиях, но STATICA делает это за N раз меньше шагов, где N – количество спинов в модели», – отмечает проф. Масато Мотомура, который руководил этим проектом. Кроме того, исследовательская группа реализовала подход, называемый обновлением спина на основе дельты.
Поскольку при вычислении следующей итерации важны только вращения, которые изменились в предыдущей итерации, используется схема селектора, чтобы задействовать только вращения, которые переворачивались на каждой итерации.
STATICA предлагает более низкое энергопотребление, более высокую скорость обработки и лучшую точность, чем другие отжигатели. «STATICA стремится произвести революцию в процессорах отжига, решая задачи оптимизации на основе математической модели стохастических клеточных автоматов.
Наши первоначальные оценки дали сильные результаты ", – заключает проф. Мотомура. Дальнейшие усовершенствования сделают STATICA привлекательным выбором для комбинаторной оптимизации.
Финансирование
Это исследование было частью проекта, финансируемого Японской программой науки и технологий CREST по вычислительным платформам под руководством профессора Шуичи Сакаи из Токийского университета . CREST – это программа финансирования командных исследований с целью достижения стратегических целей, поставленных правительством.
Информационный проект
Название: На пути к пространственно-временным интеллектуальным вычислениям: на основе обучения и математико-научных моделей Руководитель: Масато Мотомура