?
Shortest Path Search Algorithm in Optimal Two-Dimensional Circulant Networks: Implementation for Networks-on-Chip
Для семейства оптимальных двумерных циркулянтных сетей с аналитическим описанием получены две новые улучшенные версии алгоритма поиска кратчайшего пути с постоянной оценкой сложности. Приведено простое, основанное на геометрической модели циркулянтных графов, доказательство формул, используемых для алгоритма поиска кратчайшего пути. Приведены алгоритмы парного обмена и даны их оценки для сетей на кристалле (NoC) с топологией в виде рассматриваемых графов. Новые версии алгоритма улучшают предложенный ранее алгоритм поиска кратчайшего пути для оптимальных обобщенных графов Петерсена с аналитическим описанием. Новый предложенный алгоритм является многообещающим решением для использования в NoC, что было подтверждено экспериментальным исследованием при синтезе подсистем связи NoC и сравнении потребляемых аппаратных ресурсов с другими ранее разработанными алгоритмами маршрутизации.