События счет любят

[spamsink]

Даже не знаю, кому будет интересно. Математикам банально, программистам неактуально, электронщикам и так известно, остальным пофиг. Поэтому ...

Допустим, что нам для некоторого эксперимента нужно считать, сколько раз случилось каждое из многих десятков или сотен тысяч событий. Для этого мы разрабатываем специализированные чипы, каким-то умным образом анализирующие сырые данные эксперимента и получающие внутри себя много сигналов "случилось такое-то событие".
События могут происходить в произвольных сочетаниях - хоть все сотни тысяч одновременно, и - по сравнению с тактовыми частотами современных процессоров, - весьма часто. Это значит, что к схеме тех специализированных чипов придется добавить много блоков, которые только и умели бы, что по сигналу "произошло событие" как можно быстрее прибавлять 1 к счетчику (ну и по управляющему сигналу позволяли бы сбрасывать счетчик в ноль, одновременно выталкивая его текущее содержимое в порт - надо же нам как-то узнавать, до чего они там досчитали, но эту деталь функциональности мы пока для простоты опустим).

Как будет выглядеть такой блок? Он будет состоять из двух частей: регистра, где хранится текущее значение счетчика, и сложителя, прибавляющего 1 к счетчику. У регистра есть два входа - сигнал и новое значение. В момент прихода сигнала содержимое регистра заменяется новым значением. В сложитель же входит текущее значение регистра, а выходят из него провода, несущие "новое значение":

reg [63:0] counter;
wire [63:0] new_value = counter + 1; // Сложение происходит "непрерывно"
always @(signal) begin // Каждый раз, когда приходит сигнал (верилоговцы меня простят)
    counter = new_value;
end

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

Посмотрим теперь, как сложитель устроен внутри. Понятно, что из четного числа получается нечетное, и наоборот: new_value[0] = !counter[0];

Каждый следующий бит изменяется на противоположный, если все биты правее него были равны единице, или, что то же самое, если логическое И от всех этих битов равно единице:

for (int i = 1; i < 64; i++) // Декларативный цикл, описывающий подключение отдельных битов new_value
    new_value[i] = counter[i] ^ (counter[i-1:0] == (1 << i) - 1);

Это довольно быстро становится или дорого с точки зрения количества необходимых логических элементов - если мы будем вычислять все частичные логические И параллельно, их потребуются сотни, или недопустимо медленно - если мы будем экономить и вычислять их по цепочке:

wire [63:0] ands;
assign ands[0] = counter[0];
for (int i = 1; i < 64; i++) begin
    new_value[i] = counter[i] ^ ands[i-1];
    if (i != 63) ands[i] = ands[i-1] & counter[i];
end

Да и то понадобится по два элемента (XOR и AND) почти на каждый бит счетчика.

Как же быть? Как сделать счетчик событий так, чтобы он, кроме собственно регистра, использовал самый минимум логических элементов?

Comments

[potan.livejournal.com]

Параллельно - это сумматор с распространением переноса? Его использованием будет непозволительной роскошью по использованию элементов?

Самое простое решение - делать несколько инкриметров параллельно. То есть пока расчитывается перенос от одного инкримента из n-ного разряда, можно уже начинать высчитывать перенос их n-1-го разряда для следующего. Правда схема чтения сильно усложниться.

Можно пропускать события через ряд делителей. Схема чтения упрощается, но фактически становятся недоступны несколько младшие несколько бит.

[spamsink]

В случае инкрементора распространение переноса превращается просто в AND разной ширины. Да, считаем, что роскошь непозволительная, ведь счетчиков очень много.

Отдельные инкременторы всегда работают параллельно и независимо.

Делители недопустимы, каждое событие на счету.

Подсказка: искомое решение математически нетривиально.

[potan.livejournal.com]

Распространение переноса требует логорифмической глубины и ширины.

Параллельно может работать и отдельный инкрементатор, если второе событие пришло когда первое еще не до конца обработано - младший бит инвертировался, но перенос еще до старшего не дошел.

[spamsink]

http://spamsink.livejournal.com/344876.html?thread=3473964#t3473964

[kcmamu.livejournal.com]

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

Или считай через LFSR -- вообще один XOR на все про все. Только потом ответ нетривиально будет расшифровать...

[spamsink]

На такт чего? События асинхронные.

LFSR - правильный ответ.

[potan.livejournal.com]

