Переходы (было AVR vs PIC)

  Привет!

Mon Sep 13 2004 10:39, Harry Zhurov wrote to Alexander Golov:

...

 HZ>     Вот я и спрашиваю про этот goto - ведь это безусловный переход, с ним
 HZ> никаких неожиданностей - переход есть всегда. Так что же мешает во время
 HZ> выполнения собственно перехода (т.е. грубо говоря, прописывания в PC
 HZ> нового адреса) считать инструкцию по новому адресу?

Ничего не мешает, кроме необходимого времени, тех самых 30 нс (или сколько
там?), для доступа к памяти по новому адресу:

                                                 +-- здесь известен новый
адрес
 | выборка add | выполнение add  |               v
               | выборка bra     | выполнение bra |
                                 | выборка PC+1   | выборка по новому адресу |


 HZ> Ведь скорости памяти
 HZ> повышенной тут не требуется - ситуация точно такая же, как и в случае с
 HZ> любой другой командой, когда во время выполнения команды преспокойно
 HZ> считывается следующая.

Нет, для "любой другой команды" выбирается PC+1, а для goto адрес станет
известен с момента начала её исполнения. Спор начался именно с того, когда я
сказал, что PIC не декодирует предварительно выбранные команды (т.е. у него
отсутствует процессинг-конвейер), а только задерживает исполнение первой
команды на время выборки из памяти, общим случаем для которого выбран 1 цикл.

 HZ> Однако тут даже в случае простейшего безусловного перехода требуется
 HZ> дополнительный цикл. Очевидно, что дело не медленности памяти, а в том,
 HZ> что сама следующая команда лежит не за инструкцией собственно перехода, а
 HZ> в другом месте - по новому адресу, и чтобы ее оттуда выцепить _ВО ВРЕМЯ_
 HZ> перехода, надо иметь специальные аппаратные средства, которыми МК не
 HZ> оснащаются, ибо роскошь.

Это не роскошь, а просто балласт. Создавать аппаратные навески для
параллельного предварительного декодирования однословных безусловных
переходов, чтобы в результате поднять производительность на 1% нет никакого
смысла.

 HZ> Вот здесь и кроется торможение при переходе, а не в пресловутой
 HZ> медленности памяти. Hеужели не понятно?! Я уже устал твердить об этом!

Я уже давно не понимаю что ты хочешь доказать. Ты в сущности пересказываешь
мне мои же слова и одновременно снимаешь акценты с проблемы
производительности памяти, пытаясь поставить их на якобы безумных затратах
аппаратной реализации. Я же могу только ещё раз подтвердить: никакого другого
смысла задерживать исполнение команды кроме наличия большого времени выборки
из памяти просто не существует.

...

 HZ>>>     Hу, так и выбирай, кто мешает-то? Если следующую команду ты можешь
 HZ>>> выбрать - хватает быстродействия памяти, то кто мешает выбрать вместо
 HZ>>> нее  ту, которая по новому адресу?

В момент начала декодирования goto начинается выборка следующей (PC+1)
команды. К моменту когда станет ясно, что выполняется goto эта выборка будет
в полном разгаре. Новая выборка требует своих 30 нс, для получения которых
вводится дополнительный цикл.

 AG>> Следующая команда к моменту завершения выполнения условного перехода уже
 AG>> выбрана и её приходится выбрасывать и выбирать новую.

 HZ>     Так выбирай не ту, которая за инструкцией перехода, а ту, которая по
 HZ> новому адресу! Что мешает?

Тогда два цикла потребуется каждой команде уже на линейном коде и только
переходы будут выполняться за 1 цикл.

 HZ> "Ведь переход - это тривиальная вещь".

Естественно, что там может быть нетревиального?

Thu, 23 Sep 2004 16:44:14 +0000 (UTC) Alexander Golov wrote to Harry Zhurov:


HZ>>     Вот я и спрашиваю про этот goto - ведь это безусловный переход, с ним
HZ>> никаких неожиданностей - переход есть всегда. Так что же мешает во время
HZ>> выполнения собственно перехода (т.е. грубо говоря, прописывания в PC
HZ>> нового адреса) считать инструкцию по новому адресу?

AG> Ничего не мешает, кроме необходимого времени, тех самых 30 нс (или сколько
AG> там?), для доступа к памяти по новому адресу:

AG>                                                  +-- здесь известен новый
AG> адрес
AG>  | выборка add | выполнение add  |               v
AG>                | выборка bra     | выполнение bra |
AG>                                 | выборка PC+1   | выборка по новому адресу
AG> |

-----------------------------------------^^^^^^^^

    А почему бы не сделать в этом месте вместо "выборка PC+1" "выборка
bra->addr"? Адрес-то уже известен. Уж в случае безусловных переходов точно
никаких принципиальных трудностей нет. Даже выяснять не надо (как в случае
условного перехода), откуда следующую инструкцию фетчить.


HZ>> Ведь скорости памяти
HZ>> повышенной тут не требуется - ситуация точно такая же, как и в случае с
HZ>> любой другой командой, когда во время выполнения команды преспокойно
HZ>> считывается следующая.

