Устройство управления цифровой вычислительной машины Советский патент 1974 года по МПК G06F9/19 

1

Изобретение относится к вычислительной технике и может быть применено в устройствах управления цифровых вычислительных машин, способных интерпретировать алгоритмические языки.

Известное устройство управления по авт. св. № 209040 позволяет интерпретировать алгоритмические языки типа АЛГОЛ-60, т. е. преобразовывать программы, записанные на этих языках в рабочие программы, представленные в символах машинного языка.

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

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

С этой целью в устройство управления по авт. св. № 209040 введен блок автоматической оптимизации программ, что повышает производительность вычислительной системы.

На фиг. 1 изображена блок-схема устройства управления цифровой вычислительной машины совместно с блоками оперативного запоминающего устройства; на фиг. 2-структурная схема блока автоматической оптимиаации программ.

.

Блоки оперативного запоминаюш,его устройства 1 и долговременного запоминающего устройства 2 образуют оперативную и долговременную память цифровой вычислительной машины.

Устройство управления состоит из блока 3 автоматного управления, осуществляющего реализацию алгоритмов интерпретации операторов внутреннего языка, регистра 4 текущего командного элемента программы, хранящего текущий анализируемый элемент программы, схемы 5 приоритета выполнения элементов программы, осуществляющей динамический анализ выполнимости элементов программы, регистра режима 6, в котором содержится признак режима, командного блока 7, осуществляющего микропрограммную реализацию алгоритмов интерпретации операторов внутреннего языка, адресного регистра 8, предназначенного для задания адреса запоминаемых микропрограмм, блока 9 чтения программы, служащего для чтения и выделения элементов рабочей программы, регистров 10- 12 стековой памяти, совместно образующих верхнюю оперативную ступень стековой памяти, блока 13 динамического хранения содержимого оперативных ячеек устройства, предназначенного для динамического хранения содержимого запоминаемых регистров, блока 14, в который входит группа индекс-регистров, счетчиков и сумматор устройства

управления цифровой вычислительной машины.

Предусмотрены также логический блок 15 вычисления булевских функций, регистр 16 следующего элемента программы, предназначенный для хранения следующего, по отношению к текущему, элемента программы, блок 17 динамической адресации, осуществляющий обращение к оперативной памяти по математическому адресу, и блок 18 автоматической оптимизации программ, предназначенный для автоматической оптимизации рабочих программ.

Блок 3 автоматного управления соединен с регистром 4 текущего командного элемента программы, схемой 5 приоритета выполнения элементов программы, регистром режима б, командным блоком 7 и адресным регистром 8.

Командный блок 7 соединен с общей кодовой шиной числа и с адресным регистром 8. С общей кодовой щиной числа соединены также регистр 4 текущего командного элемента программы, регистр режима 6, блок чтения программы 9, оперативные регистры стековой памяти 10-12, блок 13 динамического хранения содержимого оперативных ячеек устройства, блок 14, логический блок 15 вычисления булевских функций и регистр 16 следующего элемента программы.

Командный блок 7, блок чтения программы 9, блок 17 динамического хранения содержимого оперативных ячеек устройства, а также адресные регистры оперативного запоминающего устройства. 1 и долговременного запоминающего устройства 2 соединены с общей кодовой шиной адреса.

Кроме того, между некоторыми регистрами имеется непосредственная связь. В частности, регистр 16 следующего элемента программы соединен с регистром 4 текущего командного элемента программы, схемой ириоретата выполиения элементов программы 5 и блоком 9 чтения Программы; регистр 4 текущего командного элемента программы - С адресным -регистром 8 и оперативным регистром 12 стековой памяти; регистр режима 6 - С схемой 5 приоритета выполнения элементов программы; адресный регистр 8 - с командным блоком 7.

Кроме того, устройство соде,ржит блок 18 автоматической оптимизации программ, который состоит из регистра 19 номера поля, осуществляющего задание номера поля размещения программного элемента в ячейке памяти, регистра 20 формирования, шредназначениого для поячеечного формирования программы, триггера режима 21, задающего режим работы блока автоматической оптимизации программ, И автономного автомата управления 22, управляющего работой блока автоматической оптимизации программ.

