Эффективный способ вычисления выражения MIPS

Question

Я пишу программу для встроенного компьютера, и у меня ОЧЕНЬ мало памяти и вычислительной мощности для работы.

y и a - это двойные числа, хранящиеся в регистрах с плавающей запятой, а x - это массив двойных чисел. Как наиболее эффективно написать это выражение в MIPS?

 y = y + a * x[i];

Answer 1

Я не бегло разбираюсь в ассемблере MIPS, поэтому я не буду беспокоиться о реальных инструкциях MIPS, я буду использовать что-то вроде простого английского языка на полпути к z80/x86 TASM, надеюсь, вы поймете идею.

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

Если вы действительно хотите просто оптимизировать эту единственную строку, мало места для ее придумывания. Просто загрузите x[i], умножьте его на a и добавьте результат к y.

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

Если мы говорим о некотором массиве, он отличается (но вы должны были опубликовать его так), вы можете сохранить много (n-1) умножений, суммируя сначала массив x:

    load r1, x_array_pointer
    load r2, x_array_end_pointer
    load fpr0, zero_value
:loop_sum_x_array
    add fpr0,[r1]
    add r1,size_of_double
    cmp r1,r2
    jump_less loop_sum_x_array ; till whole array is summed
    mul fpr0, *a* ; now multiply sum{x} by "a"
    add fpr0, *y* ; and add initial "y" value
    ; fpr0 contains result

"Алгоритм": y + a * x0 + a * x1 + a * x2 +... = y + a * (x0 + x1 + x2 +...) (если вы раньше не видели этого самостоятельно) Вы писали в SO, вы даже не пытались, или вам 8 лет, или вы должны серьезно заняться мышлением и базовыми математическими упражнениями, потому что это похоже на очевидность. Хех, на самом деле, на этом уровне сложности это просто весело, почему вы позволяете другим в ТАКОМ жить весело? Вы очень щедры, сэр.:))

Память: здесь не используется дополнительная память, только входы y, a и x, вам нужно несколько временных регистров (r1, r2, fpr0) (поэтому, пока вы не выполняете 8-битное упражнение с процессором, у вас должно быть достаточно запасные для этого).

Мощность обработки: сложность алгоритма составляет O(n) (и, поскольку вы должны добавлять каждое значение из массива x, вы не можете превзойти его). Внутренний цикл использует довольно простые инструкции: одно сложение с плавающей запятой, загрузка двойного значения из памяти, увеличение адреса, сравнение и условный переход. Тогда ему нужно буквально одно умножение с плавающей запятой и еще одно дополнение к fp. Доступ к массиву x осуществляется последовательно, поэтому потери в кеше памяти должны быть минимальными.

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

редактировать: как Майкл заметил, что использование C-компилятора - правильный путь, я сделал свой ответ просто для забавы, написав псевдо-ассемблер. Я не уверен, какая у вас платформа, но если она чего-то стоит, должен быть кросс-компилятор для ПК плюс способ получить двоичный результат для цели.