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

 

(1 (3 437074.

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскит(Социалистииеских

Республик ась-.союзно (61) Зависимое от авт. свидетельства 209040 (22) Заявлено 12.05,71 (21) 1657941/18-24 с присоединением заявки ¹ (32) Приоритет

Опубликовано 25.07.74. Бюллетень № 27

Дата опубликования описания 15.01.75 (51) М. Кл, 6 061 9/19

Государственный комитет

Совета Министров СССР по делам изобретений и открытий (53() УДК 681.326.3 (088.8) (72) Авторы изобретения

Л. Я. Кар ман и 3. Л. Рабинович

Институт кибернетики АН Украинской ССР (71) Заявитель (54) УСТРОЙСТВО УПРАВЛЕНИЯ ЦИФРОВОЙ

ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ

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

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

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

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

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

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

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

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

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

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

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

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

Блок 3 автоматного управления соединен с регистром 4 текущего командного элемента программы, схемой 5 приоритета выполнения элементов программы, регистром режима 6, командным блоком 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 номера поля, осуществляющего задание номера поля paaiMeщения програм много элемента в ячейке памяти, регистра 20 формирования, предназ наченцого для поячеечного формирования программы, триггера режима 21, задающего режим работы блока автоматической оптимизации программ,:и автономного автомата управления 22, управляющего работой блока автоматической оптимизации программ.

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

65 с блоком 3 автоматного управления по входу

24 и выходу 25 и с блоком 14 — по;выходу 26 блоков автоматической оптимизации программ.

Устройство управления работает следующим образом, Чтение и выделение элементов рабочей программы IBbIIIOJIHIIeTcII блоком 9 чтения программы. Очередной командный элемент программы, состоящий в случае языка

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

Выполнение (интерпретация) командных элементов программы осуществляется в соответствии с приоритетом их выполнимости, проверяемым схемой приоритета вы полнения элементов программы. Вы полняемый командный элемент программы помещается на регистр 4 текущего командного элемента:программы, Если командный элемент программы не может быть выполнен, то его операнд переписывается на,регистры стековой памяти 10 — !2, образующие верхнюю оперативную ступень стековой памяти.

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

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

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

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

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

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

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

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

Активизация работы данного блока блоком

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

Формальным признаком оптимального или неоптимального цикла is рабочей программе задачи могут служить сами операторы цикла

for — для неоптимального (исходного) цикла и simple for — для оптимального (оптимизированного) цикла.

В результате работы блока автоматической оптимизации программ 18 последовательно будут выполнены следующими действиями: формирование оптимизированной программы цикла, в которой все операторы «for» заменены IHa «simple for»; занесение сформированной оптимизированной программы цикла на место исходной программы цикла в общей |программе задачи; возможная выдача программисту информации о выполненных в программе преобразованиях.

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

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

437074

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

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

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

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

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

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

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

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

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

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

В процесе обработки программы цикла с помощью регистра формирования 20 в блоке

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

Регистр 20 формирования разбит на отдельные поля, каждое длиной в байт, »с возможностью независи мого ооращения к ним. Формирувмые в регистре 20 формирования программные записи поступают в него Бо входу

23 через кодовую щи ну числа из регистра 4 текущего команд ного элемента и блока 9 чтения программы (см. фиг. 1).

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

19 номера поля.

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

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

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

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

Применительно к булевоким выражениям такая проверка может быть прервана при обнаружении в булевоком терме (выражении) инвариантного подвыражения, равного 0 /1/.

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

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

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

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

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

Адрес текущей компоненты заносится iB адресный регистр 8 из регистра теку щего

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

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

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

40 упомянутых условий зависимости переменной от цикла.

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

Для ускорения цикла обращения к служебному массиву, в случае повторного обращения к нему по одной и той же перемен ной, B структуре элементов массива предусматривается

50 наличие отдельных разрядов;признаков, хранящих результат предыдущей проверки (третье информационное поле).

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

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

437074

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

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

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

5 режима и а втономный автомат управления. причем BbIxoijlû автономного автомата управления соединены с первым и вторым выходом, регистр номера поля, регистр формирования и триггер режима соединены с третьим выхоlo дом блока, а вход автономного автомата управления соединен с входом блока.

437074

Фиг

Составитель С, Громова

Техред А. Дроздова

Редактор Е. Гончар

Корректор О. Тюрина

Типография, пр, Сапунова, 2

Заказ 3474/l3 Изд. Ыа 89 Тираж 624 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, Ж-35, Раушская наб., д. 4/5