Регистр 19 номера поля, регистр формирования 20, триггер режима 21 соединены с общей кодовой шиной числа через выход 23, автономный автомат 22 управления соединен

с блоком 3 автоматного управления по ВХОду 24 и выходу 25 и с блоко м 14 - по выходу 26 блоков автоматической оптимизации программ.

Устройство управления работает следующим образом. Чтение и выделение элементов рабочей программы выполняется блоком 9 чтения программы. Очередной командный элемент прогр:аммы, состоящий в случае языка АЛГОЛ-60 из кода ограничителя и признака операнда, принимается из блока чтения программы на регистр 16 следующего элемента программы.

Выполнение (интерпретация) командных элементов программы осуществляется IB соответствии с приоритетом их выполнимости, проверяемым схемой приоритета выполнения элементов программы. Выполняемый командный элемент программы помещается на регистр 4 текущего командного элемента програ.ммы.

Если командный элемент программы не может быть выполнен, то его операнд переписывается на регистры стековой памяти 10-12, образующие верхнюю оперативную ступень стековой памяти.

В зависимости от интенсивности использования алгоритмы интерпретации реализуются либо в автомате управления 3, либо в командном блоке 7 в виде запоминаемых микропрограмм. Для выполнения микропролрамма вызывается по адресу в адресном регистре 8, адрес в который либо пересылается из регистра 4 текущего командного элемента программы, либо устанавливается блоком 3 автоматного управления.

Командным блоком 7 реализуется система команд, которая имеет адресную структуру и обеспечивает запуск и управление операциями над содержимым регистров устройства управления цифровой вычислительной машины и ячеек оперативной памяти, выполняемых средствами устройства управления цифровой вычислительной машины.

Способ интерпретации командного элемента программы зависит от вида синтаксического понятия языка, которому этот элемент принадлежит. Признак текущего интерпретируемого понятия языка фиксируется в регистре режимов 6.

Устройство управления цифровой вычислительной машины располагает своим сумматором, используемым для модификации адресов, и ограниченной группой счетчиков и регистров, содержащихся в блоке 14.

Широкое Использование стандартных ячеек оперативной памяти в качестве регистров хранения обеспечивается применением в предлагаемом устройстве блока 13 динамического храиения содержимого оперативных ячеек устройства. Адрес требуемой ячейки, принятый с кодовой шины адреса в блок 13 динамического хранения содержимого оперативных ячеек устройства, сравнивается с адресами ячеек, содержимое которых хранится в этом 5 же блоке. При совпадении адресов требуемый

код .выдается из выбранного регистра этого блока «а .кодовую ишну числа. Если среди адресов iB этом блоке нет адреса и.скомой ячейки, содержимое одного из регистров этого блока 1пербнисы вается в соответствующую ячейку памяти, а иа его .место вызывается содержимое требуе-мой ячейки. В результате указанной динамической замены в регистрах блока 13 сохраи.яется содержимое ячеек, которые используются наиболее активно.

Для вычисления переключательных функций, в том числе и от леремениых .выходных сигналов схем устройства управления, в его состав «веден логический блок 15 вычисления булевс1ких функций.

Обращение к блоку 1 онеративной памяти может выполняться как непосредственно по физическому адресу, так и через блок 17 динамической адресации .по математическому адресу. В последнем случае требуемый сегмент информации, если о.н отсутствует в оперативной памяти, вызывается IB нее из внешней па:мяти.

О.птимиза.ция рабочей программы непосредственно в процессе счета задачи осуществляется в Предлагаемом устройстве блоком 18 автоматической оптимизации программы.

Активизация работы данного блока блоком 3 автоматного управления происходит всякий раз при входе в .процессе интерпретации (режим интерпретации) в цикл, она:бженный цризнако.м неоптимального цикла. В режиме отладки программы, ,неза;висимо от признака цикла, передача управления блоку 18 автоматической оптимизации программ лроисходить не будет.

Формальным признаком оптимального или неоптимального цикла ъ рабочей программе задачи могут служить сами операторы цикла for - для неоптимального (исходного) цикла и simple for - для оптимального (оптимизированного) цикла.

