УСТРОЙСТВО ДЛЯ УСТРАНЕНИЯ ИЗБЫТОЧНЫХ ВЫЧИСЛЕНИЙ

Полезная модель относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании вычислительных систем (далее - ВС).
Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 1291957 СССР кл. G06F 7/00, опубл. 23.02.87, БИ №7).
Недостатком указанного элемента является узкая область применения, обусловленная отсутствием средств для формирования размещения в системах с линейной организацией по критерию минимизации интенсивности обмена данными между модулями размещаемой задачи.
Наиболее близким к предлагаемому устройству по технической сущности является устройство для оценки размещения элементов, содержащее матрицу элементов однородной среды, состоящую из элементов однородной среды, блоки подсчета единиц, блок нахождения максимума, сумматор, блок памяти, вход записи исходного гиперграфа, вход управления перестановкой столбцов, вход управления перестановкой строк, вход управления записью в блок памяти, выходы оценки текущего размещения, информационный выход и вход установки (а.с. 1430949 СССР, кл. G06F 7/00, 15/20, опубл. 15.10.88, БИ №38).
Недостатком указанного устройства является узкая область применения, обусловленная отсутствием средств для устранения избыточных вычислений, встречающихся в теле программы и увеличивающих скорость их выполнения.
Технической задачей полезной модели является увеличение скорости выполнения программ за счет устранения избыточных вычислений, встречающихся в теле программы.
Техническая задача решается тем, что в устройство для оценки размещения по критериям суммарной длины ребер и максимальной длины ребра, содержащее матрицу из m строк и n столбцов элементов однородной среды, n блоков подсчета единиц, блок нахождения максимума, сумматор, блок памяти, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи устройства, индикаторные выходы элементов j-го столбца (j=1, 2, …, n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен с j-м входом блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходом максимальной длины ребра и выходом суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, …, m) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, дополнительно введен блок устранения избыточности вычислений, содержащий матрицу I входных переменных, матрицу О выходных переменных, регистр хранения константы единицы, RS-триггер выбора режима работы устройства, три элемента сравнения, элемент неравенства, два элемента задержки, реверсивный счетчик, счетчик адреса, два промежуточных счетчика, вычитатель, 4 элемента ИЛИ, причем выход матрицы входных переменных соединен с первым входом второго элемента сравнения, выход матрицы выходных переменных соединен с первым входом первого элемента сравнения, вторые входы всех элементов сравнения соединены с выходом регистра хранения константы единицы, первый вход третьего элемента сравнения, как и второй вход элемента неравенства, соединены с выходом вычитателя, первый вход которого соединен с выходом первого промежуточного счетчика, а так же с четвертым входом четвертого элемента ИЛИ, выход элемента неравенства соединен с первым входом второго элемента ИЛИ и отрицательным входом реверсивного счетчика, реверсивный выход элемента неравенства соединен со входом вычитателя, входом сигнала увеличения первого промежуточного счетчика и вторым входом первого элемента ИЛИ, выход первого элемента сравнения соединен с входом сигнала увеличения второго промежуточного счетчика, и через элемент задержки со вторым входом второго элемента ИЛИ, инверсный выход первого элемента сравнения соединен с R входом триггера выбора режима, выход реверсивного счетчика соединен с первым входом четвертого элемента ИЛИ, входами промежуточных счетчиков, и первым входом третьего элемента ИЛИ, выход второго промежуточного счетчика соединен со вторыми входами третьего и четвертого элементов ИЛИ, выход первого элемента ИЛИ соединен с входом увеличения инверсного счетчика, выход второго элемента ИЛИ соединен с третьим входом четвертого элемента ИЛИ, выход третьего элемента ИЛИ соединен с входом a1 матрицы входных переменных, выход четвертого элемента ИЛИ соединен с входом a1 матрицы выходных переменных, выход счетчика адреса соединен со входами а2 матриц входных и выходных переменных.
Сущность полезной модели поясняется чертежами, где на фиг. 1 изображена функциональная схема устройства для устранения избыточных вычислений; фиг. 2 поясняет принцип использования и целесообразность применения предложенного устройства, фиг. 3 описывает работу блока 23.
Предлагаемое устройство может использоваться в области проектирования ВС, например, при проектировании и эксплуатации многопроцессорных систем.
В ВС исходный фрагмент программы задается в следующем виде:
i
ij
1. Исходный алгоритм (фиг. 2а) представляется графом взаимодействия задач: G=<Х,Е>, где X - множество вершин графа G, вершины x∈X которого соответствуют операторам программы, а дуги e∈Е представляют информационные связи.
2. Матрица входных переменных , где , , характеризующая присутствие j-й переменной во входном наборе i-го оператора (фиг. 2б), N - число операторов последовательной программы,.
3. Матрица выходных переменных , где , , характеризующая присутствие j-й переменной в выходном наборе i-го оператора (фиг. 2в).
Основная идея вытекает из определения избыточных вычислений. Способ основан на проверке, используется ли переменная в теле программы до ее переопределения.
Первоначально выполняется поиск в первой строке матрицы О единичного значения, соответствующего первому оператору. В данном случае это значение соответствует переменной ′а′. Далее следует проверить, используется ли эта переменная в следующих операторах. Причем анализ необходимо вести до момента, когда переменной ′а′ будет присвоено новое значение. Для этого последовательно просматриваются элементы столбца, соответствующие переменной ′а′ в матрице I, начиная со следующей строки. В результате просмотра находим, что I(2,1)=0, следовательно, переменная ′а′ во втором операторе не используется. При этом, при выполнении второго оператора значение переменной ′а′ не переопределяется (О(2,1)=0).
Просматривая далее, находим, что I(3,1)=1, следовательно, переменная ′а′ используется в третьем операторе. Это означает, что при выполнении третьего оператора значение ′а′ переопределяется (O(3,1)=1), следовательно, выполнение первого оператора не является обязательным и соответствующие ему строки матрицы входных и выходных переменных можно исключить.
Аналогично происходит обработка всех оставшихся единиц в матрице выходных переменных.
В результате работы алгоритма в данном примере будут исключены операторы 1 и 4, при этом после перекомпоновки программа будет иметь следующий вид (рис. 1):
Модифицированные матрицы входных и выходных переменных представлены в таблицах 1 и 2..
Применение данной методики позволяет находить и исключать избыточные вычисления, причем наибольший эффект может быть достигнут при ее использовании применительно к телу циклов с большим числом итераций. Таким образом, предлагаемое устройство расширяет область применения за счет введения средств для устранения избыточных вычислений, встречающихся в теле программы.
Матрицы входных и выходных переменных отображаются однородной средой, содержащей N×М элементов. Функционирование однородной среды аналогично прототипу. При поступлении сигнала от внешнего устройства управления (далее - ВУУ) последовательно происходит моделирование перестановки пары строк матрицы входных переменных, матрицы выходных переменных, а также матрицы достижимости. Предлагаемое устройство вычисляет значения элементов из матриц входных и выходных переменных и выдает полученные перестроенные матрицы входных и выходных переменных в ВЗУ для принятия решения о дальнейших действиях ВС.
В отличие от прототипа, где формирование выполняется по двум критериям - суммарной длине ребер и максимальной длине ребра, предлагаемое устройство дополнительно расширяет область применения устройства за счет введения средств для устранения избыточных вычислений, встречающихся в теле программы.
Устройство для устранения избыточных вычислений (фиг. 1) содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блоки 2.1-2.n подсчета единиц, блок 3 нахождения максимума, сумматор 4, блок 5 памяти, причем входы управления перестановкой столбцов матрицы 1 элементов однородной среды соединены с входом 7 управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы 1 элементов однородной среды соединены с входом 8 управления перестановкой строк устройства, входы установки матрицы 1 элементов однородной среды соединены с входом 13 установки устройства, информационные входы матрицы 1 элементов однородной среды соединены с входом 6 записи устройства, индикаторные выходы элементов j-го столбца (j=1, 2, …, n) матрицы 1 элементов однородной среды соединены с входом блока 2.j подсчета единиц, выход которого соединен с j-м входом блока 3 нахождения максимума и j-м входом сумматора 4, выходы которых соединены с выходом 10 максимальной длины ребра устройства и выходом 11 суммарной длины ребер устройства соответственно, вход управления записью блока 5 памяти соединен с входом 9 управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, …, m) матрицы 1 элементов однородной среды соединены с i-м информационным входом блока 5 памяти, выход которого соединен с информационным выходом 12 устройства, а также дополнительно введенный блок устранения избыточности вычислений, содержащий матрицу I входных переменных 27, матрицу О выходных переменных 28, регистр хранения константы единицы 29, RS-триггер выбора режима работы устройства 30, три элемента сравнения 31,32,35, элемент неравенства 34, два элемента задержки 36-37, реверсивный счетчик 38, счетчик адреса 39, два промежуточных счетчика 40-41, вычитатель 42, 4 элемента ИЛИ 43-46, причем выход матрицы входных переменных 27 соединен с первым входом второго элемента сравнения 32, выход матрицы выходных переменных 28 соединен с первым входом первого элемента сравнения 31, вторые входы всех элементов сравнения соединены с выходом регистра хранения константы единицы 29, первый вход третьего элемента сравнения 35, как и второй вход элемента неравенства 34, соединены с выходом вычитателя 42, первый вход которого соединен с выходом первого промежуточного счетчика 40, а так же с четвертым входом четвертого элемента ИЛИ 46, выход элемента неравенства 34 соединен с первым входом второго элемента ИЛИ 44, и отрицательным входом реверсивного счетчика 38, реверсивный выход элемента неравенства 34 соединен со входом вычитателя 42, входом сигнала увеличения первого промежуточного счетчика 40 и вторым входом первого элемента ИЛИ 43, выход первого элемента сравнения 31 соединен с входом сигнала увеличения второго промежуточного счетчика 41, и через элемент задержки 36 со вторым входом второго элемента ИЛИ 44, инверсный выход первого элемента сравнения 31 соединен с R входом триггера выбора режима 30, выход реверсивного счетчика 38 соединен с первым входом четвертого элемента ИЛИ 46, входами промежуточных счетчиков 40, 41, и первым входом третьего элемента ИЛИ 45, выход второго промежуточного счетчика 41 соединен со вторыми входами третьего и четвертого элементов ИЛИ 45, 46, выход первого элемента ИЛИ 43 соединен с входом увеличения инверсного счетчика 38, выход второго элемента ИЛИ 44 соединен с соединен с третьим входом четвертого элемента ИЛИ 46, выход третьего элемента ИЛИ 45 соединен с входом a1 матрицы входных переменных 27, выход четвертого элемента ИЛИ 46 соединен с входом a1 матрицы выходных переменных 28, выход счетчика адреса 39 соединен со входами а2 матриц входных и выходных переменных 27, 28.
Назначение элементов и блоков устройства (фиг. 1) для устранения избыточных вычислений.
Матрица 1 элементов однородной среды предназначена для моделирования процесса решения задач линейного размещения и трассировки.
Блоки 2.1-2.n подсчета единиц предназначены для преобразования кодов с индикаторных выходов элементов соответствующих столбцов матрицы 1 в двоичные коды.
Блок 3 нахождения максимума предназначен для выделения максимального кода из множества кодов на его входах.
Сумматор 4 предназначен для суммирования n двоичных кодов.
Блок 5 памяти предназначен для хранения наилучшего на данный момент варианта размещения.
Вход 6 записи устройства служит для записи матрицы, представляющей размещаемую схему (граф).
Вход 7 управления перестановкой столбцов устройства предназначен для приема сигнала от ВУУ о перестановке столбцов.
Вход 8 управления перестановкой строк устройства предназначен для приема сигнала от ВУУ о перестановке строк.
Вход 9 управления записью устройства необходим для приема сигнала «Запись» от ВУУ. По этому сигналу в блок 5 памяти заносится текущий вариант размещения из матрицы 1.
Выход 10 максимальной длины ребра устройства необходим для выдачи значения максимальной длины ребра на ВУУ.
Выход 11 суммарной длины ребер устройства необходим для выдачи значения суммарной длины ребер на ВУУ.
Информационный выход 12 устройства необходим для выдачи варианта размещения, находящегося в блоке 5 памяти, на ВУУ.
Вход 13 установки устройства необходим для синхронизации записи информации в элементы матрицы 1.
Генератор 14 импульсов предназначен для формирования импульсной последовательности, синхронизирующей работу блока 24.
Мультиплексор 15 выбора элемента предназначен для подачи с выходов триггеров 19.1-19.m информации о загрузке канала на вход дешифратора 16 выбора элемента.
Дешифратор 16 выбора элемента служит для выдачи информации о загрузке канала на вход блока 23.
Дешифратор 17 выбора строки предназначен для выбора строки матрицы 1 элементов однородной среды.
Группа 18.1-18.m элементов ИЛИ служат для объединения сигналов с выходов группы элементов 22.1-22.m запрета соответственно.
Группа 19.1-19.m триггеров необходимы для хранения информации о загрузке канала между соответствующими элементами матрицы 1.
Счетчик 20 строк предназначен для выбора очередной обрабатываемой строки из матрицы 1 элементов однородной среды.
Счетчик 21 столбцов необходим для выбора очередного элемента из выбранной строки матрицы 1 элементов однородной среды.
Группа 22.1-22.m блоков элементов запрета служит для выбора строки из матрицы 1 элементов однородной среды.
Блок 23 избыточных вычислений предназначен для устранения избыточных переменных в программах.
Блок 24 поиска необходим для поиска и устранения избыточных переменных в последовательных наследуемых программах.
Группа 25.1, 25.2, …, 25.m элементов ИЛИ служит для объединения сигналов с выходов элементов группы 221-22.m элементов запрета и последующей подачи на S-входы группы 19.1-19.m триггеров соответственно.
Выход 26 переполнения предназначен для подачи сигнала о переполнении счетчика 20 строк и одновременно служит сигналом о завершении работы блока 24 поиска и подачи соответствующего сигнала на ВУУ.
Назначение элементов блока 23 избыточных вычислений состоит в следующем.
Блок 23 избыточных вычислений служит для выделения избыточных переменных в последовательных наследуемых программах.
Матрица 27 I входных переменных предназначена для хранения данных о входных переменных подпрограммы.
Матрица 28 О выходных переменных необходима для хранения выходных переменных, являющихся результатом оператора подпрограммы.
Регистр 29 константы единицы необходим для хранения кода значения единицы.
Триггер 30 режима служит для выбора режима работы схемы. В единичном состоянии устройство работает в режиме поиска избыточности рассматриваемой переменной. В нулевом состоянии происходит выбор очередной строки матрицы 28 выходных переменных.
Первый 31, второй 32 и третий 35 элемент сравнения предназначены для сравнения выбранного кода со значением единицы.
Элемент 34 неравенства необходим для анализа неравенства двух входных кодов.
Первый 36 и второй 37 элемент задержки предназначен для задержки тактового импульса.
Реверсивный 38 счетчик необходим для подсчета номера обрабатываемых строк матрицы 28 О выходных переменных.
Счетчик 39 адреса предназначен для подсчета адреса столбца выбранной строки матрицы 28 О выходных переменных.
Первый 40 и второй 41 промежуточный счетчик служит для промежуточного подсчета обрабатываемых переменных матрицы 28 выходных переменных.
Вычитатель 42 предназначен для подсчета количества вхождений обрабатываемой переменной в анализируемом участке программы.
Первый 43 элемент ИЛИ необходим для объединения сигналов с выхода третьего 35 элемента сравнения и элемента 34 неравенства.
Второй 44 элемент ИЛИ служит для объединения сигналов с выхода первого 31 элемента сравнения и элемента 34 неравенства.
Третий 45 элемент ИЛИ необходим для объединения сигналов с выхода второго 41 промежуточного счетчика и реверсивного 38 счетчика.
Четвертый 46 элемент ИЛИ предназначен для подачи адреса на вход a1 матрицы 28 О выходных переменных.
Выход 47 неравенства служит для подачи сигнала на ВУУ о несовпадении входных кодов на входе второго 32 элемента сравнения.
Выход 48 несовпадения необходим для подачи сигнала на ВУУ о несовпадении входных кодов на входе третьего 35 элемента сравнения.
Вход 49 установки служит для установки регистра 29 константы единицы единичное значение.
Вход 50 запуска служит для подачи тактовых импульсов на вход генератора 14 импульсов.
Инверсный 51 выход триггера 30 режима предназначен для подлачси сигнала о сбросе триггера в нулевое состояние.
Вход 52 установки служит для установки в единичное состояние триггера 30 режима.
Вход 53 счета служит для подачи тактовых импульсов на вход счетчика 39 адреса, который поступает на второй а2 вход матрицы 28 выходных переменных, на первом a1 входе которого присутствует другой адрес с выхода четвертого 46 элемента ИЛИ.
Работа блоков 1, 2, 3, 4 и 5 подробно описана в прототипе и поэтому здесь не рассматривается.
Первоначально в матрице 28 выходных переменных и матрице 27 выходных переменных хранятся описания входных и выходных переменных, соответствующих анализируемому фрагменту последовательной наследуемой программы, которая была получена от ведущей ЭВМ хост-компьютера. В регистре 29 хранится код значения единицы, который подается на второй вход первого 31 элемента сравнения. В счетчике 42 хранится значение числа N, обозначающее количество операторов исходной анализируемой программы. Этот код поступает на второй вход элемента 34 неравенства. Триггер 30 режима находится в состоянии единицы. Это означает, что на прямом его выходе присутствует значение единицы, которое подается на разрешающий е-вход элемента 31 сравнения, разрешая его работу. На инверсном выходе триггера 30 режима присутствует нулевой потенциал. На первом входе второго 32 элемента сравнения присутствует код выходной переменной с выхода матрицы 27 выходных переменных, а на втором входе второго 32 элемента сравнения присутствует код константы единицы с выхода регистра 29 константы единицы, но из-за отсутствия тактовых импульсов дальнейшего анализа не происходит. В реверсивном 38 счетчике присутствует код единицы («0…01»), который одновременно является первым адресом для матрицы 28 выходных переменных, который проходит через четвертый элемент ИЛИ. В первом 40 промежуточном счетчике хранится код («0…01»). В счетчике 21 столбца хранится код единицы («0…01»). В счетчике 20 строки содержится код единицы («00...01»), поэтому код единицы с его выхода поступает на дешифратора 17 и на его первом выходе появляется единичный импульс, который подается на входы блока 22.1 группы 22.1-22.m блоков элементов запрета и разрешает поступление кодов с выходов элементов 1.1, 1.2, …, 1.n матрицы 1 элементов однородной среды Эти коды поступают на соответствующие входы блока 22.1 группы 22.1-22.m блоков элементов запрета и передаются на их выходы. Эти коды проходят через соответствующие элементы 25.1, 25.2, …, 25m и подаются на S-входы группы 19.1-19.m триггеров, устанавливаясь при этом в соответствующее состояние.
Предлагаемое устройство предназначено для оценки размещения по критериям суммарной длины ребер, максимальной длины ребра и критерию максимальной загрузки канала между смежными модулями, а также для устранения избыточных вычислений, встречающихся в телах программ.
Оценка размещения по критериям суммарной длины ребер и максимальной длины ребра происходит следующим образом. Информация с индикаторных выходов элементов каждого столбца матрицы 1 поступает в соответствующие блоки подсчета единиц. Блок 2.i (i=1, 2, …, n) выдает двоичное число (код), равное количеству поступивших на его вход единиц. Полученное число далее поступает на входы сумматора 4 и блока 3 нахождения максимума, соответствующие данному блоку подсчета единиц. В результате на выходе 10 устройства образуется код (оценка) максимальной длины ребра, а на выходе 11 - код (оценка) суммарной длины ребер, отвечающие текущему варианту размещения схемы (содержащемуся в матрице 1). Полученные оценки далее поступают на ВУУ, где происходит их сравнение с предыдущими значениями. В случае улучшения оценок ВУУ подает импульс (сигнал «Запись») на вход 9 управления записью устройства и текущий вариант размещения переписывается в блок 5 памяти из матрицы 1. Более подробно рассмотренный режим работы устройства описан в прототипе.
Устранение избыточных вычислений происходит следующим образом. После выполнения очередной перестановки строк на индикаторных выходах элементов матрицы 1 появляются сигналы, соответствующие новому варианту размещения. Одновременно с этим запускается генератор 14 импульсов и начинается работа блока 24 устранения избыточных вычислений.
Появление единицы на входе 50 запуска запускает генератор 14 тактовых импульсов, в результате чего тактовый импульс поступает на счетный вход счетчика 21 и по переднему фронту увеличивает его содержимое на единицу до кода двойки («0…10»). Код двойки с выхода счетчика 21 поступает на управляющие входы мультиплексора 15 и дешифратора 16. Так как на соответствующие управляющие входы подан код двойки, то единичный потенциал с выхода триггера 25.2 поступает на вход мультиплексора 15 и далее на его выход. Оттуда он подается на вход дешифратора 16 и на его втором выходе появляется единичный потенциал, который поступает на вход блока 23 устранения избыточных вычислений и с этого момента нача начинается его работа.