Comments 15
То что вы описали, называется loop unrolling. Точнее частная его реализация. Вот только, какого рода операции вы собираетесь таким образом параллелить? Как например это поможет с операциями редукции и чем это принципиально отличается от существующих вариантов?
P.S.: А трижды текст был повторен чтобы выглядеть более значительным или чтобы понятнее стало? :)
P.S.: А трижды текст был повторен чтобы выглядеть более значительным или чтобы понятнее стало? :)
Большая дорога начинается с первого шага. Если несколько команд будут работать с массивами параллельно, то уже будет большой выигрыш в производительности. А обычные циклы никто отменять не будет.
P.S. Три экземпляра текста меня тоже удивили. Это вопрос к разработчикам сайта.
P.S. Три экземпляра текста меня тоже удивили. Это вопрос к разработчикам сайта.
Приведите пожалуйста конкретный пример программы и итогового кода, который дает выигрыш (в чем? ценой чего?).
Программа не покажет, как её будет выполнять мультиклеточный процессор. А выигрыш можно показать на пальцах.Суммируем массив из 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% ресурса процессора.
Не ругайте меня за большой текст.
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% ресурса процессора.
Не ругайте меня за большой текст.
1 Выборка команды
2 Установка счётчика в 100
3 Выборка команды
4 Обнуление суммы
…
Каждый пункт примем за 1 такт.
Процессоры с пайплайном при выполнении линейного кода выполняют выборку команды параллельно с исполнением предыдущей команды. А при наличии логики предсказания переходов и при нелинейном выполнении выборка команд будет запараллелена. Т.е. не 806 такт, а 404 + ε, т.е. примерно в 4 (количество работающих клеток) раз меньше, чем мкльтиклеточный вариант, как и ожидалось.
Про более сложные и энергоёмкие процессоры с предвыборкой и предсказаниями согласен. Но пересчитаем такты снова.
404 такта Неймановский процессор
106 тактов одна четвёртая часть мультиклеточного процессора
Выигрыш во времени в 4 раза (в среднем ОДНОЙ клеткой) При этом остальные клетки могут выполнить такой же объём вычислений ещё три раза в пределах этого же промежутка времени.
Я для расчёта принял, что будем затрачивать один такт на выборку из памяти. Если учесть предвыборку памяти, то картинка становится ещё привлекательней. Четыре клетки за один такт загрузят 4 элемента массива. Тогда на загрузку ВСЕГО массива потребуется 25 тактов и формула будет выглядеть так: 4+(25+24 на суммирование)+7= 60 тактов. При этом варианте клетки будут загружены на 35%-40%.
60 тактов против 404 серьёзная заявка.
24 такта добавлены для использования уже загруженных данных. Клетки не могут загружать новые данные, они должны сначала просуммировать загруженные.
404 такта Неймановский процессор
106 тактов одна четвёртая часть мультиклеточного процессора
Выигрыш во времени в 4 раза (в среднем ОДНОЙ клеткой) При этом остальные клетки могут выполнить такой же объём вычислений ещё три раза в пределах этого же промежутка времени.
Я для расчёта принял, что будем затрачивать один такт на выборку из памяти. Если учесть предвыборку памяти, то картинка становится ещё привлекательней. Четыре клетки за один такт загрузят 4 элемента массива. Тогда на загрузку ВСЕГО массива потребуется 25 тактов и формула будет выглядеть так: 4+(25+24 на суммирование)+7= 60 тактов. При этом варианте клетки будут загружены на 35%-40%.
60 тактов против 404 серьёзная заявка.
24 такта добавлены для использования уже загруженных данных. Клетки не могут загружать новые данные, они должны сначала просуммировать загруженные.
Ваш подход напоминает CISC. В свое время тоже считалось, что инструкции должны быть сложными и их должно быть много на все [сложные] случаи жизни. А на деле оказалось, что проще и быстрее (во всех смыслах) сделать много мелких микроопераций, даже если их придется повторять несколько раз. Даже имеющиеся сложные инструкции вроде rep movsw (куда уж проще — копирование регионов без какой либо обработки) на деле разбиваются на микрооперации, вместо того чтобы крутить мегакоманду.
Сравнивать только такты некорректно, поскольку утрируя, можно получить 4 CISC такта вместо 16 RISC, в то время как реализация в железе такого процессора сможет работать лишь на частоте в 100 раз меньшей.
Сравнивать только такты некорректно, поскольку утрируя, можно получить 4 CISC такта вместо 16 RISC, в то время как реализация в железе такого процессора сможет работать лишь на частоте в 100 раз меньшей.
Четыре клетки за один такт загрузят 4 элемента массива. Тогда на загрузку ВСЕГО массива потребуется 25 тактов
Может быть, но это быстро упрётся в ширину внешней шины.
Вообще, то что вы описываете больше похоже на задачу для SIMD: если действия выполняемые параллельно одинаковы, нет нужды в дупликации како-либо аппаратной логики, кроме вычислительной.
Не факт, что в результате получится такой большой выйгрыш, но теоретически Ваша мультикоманда может ускорить вычисления. Но вопрос еще в записи и указании, что ссылка должна меняться соответствующим образом, но это все решаемо. Если будете продумывать логику, то может Вам пригодиться система команд побитовая multiclet.com/community/projects/examples/wiki/R1_ISA
Обратился по факту этого вопроса к руководству, комментарий Стрельцова:
Эта команда была сделана в проекте Синпьютер, но была выполота, т.к. не дала такого эффекта. Говорит, что это не первый случай когда такое предлагают, но смысла добавления данной команды, кроме экономии памяти программ особого нет. У нас выборка за такт, чтение внутренней памяти за такт.
Эта команда была сделана в проекте Синпьютер, но была выполота, т.к. не дала такого эффекта. Говорит, что это не первый случай когда такое предлагают, но смысла добавления данной команды, кроме экономии памяти программ особого нет. У нас выборка за такт, чтение внутренней памяти за такт.
Если там суммирование от 1 до 2^32 буфер считать резиновым? Что бы это масштабировалось я вижу пути:
1-вложенный обработчик команд, но архитектурно это выбивается из понятия инструкции, получается такая мегаинструкция которая контролирует весь процессор во время своей работы неопределённой длительности
2-иметь лимитированный повторитель и обвешивать его доп логикой, но скорее всего эта логика сведёт выигрыш в ноль
3-повторитель внутри решает разворачивается ли он в набор повторителей меньшей кратности или же комманд, но чтобы обслужить такую схему нужно усложнять ядра или буфер инструкций
0й вариант — регистр для счетчика повторителя и контроль передачи управления на следующую команду, тут вопрос в том когда происходит выполнение следующей команды, иначе имеем не «повторитель» а рекурсивный условный оператор
1-вложенный обработчик команд, но архитектурно это выбивается из понятия инструкции, получается такая мегаинструкция которая контролирует весь процессор во время своей работы неопределённой длительности
2-иметь лимитированный повторитель и обвешивать его доп логикой, но скорее всего эта логика сведёт выигрыш в ноль
3-повторитель внутри решает разворачивается ли он в набор повторителей меньшей кратности или же комманд, но чтобы обслужить такую схему нужно усложнять ядра или буфер инструкций
0й вариант — регистр для счетчика повторителя и контроль передачи управления на следующую команду, тут вопрос в том когда происходит выполнение следующей команды, иначе имеем не «повторитель» а рекурсивный условный оператор
Контроль передачи управления остаётся мультиклеточный — по готовности источника и приёмника. Клетки сами будут выбирать, готова ли команда к исполнению. Просто на момент обработки массива буфер перестанет пополняться новыми командами из программной памяти, а имеющиеся будут повторяться, пока имеют этот признак повторить. (См. ответ на комментарий ниже)
Потенциально преимущества: уменьшение занимаемой памяти программ и ускорение загрузки команд.
Только вопрос в какую логику это выливается в ядре, получится ли это реализовать просто.
Сейчас у нас есть .rept .endr в ассемблере для простого повторения команды.
Но иногда, бывает нужно не просто повторять команду, а повторять с измененной ссылкой на аргументы.
Но, чтобы разработчики ядра это сделали аппаратно необходимо доказать ощутимую пользу от этого усложнения ядра.
Буфер у нас в каждой клетке на 64 команды.
P.S. пишете на verilog, vhdl; svn, git для вас знакомые слова, умеете пользоваться потактовыми симуляторами, есть опыт разработки устройств на fpga, отдельных блоков, отправляйте своё резюме генеральному директору(почта есть в контактах на сайте мультиклет). Мы находимся в г, Екатеринбург.
Только вопрос в какую логику это выливается в ядре, получится ли это реализовать просто.
Сейчас у нас есть .rept .endr в ассемблере для простого повторения команды.
Но иногда, бывает нужно не просто повторять команду, а повторять с измененной ссылкой на аргументы.
Но, чтобы разработчики ядра это сделали аппаратно необходимо доказать ощутимую пользу от этого усложнения ядра.
Буфер у нас в каждой клетке на 64 команды.
P.S. пишете на verilog, vhdl; svn, git для вас знакомые слова, умеете пользоваться потактовыми симуляторами, есть опыт разработки устройств на fpga, отдельных блоков, отправляйте своё резюме генеральному директору(почта есть в контактах на сайте мультиклет). Мы находимся в г, Екатеринбург.
Логику ядра для такого рода команд я уже начал продумывать. Но это всё надо согласовывать с существующей логикой, чем я, к сожалению, пока ещё не владею. А польза будет ощутимая. Команды не надо будет перезагружать, только менять у них аргументы, оставляя в буфере в той же последовательности. Только на начальном этапе надо будет в буфере разместить копии этих команд в количестве клеток группы, которые заняты в этом процессе. Так как работа выполняется над массивом, его адрес (адрес памяти) присутствует в ядре процессора, его надо увеличить или уменьшить и использовать. Аппаратно в ядро процессора необходимо будет добавить компаратор конечного адреса массива. Но что-то мне подсказывает, что необходимая структура уже есть, остаётся только использовать с неё сигнал для окончания дублирования команд. Пока ещё ничего не придумал для нечётной границы массива. Возможно, придётся подставлять фиктивный аргумент, но лучше провалить этот элемент массива к заключительной команде, как результат. Естественно, в буфере команд надо будет добавить индикатор мультикоманды. Ещё уточнение: дублировать или повторять команды в буфере с изменением аргументов надо будет только те, которые считывают аргументы из памяти. Те команды, которые используют их результаты достаточно только повторять.
Что, только фон-неймановской?
А у гарвардской разве нет такого же «камня»?
А у гарвардской разве нет такого же «камня»?
Only those users with full accounts are able to leave comments. Log in, please.
Мультиклеточный микропроцессор, «макроциклы» для работы с массивами