[ЕвгенийЗлыднев 0]

Здравствуйте.

Не получается решить следующую задачу.

Есть 25 чисел, каждое 8 бит. Надо найти наиболее часто встречающиеся среди них т.е. если число встречается 13 и больше раз, это то что мы ищем.  Если такого не нашлось, то надо выдать 8 нулей. Когда алгоритм отработал нужен импульс который сообщит о этом.  

Опишу что я сделал и как решал эту задачу.

1) https://habr.com/ru/post/167177/   Прочитал эту статью. Взял как образец. Там как раз для маленьких устройств рассмотрено. 

Этот алгоритм. 

int* majority(int[] array, int N) {
  int confidence = 0; // количество людей, не нашедших пары и оставшихся стоять
  int* candidate = NULL; // последний человек, не нашедший пару -- 
                         // возможно, его элемент встречается чаще всего

  // проходим по массиву и усаживаем пары с разными элементами
  for (int i = 0; i<N; i++) {

    // если до сих пор все сидят, то следующему пока придётся постоять
    if (confidence == 0) {
      candidate = array+i;
      confidence++;
    }

    // иначе следующий либо садится с одним из стоящих,
    // либо будет стоять вместе с ними, если у него такой же элемент
    else if (*candidate == array[i])) 
      confidence++;
    else 
      confidence--;
  }

  return confidence > 0 ? candidate : NULL;
}

2) В учебнике Digital Design Using Diligilent FPGA Boards VHDL/Active-HDL Edition. Richard E. Haskell, Darrin M. Hanna 2010. 
Со страницы 278 там показывается как правильно реализовывать такие алгоритмы на плис на примере поиска корня и евклидов НОД. Рисунки 1 и 2 не синтезируемый код этих алгоритмов. 

Рисунок 3 и 4  синтезируемые на плис реализации этих  алгоритмов. 

3) Попытался адаптировать этот алгоритм для синтеза. 

Получилось следующие, точнее изначально был  другой код, но я много раз пытался его исправить, но особо ничего не менялось. И я уже не помню какой он был изначально. 

-----Author: Zlydnev E.N.
-----function: vybiraem nomera
-- Revision history
-- Version 1.0 :
-- Date: 6/09/2019
-- Comments : Original
----
library IEEE;-- vklychaem biblioteki
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;
use IEEE.numeric_std.all;


entity  chastye_elementy  is  -- vhodnie/vyhodnye signals

 port( clk      : in std_logic; 
       GO       : in std_logic;
       clr      : in std_logic;
       ------------------------------------------------
       ------------------------------------------------
       ------------------------------------------------
       
       nomer     :  out std_logic_vector(7 downto 0);
       
       ibn1     :  in std_logic_vector(7 downto 0);-- nomer borta na pervom  zaprose
       ibn2     :  in std_logic_vector(7 downto 0);-- nomer borta na vtorom  zaprose
       ibn3     :  in std_logic_vector(7 downto 0);-- -//-
       ibn4     :  in std_logic_vector(7 downto 0);-- -//-
       ibn5     :  in std_logic_vector(7 downto 0);-- -//-
       ibn6     :  in std_logic_vector(7 downto 0);-- -//- 
       ibn7     :  in std_logic_vector(7 downto 0);-- -//- 
       ibn8     :  in std_logic_vector(7 downto 0);-- -//-
       ibn9     :  in std_logic_vector(7 downto 0);
       ibn10    :  in std_logic_vector(7 downto 0);-- -//-
       ibn11    :  in std_logic_vector(7 downto 0);--
       ibn12    :  in std_logic_vector(7 downto 0);--
       ibn13    :  in std_logic_vector(7 downto 0);--
       ibn14    :  in std_logic_vector(7 downto 0);--
       ibn15    :  in std_logic_vector(7 downto 0);--
       ibn16    :  in std_logic_vector(7 downto 0);--
       ibn17    :  in std_logic_vector(7 downto 0);--
       ibn18    :  in std_logic_vector(7 downto 0);--
       ibn19    :  in std_logic_vector(7 downto 0);--
       ibn20    :  in std_logic_vector(7 downto 0);--
       ibn21    :  in std_logic_vector(7 downto 0);--
       ibn22    :  in std_logic_vector(7 downto 0);--
       ibn23    :  in std_logic_vector(7 downto 0);--
       ibn24    :  in std_logic_vector(7 downto 0);--
       ibn25    :  in std_logic_vector(7 downto 0);-- nomer borta na 25 zaprose
       ------------------------------------------

        
       done :  out std_logic  --dalnostb po poslednemy impulsu 
       
       );
end chastye_elementy;    

architecture rtl of chastye_elementy is


