Простая реализация небольших CAM на ПЛИС

    Введение


    Как-то раз мне потребовалось по работе реализовать небольшой блок CAM (ассоциативной памяти). Почитав, как это делается у Xilinx на BRAM (блоках статической памяти) или на SRL16 (16 — битных сдвиговых регистрах), я несколько опечалился, так как их реализации занимали довольно много места. Решил попробовать сделать его самостоятельно. Первым вариантом стала реализация в лоб. Забегая вперед, она практически сходу мне и подошла, благо, целевая частота для дизайна была всего 125 МГц.


    Архитектура


    Для начала рассмотрим постановку задачи. Итак, нам требуется небольшой CAM с шириной слова 8-64 бит и глубиной 16-1024 слов. Поиск в CAM мне требовался бинарный, но позже оказалось, что сделать из него TCAM (троичной ассоциативной памяти) довольно дёшево по ресурсам и незначительно влияет на тайминг. Нижняя граница частоты — 125 МГц на семействе Kintex7. Начнем! Наш CAM будет набран из вот таких линеек, каждая из которых будет соответствовать одному адресу и хранить одно слово:


    CAM_line


    Рисунок 1. Структура одной линейки CAM


    На рис.1 D — обычный D-триггер для хранения данных, число этих триггеров в линейке соответствует ширине входного слова данных в CAM. VALID — D-триггер, в котором хранится '1' если данные в линейке актуальны. CMP — компаратор, который сравнивает значение соответствующего бита шины ключа поиска search key, если VALID = '1'. write data — шина данных на запись, побитово подключенная к соответствующим D (N — ширина слова CAM), we — флаг записи, clear — сброс VALID (инвалидация данных линейки). AND — логический AND от N выходов компараторов, match — флаг, переходящий в '1', если поиск в данной линейке успешен.


    Итак, у нас есть одна линейка, в которой мы можем осуществлять поиск. Теперь объединим их:


    CAM_structure


    Рисунок 2. Структура CAM


    На рис.2 CAM_line — собственно линейки CAM с рис.1, MUX — входной адресный мультиплексор, MATCH REGISTER — регистр, сохраняющий значения флагов совпадения match, ENCODER — дешифратор, преобразующий шину совпадений в младший из найденных адрес совпадений. FSM — управляющий конечный автомат, который по линии prev. match удаляет из MATCH REGISTER бит, соответствующий отправленному адресу, чтобы ENCODER переключился на следующий найденный адрес. Интерфейс нашего CAM будет следующим:


    Линия Направление Назначение
    addr Вход Адрес записи/стирания
    data Вход Данные на запись/ключ
    we Вход Флаг записи
    check Вход Флаг поиска по ключу
    clear Вход Флаг инвалидации линии по адресу
    addr_o Выход Адрес, найденный по ключу
    match_o Выход Флаг успеха поиска по ключу

    Таблица 1. Интерфейс CAM


    Ниже на рис.3 представлена временная диаграмма работы данного интерфейса, где показана сначала запись трёх слов в CAM, затем успешный поиск, стирание и снова поиск:


    CAM_diagramm
    Рисунок 3. Временная диаграмма работы интерфейса к CAM


    Итак, у нас есть описание CAM, давайте перейдём к синтезу.


    Синтез


    Синтезировать будем в Xilinx ISE, чтобы сравнить результаты с полученными в XAPP1151.


    W8V5


    Рисунок 4. Зависимость частоты после XST (синтезатора в составе ISE) от глубины CAM для ширины шины данных 8 бит


    W32V5


    Рисунок 5. Зависимость частоты после XST от глубины CAM для ширины шины данных 32 бита


    W64V5


    Рисунок 6. Зависимость частоты после XST от глубины CAM для ширины шины данных 64 бита


    На на рис.6 отсутствуют данные для Virtex5, так как CAM такого размера не влез в имеющиеся BRAM. Отметим также, что для ширины 64 бита и глубины 1024 наш результат оказался чуть хуже, чем у реализации на SRL16. Перейдём теперь к синтезу на Vivado для XC7K325T. Результаты получились следующие:


    W32K7


    Рисунок 7. Зависимость частоты после PnR (размещения блоков на чипе и трассировки сигналов) от глубины CAM для ширины шины данных 32 бита


    K7res


    Рисунок 8. Утилизация ресурсов для различных глубин CAM для ширины данных 32 бита в %


    Важно отметить, что результаты на Vivado были получены уже после PnR, а значит в дизайне нет сложностей с трассировкой.


    TCAM


    Как говорилось выше, получить при данном подходе из CAM TCAM особой проблемы не составило. Достаточно добавить шину маскирования битов data и раздать её побитно в компараторы, чтобы при сравнении данных с ключом они учитывали её значение. Такое изменение не привело к падению частоты или серьёзному росту потребляемых ресурсов, так что TCAM мы получили бесплатно.


    Выводы


    Итак, нам удалось выполнить поставленную задачу. Полученный дизайн позволяет на 7-м семействе ПЛИС Xilinx получать достаточно большие CAM с частотой выше целевых 125 МГц. Результат сравнения с XAPP1151 оказался для меня неожиданным, я предполагал, что реализация на BRAM, хоть и является очень дорогой с точки зрения ресурсов, обгонит лобовую реализацию по частоте. Однако не стоит праздновать победу так рано, в этом документе дано описание IP-ядра CAM от Xilinx, которое позволяет, например, получать CAM глубиной 32К ячеек и частотой 155 МГц, базируясь на BRAM. Такого результата наверное можно добиться и в предложенном в статье варианте, за счет добавления стадий конвейера, или набирая большой CAM из маленьких, но предсказать сходу, влезет ли это в чип я не могу. В дальнейшем попробую реализовать на BRAM нечто похожее, а пока спасибо за внимание.

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 21

      0
      Ещё бы переставил местами буквы в словах и было бы совсем понятно о чём реч. А по делу — что такое CAM, TCAM, BRAM и для чего так писать? (Подразумевается что кто то будет это читать)
        –4
        Я хотя бы не потерял мягкие знаки. По делу — TCAM и CAM общепринятые обозначения, хотя из текста вполне можно понять, что это такое. Что такое BRAM (а иже с ним SRL16, XST, PnR и проч.) должно быть и так известно читающим хаб PFGA, никто же в статьях по программированию не разжевывает, что такое цикл, компилятор и регистры.
          0
          Не обижайся друже, я просто спросил т.к. не понятно было. Читают статьи не только специалисты. Если бы хоть в заголовке расшифровка была, то вопросов бы не было.
            0

            Расставил ссылки

            0
            А в каких задачах эти CAM применяются на плисах?
              0

              У меня в контроллере памяти в таком CAM будут храниться кое-какие признаки, нужные для синхронизации потоков. Потоков не будет больше 1000 одновременно, поэтому я не гнался за размером. А так, серьёзные CAM используются для таблиц в коммутаторах и в TLB.

                0
                Синхронизации потоков чего?
                  0

                  Синхронизация данных для программных потоков в многоядерной вычислительной системе.

                    0
                    Ясно. Я думал вы сетевой коммутатор делаете.
                    Мне просто тоже пару раз указывали, что непонятно пишу, когда статья узкоспециализированная, теперь понял каково это со стороны))
                    Я думаю до ката нужна предыстория описанием постановки задачи на один абзац и многие вопросы отпадут.
                      0

                      К сожалению более менее понятное описание будет в отдельной статье, здесь я постарался сконцентрироваться на CAM as is, это мне показалось достаточно самостоятельной темой. Возможно бы не прав.

                        0
                        Тема самостоятельная, но читать всегда интереснее, если перед глазами есть пример того, для чего оно может быть нужно.
              0
              Кстати так и не понял, почему заминусовали. Хаб довольно специфический. И мне кажется по умолчанию должно предполагаться, что читающие его в курсе, хотя бы что такое BRAM. Жаль оценивать по срокам уже нельзя, а то бы поставил плюсик в качестве хоть какой-то, но компенсации :)))
              +4
              CAM — content addresable memory, наверно.
              BRAM — это устоявшееся у плисоводов сокращение от Block Random Access Memory (встроенных блоков памяти ПЛИС).
              А по существу, у меня вопрос: зачем такие тяжелые плисины использовали, вроде overkill по ресурсам и ценнику?
                +1
                Такие тяжёлые (если речь идёт про 325-й Кинтекс) просто потому, что CAM там маленький кусок большого дизайна. Так то у меня 32x256 например влезал в XC3S1400A и почти влезал 32x1024, если попрыгать чутка на нем, то влез бы.
                  0
                  CAM там маленький кусок большого дизайна

                  Теперь понятно, благодарю.
              0
              Дико извиняюсь, но честно говоря вообще не понял, как что-то подобное можно сделать на BRAM. Нет, оно понятно, что там можно искать. А если озаботиться сортировкой, то можно даже применить бинарный поиск вместо линейного. Но смысл-то всего, это искать за один такт! Не знаю как тут BRAM поможет… Просветите уж неуча! :))))
              Как раз сейчас о чём-то похожем думаю. Хочу чтобы процессор на плисине пореже лазил в SDRAM и почаще пользовался BRAM. Иными словами сделать для него кеш. Вспомнил что мельком видел на хабре Вашу статью, и сейчас полез читать. К сожалению не нашел ничего, о чём бы я сам не подумал. Единственно совершенно не понял, как тут можно использовать BRAM. А так получается дороговато. Если линейка кеша 64 байта(как у x86, x86_64), то на один BRAM(Spartan-7) кеша придется использовать 64 таких регистра-компаратора как у Вас. Что делать? Увеличивать размер ячейки кеша ??? Не лучший вариант.
                0

                Если у вас вообще нет кеша, то почему бы не попробовать BRAM, адресуемый хешем адреса? При записи просто записываем по адресу, равному хешу от целевого адреса в BRAM сам целевой адрес и слово данных. При чтении проверяем, действительно ли в ячейке BRAM, адресуемой хешем целевого адреса, лежит требуемый целевой адрес: нет — промах, да — попадание.


                Промахов, конечно, будет больше из-за коллизий, чем при реализации via CAM.

                  0
                  Промахов, конечно, будет больше из-за коллизий, чем при реализации via CAM.

                  Таки на случай коллизий можно организовать цепочки значений для каждого адреса.
                  Имхо, всё украдено до нас, много интересных кейсов и вариаций можно глянуть у Jacob в «Memory Systems: Cache, DRAM, Disk».
                    0

                    Можно, можно opening adressing hast table использовать для цепочек прямо в том же BRAM, но, по-моему, это излишнее усложнение. (Только стоит помнить, что OAHT ведёт себя хорошо при таблице, заполненной, примерно, не более, чем на 2/3 — вот ещё усложнение.)


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


                    Имхо, всё украдено до нас, много интересных кейсов и вариаций можно глянуть у...

                    С этим я не спорю )

                    0
                    И как Вы это себе представляете ??? Ну хорошо, набрали из BRAM буфер на 16К слов. Если так, то хеш должен быть 14-битный. При 1М адресном пространстве вероятность коллизии 1/64. А их тоже придётся как-то разрешать! Что время либо ресурсы. А скорее и то и другое. Я тут ниже ещё один коммент написал про использование мелкой памяти на LUT вместо регистров. Наверно буду делать всё-таки как-то так. Вообще тема интересная. Смотрел на opencores, реализаций кеш-памяти там не нашел.
                  0
                  Придумал небольшое улучшение Вашей приблудины. Дело в том что у Xilinx есть мелкая память на основе LUT. Если мне не изменяет мой склероз, библиотечные примитивы на 16, 32, 64 и 128 бит. Можно в том что Вы называете Cam Line заменить каждый триггер на такую вот память. Что это даёт:
                  Фактически каждый бит в линии заменяется адресуемым набором из 16 (до 128) битов. Положим кеш состоит из нескольких блоков, и в каждый блок мы кладём данные из строго определённого диапазона адресов основной памяти, и никакие другие. Тогда физический адрес можно разбить на три части:
                  — Младшие биты — смещение относительно начала линейки кеша.
                  — Средние биты — ключ поиска в ассоциативной памяти.
                  — Старшие биты — адрес блока кеша.
                  Если адрес блока кеша мы подаём в качестве адреса на нашу память, заменяющую триггеры, на компараторы подадутся как раз нужные ключи для сравнения.
                  Таким образом один такой контроллер сможет управлять сразу множеством блоков кеша. Практически бесплатно экономим дохренищща ресурсов кристалла!

                  Only users with full accounts can post comments. Log in, please.