|
|
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Коллеги, посоветуйте, пожалуйста как можно решить следующую проблему. В цифровой обработке изображений есть набор функций под общим названием color transformation, аргументами которых являются только значения исходных пикселов (ex: изменение яркости, контраста, гамма-коррекции, эквализация и т.д.). Сам алгоритм примитивный и быстрый (подстановка по заранее вычисленной таблицы), но имеет известный дефект, связанный с тем, что в результате преобразования на выходе могут выпадать некоторые разряды, соответственно, автоматическая обработка гистограмм сильно усложняется из-за наличия мнимых провалов. Для борьбы обычно используется добавление [псевдо-]случайного шума, амплитуда которого зависит от значения аргумента. Иными словами, преобразование выглядит как: Код: pascal 1. Проблема в том, что второе слагаемое вычисляется неприемлемо долго, даже при распараллеливании. Пробовал плюнуть на случайность и подставить вместо него i mod Tab_N[Val] (i - некий индекс в массиве), но время выполнения все равно оставляет желать лучшего. Есть идеи, как это можно ускорить? Может какие-то SIMD-инструкции использовать (я в них не силен)? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 15:04 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Может какие-то SIMD-инструкции использовать (я в них не силен)? Начиная с IvyBridge у процессора есть инструкция RDRAND . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 15:31 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 15:37 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
locked, Понял, спасибо. Но, во-первых, IvyBridge присутствует сильно не везде. Во-вторых, насколько я понимаю, тормозит именно вычисление остатка от деления, которое все равно придется выполнять. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 15:46 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
В свое время была такая программа Intel VTune. Она и показывала, что именно "тормозит". В настоящее время в процессорах конвеер. Т.ч. собственно показатель "кол-во тактов на инструкцию" уже не актуален. Если througth input большой, то долгое execution time проблемой не является. Т.ч. фраза "тормозит именно вычисление остатка от деления" подкупает своей загадочностью. IMHO & AFAIK Может какие-то SIMD-инструкции использовать (я в них не силен)? SSE позволяет за одну операцию обработать до 4 чисел одновременно. Если разрядности хватает, то соответственно с SSE будет до 4 раз быстрее. Соколинский БорисRes:=Tab_I[Val]+Random(Tab_N[Val]); А тебе действительно нужно Random? Может просто заранее посчитать массив в 32-64K чисел, сохранить его в программе и вместо генерации псевдослучайных чисел использовать просто константы из данного массива? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 16:25 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Leonid KudryavtsevВ настоящее время в процессорах конвеер. Т.ч. собственно показатель "кол-во тактов на инструкцию" уже не актуален. Если througth input большой, то долгое execution time проблемой не является. Т.ч. фраза "тормозит именно вычисление остатка от деления" подкупает своей загадочностью. Да чего тут загадочного, просто сравниваются два времени с добавкой и без нее. Даже в случае i mod Tab_N[Val] скорость падает в 4 раза. Возможно проблема не в вычислении как таковом, а в переключении логики 8-32-8 бит (AFAIK есть такая проблема), но я не представляю, как от нее уйти. Если разрядности хватает, то соответственно с SSE будет до 4 раз быстрее. В SSE нет операции "остаток от деления", перепроверил на всякий случай. Leonid KudryavtsevА тебе действительно нужно Random? Может просто заранее посчитать массив в 32-64K чисел, сохранить его в программе и вместо генерации псевдослучайных чисел использовать просто константы из данного массива? Без рандома я обойдусь и памяти совсем не жалко, но описанная логика пока не ясна. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 16:41 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Ну кидай тогда какой нибудь простой тест. Если я правильно понимаю, у тебя на входе массив чисел (какого типа?) и на выходе должен тоже быть массив чисел. А то лично я совершенно не понимаю: "падает в 4 раза" по сравнению с чем, откуда и где берется "отстаток от деления" и что есть "переключении логики 8-32-8 бит". Потом она сползла с гриба и скрылась в траве, бросив Алисе на прощанье: -- Откусишь с одной стороны -- подрастешь, с другой -- уменьшишься! -- С одной стороны чего? -- подумала Алиса. -- С другой стороны чего? -- Гриба, -- ответила Гусеница, словно услышав вопрос, и исчезла из виду. С минуту Алиса задумчиво смотрела на гриб, пытаясь определить, где у него одна сторона, а где--другая; гриб был круглый, и это совсем сбило ее с толку. Наконец, она решилась: обхватила гриб руками и отломила с каждой стороны по кусочку. -- Интересно, какой из них какой?--подумала она ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 17:00 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис Код: pascal 1. Нифига не понимаю, где в этой формуле "остаток от деления". Если на входе данные в виде целых чисел (или числа с фиксированной точкой), то банально: умножение + сдвиг + сложение PMULHW (multiply packed signed integers and store high result) + PADDW (?) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 17:27 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Leonid KudryavtsevНу кидай тогда какой нибудь простой тест. Если я правильно понимаю, у тебя на входе массив чисел (какого типа?) и на выходе должен тоже быть массив чисел. Коль скоро это работа с пикселами, данные либо byte, либо word (каждый канал обрабатывается отдельно). Тест program TestColorTransform; {$APPTYPE CONSOLE} uses Windows, SysUtils, math; const MaxLen=100000000; type TTransTab= array[byte] of byte; TDataTab = array[0..MaxLen-1] of byte; procedure CreateTransformTab(const Brighness, contrast, gamma: single; out PixTab, NoizeTab: TTransTab); var i: byte; Val: single; begin for i:=0 to maxByte do begin val:= MaxByte*(Power(i/MaxByte, gamma)+Brighness)*contrast; if Val<0 then PixTab[i]:=0 else if Val>MaxByte then PixTab[i]:=MaxByte else PixTab[i]:=Trunc(Val); end; for i:=0 to maxByte-1 do NoizeTab[i]:=pixTab[i+1]-pixTab[i]+1; NoizeTab[maxByte]:=1; end; procedure InitData(out DataTab: TDataTab); var i: integer; begin for i:=0 to High(DataTab) do DataTab[i]:=random(256); end; procedure ProcDataTabNoNoize(var DataTab: TDataTab; const TransTab: TTransTab); var i: integer; begin for i:=0 to High(DataTab) do begin DataTab[i]:=TransTab[DataTab[i]]; end; end; procedure ProcDataTabRegNoize(var DataTab: TDataTab; const TransTab, NoizeTab: TTransTab); var i: integer; begin for i:=0 to High(DataTab) do begin DataTab[i]:=TransTab[DataTab[i]]+I mod NoizeTab[DataTab[i]]; end; end; procedure ProcDataTabRandNoize(var DataTab: TDataTab; const TransTab, NoizeTab: TTransTab); var i: integer; begin for i:=0 to High(DataTab) do begin DataTab[i]:=TransTab[DataTab[i]]+ Random(NoizeTab[DataTab[i]]); end; end; //собственно тест var PixTab, NoizeTab: TTransTab; TC: cardinal; Data: TDataTab; begin CreateTransformTab(-0.05, 1.1, 0.5, PixTab, NoizeTab); InitData(Data); TC:=gettickcount; ProcDataTabNoNoize(Data, PixTab); Writeln('No noize: ', Gettickcount-TC); InitData(Data); TC:=gettickcount; ProcDataTabRegNoize(Data, PixTab, NoizeTab); Writeln('Regular noize: ', Gettickcount-TC); InitData(Data); TC:=gettickcount; ProcDataTabRandNoize(Data, PixTab, NoizeTab); Writeln('Random noize: ', Gettickcount-TC); Readln; end. Результат No noize: 79 Regular noize: 453 Random noize: 375 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 17:49 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Блин, забыл тег вставить Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 17:52 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Соколинский БорисБез рандома я обойдусь и памяти совсем не жалко, но описанная логика пока не ясна. Если входные данные в виде 8 битового байта, то на C я бы изображал что-то следующее. Код накидывал ради простоты последующей переделки под скорость, в ушерб читаемости. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 18:11 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Блин. Писали одновременно. Твой код не видел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 18:13 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev, Я вроде понял идею - перейти к умножению и сдвигу разрядов. То бишь нечто вроде Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. На чистом паскале быстрее не становится, но с MMX, наверное, будет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 18:39 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. Эти числа мне больше понятны, чем Delphi'ские. Каким образом в дельфи генератор случайных чисел оказался быстрее остатка от деления - мне не понятно ))). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 19:16 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Эти числа мне больше понятны, чем Delphi'ские. Каким образом в дельфи генератор случайных чисел оказался быстрее остатка от деления - мне не понятно ))). Random(x) - и есть остаток от деления :). Просто сама функция на asm-е сделана, а судя по тому, что компилятор нагородил в при вычислении остатка, с оптимизацией имеются(лись) некоторые проблемы. Меня больше удивляет, почему c-ный вариант генератора такой тормозной. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 19:33 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
На ассемблере у меня получается в 3 раза медленнее, чем на C ))) ProcDataNoNoise - 32 мой вариант того же на ASM'е с обработкой по 4 штуки за раз - 94 ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 20:57 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
А вот это уже радует. IMHO Показатель насколько старой Intel архитектуре не хватает регистров. Код: plaintext 1. 2. 3. 4. 5. 6. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 21:08 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Leonid KudryavtsevНа ассемблере у меня получается в 3 раза медленнее, чем на C ))) Бывает. Я лет 10 назад решил для себя, что достаточно научиться читать асм-код, сгенерированный компилятором и переделывать исходник так, чтобы он транслировался в более эффективный. Кстати, я понял как усовершенствовать Вашу идею так, чтобы шум действительно был случайным (ну почти). Нужно один раз сгенерировать массив случайных множителей с длиной, большей чем длина данных на DeltaN, а при выполнении определять начальное смещение как Random(DeltaN). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 22:26 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис, Прошу прощения, если скажу глупость, т.к. не специалист в этой предметной области. Но не годится ли последний бит сделать просто чередующимся 0/1 (возможно, с так же чередующимся начальным значением для каждой строки) ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.06.2015, 22:38 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Соколинский БорисЯ лет 10 назад решил для себя, что достаточно научиться читать асм-код, сгенерированный компилятором и переделывать исходник так, чтобы он транслировался в более эффективный. нужно ещё мануалы от интела читать. "здравый смысл" может навредить ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.06.2015, 01:45 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис... в результате преобразования на выходе могут выпадать некоторые разряды... А нельзя ли применить код Грея? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.06.2015, 21:55 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
От нечего делать, поставил себе триал версию Intel VTune 2013 (версия 2015 с багой - в триал режиме не работает). Если ни в чем не ошибся, то теперь мой вариант ProcDataTabNoNoize работает в 2.5 раза быстрее чем C-ный ))) Теоретически процессор может вычислять до 2-х простых исполняемых адресов за такт, т.ч. большое кол-во обращений к таблицам констант вроде не так страшно, как казалось на первый взгляд. Разпаковка/упаковка данных на новых процах Intel круто оптимизировал. Раньше при попытке обращения к 8 битам из 32 битного регистра было пенальти, теперь вообще, инструкция MOVZX вообще Zero Latency. Круть! пошел развлекаться дальше, от нечего делать..... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.06.2015, 20:03 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
При этом стоит на L2_LINES_IN.ALL This event counts the number of L2 cache lines brought into the L2 cache. Lines are filled into the L2 cache when there was an L2 miss. судя по всему на чтение входного потока (таблица констант закешировались нормально) и на MEM_UOPS_RETIRED.ALL_STORES_PS This event counts all store uops retired. This is a precise event. что, в целом очень не плохо. IMHO CPI Rate 0.355 /тактов на инструкцию, минимально возможное 0.25, 4 инструкции за такт) Пойду арифметику добавлять. С доступом к данным по 4 байта за операцию (чтение из памяти по 32 битным словам) и их разпаковкой/упаковкой я разобрался. ))) Занятно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.06.2015, 20:27 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
IMHO переводить на MMX/SSE смысла нет. Ускорение не получится, т.к. основная работа это просмотр в таблицах. А оно никак за счет MMX не ускорится. А арифметика... паковка/распаковка для MMX займет больше, чем собственно вычисления. AFAIK Пытался поиграться с PREFETCH - вообще ноль эффекта. Но процессор сейчас должен сам уметь автоматом Prefetch делать Изменение порядка вычислений + оптимизация размещение таблиц в памяти ==> небольшое, но заметное ускорение. С учетом, что с введением шума _реальной_ работы становится в 3 раза больше (в 3 раза больше таблиц+простейшая арифметика) IMHO падение скорости вполне приемлемое. Или я с Intel VTune не разобрался или он реально стал менее удобный, чем был 10 лет назад. Процессоры и метрики конечно полностью поменялись, но цифры он показывает странные, а раскладка показателям по отдельным ассемблерным командам - вообще как бог на душу положит. Сейчас по метрикам вообще не понятно, в чем проблема и на какой команде она возникает. Раньше он более точно отрабатывал. Пенальти показывал точно. Код: plaintext 1. 2. 3. 4. 5. 6. 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.06.2015, 18:36 |
|
||
|
Требуется очень быстрый генератор шума
|
|||
|---|---|---|---|
|
#18+
Не прав. Оно же на SSE2 для байтов (16 значений/128 бит за операцию). Вычисления через PMADDWD Результат не проверял, нужно долго отлаживать. Т.к. с порядком байтов и знаком в регистре при перепаковках сам черт ногу сломит. Плюс хитрая структура хранения данных в таблицах констант. Код: plaintext 1. 2. 3. 4. 5. 6. 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.06.2015, 22:15 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=38992771&tid=1340982]: |
0ms |
get settings: |
6ms |
get forum list: |
10ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
52ms |
get topic data: |
6ms |
get forum data: |
1ms |
get page messages: |
56ms |
get tp. blocked users: |
1ms |
| others: | 199ms |
| total: | 335ms |

| 0 / 0 |