type reg is array (25 downto 1) of std_logic_vector(7 downto 0);--type danyx dlya xraneniya IBN
signal ibn :reg := (others => (others =>'0'));


signal i : integer range 0 to 25;
signal j : integer range -25 to 25;
signal temp_nomer    : std_logic_vector(7 downto 0);



begin
 

G3: process(clr,clk)   
variable calk,donev: std_logic;
begin
if clr = '1' then 
ibn <= (others => (others =>'0'));
nomer <= (others =>'0');
temp_nomer <= (others =>'0');
i <= 1;
j <= 0; 
calk := '0';
donev := '0'; 
elsif rising_edge(clk) then
donev := '0';
if go = '1' then 
ibn(1) <= ibn1; ibn(2)   <= ibn2; ibn(3)  <= ibn3; ibn(4)<=ibn4 ;ibn(5)<= ibn5 ;   ibn(6) <= ibn6;
ibn(7) <= ibn7; ibn(8)   <= ibn8; ibn(9)  <= ibn9; ibn(10)<= ibn10;  ibn(11)<=ibn11 ; ibn(12)<=ibn12  ;
ibn(13) <= ibn13; ibn(14)<= ibn14; ibn(15)<= ibn15; ibn(16)<= ibn16; ibn(17)<= ibn17 ; ibn(18) <= ibn18;
ibn(19) <= ibn19; ibn(20)<= ibn20; ibn(21) <= ibn21; ibn(22)<=ibn22  ; ibn(23) <= ibn23; ibn(24) <= ibn24;ibn(25)<=ibn25 ;
i <= 1;
j <= 0; 
temp_nomer  <= (others =>'0');
nomer <= (others =>'0');
calk := '1';
elsif calk = '1' then 
    if i=24 then 
      if j > 0 then  
      nomer <= temp_nomer;
      else nomer <= "00000001";
      end if;
      donev := '1';
      calk  := '0';
elsif j = 0 then
   temp_nomer <= ibn(i+1);
   j<= j + 1;
   i<= i + 1;
elsif temp_nomer = ibn(i+1) then
     i<= i + 1;
     j<= j + 1;
     temp_nomer <= temp_nomer;
   else 
     i<=i + 1;
     j<=j - 1;
     temp_nomer <= ibn(i+1);
end if;
end if;
end if;
done <= donev;
end process; 

end rtl; 

Расскажу про код

ibn 1-25  - входные данные. 

nomer - выходное число, результат. 

Go- сигнал для начала алгоритма

Done - сигнал для конца алгоритма

Сlk - частота, clr - сброс. 

Остальное сделал по аналогии с примерами из учебника. 

Получил плохие результаты. рисунок 5. Хотя тут показана только одна попытка сделать так чтобы схема заработала.

ПРОБЛЕМЫ всегда одни и та же:

1) Сигнал i не увеличивается на каждом шаге на 1, а почему то так же как и джей то увеличивается то возрастает. Также он стартует не с 0, а с 3. Хотя я прописал что i=0. 

2) В результате (signal nomer)  всегда выдается просто значение ibn25

Прошу помогите разобраться  в этом вопросе. 

 

P.S Сейчас алгоритм занимает 270 ЛЭ. Плис крохотная как я говорил, хочется чтобы занимало это все как можно меньше места. Скорость работы не так важна. Частота у меня 37 МГц. 

[xvr 12]

Это не код, а тихий ужас.

33 minutes ago, ЕвгенийЗлыднев said:

Плис крохотная как я говорил, хочется чтобы занимало это все как можно меньше места.

Не подскажете, в какой 'крохотной плис' нашлось 211 ног на ввод/вывод?

Или у вас данные идут последовательно? Исходный алгоритм обрабатывает массив именно последовательно, т.е. всё можно посчитать на лету

 

[ЕвгенийЗлыднев 0]

1 час назад, xvr сказал:

Это не код, а тихий ужас.

  1 час назад, ЕвгенийЗлыднев сказал:

Плис крохотная как я говорил, хочется чтобы занимало это все как можно меньше места.

Не подскажете, в какой 'крохотной плис' нашлось 211 ног на ввод/вывод?

Или у вас данные идут последовательно? Исходный алгоритм обрабатывает массив именно последовательно, т.е. всё можно посчитать на лету

 

