Требование давней слабости в классическом алгоритме для программирования реконфигурируемых чипсов

Исследователи из EPFL, AMD и Университета Novi SAD обнаружили давнюю неэффективность в алгоритме, который программирует миллионы реконфигурируемых чипов, используемых по всему миру, что может изменить то, как будущие поколения их разработаны и запрограммированы.

Многие отрасли, в том числе телекоммуникации, автомобильные, аэрокосмические и физика частиц Полагайтесь на специальную породу чипа, называемую полевой массией ворот, программируемой полевой программы (FPGA). В отличие от традиционных чипов, FPGAS можно перенастроить почти бесконечно, что делает их бесценными в быстро меняющихся областях, где проектирование пользовательского чипа займет годы и стоит целое состояние. Но эта гибкость имеет улов: эффективность FPGA в значительной степени зависит от программного обеспечения, используемого для их программирования.

С конца 1990 -х годов алгоритм, известный как Pathfinder, был основой маршрутизации FPGA. Его работа: соединение тысяч крошечных компонентов схемы без создания перекрытий.

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

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

В их бумагакоторый получил лучшую бумажную награду в 33 -й Международный симпозиум IEEE На полевых программируемых компьютерных компьютерах они показали, почему эти сбои происходят и как можно преодолеть пределы Pathfinder.

Трещины в алгоритме

«На самом деле, неудивительно, что Pathfinder иногда терпит неудачу», – объяснил Шашват Шривастава, доктор философии. Студент с Парсой и первый автор газеты.

«Очень рано исследователи показали, что проблема маршрутизации FPGA чрезвычайно сложна. Позже создатели оригинального алгоритма вместе с несколькими сотрудниками обнаружили случаи, когда Pathfinder никогда не удастся, но они отметили, что такие случаи не появятся на практике».

В течение десятилетий казалось, что они были правильными – папотовод работал на удивление хорошо.

«На самом деле Pathfinder работал так хорошо, что, когда он потерпел неудачу, люди редко подвергали сомнению алгоритм. Вместо того, чтобы отправиться внутрь, чтобы посмотреть, что происходит, они настраивали его параметры, модифицированные схемы или переключились на более крупные FPGA», – добавил Стефан Николич, выпускник EPFL и теперь профессор в Университете Нови Сад.

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

Войти в лес

«Итак, нам действительно нужно было взглянуть на отдельные деревья в этих джунглях», – продолжил Shrivastava, – и я действительно имею в виду деревья. Каждый сигнал – соединение, которое несет информацию между компонентами цепи, – до достижения нескольких направлений, не перекрывая другие сигналы. Маршрутизация FPGA предназначена для строительства одного дерева для каждого сигнала на чипе ».

Работая над другим проектом, который опирался на Pathfinder, команда продолжала видеть результаты, которые бросали вызов интуиции. Сначала они обвинили внешние факторы, а не алгоритм сам В конце концов они поняли, что им нужны контролируемые примеры: небольшие, сложные случаи, когда решение определенно существовало, и в котором Pathfinder должен добиться успеха.

«Нам нужны были настоящие, практические примеры и их много, чтобы понять, что на самом деле происходит», – объясняет Шривастава. «Итак, мы создали структуру для автоматического извлечения небольших, жестких проблем из реальных цепей. Наблюдение за тем, как Pathfinder боролся с ними, помогло нам раскрыть проблемы, которые оставались скрытыми в течение очень долгого времени».

Власть в партнерстве

«Этот прорыв был бы гораздо сложнее без поддержки отрасли», – сказала Мирджана Стоджилович, доктор философии Шриваставы. советник. «С самого начала мы сотрудничали с Chirag Ravishankar и Dinesh Gaitonde из AMD. Они помогли нам максимально близко моделировать FPGAS для коммерческих устройств, гарантируя, что наши результаты оказывали реальное влияние».

Как только структура была готова, все двигалось быстро. Команда обнаружила, что Pathfinder часто строил маршрутизационные деревья больше, чем необходимо, увеличивая риск перекрытий. Проблема возникла из -за порядка, в котором он создал и добавил новые ветви на деревья.

«Оглядываясь назад, это интуитивно понятно, но каким -то образом он оставался в основном незамеченным в течение многих лет», – сказал Шривастава. «Наше первое решение было простым: попробуйте разные заказы и выберите тот, который приводит к наименьшему дереву. Экспериментально это сработало на удивление хорошо».

Команда теперь изучает более масштабируемые решения. «Я особенно горжусь тем, что лето@epfl стажеры внесли значительный вклад. Один из них, Sun Tanaka, также является соавтором газеты»,-добавил Стодзилович.

«Наше открытие может изменить то, как миллионы FPGA запрограммированы и влияют на дизайн будущих поколений этих реконфигурируемых чипов».