[Vengin 0]

Приветствую, други.

Есть некий модуль, условно называемый матрицей переключений:

entity matrix is
  generic(
     N : natural := 16
  );
  port( 
     di  : in  std_logic_vector (N-1 downto 0);
     do  : out std_logic_vector (N-1 downto 0);
     sel : in  std_logic_vector (N * integer(CEIL(LOG2(real(N)))) - 1 downto 0)
  );
end matrix;

Надо каждому выходу do(i) назначить некоторый вход di(j), причём сделать это "взаимоисключающе". Т.е. любой входной сигнал может быть назначен только на один выходной сигнал и ни на какой другой. Другими словами, нужно сделать нечто похожее на "единичную матрицу", в которой можно менять местами ряды:

Исходная матрица:
100...0
010...0
001...0
.......
000...1

Вариант возможной конфигурации:
001...0
100...0
000...1
.......
010...0

Настройки переключений задаются, соответственно, сигналом sel.

 

На данный момент видится такое решение:

Матрица: N мультиплексоров каждый разрядностью N (весьма ресурсоёмко).

 

Решение задачи "в лоб" (построение N мультиплексоров каждый разрядностью N и взаимоисключающее демультиплексирование соответствующих битов сигнала sel.) получается весьма ресурсоёмким и неэффективным.

При этом необходимо учитывать, что размер матрицы N будет достаточно большим (в моём случае 16, 80, 320).

Ещё один нюанс: предполагается, что сигнал настройки переключений sel будет представлять некий набор регистров записи процессора (например каждый ряд матрицы - регистр). Соответственно при изменении какого-либо регистра нужно предусмотреть некий механизм проверки матрицы на "взаимоисключаемость".

 

Какие есть идеи у "коллективного разума" по более реализации всего этого счастья?

P.S.: язык VDHL/Verilog, синтезатор ISE XST, кристалл Spartan3.

 

[FROL_256 0]

Я совершенно не понял что требуется сделать. М.б. если вы приведете еще примеров будет понятнее.

>>Настройки переключений задаются, соответственно, сигналом sel.

А как именно?

 

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

[sazh 8]

Какие есть идеи у "коллективного разума" по более реализации всего этого счастья?

 

Сначала в виде функции реализуйте.

Потом коллективный разум подумает о минимизации.

[SergeyF 0]

Что-то в таком духе приспособить?

http://en.wikipedia.org/wiki/Omega_network

http://en.wikipedia.org/wiki/Bitonic_sorting

 

[CaPpuCcino 0]

Что-то в таком духе приспособить?

скажите, плз, в чём практическое значение omega network, а то я не всосал из англ. описания.

спб

[tAmega 0]

Какие есть идеи у "коллективного разума" по более реализации всего этого счастья?

А чо тут думать, человек хочет организовать доступ "всех ко всем", то есть проложить 100% соединений между всеми участниками формулы.

Тут нечего оптимизировать. Оптимизация возможна, когда число соединений меньше 100%. Вот тогда идут на всякие ухищрения.

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

 

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

[Oldring 0]

При этом необходимо учитывать, что размер матрицы N будет достаточно большим (в моём случае 16, 80, 320).

 

Скорость не важна?

Классическое решение - последовательные запись/чтение элементов и промежутосная память с произвольным доступом.

[Vengin 0]

Я совершенно не понял что требуется сделать. М.б. если вы приведете еще примеров будет понятнее.

Хорошо. Например N=3. Число возможных конфигураций равно 6:

[0] sel <= (0 & 1 & 2):
100   do(0) <= di(0)
010   do(1) <= di(1)
001   do(2) <= di(2)

[1] sel <= (0 & 2 & 1):
100   do(0) <= di(0)
001   do(1) <= di(2)
010   do(2) <= di(1)

[2] sel <= (1 & 0 & 2):
010   do(0) <= di(1)
100   do(1) <= di(0)
001   do(2) <= di(2)

[3] sel <= (1 & 2 & 0):
010   do(0) <= di(1)
001   do(1) <= di(2)
100   do(2) <= di(0)

[4] sel <= (2 & 0 & 1):
001   do(0) <= di(2)
100   do(1) <= di(0)
010   do(2) <= di(1)

[5] sel <= (2 & 1 & 0):
001   do(0) <= di(2)
010   do(1) <= di(1)
100   do(2) <= di(0)

>>Настройки переключений задаются, соответственно, сигналом sel.

А как именно?

Число возможных конфигураций (состояний) будет вычисляться по формуле N*log(N).

Опять таки подходов можно сделать несколько. На данный момент это фактически шина разрядностью N*log(N), каждый эелемент которой задаёт номер входного сигнала. Т.е. для N=3, sel((3*2)-1 downto 0).

[0]
100   do(0) <= di(0)
010   do(1) <= di(1)
001   do(2) <= di(2)
DECI: sel <= (0 & 1 & 2)
BIN:  sel <= ("00" & "01" & "10")

Можно сделать сигнал sel(N*N-1 downto 0), и тогда каждый элемент будет фактически битовой маской:

MASK: sel <= ("001" & "010" & "100")

Главное чтобы каждый входной сигнал был поставлен в соответсвие некоторому одному (и только одному!) выходному сигналу. Т.е. нельзя чтобы входной сигнал di(0) выходил как на выход di(0), так и на di(1).

 

Сначала в виде функции реализуйте.