AG> Нет, для "любой другой команды" выбирается PC+1, а для goto адрес станет
AG> известен с момента начала её исполнения.

    Для goto адрес известен после ее выборки. А во время ее выполнения можно
выбрать инструкцию по новому адресу. Тем более, что уже известно перед
выборкой, что следующая команда - абсолютно точно не та, которая PC+1, а та,
которая указана в goto.

AG> Спор начался именно с того, когда я сказал, что PIC не декодирует
AG> предварительно выбранные команды (т.е. у него отсутствует
AG> процессинг-конвейер), а только задерживает исполнение первой команды на
AG> время выборки из памяти, общим случаем для которого выбран 1 цикл.

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

HZ>> Однако тут даже в случае простейшего безусловного перехода требуется
HZ>> дополнительный цикл. Очевидно, что дело не медленности памяти, а в том,
HZ>> что сама следующая команда лежит не за инструкцией собственно перехода, а
HZ>> в другом месте - по новому адресу, и чтобы ее оттуда выцепить _ВО ВРЕМЯ_
HZ>> перехода, надо иметь специальные аппаратные средства, которыми МК не
HZ>> оснащаются, ибо роскошь.

AG> Это не роскошь, а просто балласт. Создавать аппаратные навески для
AG> параллельного предварительного декодирования однословных безусловных
AG> переходов, чтобы в результате поднять производительность на 1% нет никакого
AG> смысла.

    Производители DSP процессоров так не считают. Просто в МК это именно
роскошь, они и так не претендуют на максимальное быстродействие, поэтому им не
нужен такой наворот, увеличивающий стоимость и энергопотребление, бо автомат
этот отнюдь не простой. Только и всего.

    И потом, откуда ты взял 1%? Вот возьми какой-нибудь цикл, где три-четыре
инструкции, одна из которых переход. Сколько % прирост на четырех командах,
если переход выполняется не два, а 1 цикл? Другой вопрос, стОят ли эти 10-25%
прироста скорости дополнительных наворотов в ядре МК. Очевидно, что не стОят,
т.к. производительность и так не стоИт во главе угла.

HZ>> Вот здесь и кроется торможение при переходе, а не в пресловутой
HZ>> медленности памяти. Hеужели не понятно?! Я уже устал твердить об этом!

AG> Я уже давно не понимаю что ты хочешь доказать. Ты в сущности пересказываешь
AG> мне мои же слова и одновременно снимаешь акценты с проблемы
AG> производительности памяти, пытаясь поставить их на якобы безумных затратах
AG> аппаратной реализации. Я же могу только ещё раз подтвердить: никакого
AG> другого смысла задерживать исполнение команды кроме наличия большого
AG> времени выборки из памяти просто не существует.

    Это еще вопрос, кто чьи слова пересказывает. Но не будем на это
отвлекаться. Итак, ты по-прежнему утверждаешь, что единственная причина в
медленности памяти. Я же утверждаю, что принципиальная причина не в медленности
памяти, а в отсутствии в МК специальных аппаратных средств, наличие которых
решает проблему - любой переход может быть выполнен за один цикл. Пресловутая
"медленность" памяти проблемой не является при желании. Кроме того, не забывай,
что бывают и другие процессоры, где программа выполняется из ОЗУ (почти все
DSP), и память там отнюдь не медленная. Но проблема остается. И решается именно
применением предиктора ветвлений. Просто кроме памяти есть еще и остальная
логика, которая тоже имеет конечное быстродействие, и те же проблемы встают в
полный рост. И решаются указанным способом.

    В заключение еще раз (последний): переход является тривиальным _ТОЛЬКО_ в
случае, если оставить его как есть и получить потерю производительности. Любая
попытка довести производительность на переходах до уровня линейных команд
выливается либо в необходимость значительно более быстрой памяти (это может
помочь до некоторого предела скоростей), либо в необходимость городить
специальные аппаратные средства (что кардинально решает проблему в любом
случае). И то, и другое и есть та самая _нетривиальность_, которую порождают
тривиальные переходы.

  Привет!

Sat Sep 25 2004 19:59, Harry Zhurov wrote to Alexander Golov:

...

 AG>> Hичего не мешает, кроме необходимого времени, тех самых 30 нс (или
 AG>> сколько  там?), для доступа к памяти по новому адресу:

 AG>>                                                  +-- здесь известен
 AG>> новый  адрес
 AG>>  | выборка add | выполнение add  |               v
 AG>>                | выборка bra     | выполнение bra |
 AG>>                                 | выборка PC+1   | выборка по новому
 AG>> адресу  |

 HZ> -----------------------------------------^^^^^^^^

 HZ>     А почему бы не сделать в этом месте вместо "выборка PC+1" "выборка
 HZ> bra->> addr"? Адрес-то уже известен. Уж в случае безусловных переходов
 HZ> точно никаких принципиальных трудностей нет. Даже выяснять не надо
 HZ> (как в случае условного перехода), откуда следующую инструкцию фетчить.