это отдельный компонент, он будет использован вместе с другими файлами. Так что "ноги" напрямую кроме clr, clk использоваться не будут.  То есть я сначала отлаживаю отдельный компонент, потом формирую общий топовый файл где соединяю их вместе. Данные идут таким образом: эти регистры заполняются другим внешним компонентом по определенному закону. Точнее даже они входят в него. Это экспериментальный код, для отлаживания самого принципа.Так что не обращайте на это внимание, все эти 209 ног будут внутренними сигналами в самой плис.  Когда он все сформировал, то посылает сигнал GO начала операции по выявлению этого самого повторяющегося элемента. А данный алгоритм за 25 тактов должен выявить повторяющийся элемент. Если у Вас есть идеи как сделать "на лету", я обязательно рассмотрю ваш вариант. Что касается кода, я понимаю что он не очень. Хотя бы из-за того что не работает) Но я приложил примеры из литературы на которые ориентировался. В них подобным образом все организовано и работает. Я лично проверял эти алгоритмы, тем более в учебнике приложены другие необходимые компоненты для проверки. К сожалению не могу скинуть книгу целиком. Но вот эта схема для проверки алгоритма Евклидов НОД. Я имею другую отладочную плату, но тем не менее приспособил данную схему под себя и все работает. Не говоря уже о времнных диаграммах. В любом случае буду рад если Вы предложите свой вариант реализации данного алгоритма, либо же другого, но схожего по функциям и занимаемому пространству на плис. 

[RobFPGA 27]

Приветствую!

Отличие  разработки для RTL от чистого программирования в том что надо еще мыслить в 3-ем измерении - во времени. От того как приходят данные, как быстро из надо обрабатывать зависит какой алгоритм вы можете реализовать.

В вашем случае вам надо строить гистограмму от входных чисел. Можно тупо иметь память на 256 слов, входным числом индексировать ячейку и увеличивать ее значение на 1 (запоминая индекс с макс результатом). Но для ваших условий (букет ограничен 25-ю числами и порог 13) достаточно будет иметь кеш-память (число - счетчик)  всего на (25-13)+1 ячеек.  . А будет ли реализация такой кэш памяти  параллельной (1 число за такт) или последовательной (13+ тактов  на число) зависит от требования к быстродействию и ограничений на ресурсы. 

Удачи! Rob.

[ЕвгенийЗлыднев 0]

3 минуты назад, RobFPGA сказал:

Приветствую!

Отличие  разработки для RTL от чистого программирования в том что надо еще мыслить в 3-ем измерении - во времени. От того как приходят данные, как быстро из надо обрабатывать зависит какой алгоритм вы можете реализовать.

В вашем случае вам надо строить гистограмму от входных чисел. Можно тупо иметь память на 256 слов, входным числом индексировать ячейку и увеличивать ее значение на 1 (запоминая индекс с макс результатом). Но для ваших условий (букет ограничен 25-ю числами и порог 13) достаточно будет иметь кеш-память (число - счетчик)  всего на (25-13)+1 ячеек.    

Удачи! Rob.

Будем считать что данные пришли уже. То есть записаны в регистры. Когда записаны, тогда сортируем.Специальный сигнал запуска Go.  Отсортировать планирую за 25 тактов clk, либо меньше если возможно. Так как каждый ход  алгоритма равен одному такту clk.  Не хочу таблицами сортировать, так как это требует много ресурсов. Нужно держать в памяти все возможные значения. Про гистограммы не совсем понял. 

[RobFPGA 27]

Приветствую!

1 hour ago, ЕвгенийЗлыднев said:

 Не хочу таблицами сортировать, так как это требует много ресурсов

Много ресурсов понятие относительное - таблица 256 x 5 bit всего лишь  один  блок памяти.  Если он конечно есть в вашей FPGA. В противовес параллельная кэш память на 13 слов  будет иметь (8+5)*13 LUT и регистров.   

1 hour ago, ЕвгенийЗлыднев said:

Отсортировать планирую за 25 тактов clk, либо меньше

Можно и за 1 такт все 25 чисел обработать (чисто комбинаторика , но на 37 MHz тактовой может и прокатит) - только вот ресурсов это потянет  поболее чем если 1 число за такт. 

Удачи! Rob.

[ЕвгенийЗлыднев 0]

4 минуты назад, RobFPGA сказал:

Приветствую!

Много ресурсов понятие относительное - таблица 256 x 5 bit всего лишь  один  блок памяти.  Если он конечно есть в вашей FPGA. В противовес параллельная кэш память на 13 слов  будет иметь (8+5)*13 LUT и регистров.   

Можно и за 1 такт все 25 чисел обработать (чисто комбинаторика , но на 37 MHz тактовой может и прокатит) - только вот ресурсов это потянет  поболее чем если 1 число за такт. 

Удачи! Rob.

Блоки памяти использовать не желательно. Параллельная слишком много займет. Необходимо плюс минус 300 ЛЭ, 25 тактов. лучше одно число за один такт, чем больше ресурсов потратить.  Посмотрите мой алгоритм, он как раз за один такт одно число обрабатывает. Не подскажете в чем ошибка? Или если возможно попробуйте повторить его, может у вас получится реализовать. 

[ЕвгенийЗлыднев 0]