В результате работы блока автоматической оптимизации программ 18 последовательно будут выполнены следующими действиями:

формирова.ние оптимизированной программы цикла, в которой все операторы «for заменены на «simple

занесение сформированной оптимизированной программы цикла на место исходной программы цикла в общей программе задачи;

возможная выдача пропраммисту информации о выполненных в программе преобразованиях.

По завершении работы блока 18 автоматической оптимизации программ будет возобновлена интерпретация вновь сформированной программы цикла. Повторная активиза.ция работы данного блока уже не последует вследствие наличия признака оптимальности цикла - оператор «simple for.

Очередная встреча неоптимального цикла в программе вновь вызовет прерывание режима интерпретации и вход в режим оптимизации и т. д.

Формируемая блоком автоматической оптимизации программ оптимизированная програм ма цикла отличается от своего прообраза- исходной программы цикла следующим:

а.инвариантные арифметические подвыражения (выражения) вычисляются и полностью исключаются из записи всей рабочей программы задачи. В последней в виде констант сохраняются лишь результаты вычисления удаляемых подвыражений (выражений);

б.инвариантные булевские подвыражения вычисляются и полностью исключаются из записи всей рабочей программы за.дачи. При этом из рабочей программы может быть полностью исключен булевский терм (выражение), если входящее в него инвариантное подвыражение равно 0/1/;

б. програм.мные записи индексных выражений (помимо выполнения в них действий в соответствии с п. а) выносятся в рабочей программе задачи за пределы циклов, по отнощению к которым эти выражения инварианттны. Внутри циклов эти выражения представляются фиктивными переменными;

г.условные операторы, содержащие инвариантное булевское выражение, в зависимое ги от значения выражения и типа оператора, либо полностью исключаются из рабочей программы задачи, либо заменяются соответствующими безусловными операторами;

д.естественная (скобочная) запись арифметических и булевских выражений в исходной програ.мме цикла преобразуется в оптимизированной программе цикла в запись также формульного вида, расположение элементов которой в больщинстве случаев соответствует последовательности их (элементов) выполнения, что позволяет ускорить процесс решения. Исключение составляют лишь случаи скобочной записи теремов, соседних .в записи исходного выражения.

Информация, выдаваемая программисту блоком автоматической оптимизации программ, содержит исходную програм.му циклов; оптимизированную программу цикла; программные записи исключенных из цикла ариф.метических и булевских .выражений (подвыражений), условных операторов, а также вынесенных из цикла индексных выражений.

Блок 18 автоматической оптимизации программ работает следующим образом (см. фиг. 2). Управление работой рассматриваемого блока осуществляется с помощью автономного автомата управления 22, сигнал запуска которого по входу 24 поступает из блока 3 автоматного упра.вления.

Триггер режима 21 хранит признак текущего режима работы (счет или отладка) и, в случае режима отладки, блокирует передачу управления блоку 18 автоматической оптимизации программ блоком 3 автоматного управления.

В свою очередь, автономный автомат управления 22 1ПО выходу 25 пер&дает управление блоку 3 автоматного управления либо

временно с последующим возвратом - в процеосе оптимизации, либо постоянно - по окончании ее.

Временная передача управления блоку автоматного управления 3 происходит в случае необходимости выполнения в процессе оптимизации функций, связанных с интерпретацией програм.мы. Сюда входит чтение и выделение элементов рабочей программы, а также выполнение командных элементов, которые содержатся в исключаемых из цикла арифметических и булевских подвыражениях (выражениях) .

В лроцесе обработки нрограм1мы цикла с помощью регистра формирования 20 в блоке 1 оперативной памяти осуществляется форМИрование двух массивов программных за-писсй- оптимизированной программы цикла п фрагментов исходной программы цикла, исключенных из нее нли вынесенных в программе за пределы цикла в результате оптимизации.

Регистр 20 формирования разбит на отдельные поля, каждое длиной в байт, с возможностью независимого обращения к ним. Формируемые в регистре 20 фор1мирования программные записи поступают в него по входу 23 через кодовую шину числа из регистра 4 текущего командного элемента и блока 9 чтения прорра.ммы (см. фиг. I).

