Новосибирский государственный университет

Факультет информационных технологий

ICT SBRAS
А.М.Федотов

Словарь терминов в коллекции "Вычислительные системы"

Функция «баттерфляй»

Синонимы: Функция «баттерфляй»; «Баттерфляй»; Баттерфляй;

Функция «баттерфляй» (butterfly) была разработана в конце 60-х годов Рабинером и Гоулдом. Свое название она получила из-за того, что построенная в соответствии с ней сеть по конфигурации напоминает крылья бабочки. Математически функция может быть записана в виде

Bi(xn-1,...,xi+1xixi-1,...,x0) = xn-1,...,xi+1x0xi-1,…,x1xi, 0 ≤ i ≤ n-1.

Предполагается, что размер сети (количество узлов) равен N, разрядность адреса - n, где n=log2N и биты адреса обозначены как xi.
Двоичное представление узла-получателя получается путем взаимной перестановки в адресе узла источника битов с индексами i и 0. Хотя «баттерфляй»-функция используется в основном при объединении ступеней в сетях с динамической многоступенчатой топологией, известны также и «чистые» «баттерфляй»-сети.

Ключевые термины, связанные с термином "Функция «баттерфляй»":

  1. Топология «Баньян»
  2. Топология «Дельта»
  3. Функция реверсирования битов

Ключевые термины (головные):  Функции маршрутизации данных;   Динамическая топология;   Многоступенчатая сеть;

Контекстный поиск: Задайте образец для поиска:
|Головная| |Преподавание| | Современные проблемы информатики| |Информатика| |Ключевые термины| |Персоны|

Федотов Анатолий Михайлович 		[SBRAS]
НГУ
ФИТ НГУ
ИВТ СО РАН
© 1998-2024, Новосибирский государственный университет, Новосибирск
© 1998-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 1998-2024, Федотов А.М.
    Дата последней модификации: 14.08.2013