54 минуты назад, RobFPGA сказал:

Приветствую!

Много ресурсов понятие относительное - таблица 256 x 5 bit всего лишь  один  блок памяти.  Если он конечно есть в вашей FPGA. В противовес параллельная кэш память на 13 слов  будет иметь (8+5)*13 LUT и регистров.   

Можно и за 1 такт все 25 чисел обработать (чисто комбинаторика , но на 37 MHz тактовой может и прокатит) - только вот ресурсов это потянет  поболее чем если 1 число за такт. 

Удачи! Rob.

нашел видеоурок по данному вопросу. Тут  за 6 минут  не целиком разобрана глава из книги. Но никак не могу добиться чтобы этот алгоритм  заработал на ПЛИС. В следующем видео 99 идут подробности для метода Евклида. они уже не так интересны. 

 

Изменено 11 сентября, 2019 пользователем ЕвгенийЗлыднев

[wolfman 0]

D

[RobFPGA 27]

Приветствую!

2 hours ago, ЕвгенийЗлыднев said:

Не подскажете в чем ошибка? Или если возможно попробуйте повторить его, может у вас получится реализовать. 

Основная ошибка в неправильном алгоритме  который вы пытаетесь  повторить. Даже у меня не получится реализовать неправильный алгоритм  У вас какое условие?

6 hours ago, ЕвгенийЗлыднев said:

Есть 25 чисел, каждое 8 бит. Надо найти наиболее часто встречающиеся среди них т.е. если число встречается 13 и больше раз, это то что мы ищем.

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

 Ну а дальше начинаем оптимизировать по условиям задачи - ограничение длины последовательности и конкретный порог превышения дают нам уверенность что таких счетчиков достаточно  будет (длина - порог)+1 (намекну - что если первые 13 чисел у вас будут все разные? ). 

Удачи! Rob.

[Skryppy 0]

Нет компьютера под рукой, завтра попробую набросать модуль. Гугл нашёл такой пример:

Google book

Spoiler

 

 

 

[MrGalaxy 9]

Евгений Злыднев,

Код непонятен. Первый if понятно, асинхронная установка, второй if тоже понятно, работа по фронту, а дальше ничего не понимаю...

Синхронный if не предусматривает else. Разве Квартус на такую конструкцию не ругается? Вроде должен. 

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

И не стесняйтесь в коде писать комментарии, самому проще будет, как можно писать код без единого комментария! Else желательно писать под соответствующим then, т.е. с необходимым отступом, так код будет лучше читаться. Потом, когда проект отладите и будете ставить исходники на учёт в ОТД, подробные комментарии уберёте. :)

Изменено 12 сентября, 2019 пользователем MrGalaxy
Не разглядел ещё один if после rising_edge

[Maverick_ 15]

2 ЕвгенийЗлыднев

Для старта можно попробовать так:

Создаем (исходя что 2^8=256) массивы регистров:

- таблицы данных 256х8бит регистров (с начальной инициализацией равной 0)

 -таблицы индексов  256х8бит регистров (с начальной инициализацией равной 0). 

 

 По приходу нового значения (само значение это адрес для таблицы 256х8бит регистров). Читаем по данному адресу если там уже имеется такое же число (работает 8 бит компаратор на равенство) и параллельно читаем индекс для данного регистра (адрес одинаковый для двух таблиц), то производим прибавление 1 для данного индекса иначе прибавляем 0 и записываем результат полученного индекс обратно в таблицу индексов. И так далле.

В конце если требуется найти максимальное число повторений можно модифицировать такой поиск по таблице индексов (там же можете посмотреть как создавать массивы регистров):

 

PS Массивы регистров можно заменить при необходимости память на BRAM или ALM(SRL). Скорее всего нужна только одна таблица индексов (оптимизация за Вами). Например просто добавить в таблицу индексов один бит по которому можно будет судить было ли раннее такое входное число.

[Skryppy 0]

Так как у вас число должно встречаться половину и более раз, то можно сделать так: Задача 6

Сделал два варианта:

1 ) Использование промежуточных регистров, regs = 221, luts = 95,

2) без них, кода много, но работает

Regs= 32, luts = 253.

 

histogram_max_tb.vhd

histogram_max.vhd

P.S.: забыл протестировать при отсутствии всех данных, но думаю там исправлений немного будет

 

[RobFPGA 27]

Приветствую!

1 hour ago, Skryppy said:

Так как у вас число должно встречаться половину и более раз, то можно сделать так

Классическая ошибка - упрощение требований к заданию до удобных. У TC числа МОГУТ встречаться половину и более раз. Проверьте этот же алгоритм для длинны 3 точки  (2 из 3)  Каков будет ответ для входных чисел 1,2,3  и 1,2,1 ?

Удачи! Rob.