Всего на сайте:
248 тыс. 773 статей

Главная | Информатика

Использующая таблицу переходов  Просмотрен 165

 

Ячейка памяти Команда на машин­ном языке Команда в симво­лической форме Комментарий
. . . . . . . . .    
LRI 1 Загрузка регистров Н, L начальным
адресом таблицы переходов
LRI 2  
   
F4 RSC Сброс триггера С
F2 RTR Сдвиг младшего разряда аккумулятора в
      в триггер С
JCN Если С=1, то содержимое Н, L указы-
вает на начальный адрес нужной ветви
программы
F5 IHL Если С = 0, содержимое пары
100А F5 IHL регистров Н, L увеличивается дважды на 1 и
100В JMP 1 и указывает на
100С следующий начальный адрес
100D    
100Е 1F MOV 0 from F Замена в Н, L указателя на элемент таблицы переходов самим
100F 5F IHL адресом перехода
F5 MOV 2 from F  
MOV 1 from 0  
F9 JHL Переход на нужную ветвь программы
. . . . . . . . .    
Таблица переходов:    
Начальный адрес ветви 1
 
Начальный адрес ветви 2
 
. . . . . . . . .    
200Е Начальный адрес ветви 8
200F    

 

 

В какой-то момент по команде перехода в ячейке 1006 микропро­цессор выйдет из цикла на команду в ячейке 100Е. В этот момент со­держимое пары регистров Н, L будет указывать на строку, содержа­щую начальный адрес нужной программной ветви. Четыре команды служат для загрузки этого начального адреса в регистры Н, L. По­скольку начальный адрес в строке таблицы замещает находившийся в Н, L указатель на саму строку, нужно особо позаботиться о том, чтобы не испортить указатель до того, как будет использована нахо­дящаяся в нем информация. Поэтому старшие разряды начального адреса ветви сначала переносятся в регистр 0, а не прямо в регистр Н. После этого указатель в Н, L увеличивается на 1, чтобы указывать на младшие разряды начального адреса, и эти разряды выбираются в регистр L, поскольку указатель больше не нужен. Затем в регистр Н переносятся старшие разряды начального адреса из регистра 0. На­конец, выполняется команда перехода по косвенному адресу, которая заносит содержимое регистров Н, L на программный счетчик, в ре­зультате чего начнется выполнение нужной программной ветви.

Недостатки обоих рассмотренных методов заключаются в том, что перебор всех возможных альтернатив делается последовательно. Это может потребовать заметного времени, особенно при большом числе альтернатив. Задержку можно уменьшить, если процедуру поиска альтернативы организовать в виде двоичного дерева. При такой про­цедуре последовательно отбрасывается половина оставшихся альтер­натив, пока не останется единственная.

Для случая с таблицей переходов, например, на первом шаге нужно проверить, лежит ли нужный начальный адрес в первой чет­верке адресов или во второй. Затем на втором шаге нужно установить, принадлежит ли адрес первой или второй паре в выбранной на первом шаге четверке. На третьем шаге выбор сузится до одного адреса. Легко видеть, что такая процедура требует только трех, а не восьми шагов, соответствующих худшему случаю в описанной ранее процедуре. В об­щем случае, если число альтернатив равно N, то при поиске по двоич­ному дереву число шагов будет равно наименьшему целому числу, которое больше или равно Iog2 N. При больших N это дает значительную экономию по сравнению с последовательным перебором альтернатив.

Предыдущая статья:Разветвлений Следующая статья:Вход в подпрограмму и выход из подпрограммы
page speed (0.0169 sec, direct)