Интересная мысль...
Можно счетчик команд в процессоре таким же образом инкрементировать. :-)

[kcmamu.livejournal.com]

> На такт чего? События асинхронные.

Вот сам входной сигнал и будем использовать как тактовый генератор.

[spamsink]

Тогда схема получения результата усложнится. В рамках поставленной задачи считаем, что устройство регистра фиксировано, а то можно было бы совсем просто - тактировать каждый следующий бит нулём предыдущего, и всё.

[kcmamu.livejournal.com]

А чтобы LFSR расшифровывать проще -- берем не один длинный, а несколько коротких с взаимно простыми периодами.

[spamsink]

Тоже вариант, да и с длинным несложно - ведь на практике могут встретиться только "не очень большие" значения.

[vak]

Почему бы не использовать арифметику по модулю какого-нибудь полинома, например x^64+1? Вместо сумматора будет сдвиговый регистр с небольшим количеством обратных связей.

[spamsink]

Этот полином - просто циклический сдвиг. :) Но да, я LFSR и имел в виду.

[vak]

LFSR, ага. Я англоязычный термин не вспомнил. Надо просто подобрать хороший (примитивный) полином. Для чётных степеней будет минимум три XOR-a, для нечетных - два.

[spamsink]

Минимум - один XOR: примитивный полином x^N + x^M + 1. Бывает не для всех степеней и от четности степени зависит неочевидным образом. Судя по Xilinx-овской таблице, для 37 степени - единственной для всех вплоть до 168 - минимум 5.

[vak]

Да, действительно... Забавная штука арифметика. :)
Для 63-й, 31-й и 15-й степеней есть полиномы с одним XOR-ом. Вполне практично.

[http://users.livejournal.com/_navi_/]

skew binary использовать?

[spamsink]

Сколько логики получится?

[http://users.livejournal.com/_navi_/]

ну, как я понимаю, меньше чем с двоичным представлением :-)

А воообще, спасибо, прочитал про LFSR, очень интересно. Кстати, есть какой-то простой метод декодирования из LFSR в порядковый номер?

[spamsink]

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

Простейшим методом декодирования из N-битного LFSR в порядковый номер я считаю rainbow table: выбираем, сколько в среднем итераций мы готовы жертвовать на декодирование - пусть это 2^M. Выбираем некоторый паттерн с фиксированными M битами - он будет в среднем встречаться через 2^M итераций. Генерируем таблицу, сопоставляющую каждое (в случае большого N - каждое возможное на практике) значение, соответствующее паттерну, с порядковым номером. Тогда для декодирования нам потребуется лишь прогнать полученный результат вперед до ближайшего совпадения с паттерном, считая итерации, потом заглянуть в таблицу и вычесть.

[http://users.livejournal.com/_navi_/]

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

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

[spamsink]

Cоветский троичный компьютер ("Сетунь") внутри был двоичным.

Декодирование LFSR эквивалентно нахождению дискретного логарифма, а это пока быстро делать не умеют.

[malaya-zemlya.livejournal.com]

Я наверное чего-то не понимаю, но зачем наворот с LFSR? Сдвиги они тоже элементов требуют.

Очевидно, чтоб досчитать до N нужно минимум O(log(N)) элементов. Ну хотя б чтобы ответ выводить.
Вполне достаточно каскада флип-флопов. При поступлении сигнала на вход состояние счетчика переключается между 0 и 1, а каждый второй раз посылается сигнал на следующую стадию.
Если мои смутные воспоминания об электронике верны, то на все про все требуется 2 транзистора. Куда уж меньше-то.

[spamsink]

Совершенно верно, но в реальной задаче, из которой я сделал мой пост, сдвиговые регистры (== группы флип-флопов с одним и тем же клоком) дешевы, а а каждый новый клок - дорог. Опять же, считывать значение из каскада сложнее, чем из сдвигового регистра.

[malaya-zemlya.livejournal.com]

:считывать значение из каскада сложнее

?????
У него состояние заведено выход - бери и пользуйся.
Клоки помойму вообще не нужны - бывают асинхронные флип-флопы.

[spamsink]

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

Асинхронным флип-флопом обычно называется флип-флоп с асинхронными сбросом в 0 и установкой в 1.

[potan.livejournal.com]

Асинхронные считывать сложно. Требуется довольно много оборудования, что бы сччитать все разряды синхронно и корректно.