Для процессоров, работающих с векторами, накладные расходы ниже. Количество циклов уменьшается в N раз, где N — количество одновременно обрабатываемых элементов массива. Однако, проблему это не снимает. Да ещё добавим расходы на границу массива, если число элементов не укладывается целое число раз в вектор процессора.
Для уменьшения накладных расходов можно было бы обрабатывать элементы массива как свободные переменные, то есть составить программу, которая обрабатывала бы элементы попарно, потом результаты попарно и т.д. Но такой способ возможен только для фиксированного размера массива. Да и размер программы может оказаться значительным.
Однако последний способ или его модификация больше подходит для многоядерных архитектур, где можно было бы организовать обработку массива частями на разных ядрах или процессорах параллельно. Но здесь опять проявится ограничение в компиляции программы. Если размер массива динамически изменяется, то сложно или невозможно будет автоматически распараллеливать его обработку на разные ядра. Программа имеет фиксированное число команд и указателей. Или придётся разрешить модификацию программного кода. Что очень чревато.
А вот теперь обратимся к мультиклеточному процессору. Рассматривалась ли авторами процессора идея «мультикоманды»? Что я имею в виду. Это обычная машинная команда или группа команд, но она имеет динамический повторитель. В коде программы она занимает несколько байт, а во время исполнения программы дублируется в буфер команд заданное количество раз в зависимости от длины обрабатываемого массива. Дублировать можно сразу всю последовательность, что нецелесообразно, а можно сделать столько копий, сколько клеток в процессоре или даже ограничить количеством клеток, которые участвуют в этой программе. Каждую копию этой команды может обрабатывать своя клетка совершенно независимо и параллельно.
Понятно, что каждая последующая копия команды обрабатывает следующий или следующие элементы массива своей клеткой. Этот механизм почти избавлен от накладных расходов на организацию циклов, не увеличивает размер компилированной программы, позволяет распараллелить обработку элементов массива на любое число клеток процессора. Кроме того, одна из клеток будет выполнять крайнюю операцию обработки массива и отслеживать необходимость дальнейшей обработки. При достижении требуемых условий, действия с массивом можно прекратить. Конечно, выбор и местоположение мультикоманды и команды завершения определит компилятор, а дублировать команду будет уже процессор.
Если нет патентов и публикаций данной идеи. Этой публикацией я заявляю на неё авторское право от 17 мая 2015 года.
В данный момент автор публикации готов принять предложение работы.
Комментарии (15)
tzlom
18.05.2015 11:28+1Если там суммирование от 1 до 2^32 буфер считать резиновым? Что бы это масштабировалось я вижу пути:
1-вложенный обработчик команд, но архитектурно это выбивается из понятия инструкции, получается такая мегаинструкция которая контролирует весь процессор во время своей работы неопределённой длительности
2-иметь лимитированный повторитель и обвешивать его доп логикой, но скорее всего эта логика сведёт выигрыш в ноль
3-повторитель внутри решает разворачивается ли он в набор повторителей меньшей кратности или же комманд, но чтобы обслужить такую схему нужно усложнять ядра или буфер инструкций
0й вариант — регистр для счетчика повторителя и контроль передачи управления на следующую команду, тут вопрос в том когда происходит выполнение следующей команды, иначе имеем не «повторитель» а рекурсивный условный оператор
SvetlyNik Автор
18.05.2015 16:37Контроль передачи управления остаётся мультиклеточный — по готовности источника и приёмника. Клетки сами будут выбирать, готова ли команда к исполнению. Просто на момент обработки массива буфер перестанет пополняться новыми командами из программной памяти, а имеющиеся будут повторяться, пока имеют этот признак повторить. (См. ответ на комментарий ниже)
krufter
18.05.2015 13:47Потенциально преимущества: уменьшение занимаемой памяти программ и ускорение загрузки команд.
Только вопрос в какую логику это выливается в ядре, получится ли это реализовать просто.
Сейчас у нас есть .rept .endr в ассемблере для простого повторения команды.
Но иногда, бывает нужно не просто повторять команду, а повторять с измененной ссылкой на аргументы.
Но, чтобы разработчики ядра это сделали аппаратно необходимо доказать ощутимую пользу от этого усложнения ядра.
Буфер у нас в каждой клетке на 64 команды.
P.S. пишете на verilog, vhdl; svn, git для вас знакомые слова, умеете пользоваться потактовыми симуляторами, есть опыт разработки устройств на fpga, отдельных блоков, отправляйте своё резюме генеральному директору(почта есть в контактах на сайте мультиклет). Мы находимся в г, Екатеринбург.SvetlyNik Автор
18.05.2015 16:27Логику ядра для такого рода команд я уже начал продумывать. Но это всё надо согласовывать с существующей логикой, чем я, к сожалению, пока ещё не владею. А польза будет ощутимая. Команды не надо будет перезагружать, только менять у них аргументы, оставляя в буфере в той же последовательности. Только на начальном этапе надо будет в буфере разместить копии этих команд в количестве клеток группы, которые заняты в этом процессе. Так как работа выполняется над массивом, его адрес (адрес памяти) присутствует в ядре процессора, его надо увеличить или уменьшить и использовать. Аппаратно в ядро процессора необходимо будет добавить компаратор конечного адреса массива. Но что-то мне подсказывает, что необходимая структура уже есть, остаётся только использовать с неё сигнал для окончания дублирования команд. Пока ещё ничего не придумал для нечётной границы массива. Возможно, придётся подставлять фиктивный аргумент, но лучше провалить этот элемент массива к заключительной команде, как результат. Естественно, в буфере команд надо будет добавить индикатор мультикоманды. Ещё уточнение: дублировать или повторять команды в буфере с изменением аргументов надо будет только те, которые считывают аргументы из памяти. Те команды, которые используют их результаты достаточно только повторять.
Halt
То что вы описали, называется loop unrolling. Точнее частная его реализация. Вот только, какого рода операции вы собираетесь таким образом параллелить? Как например это поможет с операциями редукции и чем это принципиально отличается от существующих вариантов?
P.S.: А трижды текст был повторен чтобы выглядеть более значительным или чтобы понятнее стало? :)
SvetlyNik Автор
Большая дорога начинается с первого шага. Если несколько команд будут работать с массивами параллельно, то уже будет большой выигрыш в производительности. А обычные циклы никто отменять не будет.
P.S. Три экземпляра текста меня тоже удивили. Это вопрос к разработчикам сайта.
Halt
Приведите пожалуйста конкретный пример программы и итогового кода, который дает выигрыш (в чем? ценой чего?).
SvetlyNik Автор
Программа не покажет, как её будет выполнять мультиклеточный процессор. А выигрыш можно показать на пальцах.Суммируем массив из 100 элементов:
1 Выборка команды
2 Установка счётчика в 100
3 Выборка команды
4 Обнуление суммы
5 Выборка команды
6 Выборка начального адреса
7 Выборка команды
8 Выборка элемента
9 Выборка команды
10 Суммирование
11 Выборка команды
12 Декремент счётчика
13 Выборка команды
14 Проверка счётчика и переход
Каждый пункт примем за 1 такт. Пункты 7-14 повторяются 100 раз. Итого 806 тактов.
Теперь рассмотрим работу мультиклеточного процессора. Тоже грубо.
1 Выборка команды Выборка начального адреса
2 Выборка команды Выборка конечного адреса и Выборка начального адреса
3 Выборка команды суммирования массива и Выборка конечного адреса
4 Размножение команды суммирования
Теперь все действия выполняются параллельно четырьмя клетками. Команды перемежаются по мере готовности предыдущих сумм.
100 тактов выборки элементов массива, 50 попарных суммирований элементов массива четырьмя клетками — 13 тактов 25 попарных суммирований предыдущих сумм четырьмя клетками — 7 тактов, 13 попарных суммирований предыдущих сумм четырьмя клетками — 4 такта, 7 попарных суммирований предыдущих сумм четырьмя клетками — 2 такта и ещё 1 такт на получение окончательной суммы.
Таким образом имеем 4+100+2=106 тактов затраченного времени и 300 тактов для выполнения других команд.
Выигрыш примерно в 8 раз во времени при использовании ~ 25% ресурса процессора.
Не ругайте меня за большой текст.
jcmvbkbc
Процессоры с пайплайном при выполнении линейного кода выполняют выборку команды параллельно с исполнением предыдущей команды. А при наличии логики предсказания переходов и при нелинейном выполнении выборка команд будет запараллелена. Т.е. не 806 такт, а 404 + ?, т.е. примерно в 4 (количество работающих клеток) раз меньше, чем мкльтиклеточный вариант, как и ожидалось.
SvetlyNik Автор
Про более сложные и энергоёмкие процессоры с предвыборкой и предсказаниями согласен. Но пересчитаем такты снова.
404 такта Неймановский процессор
106 тактов одна четвёртая часть мультиклеточного процессора
Выигрыш во времени в 4 раза (в среднем ОДНОЙ клеткой) При этом остальные клетки могут выполнить такой же объём вычислений ещё три раза в пределах этого же промежутка времени.
Я для расчёта принял, что будем затрачивать один такт на выборку из памяти. Если учесть предвыборку памяти, то картинка становится ещё привлекательней. Четыре клетки за один такт загрузят 4 элемента массива. Тогда на загрузку ВСЕГО массива потребуется 25 тактов и формула будет выглядеть так: 4+(25+24 на суммирование)+7= 60 тактов. При этом варианте клетки будут загружены на 35%-40%.
60 тактов против 404 серьёзная заявка.
24 такта добавлены для использования уже загруженных данных. Клетки не могут загружать новые данные, они должны сначала просуммировать загруженные.
Halt
Ваш подход напоминает CISC. В свое время тоже считалось, что инструкции должны быть сложными и их должно быть много на все [сложные] случаи жизни. А на деле оказалось, что проще и быстрее (во всех смыслах) сделать много мелких микроопераций, даже если их придется повторять несколько раз. Даже имеющиеся сложные инструкции вроде rep movsw (куда уж проще — копирование регионов без какой либо обработки) на деле разбиваются на микрооперации, вместо того чтобы крутить мегакоманду.
Сравнивать только такты некорректно, поскольку утрируя, можно получить 4 CISC такта вместо 16 RISC, в то время как реализация в железе такого процессора сможет работать лишь на частоте в 100 раз меньшей.
jcmvbkbc
Может быть, но это быстро упрётся в ширину внешней шины.
Вообще, то что вы описываете больше похоже на задачу для SIMD: если действия выполняемые параллельно одинаковы, нет нужды в дупликации како-либо аппаратной логики, кроме вычислительной.
krufter
Не факт, что в результате получится такой большой выйгрыш, но теоретически Ваша мультикоманда может ускорить вычисления. Но вопрос еще в записи и указании, что ссылка должна меняться соответствующим образом, но это все решаемо. Если будете продумывать логику, то может Вам пригодиться система команд побитовая multiclet.com/community/projects/examples/wiki/R1_ISA
krufter
Обратился по факту этого вопроса к руководству, комментарий Стрельцова:
Эта команда была сделана в проекте Синпьютер, но была выполота, т.к. не дала такого эффекта. Говорит, что это не первый случай когда такое предлагают, но смысла добавления данной команды, кроме экономии памяти программ особого нет. У нас выборка за такт, чтение внутренней памяти за такт.