Сортировка / переупорядочение зависимых инструкций для обработки двух выпусков

Question

Я попытался написать алгоритм сортировки, чтобы изменить порядок команд для процессора с двумя выпусками (Cell SPU). Один из способов получения двойной инструкции обработки не должен зависеть от предшествующей ей инструкции (другой связан с отдельными конвейерами, но я сосредоточен на инструкциях в одном конвейере). Я понимаю, что это будет слишком много для компилятора, и я не нашел то, что мне нужно при поиске. В большинстве случаев это может быть сделано вручную, но алгоритм сортировки должен обеспечивать наименьшее "количество последовательностей" (число или зависимые инструкции, которые следуют друг за другом).

У меня вопрос, было ли это или что-то подобное было сделано раньше? Есть ли оптимизированный подход?

Простой пример псевдокода вдвое меньше времени команды (входы: i1, i2, i3):

v1 = i1 ^ i2; - #single-issued
v2 = v1 | i2; \ #v2,v3 dual-issued
v3 = i1 & i3; / #v2,v3 dual-issued
v4 = v3 & i2; - #single-issued

можно записать как:

v1 = i1 ^ i2; \ #v1,v3 dual-issued
v3 = i1 & i3; / #v1,v3 dual-issued
v2 = v1 | i2; \ #v2,v4 dual-issued
v4 = v3 & i2; / #v2,v4 dual-issued

Вот реализация Python, которую я создал, которая рекурсивно меняет порядок команд для достижения наименьшего "количества последовательностей".

reorder.py
http://pastebin.com/dt8eWy3H

образец t8-1.h
http://pastebin.com/w0DYg8ff

Answer 1

Я закончил тем, что использовал "Визуализатор сборки" asmVis.jar Ява-программа для просмотра разделов сборки, которые можно оптимизировать, и я переупорядочил инструкции вручную. Я значительно увеличил скорость функции ассемблера, используя как нечетную, так и четную сторону почти в каждом цикле инструкций (инструкции двойного назначения).

TODO: добавить ссылку на github к источнику

Answer 2

Хотя я не могу говорить конкретно о Cell, планирование кода - это АБСОЛЮТНО то, что компилятор должен сделать для вас.

Компиляторы будут переупорядочивать инструкции, вставлять в NOPS по мере необходимости и делать все возможное, чтобы обеспечить хороший график кодов для вас. Обычно я бы посоветовал вам взглянуть на параметры "mtune" для вашего компилятора (они позволяют вам точно сказать вашему компилятору, как выглядит ваш процессор), но, поскольку вы кодируете для Cell, он должен уже знать, что делать (но проверьте руководство компилятора, чтобы быть уверенным).

Краткий взгляд на компилятор GCC для SPU здесь показывает такие параметры, как:

-mdual-nops=n
    By default, GCC inserts nops to increase dual issue when 
    it expects it to increase performance. n can be a value from 
    0 to 10. A smaller n inserts fewer nops. 10 is the default, 0 
    is the same as -mno-dual-nops. Disabled with -Os. `

Как программист, ваша работа состоит в том, чтобы обеспечить достаточное количество ILP в вашем коде, чтобы получить хорошее планирование. Старайтесь избегать ветвлений, избегайте операций с большим временем ожидания на критическом пути и т. Д., И все будет в порядке. Проанализируйте objdump ваших критических циклов, чтобы убедиться, что код запланирован по вашему желанию. Компилятор очень умен, но может потребовать немного уговорить.