На данный момент реализация самой матрицы такова:

architecture syn of matrix is
  constant C_SEL_WIDTH : integer := integer(ceil(log2(real(N))));
begin

  G_MUX_I: for i in 0 to N - 1 generate
  begin
     I_MUX_N_1: audio_mux_N_to_1 
     generic map(N => N)
     port map(
        clk => clk,
	 ce  => ce,
        sel => sel((i+1)*C_SEL_WIDTH - 1 downto i*C_SEL_WIDTH),
        di  => di,
        do  => do(i)
     );
  end generate;
end syn;

В данном случае матрица допускает возможность назначения одного входа на несколько выходов. Например если sel <= "00...0";, то всем выходам будет соответствовать нулевой вход: do <= (others => di(0));

Вот теперь думаю как бы сделать так, чтобы настройки sel давали только взаимоислючающие переключения (т.е. нельзя один вход на несколько выходов). Как один из вариантов исользовать сигнал sel(N*N-1 downto 0). Тогда каждый столбец матрицы можно будет в свою очередь интерпретировать как число и уже его реализовать как демультиплексор:

case (sub_sel(j)):
  when "0..001" =>
  do(j) <= do(0);
  when "0..010" =>
     do(j) <= do(1);
  ...
  when "1..000" =>
     do(j) <= do(N-1);
  when others =>	-- mutual exclusive violation!
     do(j) <= '0';

Но, даже при N=16 получаются огромные, неэффективные контрукции. Что уж тут говорить о размерах N=80, N=320.

 

Что-то в таком духе приспособить?

Спасибо, что-то такое крутилось в голове, надо эти варианты обмозговать.

 

Скорость не важна?

Скорость 25MHz.

[SergeyF 0]

скажите, плз, в чём практическое значение omega network, а то я не всосал из англ. описания.

спб

Не смогу, к сожалению. Хотел найти свою подборку статей про коммутаторы (в основном аппаратную ATM коммутацию) с рассмотрением различных типов сетей сортировки и их сравнение, но не нашел, поэтому просто бросил пару ссылок, которые попались под руку.

 

[tAmega 0]

25MHz это скорость передачи данных по входам? Если да, то какова частота смены матрицы, то есть как часто происходят изменения по сигналу sel и перенаправление входов к выходам.

[SergeyF 0]

скажите, плз, в чём практическое значение omega network, а то я не всосал из англ. описания.

спб

Вот, ниже ссылки. Это коммутатор, по сути дела, реализация crossbar switch в несколько этапов. Есть разные структуры с разными характеристиками по блокировке и т.д. Как всегда компромисс между объемом и быстродействием.

 

Спасибо, что-то такое крутилось в голове, надо эти варианты обмозговать.

Лучше поискать и почитать. Эти проблемы были решены, есть разные архитектуры. Гуглите статьи по switching networks.

 

Пока никак не могу найти статьи про сети. Вот, например, еще:

http://books.google.ru/books?id=eHXblLeXxr...p;q&f=false

Вот неплохая презентация про блокировку:

http://pages.cpsc.ucalgary.ca/~carey/CPSC6...megaExample.ppt

Вот вики:

http://en.wikipedia.org/wiki/Clos_network

 

Но на скорости 25МГц, особенно если коммутатор конвейеризовать на каждом этапе коммутации, можно много чего успеть сделать.

[des00 25]

На форуме есть тема о создании подобных быстрых коммутаторов с небольшим ресурсом. Используйте поиск.

[Sefo 0]

А какая, всетаки, стоит из 2-х задач: коммутация каналов или коммутация пакетов?

 

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

[SergeyF 0]

Насколько я понимаю, все "хитрые" методы придуманы для коммутации пакетов.

Ну почему же. Вот выше по ссылке в Википедии - сети Клоса. Были придуманы для телефонии, когда никаких пакетов и электроники там еще не было. Есть неблокирующие, есть неблокирующие с переупорядочением (как раз проблема и решение показана в презентации).

 

Просто не факт, что это будет применимо для конкретной задачи или получится эффективнее, чем деревья мультиплексоров.

 

[sazh 8]

Надо каждому выходу do(i) назначить некоторый вход di(j), причём сделать это "взаимоисключающе". Т.е. любой входной сигнал может быть назначен только на один выходной сигнал и ни на какой другой. Другими словами, нужно сделать нечто похожее на "единичную матрицу", в которой можно менять местами ряды:

 

При этом необходимо учитывать, что размер матрицы N будет достаточно большим (в моём случае 16, 80, 320).

А может размер и приемлимым будет.

Вот пример N в один. На эту функцию другую наложить (N регистров записи процессора)

 

/*

sel будет представлять некий набор регистров записи процессора

(например каждый ряд матрицы - регистр).

Соответственно при изменении какого-либо регистра

нужно предусмотреть некий механизм проверки матрицы на "взаимоисключаемость".

*/

module fun_matrica

(

input [3:0] in_m,

input [3:0] one_rg,

input ena_one,

output y

);

 

 

 

function yy (input [3:0] in_m, input [3:0] one_rg, input ena_one);

integer i, y;

begin

y = 0;

begin: block_a

for (i=0; i<=3 ; i=i+1)

y = in_m && one_rg;

end

yy = ena_one && (|y[3:0]);

end

endfunction

 

assign y = yy(in_m, one_rg, ena_one);

 

endmodule