В этом момент это не адрес, а абстрактный набор битов, адресом он станет лишь
по завершению первого такта цикла, в котором осуществляется декодирование
команды и станет известно, что это "bra". А подозрение в каждом выбранном
последним наборе битов адреса безусловного перехода грозит тем, о чём я
говорил в прошлый раз -- выбором каждой последующей команды за 2 цикла. Хотя
на самом деле делать выборки по данным в полях команды без предварительного
декодирования вообще нельзя.

...

 AG>> Hет, для "любой другой команды" выбирается PC+1, а для goto адрес станет
 AG>> известен с момента начала её исполнения.

 HZ>     Для goto адрес известен после ее выборки.

Только не известно, что это goto, и что там адрес команды, а не, скажем,
SFR'а.

...

 AG>> Спор начался именно с того, когда я сказал, что PIC не декодирует
 AG>> предварительно выбранные команды (т.е. у него отсутствует
 AG>> процессинг-конвейер), а только задерживает исполнение первой команды на
 AG>> время выборки из памяти, общим случаем для которого выбран 1 цикл.

 HZ>     Hет. Спор начался, когда ты сказал, что переходы тривиальные, а я
 HZ> сказал, что это несколько не так, и именно из-за этого переходы и требуют
 HZ> дополнительных затрат либо в виде времени выполнения, либо в виде
 HZ> дополнительной аппаратуры. В этом и состоит нетривиальность.

Нет, мои слова относились к 2810 у которого из-за конвейера и вайт-стейтов
переход тянет на 4...12 циклов, а здесь мы долго и нудно обсуждаем почему
меня не смущает, что у PIC'ов переход длится 2 цикла; я описал почему (см.
два абзаца выше).

...

 AG>> Это не роскошь, а просто балласт. Создавать аппаратные навески для
 AG>> параллельного предварительного декодирования однословных безусловных
 AG>> переходов, чтобы в результате поднять производительность на 1% нет
 AG>> никакого  смысла.

 HZ>     Производители DSP процессоров так не считают. Просто в МК это именно
 HZ> роскошь, они и так не претендуют на максимальное быстродействие, поэтому
 HZ> им не нужен такой наворот, увеличивающий стоимость и энергопотребление,
 HZ> бо автомат этот отнюдь не простой. Только и всего.

Не знаю, что там считают производители DSP, но у них оптимизация goto не
будет обеспечивать существенного прироста производительности. А ускорение
DSP-алгоритмов в этой части, куда эффективнее при создании специальных
конструкций организации циклов, после чего переход выполняется даже не за 1,
а за 0 циклов. Что мы и наблюдаем в dsPIC30F.

 HZ>     И потом, откуда ты взял 1%? Вот возьми какой-нибудь цикл, где
 HZ> три-четыре инструкции, одна из которых переход.

Близко к 100% -- условный. А мы говорим про безусловные, более того, только
однословные, т.е. только bra, ещё возможно: rcall и return.

...

 HZ>     Это еще вопрос, кто чьи слова пересказывает. Hо не будем на это
 HZ> отвлекаться. Итак, ты по-прежнему утверждаешь, что единственная причина в
 HZ> медленности памяти.

Медленность -- причина, а всё остальное -- следствия конкретных путей
преодоления связанных с ней проблем.

 HZ> Я же утверждаю, что принципиальная причина не в
 HZ> медленности памяти, а в отсутствии в МК специальных аппаратных средств,

Для PIC'ов специальные аппаратные средства позволят разобраться лишь с
однословными безусловными переходами.

 HZ> наличие которых решает проблему - любой переход может быть выполнен за
 HZ> один цикл.

Чтобы разобраться с остальными переходами нужно строить абсолютно другой
командный цикл с конвейерным декодированием и специальными аппаратными
навесками смотрящими вперёд по конвейеру.

 HZ> Пресловутая "медленность" памяти проблемой не является при
 HZ> желании.

Значит ни у кого нет желания, ибо все на этой памяти безбожно тормозят и
единственный на всех способ преодоления -- кэш того или иного вида.

...

 HZ>     В заключение еще раз (последний): переход является тривиальным
 HZ> _ТОЛЬКО_ в случае, если оставить его как есть и получить потерю
 HZ> производительности.

Для PIC'ов переход это простое копирование адреса в PC и вставка одного nop.
Единственное радикальное средство ускорения -- подкладывание полноразмерного
скоростного ОЗУ под Flash и полное копирование кода перед запуском. Любые
другие варианты работают в одних случаях и не работают в других, т.е. вносят
дисперсию в результаты выполнения и в общем случае требуют закладываться на
максимум.

...

 HZ> И то, и другое и есть та
 HZ> самая _нетривиальность_, которую порождают тривиальные переходы.

Ну да, только вся "нетривиальность" наворотов у 2810 приводит к переходам
даже без вайт-стейтов за 4/7 циклов, а "тревиальность" у PIC за 2 цикла в
любых условиях.