![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Использующая таблицу переходов
В какой-то момент по команде перехода в ячейке 1006 микропроцессор выйдет из цикла на команду в ячейке 100Е. В этот момент содержимое пары регистров Н, L будет указывать на строку, содержащую начальный адрес нужной программной ветви. Четыре команды служат для загрузки этого начального адреса в регистры Н, L. Поскольку начальный адрес в строке таблицы замещает находившийся в Н, L указатель на саму строку, нужно особо позаботиться о том, чтобы не испортить указатель до того, как будет использована находящаяся в нем информация. Поэтому старшие разряды начального адреса ветви сначала переносятся в регистр 0, а не прямо в регистр Н. После этого указатель в Н, L увеличивается на 1, чтобы указывать на младшие разряды начального адреса, и эти разряды выбираются в регистр L, поскольку указатель больше не нужен. Затем в регистр Н переносятся старшие разряды начального адреса из регистра 0. Наконец, выполняется команда перехода по косвенному адресу, которая заносит содержимое регистров Н, L на программный счетчик, в результате чего начнется выполнение нужной программной ветви. Недостатки обоих рассмотренных методов заключаются в том, что перебор всех возможных альтернатив делается последовательно. Это может потребовать заметного времени, особенно при большом числе альтернатив. Задержку можно уменьшить, если процедуру поиска альтернативы организовать в виде двоичного дерева. При такой процедуре последовательно отбрасывается половина оставшихся альтернатив, пока не останется единственная. Для случая с таблицей переходов, например, на первом шаге нужно проверить, лежит ли нужный начальный адрес в первой четверке адресов или во второй. Затем на втором шаге нужно установить, принадлежит ли адрес первой или второй паре в выбранной на первом шаге четверке. На третьем шаге выбор сузится до одного адреса. Легко видеть, что такая процедура требует только трех, а не восьми шагов, соответствующих худшему случаю в описанной ранее процедуре. В общем случае, если число альтернатив равно N, то при поиске по двоичному дереву число шагов будет равно наименьшему целому числу, которое больше или равно Iog2 N. При больших N это дает значительную экономию по сравнению с последовательным перебором альтернатив.
|