ВУЗ:
Составители:
Предположение о равновероятном исходе в условных операциях
является в большинстве случаев неверным. Рассмотрим два вида опе-
раторов цикла: с постусловием и предусловием, в каждом из которых
выполняются N повторений. Схемы соответствующих алгоритмов по-
казаны на рис. 4.10. Очевидно, что прогнозирование «Переход проис-
ходит всегда» (рис. 4.10,а) дает ошибку 1/N. Аналогично, прогноз
«Переход не происходит никогда» (рис. 4.10,б) выполняется в (N-1)/
случаях.
При прогнозе на основе кода операции для одних команд предпо-
лагается, что переход произойдет, а для других команд – что не
произойдет. Например, для команды перехода по переполнению ло-
гично предположить, что перехода не будет. Для команд с условием
вида ≤0, > 0, = 0 считается, что переход произойдет всегда.
а)
б)
НЕТ
ДА
НЕТ
ДА
n<NN
n:=1
n:=1
Цикл
n:=n+1
Чаще да, чем нет
n>N
Цикл
n:=n+1
Чаще нет, чем да
Р и с. 4.10. Схемы алгоритмов операторов цикла:
а) с постусловием , б) с предусловием
Динамическое предсказание переходов
Решение о наиболее вероятном исходе условной команды прини-
мается процессором в ходе выполнения программы по истории пере-
ходов за предыдущий отрезок времени.
79
Страницы
- « первая
- ‹ предыдущая
- …
- 75
- 76
- 77
- 78
- 79
- …
- следующая ›
- последняя »
