Согласен. После того, как я сформулировал свою идею, я сам начал активно курить все свои книги по теории алгоритмов, раздел поиск :) Но ту не не все так просто. Рассмотрим реалистичную задачу - для 100к пакетов в секунду принятие решения по таблице 10к правил.
Правила бывают разные. Пусть описание каждого правила - 128 байт (с учетом дексрипторов связного списка). Объем памяти - ((2^7)*(2^10)*10)/2^20 = 1.25Мбайт Если говорить о накристальной памяти, то это только Core и сотоварищи :)
Пусть у нас проц 500 Мгц. Тогда на 100к правил в сек у нас 500к тактов на одно правило. Вроде бы дофига. Но не тут то было. Возникает задача с кешами :)
Пусть у нас кеш лайн 16 байт. Типовой для embedded процессоров.
Интерфейс к SDRAM у нас максимум DDR266 32 бита. 1 кеш лайн мы заполним за 10 (подготовка транзации и закрытие)+ 4 (burst на 4 слова)=14 тактов 266 Мгц. Т.е. у нас частота busrt=19 Мгц.
Для 128 байт нам надо 8 burst, или 2.3 описаний пакета в сек.
Итого за имеющиеся у нас 10 мкс на принятие решения о пакете мы получим 2300 описаний в сек максимальную теоретическую пропускную способность памяти нашей системы.
Вроде бы за эти 2300 описаний мы уложимся, ибо двоичный поиск нам даст обработку только 13 описаний.
Но не стоит забывать, что программе тоже надо подкачиваться в кеш, еще есть задачи по модификации этой таблицы (статическая таблица - узко, система должна самообучаться), траффик в память по DMA от ethernet понтоллера, и мы видим что 500 Мгц слабо помогают конечному результату.
Т.е. по сути, какой-нибудь навороченный 500 Мгц АРМ точно не справится с задачей.
Спасение тут - в раздельных шинах. Например, SH4 от ST
http://www.st.com/ …ooks/pdf/docs/8672.pdf
Вот только одна засада - он Not for new design
Ну и аппаратная поддержка принятия решений :)
Evgeny_CD, Архитектор (04.07.2009 14:53, просмотров: 218) ответил Rst7 на Неа. Core I7 - это дорого и круто. Бинарный поиск по таблицам правил рулит :) 10к правил - это всего-то примерно 13 сравнений ;)