Оптимизация математики для массивов поплавков в Ada 95 с GNAT - PullRequest
Новая
       17

Оптимизация математики для массивов поплавков в Ada 95 с GNAT

0 голосов
/ 26 марта 2010

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

При выполнении более 100 лотов данных объемом 1 секунда программа занимает 35 секунд (или 35%), выполняя эту функцию в цикле. Цикл тестирования рассчитан специально с Ada.RealTime. Данные предварительно генерируются, поэтому большая часть времени выполнения определенно находится в этом цикле.

Как мне улучшить код, чтобы сократить время обработки до минимума?

Код будет работать на Intel Pentium-M, который представляет собой P3 с SSE2. 

package FF is new Ada.Numerics.Generic_Elementary_Functions(Float);

N : constant Integer := 820;
type A is array(1 .. N) of Float;
type A3 is array(1 .. 3) of A;

procedure F(state  : in out A3;
            result :    out A3;
            l      : in     A;
            r      : in     A) is
   s : Float;
   t : Float;
begin
   for i in 1 .. N loop
      t := l(i) + r(i);
      t := t / 2.0;
      state(1)(i) := t;
      state(2)(i) := t * 0.25 + state(2)(i) * 0.75;
      state(3)(i) := t * 1.0 /64.0 + state(2)(i) * 63.0 /64.0;
      for r in 1 .. 3 loop
         s := state(r)(i);
         t := FF."**"(s, 6.0) + 14.0;
         if t > MAX then
            t := MAX;
         elsif t < MIN then
            t := MIN;
         end if;
         result(r)(i) := FF.Log(t, 2.0);
      end loop;
   end loop;
end;

psuedocode для тестирования 

create two arrays of 80 random A3 arrays, called ls and rs;
init the state and result A3 array
record the realtime time now, called last
for i in 1 .. 100 loop
   for j in 1 .. 80 loop
      F(state, result, ls(j), rs(j));
   end loop;
end loop;
record the realtime time now, called curr
output the duration between curr and last

Ответы [ 5 ]

1 голос
/ 26 марта 2010

Может быть быстрее заменить t := FF."**"(s, 6.0) + 14.0; с t := s ** 6 + 14.0; Возведение в степень с плавающей точкой, вероятно, сделано с журнал и опыт. - Джонатан

1 голос
/ 26 марта 2010

Сначала позвольте мне попытаться исправить мой ответ:

Это должно быть FF. "****" (s, 6.0) и s ** 6 (не FF. "*" (S, 6.0) и s * 6) в моем ответе. [Странно ... редактор все еще пытается удалить * из моего текста.]

Я только что проверил исходный код, на который указал Марк С. делай с ** 6!

Я добавлю только то, что я ожидаю, что некоторое улучшение будет делать s ** 6 самостоятельно, используя s2: = s * s и s_to_the_6: = s2 * s2 * s2; - Джонатан

1 голос
/ 26 марта 2010

Я вернусь сюда к Марку С. Я использовал gprof с Gnat раньше. Это может быть сложно настроить, но это работает как чемпион. Если хотите, вы можете использовать его для получения% от времени выполнения, используемого каждой строкой кода выше.

Я мог бы сделать некоторые предложения (например, предварительный расчет 63.0 / 64.0), но хороший оптимизатор уже должен делать большинство из них. Вам нужно выяснить, что он не делает в особенно загруженных процессором линиях, и ускорить это.

Просматривая код, я предполагаю, что профилировщик покажет вам, что операции возведения в степень и ведения журнала занимают львиную долю времени. Если бы вы могли найти способ предварительно рассчитать некоторые из этих вещей, которые могли бы помочь. Это забегает вперед. Профиль !

0 голосов
/ 14 апреля 2010

Возможно, вы захотите посмотреть на

тип A3 - массив (1 .. N, 1 .. 3) с плавающей точкой;

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

  state(i)(1) := t; 
  state(i)(2) := t * 0.25 + state(i)(2) * 0.75; 
  state(i)(3) := t * M1 + state(i)(2) * M2;

Использование переименования в 

  cur_state : array (1..3) of Float renames state(i);

, а затем 

  cur_state := (t, t * 0.25 + cur_state(2) * 0.75, t * M1 + cur_state(2) * M2)

может дать компилятору несколько советов по оптимизации.

0 голосов
/ 31 марта 2010

Следующие улучшения кода сократили время выполнения до 8 секунд.

Затем, добавив параметры командной строки -O3 и -mtune = pentium-m и -msse2, вы сократили время выполнения до 0,8 секунды.

Мои подозрения:

  • Log (x, y) реализован в виде Log (x) / Log (y), что является дорогостоящим, если y является постоянным. (7sec)
  • Мощность (x, y) реализована в виде цикла; а условные и скачки дорогие. (20сек)

процедура "**" может быть ... 

r := x; for i in 2 .. y loop; r := r * x; end loop; return r;

Пересмотренная функция 

package FF is new Ada.Numerics.Generic_Elementary_Functions(Float); 

N : constant Integer := 820; 
type A is array(1 .. N) of Float; 
type A3 is array(1 .. 3) of A; 

procedure F(state  : in out A3; 
            result :    out A3; 
            l      : in     A; 
            r      : in     A) is 
   -- Keep the Log of 2 so it is not recalculated
   ONE_ON_LOG_TWO : constant Float := 1 / FF.Log(2.0); 
   M1 : constant Float := 1.0 / 64.0;
   M2 : constant Float := 63.0 / 64.0;
   s : Float; 
   t : Float; 
begin 
   for i in 1 .. N loop 
      t := l(i) + r(i); 
      -- Multiply Not Divide
      t := t * 0.5; 
      state(1)(i) := t; 
      state(2)(i) := t * 0.25 + state(2)(i) * 0.75; 
      state(3)(i) := t * M1 + state(2)(i) * M2; 
      for r in 1 .. 3 loop 
         s := state(r)(i);
         -- Since we know the power hared code the multiply.
         t := s * s * s * s * s * s + 14.0; 
         if t > MAX then 
            t := MAX; 
         elsif t < MIN then 
            t := MIN; 
         end if; 
         -- Don't use Log(x,y) in a loop when y is constant. '
         result(r)(i) := FF.Log(t) * ONE_ON_LOG_TWO; 
      end loop; 
   end loop; 
end;
...