- Эффективное и реконфигурируемое оптимальное планирование в крупномасштабных системах с использованием иерархических конечных автоматов (arXiv)
Автор : Элис Стефанссон, Карл Х. Йоханссон
Аннотация: В этой статье мы рассматриваем задачу планирования для крупномасштабной системы, моделируемой как иерархический конечный автомат (HFSM), и разрабатываем алгоритм управления для вычисления оптимальных планов между любыми двумя состояниями. Алгоритм управления состоит из двух шагов: шаг предварительной обработки, вычисляющий оптимальные затраты на выход для каждой машины в HFSM, с линейным масштабированием временной сложности с количеством машин, и шаг запроса, который быстро вычисляет оптимальные планы, усекая ненужные части HFSM, используя оптимальные затраты на выход, при этом временная сложность масштабируется почти линейно с глубиной HFSM. Алгоритм управления реконфигурируется в том смысле, что изменение в HFSM эффективно обрабатывается, обновляя только необходимые части на этапе предварительной обработки для учета изменения, с линейной временной сложностью по глубине HFSM. Мы проверяем наш алгоритм на роботизированном приложении, сравнивая его с алгоритмом Дейкстры и иерархиями сжатия. Наш алгоритм превосходит оба.
2. ED-Batch: эффективная автоматическая пакетная обработка динамических нейронных сетей с помощью обученных конечных автоматов (arXiv)
Автор: Сыюань Чен, Пратик Фегаде, Тяньци Чен, Филипп Б. Гиббонс, Тодд С. Моури.
Аннотация: Пакетная обработка имеет фундаментальное влияние на эффективность выполнения глубокой нейронной сети (DNN). Однако для динамических DNN эффективная пакетная обработка является особенно сложной задачей, поскольку граф потока данных варьируется в зависимости от входного экземпляра. В результате современные фреймворки используют эвристики, что приводит к неоптимальным решениям по пакетной обработке. Кроме того, пакетная обработка накладывает строгие ограничения на смежность памяти и может привести к высоким затратам на перемещение данных. В этой статье мы предлагаем подход к пакетной обработке динамических DNN на основе конечных автоматов, который позволяет автоматически обнаруживать политики пакетной обработки, специализированные для каждой DNN, посредством обучения с подкреплением. Кроме того, мы обнаружили, что планирование памяти с учетом политики пакетной обработки может сократить значительные накладные расходы на перемещение данных, что автоматизировано с помощью представляемого нами алгоритма на основе дерева PQ. Экспериментальные результаты показывают, что наш фреймворк ускоряет современные фреймворки в среднем в 1,15, 1,39 и 2,45 раза для цепных, древовидных и решетчатых DNN на ЦП и ГП.
