January 20th, 2008

with Cat The Cat

ooedo no hikeshi



Smoke on The Water на японском языке и на японских музыкальных инструментах.

Есть какое-то нечеловеческое очарование. ;)
with Cat The Cat

Пишу статью.

Все еще пишу статью.

Сейчас у меня совсем поедет крыша и я рехнусь.

Очень, очень непривычный вид деятельности.

Я вот, что думаю.

Давайте я напишу серию постов про саму идею машин динамического потока данных и просто выложу исходники. По исходникам можно будет спросить, что, да как (хотя я и пытался привести их в более-менее приличный и понятный вид). Заодно будет ясно, что же за всем этим делом стоит. И, быть может, статья пойдет быстрее.

Поэтому вопрос - куда их выкладывать? Этот же вопрос я задам в mskhug.
with Cat The Cat

А начну.

Есть такая штука - ассоциативная память. В отличии от обычной памяти, куда мы обращаемся по индексу ячейки, ассоциативная память адресуется ключом.

Самый близкий аналог среди структур данных - это отображение. Data.Map или std::map. Ключ может быть огромный, пространство ключей еще более огромно, а из всего этого пространства запомнено всего несколько десятков элементов.

Ассоциативная память - основа компьютеров. Не только компьютеров динамического потока данных, но и обычных тоже.

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

Ассоциативная память реализуется, как массив пар (ключ, значение). На вход поступает ключ, по которому ведется поиск и он сравнивается со всеми уже запомненными ключами одновременно. Инженерам это просто - шины протянуть вдоль всех ключей, и все.

Если обнаружено совпадение, производятся те или иные действия (зависит от назначения). Если совпадения не обнаружено, производятся другие или совсем другие действия.

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

Собственно, все. ;)

То, что ассоциативная память дорогое удовольствие - это основной тезис. И одно из основных препятствий на пути машин динамического потока данных (третья по списку).