Важная информация
Показано с 1 по 3 из 3

Тема: Помогите с оптимизацией

  1. #1 Помогите с оптимизацией 
    Новичок
    Регистрация
    17.10.2015
    Сообщений
    6
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    В программе (Delphi XE8, x64) используются 256-битные переменные, логически представляющие из себя квадрат 16x16 бит. У такого такого квадрата существует 7 симметричных состояний (включая исходное 8). Симметричные состояния можно получить:
    Отражением по горизонтали (H)
    Отражением по вертикали (V)
    Отражением по диагонали из левого верхнего угла {0;0} в правый нижний {15;15} (Dxx)
    Комбинацией трёх предыдущих отражений (DVH). Так получается отражение по диагонали из левого нижнего угла {0;15} в правый верхний {15;0}
    Тремя оставшимися комбинациями (VH, DH, DV) - это повороты на 180o, на 90o влево и на 90o вправо
    Кстати, симметрии DH и DV встречаются только одновременно с VH. То есть, если квадрат 16х16 бит обладает симметрией DH то там есть и DV и VH. Но симметрия VH может встречаться отдельно от других.

    Есть процедура, которая преобразует квадрат всеми возможными способами и помещает результат в массив
    Assembler Code:
    1.  
    2. // RCX - адрес нулевого элемента массива, куда будут помещены все 8 состояний
    3. // RDX - адрес исходного состояния
    4.  
    5. MOVAPS XMM0,[RDX]
    6. MOVAPS XMM1,[RDX]+$10
    7. MOVNTPS [RCX],XMM0                // 0
    8. MOVNTPS [RCX]+$10,XMM1            // 0.5
    9. ADD RCX,$20
    10. XORPS XMM3,XMM3
    11. MOVNTPS [RCX],    XMM3            // 1
    12. MOVNTPS [RCX]+$10,XMM3            // 1.5
    13. MOVNTPS [RCX]+$20,XMM3            // 2
    14. MOVNTPS [RCX]+$30,XMM3            // 2.5
    15. MOVNTPS [RCX]+$40,XMM3            // 3
    16. MOVNTPS [RCX]+$50,XMM3            // 3.5
    17. MOVNTPS [RCX]+$60,XMM3            // 4
    18. MOVNTPS [RCX]+$70,XMM3            // 4.5
    19. MOVNTPS [RCX]+$80,XMM3            // 5
    20. MOVNTPS [RCX]+$90,XMM3            // 5.5
    21. MOVNTPS [RCX]+$A0,XMM3            // 6
    22. MOVNTPS [RCX]+$B0,XMM3            // 6.5
    23. MOVNTPS [RCX]+$C0,XMM3            // 7
    24. MOVNTPS [RCX]+$D0,XMM3            // 7.5
    25. MOV R9,255
    26. SFENCE
    27. JMP @work255_1
    28.  
    29. @bitset255_1:
    30.  
    31. XOR R9b,$0F
    32. BTS [RCX],R9              // xxH x=x, y=15-y
    33. XOR R9b,$FF
    34. BTS [RCX]+$20,R9          // xVx x=15-x, y=y
    35. XOR R9b,$0F
    36. BTS [RCX]+$40,R9          // xVH x=15-x, y=15-y
    37. ROL R9b,4
    38. BTS [RCX]+$C0,R9          // DVH x=15-y, y=15-x
    39. XOR R9b,$0F
    40. BTS [RCX]+$A0,R9          // DVx x=15-y, y=x
    41. XOR R9b,$FF
    42. BTS [RCX]+$80,R9          // DxH x=y, y=15-x
    43. XOR R9b,$0F
    44. BTS [RCX]+$60,R9          // Dxx x=y, y=x
    45. ROL R9b,4
    46. DEC R9b
    47. JZ @work0
    48.  
    49. @work255_1:
    50.  
    51. BT [RDX],R9
    52. JC @bitset255_1
    53. DEC R9b
    54. JNZ @work255_1
    55.  
    56. @work0:
    57.  
    58. BT [RDX],0
    59. JNC @finish
    60. MOV R9b,$F0
    61. MOV RAX,$FF
    62. BTS [RCX],$F              // xxH x=0, y=15
    63. BTS [RCX]+$20,R9          // xVx x=15, y=0
    64. BTS [RCX]+$40,RAX         // xVH x=15, y=15
    65. BTS [RCX]+$C0,RAX         // DVH x=15, y=15
    66. BTS [RCX]+$A0,R9          // DVx x=15, y=0
    67. BTS [RCX]+$80,$F          // DxH x=0, y=15
    68. BTS [RCX]+$60,$0           // Dxx x=0, y=0
    69.  
    70. @finish:


    Есть функция, которая возвращает 8 бит информации о том, какими симметриями обладает заданное состояние (заданный квадрат, заданная переменная). Нулевой бит результата всегда установлен и соответствует тому, что исходное состояние без преобразований равно самому себе.
    Assembler Code:
    1.  
    2. // RCX - адрес исходного состояния
    3. // RDX - выровненный на 16 адрес буфера
    4. // AL  - возвращаемый байт
    5.  
    6. XORPS XMM3,XMM3
    7. MOVNTPS [RDX],XMM3                // 1
    8. MOVNTPS [RDX]+$10,XMM3            // 1.5
    9. MOVNTPS [RDX]+$20,XMM3            // 2
    10. MOVNTPS [RDX]+$30,XMM3            // 2.5
    11. MOVNTPS [RDX]+$40,XMM3            // 3
    12. MOVNTPS [RDX]+$50,XMM3            // 3.5
    13. MOVNTPS [RDX]+$60,XMM3            // 4
    14. MOVNTPS [RDX]+$70,XMM3            // 4.5
    15. MOVNTPS [RDX]+$80,XMM3            // 5
    16. MOVNTPS [RDX]+$90,XMM3            // 5.5
    17. MOVNTPS [RDX]+$A0,XMM3            // 6
    18. MOVNTPS [RDX]+$B0,XMM3            // 6.5
    19. MOVNTPS [RDX]+$C0,XMM3            // 7
    20. MOVNTPS [RDX]+$D0,XMM3            // 7.5
    21. MOV R9,255
    22. SFENCE
    23. JMP @work255_1
    24.  
    25. @bitset255_1:
    26.  
    27. XOR R9b,$0F
    28. BTS [RDX],R9              // xxH x=x, y=15-y
    29. XOR R9b,$FF
    30. BTS [RDX]+$20,R9          // xVx x=15-x, y=y
    31. XOR R9b,$0F
    32. BTS [RDX]+$40,R9          // xVH x=15-x, y=15-y
    33. ROL R9b,4
    34. BTS [RDX]+$C0,R9          // DVH x=15-y, y=15-x
    35. XOR R9b,$0F
    36. BTS [RDX]+$A0,R9          // DVx x=15-y, y=x
    37. XOR R9b,$FF
    38. BTS [RDX]+$80,R9          // DxH x=y, y=15-x
    39. XOR R9b,$0F
    40. BTS [RDX]+$60,R9          // Dxx x=y, y=x
    41. ROL R9b,4
    42. DEC R9b
    43. JZ @work0
    44.  
    45. @work255_1:
    46.  
    47. BT [RCX],R9
    48. JC @bitset255_1
    49. DEC R9b
    50. JNZ @work255_1
    51.  
    52. @work0:
    53.  
    54. BT [RCX],0
    55. JNC @counttype
    56. MOV R9b,$F0
    57. MOV RAX,$FF
    58. BTS [RDX],$F              // xxH x=0, y=15
    59. BTS [RDX]+$20,R9          // xVx x=15, y=0
    60. BTS [RDX]+$40,RAX         // xVH x=15, y=15
    61. BTS [RDX]+$C0,RAX         // DVH x=15, y=15
    62. BTS [RDX]+$A0,R9          // DVx x=15, y=0
    63. BTS [RDX]+$80,$F          // DxH x=0, y=15
    64. BTS [RDX]+$60,$0          // Dxx x=0, y=0
    65.  
    66. @counttype:
    67.  
    68. MOV     RAX,1
    69.  
    70. MOV R8,[RCX]
    71. CMP R8,[RDX]
    72. JNE @rno_xxH
    73. MOV R8,[RCX+$08]
    74. CMP R8,[RDX+$08]
    75. JNE @rno_xxH
    76. MOV R8,[RCX+$10]
    77. CMP R8,[RDX+$10]
    78. JNE @rno_xxH
    79. MOV R8,[RCX+$18]
    80. CMP R8,[RDX+$18]
    81. JNE @rno_xxH
    82. OR AL,2
    83.  
    84. @rno_xxH:
    85.  
    86. MOV R8,[RCX]
    87. CMP R8,[RDX+$20]
    88. JNE @rno_xVx
    89. MOV R8,[RCX+$08]
    90. CMP R8,[RDX+$20+$08]
    91. JNE @rno_xVx
    92. MOV R8,[RCX+$10]
    93. CMP R8,[RDX+$20+$10]
    94. JNE @rno_xVx
    95. MOV R8,[RCX+$18]
    96. CMP R8,[RDX+$20+$18]
    97. JNE @rno_xVx
    98. OR AL,4
    99.  
    100. @rno_xVx:
    101.  
    102. MOV R8,[RCX]
    103. CMP R8,[RDX+$40]
    104. JNE @rno_xVH
    105. MOV R8,[RCX+$08]
    106. CMP R8,[RDX+$40+$08]
    107. JNE @rno_xVH
    108. MOV R8,[RCX+$10]
    109. CMP R8,[RDX+$40+$10]
    110. JNE @rno_xVH
    111. MOV R8,[RCX+$18]
    112. CMP R8,[RDX+$40+$18]
    113. JNE @rno_xVH
    114. OR AL,8
    115.  
    116. @rno_xVH:
    117.  
    118. MOV R8,[RCX]
    119. CMP R8,[RDX+$60]
    120. JNE @rno_Dxx
    121. MOV R8,[RCX+$08]
    122. CMP R8,[RDX+$60+$08]
    123. JNE @rno_Dxx
    124. MOV R8,[RCX+$10]
    125. CMP R8,[RDX+$60+$10]
    126. JNE @rno_Dxx
    127. MOV R8,[RCX+$18]
    128. CMP R8,[RDX+$60+$18]
    129. JNE @rno_Dxx
    130. OR AL,16
    131.  
    132. @rno_Dxx:
    133.  
    134. MOV R8,[RCX]
    135. CMP R8,[RDX+$80]
    136. JNE @rno_DxH
    137. MOV R8,[RCX+$08]
    138. CMP R8,[RDX+$80+$08]
    139. JNE @rno_DxH
    140. MOV R8,[RCX+$10]
    141. CMP R8,[RDX+$80+$10]
    142. JNE @rno_DxH
    143. MOV R8,[RCX+$18]
    144. CMP R8,[RDX+$80+$18]
    145. JNE @rno_DxH
    146. OR AL,32
    147.  
    148. @rno_DxH:
    149.  
    150. MOV R8,[RCX]
    151. CMP R8,[RDX+$A0]
    152. JNE @rno_DVx
    153. MOV R8,[RCX+$08]
    154. CMP R8,[RDX+$A0+$08]
    155. JNE @rno_DVx
    156. MOV R8,[RCX+$10]
    157. CMP R8,[RDX+$A0+$10]
    158. JNE @rno_DVx
    159. MOV R8,[RCX+$18]
    160. CMP R8,[RDX+$A0+$18]
    161. JNE @rno_DVx
    162. OR AL,64
    163.  
    164. @rno_DVx:
    165.  
    166. MOV R8,[RCX]
    167. CMP R8,[RDX+$C0]
    168. JNE @rno_DVH
    169. MOV R8,[RCX+$08]
    170. CMP R8,[RDX+$C0+$08]
    171. JNE @rno_DVH
    172. MOV R8,[RCX+$10]
    173. CMP R8,[RDX+$C0+$10]
    174. JNE @rno_DVH
    175. MOV R8,[RCX+$18]
    176. CMP R8,[RDX+$C0+$18]
    177. JNE @rno_DVH
    178. OR AL,128
    179.  
    180. @rno_DVH:
    Ответить с цитированием  
     

  2. #2  
    Новичок
    Регистрация
    17.10.2015
    Сообщений
    6
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    Первый раз на этом форуме - поторопился отправить первый пост, думал можно будет сразу-же подредактировать. Вот продолжение:

    Нужна функция, которая будет возвращать не все 8 состояний, а только заданные. Можно конечно тупо взять результат первой процедуры и в конце удалить из массива ненужные состояния. При этом придётся либо делать ещё временный массив, либо как-то смещать состояния в массиве во время удаления лишних. Это всё добавит кучу времени на выполнение, а участок кода, где это будет использоваться ко времени критичен. Подскажите, как оптимизировать?

    Вот, заготовка:
    Assembler Code:
    1.  
    2. // в aType байт, в котором 8 бит обозначают, какие именно симметрии нужно вернуть в массиве. Формат расположения бит такой-же, как возвращает вторая функция в первом посте
    3. // в T адрес нулевого элемента массива
    4.  
    5. TEST aType,1
    6.    JZ @skip_xxx
    7.    // тут копируется исходное состояние в нулевой элемент массива
    8.    ADD [T],$20
    9. skip_xxx:
    10.    AND aType,11111110b // теперь нулевой бит уже не нужен, его можно выключить, чтобы не мешал
    11.    CMP aType,00000010b // H
    12.    JE @metka_H
    13.    CMP aType,00000100b // V
    14.    JE @metka_V
    15.    CMP aType,00000110b // V,H
    16.    JE @metka_V_H
    17.    CMP aType,00001000b // VH
    18.    JE @metka_VH
    19.    CMP aType,00001010b // VH,H
    20.    JE @metka_VH_H
    21.    CMP aType,00001100b // VH,V
    22.    JE @metka_VH_V
    23.    CMP aType,00001110b // VH,V,H
    24.    JE @metka_VH_V_H
    25. ...
    26.    CMP aType,11111100b // DVH,DV,DH,D,VH,V
    27.    JE @metka_DVH_DV_DH_D_VH_V // переход к 127-й метке
    28.    // если дошли до сюда, значит остался только вариант DVH,DV,DH,D,VH,V,H
    29.    // код для DVH,DV,DH,D,VH,V,H
    30.    // JMP @finish
    31. @metka_H: // 1-я метка
    32.    // код для H
    33.    JMP @finish
    34. @melta_V: // 2-я метка
    35.    // код для V
    36.    JMP @finish
    37. ...
    38. @metka_DVH_DV_DH_D_VH_V: 127-я метка
    39.    // код для DVH,DV,DH,D,VH,V  
    40. @finish:
    Ответить с цитированием  
     

  3. #3  
    Супер модератор Аватар для >Quiet Snow<
    Регистрация
    11.04.2011
    Адрес
    Планета земля
    Сообщений
    3,931
    Сказал(а) спасибо
    1,842
    Поблагодарили 982 раз(а) в 840 сообщениях
    Записей в блоге
    1
    поторопился отправить первый пост
    Поторопились сказано мягко, человек, который хочет чтобы ему помогли, во-первых должен понимать, что 250 строк
    асм кода с SSE 2 никто разбирать не будет, во-вторых, должен понимать, что описание задачи нужно излагать корректно
    и насколько это возможно доступно аудитории, ну а в-третьих, не будет лишним понимание сложности задачи, сопоставимой
    с подтаском коммерческого проекта. Ни за кого говорить не стану, но сам с благотворительностью завязал.


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

    Подскажите, как оптимизировать?
    Могу только советом.

    1) Попробуйте оптимизацию под табличное преобразование, т.е. загрузку уже готовых значений.
    По любому не получится вогнать все данные, но какую-то нетривиальную часть можно таким макаром оптимизировать.
    2) Разрисуйте схемы на листике, какие биты и куда должны переходить для каждого состояния, посмотрите те инструкции,
    которые работают с битами, составьте 10-15 разных алгоритмов, реализуйте их, сделайте бенчмарк.
    3) Попробуйте распараллелить вычисления на несколько потоков(для задачи уровнем выше).
    Обычно не удаётся, но если удастся - будет профит.
    4) Погуглите на тему арифметических трюков, которые преобразуют битовые последовательности, может пригодиться.
    5) Вижу работаете "на ты" с SIMD, посмотрите что может предоставить данный набор вкупе с пунктом 4.
    6) Если всё вышеописанное не прокатит, тогда гуглите оптимизацию по кешу и по буферу команд\данных.
    Корректная работа с железом лишней не бывает, можно ускорить в 1.5-2 раза за счёт этого добра(если исходно был косяк).
    Обучение прикладному программированию(по skype), качественно, недорого, 18+, вопросы в личку.
    «Если вы ничего не сделаете, я уверяю вас, ничего и не произойдёт» © Жак Фреско
    Ограниченно модерирую.
    Ответить с цитированием  
     

Информация о теме
Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Ваши права
  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •