Вдогонку к посту про вычисления.

[thesz]

Параллельное сравнение с регулярными выражениями.

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

Comments

[_slw]

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

[thesz]

Вчитался.

Действительно, нет сравнения с обычным последовательным алгоритмом и в районе 4 нитей начинается замедление.

Но хоть какой-то пример. ;)

[_slw]

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

[thesz]

Они обрабатывают части пакета. Каждая i-я нитка обрабатывает (i+N*k)-й байт пакета, как я понял. Синхронизация для устранения ненужных состояний.