March 31st, 2009

with Cat The Cat

Личная война с коллективным разумом RSDN.

Один из представителей коллективного разума RSDN, имя которого моя память не сохранила для истории, предложил мне в запале битвы подумать, как бы я портировал Speex на Хаскель и чтобы я при этом выиграл. Speex - это кодек речи на основе CELP. Соответственно, контекст задачи - VoIP сервер, кодирующий большое количество каналов, несколько сотен одновременно.

То самое недавнее ж-ж-ж про RC5 и было первым пробным шаром насчёт этого.

Переписывать Speex на Хаскель смысла не имеет. Он написан плохо и непонятно, с функциями в 500 строк. Более того, параллелизация тоже бессмысленна, поскольку достаточно тяжёлых участков выполнения внутри нет - есть вложенные циклы в районе 5x10, и на этом всё.

Я вспомнил про параллельный просчёт двух потоков одновременно и решил, что это стоит обдумать подробней. Большой объём кода с ветвлениями и циклами внутри основных функций кодирования сильно затруднил изучение этого вопроса.

Однако внутри оказались две функции, что выиграли бы от этого преобразования. Их имена Роберт Полсон _spx_lpc и _spx_autocorr. Внутри них находятся циклы, которые можно выполнять параллельно, и которые от этого выиграют. Сложность, как раз, те самые O((1/2)N^2), N=10 операций с плавающей запятой. Вот пример одного внутреннего цикла:
      lpc[i] = r;
      for (j = 0; j < i>>1; j++) 
      {
         // spx_word16_t - это синоним float в случае работы с плавающей точкой.
         spx_word16_t tmp  = lpc[j];
         // #define MAX16(a,b,c) ((a)+(b)*(c))
         // обычное умножение со сложением в случае плавающей точки.
         lpc[j]     = MAC16_16_P13(lpc[j],r,lpc[i-1-j]);
         lpc[i-1-j] = MAC16_16_P13(lpc[i-1-j],r,tmp);
      }
А если массивы скаляров заменить на массивы пар чисел с плавающей запятой (вместо float* передавать float2 *), то циклы можно хорошо положить на SSE.

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

Вот на шаг "автоматически" меня и не хватает. ;)

Неохота возиться.

Я не уверен, что преобразование, которое я мог бы написать на Language.C, поможет где-то ещё, кроме этого кодека. Идея здравая, но узкая.

Поэтому надо придумать другой подвиг, после которого всё же можно будет вернуться на RSDN на щите со щитом.

PS
А делать параллельную обработку более двух потоков одновременно смысла не имеет, наверное. Скорее всего, их параметры будут слишком сильно отличаться, много будет разных отдельных ветвлений.