Задание текущего номера поля формируемой в регистре 20 формирования записи массива осуществляется с помощью регистра 19 номера поля.

Регистр 19 номера ноля и регистр 20 формирования являются оперативными регистрами. Их содержимое хранится в оперативной памяти вместе с соответствующими массивами и вызывается в эти регистры по мере необходимости.

Текущие границы массивов фиксируются по выходу 26 с помощью двух счетчиков из группы счетчиков и регистров блока 14.

Фрагменты арифметических (булевских) выражений, исключаемых из исходной программы цикла, содержат в себе .величины, инвариантные по отношению к охватывающему их циклу.

Для выявления таких величин нроверке на инвариантность должны быть подвергнуты все компоненты арифметических (булевских) выражений, содержащихся в исходной программе цикла.

Применительно к булевским выражениям такая проверка может быть нрервана при обнаружении в булевском терме (выражении) инвариантного подвыражения, равного О /1/. В этом случае исключению из цикла подлежит весь булевский терм (выражение).

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

от цикла -величину. В противном случае нередменная инвариантна (по отношению к охватывающему ее циклу.

С помощью регистра 20 формирования в блоке 1 оперативной памяти формируется служебный массив, содержащий описок величин, которьш в теле цикла присваиваются какие-либо выражения, и адресов начала записи этих выражений IB исходной (рабочей) програММе.

Каждый элемент массива разбит на три информационных поля, формируемый слул ебный массив запоминается в блоке 1 оперативной памяти. Текущая граница массива фиксируется по выходу 26 с помощью счетчика и регистров блока 14.

Проверка на инвариан-гаость состоит в сравнении адреса каждой компоненты выражения с содержимым поля величин присваивания элементов служебного иматевва (первое инфармационное поле).

Адрес текущей компоненты заносится IB адресный регистр 8 из регистра текущего командного элемента программы 4, а элементы служебного массива последовательно выбираются из блока 1 оперативной памяти в регистр 20 формирования через кодовую шину числа.

Сравнение осуществляется с помощью сумматора устройства управления цифровой вычислительной машины, содержащегося в блоке 14. При обнаружении данной компоненты на поле величин присваивания какого-либо элемента служебного массива выражение,присваиваемое ей (адрес начала записи его в программе содержится на втором информационном поле этого же элемента матеива), проверяется на выполнение в нем одного из упомянутых условий зависимости переменной от цикла.

Этот процесс может пoвтQpитьcя многократно, если величине, входящей в присваиваемое Еырал ение, в свою очередь, также присваивается KaiKoe-либо другое выражение.

Для ускорения цикла обращения к служебному массиву, в случае повторного обращения к нему по одной и той же переменной, в структуре элементов массива предусматривается наличие отдельных разрядовнпризнаков, хранящих результат предыдущей проверки (третье информационное поле).

Использование блоком 18 автоматической оптимизации программ некоторых оперативных регистров, счетчиков и сумматора устpoficTBa управления цифровой вычислительной машины представляется возможным благодаря тому, что в режиме оптимизации они оказываются свободными от выполнения своих основных функций, обусловленных режимом интерпретации.

В свою очередь, регистры |блока автоматической оптимизации программ также могут быть оперативно использованы в режиме интерпретации.

Предмет изобретения

1. Устройство управления цифровой вычислительной машины по авт. св. № 209040, о тличающееся тем, что, с целью увеличения производительности, -в него введен блок автоматической оптимизации иропрамм, первый выход которого соединен с блоком perHCTpOiB, второй выход соединен с входом блока автоматного у1пра1вления, третий выход - с кодовой шиной устройства, а вход 1блока автоматической оптимизации программ соединен с выходом блока автоматного управления.

2. Устройство управления по п. 1, отличающееся тем, что блок автоматической оптимизации программ содержит регистр номера поля, (регистр формирования, триггер режима и автономный а1втомат управления, причем выходы автономного автомата управления соединены с первым и вторым выходом, регистр номера поля, регистр формирования и триггер режима соединены с третьим выходом блока, а вход автономного автомата управления соединен с входом блока.