А начну.
Есть такая штука - ассоциативная память. В отличии от обычной памяти, куда мы обращаемся по индексу ячейки, ассоциативная память адресуется ключом.
Самый близкий аналог среди структур данных - это отображение. Data.Map или std::map. Ключ может быть огромный, пространство ключей еще более огромно, а из всего этого пространства запомнено всего несколько десятков элементов.
Ассоциативная память - основа компьютеров. Не только компьютеров динамического потока данных, но и обычных тоже.
Например, кэш-память представляет собой вариант ассоциативной памяти. Переименование регистров в современных процессорах выполняется на ассоциативной памяти. В роутерах часто делается поддержка ассоциативной памяти для быстрого поиска в таблицах маршрутизации.
Ассоциативная память реализуется, как массив пар (ключ, значение). На вход поступает ключ, по которому ведется поиск и он сравнивается со всеми уже запомненными ключами одновременно. Инженерам это просто - шины протянуть вдоль всех ключей, и все.
Если обнаружено совпадение, производятся те или иные действия (зависит от назначения). Если совпадения не обнаружено, производятся другие или совсем другие действия.
В компьютерном железе скорость разменивается на энергию. То есть, мы можем выполнить быстрый энергичный поиск по всей памяти или вдвое менее расходный поиск только по ее половине. Слишком большая ассоциативная память и ее частое использование приведут к излишнему расходу энергии. Кристалл просто может этого не выдержать. Поэтому ассоциативные памяти стараются уменьшить - и сами их объемы, и размеры ключей, оставляя скорость поиска как можно меньшей.
Собственно, все. ;)
То, что ассоциативная память дорогое удовольствие - это основной тезис. И одно из основных препятствий на пути машин динамического потока данных (третья по списку).
Самый близкий аналог среди структур данных - это отображение. Data.Map или std::map. Ключ может быть огромный, пространство ключей еще более огромно, а из всего этого пространства запомнено всего несколько десятков элементов.
Ассоциативная память - основа компьютеров. Не только компьютеров динамического потока данных, но и обычных тоже.
Например, кэш-память представляет собой вариант ассоциативной памяти. Переименование регистров в современных процессорах выполняется на ассоциативной памяти. В роутерах часто делается поддержка ассоциативной памяти для быстрого поиска в таблицах маршрутизации.
Ассоциативная память реализуется, как массив пар (ключ, значение). На вход поступает ключ, по которому ведется поиск и он сравнивается со всеми уже запомненными ключами одновременно. Инженерам это просто - шины протянуть вдоль всех ключей, и все.
Если обнаружено совпадение, производятся те или иные действия (зависит от назначения). Если совпадения не обнаружено, производятся другие или совсем другие действия.
В компьютерном железе скорость разменивается на энергию. То есть, мы можем выполнить быстрый энергичный поиск по всей памяти или вдвое менее расходный поиск только по ее половине. Слишком большая ассоциативная память и ее частое использование приведут к излишнему расходу энергии. Кристалл просто может этого не выдержать. Поэтому ассоциативные памяти стараются уменьшить - и сами их объемы, и размеры ключей, оставляя скорость поиска как можно меньшей.
Собственно, все. ;)
То, что ассоциативная память дорогое удовольствие - это основной тезис. И одно из основных препятствий на пути машин динамического потока данных (третья по списку).