ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА ДЛЯ ИНТЕРВАЛЬНЫХ ВЫЧИСЛЕНИЙ Российский патент 1994 года по МПК G06F15/16 

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

Известны способы реализации алгоритмов интервальной арифметики с помощью специальных подпрограмм ЭВМ общего назначения. При этом интервальные операции выполняются на один-два порядка медленнее обычных арифметических операций. Известны многопроцессорные вычислительные системы (например, [1,2] ), позволяющие повысить производительность (в том числе при интервальных вычислениях) за счет параллельного выполнения вычислений на нескольких процессорах. Однако ввиду ограничений распараллеливания быстродействие ЭВМ для интервальных вычислений остается низким (в 4. . . 8 раз ниже номинального).

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

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

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

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

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

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

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

Вычислительная система для интервальных вычислений содержит процессоры 1, 2, 3, оперативные запоминающие устройства 4, 5, 6, устройство 7 ввода-вывода, вход 8 кода операций системы, блок 9 микропрограммного управления, блок 10 постоянной памяти с выходами u1, u2, 1, 2, первый сдвигающий регистр 11, второй сдвигающий регистр 12, арифметико-логические блоки 13, 14, 15 процессоров, блоки 16, 17, 18 локальной памяти и коммутаторы 19-30.

На фиг. 2 t - время, t_o - время выполнения арифметической операции, t_ио - время выполнения интервальной арифметической операции, 31 - диаграмма работы первого процессора, 32 - диаграмма работы второго и третьего процессоров, 33 - считывание команды первого процессора, 34 и 35 - выборка в первом процессоре соответственно первого и второго операндов, 36 - выполнение операции в первом процессоре, 37 - запись кода операции в первый сдвигающий регистр 11 (регистр кода операции), 38 - сдвиг кода в регистре 11 кода операций вправо, 39 и 40 - запись кодов знаков соответственно первого и второго операндов во второй сдвигающий регистр 12 (регистр знаков операндов), 41 - сдвиг вправо кода в регистре 12 знаков операндов, 42 - считывание из блока постоянной памяти управляющих кодов u1, u2, 1, 2, 43 - считывание команды второго и третьего процессоров, 44 и 45 - выборка первого и второго операндов во втором и третьем процессорах, 46 - выполнение команды во втором и третьем процессорах.

Вычислительная система выполняет интервальные арифметические операции над парами приближенных чисел А, В, заданных в виде интервалов своих граничных значений в соответствии с алгоритмами
A+B= [a_н, а_в] +[b_н, b_в] = [a_н+b_н, а_в+b_в] ;
A-B= [а_н, а_в] -[b_н, b_в] = [а_н-b_в, а_в- b_н] ;
A˙B= [a_н, а_в] ·[b_н, b_в] = [min { a_н˙b_н, а_н˙b_в, а_в˙b_н, а_в˙b_в} , (1)
max { a_н˙b_н, а_н˙b_в, а_в˙b_н, а_в˙b_в} ] ;
A/B= [a_н, а_в] /[b_н, b_в] = [min { a_н/b_н, а_н/b_в, а_в/b_н, а_в/b_в} ,
max { a_н/b_н, а_н/b_в, а_в/b_н, а_в/b_в} ] , где а_н, а_в - соответственно нижняя и верхняя границы числа А;
b_н, b_в - нижняя и верхняя границы числа В;
min { . . . } и max { . . . } - соответственно минимальное и максимальное из чисел, записанных в скобках.

В процессоре 1 (в арифметико-логическом блоке 13) программно или схемно реализуется округление до ближайшего по модулю машинного числа, в процессоре 2 (в арифметико-логическом блоке 14) - округление до ближайшего меньшего числа (округление с "недостатком") и в процессоре 3 (в арифметико-логическом блоке 15) результаты арифметических операций округляются до ближайшего большего числа (округление с "избытком"). Вычислительная система работает так, что процессор 1, используя оперативное запоминающее устройство 4, выполняет обычные приближенные (ввиду округлений) вычисления по программе, хранящейся в памяти устройства 4. Процессор 2 при этом вычисляет в соответствии с алгоритмами (1) нижние границы приближенных результатов, для хранения которых используется оперативное запоминающее устройство 5 или блок 17 локальной памяти, а процессор 3 вычисляет верхние границы чисел, размещая их в оперативной памяти устройства 6 или в блоке 18 локальной памяти.

Вычисление нижних и верхних границ результатов арифметических операций в процессорах 2 и 3 обеспечивается соответствующей выборкой нижних и верхних границ каждого из операндов из оперативной памяти устройств 5, 6 или из блоков 17, 18 локальной регистровой памяти, что обеспечивается с помощью коммутаторов 19-30, управляемых выходными кодами блока 10 постоянной памяти. Логика работы блока постоянной памяти и коммутаторов поясняется таблицей.

Процессор 1 работает в соответствии с диаграммой 31 (фиг. 2). После поступления на вход 8 кода операции системы очередной операции (например, из оперативного запоминающего устройства 4), т. е. считывания команды - 33, в 2n-разрядный регистр 11 кода операции записывается n-разрядный код операции (поступающий из блока микропрограммного управления на вход кода операции арифметико-логического блока) - 37 и код в регистре 11 сдвигается на n разрядов вправо - 38. При этом код выполняемой операции (сложения, вычитания, умножения или деления) размещается в n старших разрядах регистра 11, а n младших разрядов освобождаются для приема кода операции следующей команды (операции). После выборки первого операнда - 34 (из оперативной или локальной памяти) код его знака ("0" или "1") записывается - 39 в первый разряд четырехразрядного регистра 12 знаков операндов. Аналогично после считывания второго операнда - 35 код его знака записывается - 40 во второй разряд регистра 12 знаков операндов, после чего код в регистре 12 сдвигается на два разряда вправо - 41. При этом в двух старших разрядах регистра 12 размещаются коды первого и второго операндов выполняемой операции, а два младших разряда регистра освобождаются для приема кодов знаков операндов следующей операции.

Затем (n+2)-разрядный код с выходов регистров 11 и 12 подается на адресные входы блока 10 постоянной памяти, из которого в соответствии с логикой таблицы считываются - 42 управляющие коды u1, u2, 1, 2. Они переключают коммутаторы 19-22, 25-29 в положение, при котором блоки оперативной и локальной памяти, содержащие нижние или верхние границы операндов, подключаются соответствующим образом к процессору 2 или 3. При этом коммутаторы 19, 21, 23, 25 устанавливаются в положение, соответствующее логике выборки первого операнда, а коммутаторы 20, 22, 24, 26 - в положение выборки второго операнда.

После завершения выполнения команды в процессоре 1 начинается ее одновременное выполнение в процессорах 2 и 3, показанное на диаграмме 32 и включающее фазы считывания кода команды - 43, считывание первого и второго операндов - 44, 45 и выполнение - 46. В результате на втором и третьем процессорах вычисляются соответственно нижняя и верхняя границы точного результата, т. е. завершается выполнение интервальной операции. Таким образом, для каждой команды в системе выполняются два этапа: на первом этапе в процессоре 1 выполняется обычная операция, а на втором - в процессорах 2 и 3 выполняется собственно интервальная операция. При этом выполнение текущей команды в процессорах 2 и 3 совмещено по времени с выполнением процессором 1 следующей команды программы, т. е. обеспечивается конвейерный режим работы процессоров 1 и 2, 3.

Управление работой арифметико-логических блоков 13, 14, 15, блоков 16, 17, 18 и 4, 5, 6 локальной и оперативной памяти, регистров 11, 12, а также устройства 8 ввода-вывода осуществляется кодами микрокоманд, формируемыми блоком 9 микропрограммного управления. Один из выходов блока 9 выдает код признака операнда ( α= 0 при выборке первого операнда и α= 1 при выборке второго операнда), который подается на управляющие входы коммутаторов 23, 24, 27, 30.

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

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

Емкость блока 10 постоянной памяти, в которой записана таблица переключения коммутаторов, составляет шестнадцать четырехразрядных слов (кодов u1, u2, 1, 2) или шестнадцать двухразрядных слов с организацией прямых (u1, u2) и инверсных (1, 2) выходов.

Блок 9 микропрограммного управления системы может быть реализован в виде двух аналогичных управляющих устройств 47, 48 (фиг. 3). Вход кода операции (команды) системы соединен с s младшими разрядами (0, . . . , s-1) сдвигающего 2s-разрядного регистра 49 команд (s - разрядность команды), в которые записывается очередная команда для процессора 1. В старших s разрядах регистра при этом размещается предыдущая команда первого процессора, выполняемая в процессорах 2 и 3. После выполнения i-й команды в процессоре 1 и (i-1)-й команды в процессорах 2, 3 код в регистре 49 сдвигается на s разрядов вправо, при этом в s старших разрядах регистра размещается i-я команда, а младшие s разрядов регистра освобождаются для приема (i+1)-й команды. Выходы управляющего устройства 47 соединены с входами процессора 1, устройства 4 и устройства 7 ввода-вывода, а выходы управляющего устройства 48 - с входами процессоров 2, 3, блоков 5, 6 памяти и управляющим входом устройства ввода-вывода.

Устройство 7 ввода-вывода системы (фиг. 4) может быть реализовано в виде трех устройств 50, 51, 52 ввода-вывода, соединенных с входами-выходами оперативных запоминающих устройств 4, 5, 6 и с входом-выходом системы. Выход каждого из устройств 50, 51, 52 соединен с двумя другими через буферные регистры 53, 54, 55. Это позволяет в каждом из процессоров системы оценивать точность выполняемых вычислений, например, путем допускового контроля погрешности. (56) 1. Патент США N 4199811, кл. G 06 F 15/16, опублик. 1980.

2. Прангишвили И. В. и др. Параллельные вычислительные системы с общим управлением. М. : Энергоатомиздат, 1983, с. 65, рис. 2.2в.

Изобретение относится к вычислительной технике и может использоваться для оценки точности вычислительных алгоритмов и программ ЭВМ. Вычислительная система содержит три процессора с оперативными запоминающими устройствами, устройство ввода-вывода и блок микропрограммного управления. С целью сокращения времени выполнения интервальных арифметических операций в систему введены блок постоянной памяти и коммутаторы. Второе и третье оперативные запоминающие устройства соединены с вторым и третьим процессорами через коммутаторы, управляющие входы которых соединены с выходами блока постоянной памяти. Адресные входы блока постоянной памяти соединены с выходами двух сдвигающих регистров, введенных в первый процессор и подключенных входами к выходам арифметико-логического устройства. В третьем и втором процессорах введены коммутаторы, подключенные входами к выходу блока локальной памяти, а выходами к входу арифметико-логического устройства. Логика управления коммутаторами построена так, что в системе реализуется интервальная арифметика. При этом во втором и третьем процессорах вычисляются соответственно нижние и верхние границы точного результата вычислений. 4 ил.

ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА ДЛЯ ИНТЕРВАЛЬНЫХ ВЫЧИСЛЕНИЙ, содержащая три процессора, устройство ввода-вывода, три оперативных запоминающих устройства и блок микропрограммного управления, причем каждый из процессоров содержит арифметико-логический блок и блок локальной памяти, отличающаяся тем, что в систему введены шесть коммутаторов и блок постоянной памяти, причем информационные входы-выходы системы соединены соответственно с информационными входами-выходами первой группы устройства ввода-вывода, информационные входы-выходы второй, третьей и четвертой групп которого соединены соответственно с информационными входами-выходами первого, второго и третьего оперативных запоминающих устройств, вход кода операции системы соединен с информационным входом блока микропрограммного управления, выходы групп с первой по пятую блока микропрограммного управления соединены соответственно с управляющими входами первого оперативного запоминающего устройства, с входом кода микрокоманды первого процессора, с управляющими входами второго и третьего оперативных запоминающих устройств, с входами кода микрокоманды второго и третьего процессоров и с управляющими входами устройства ввода-вывода, первый, второй и третий выходы первого процессора соединены соответственно с первым и вторым адресными входами блока постоянной памяти и с информационным входом первого оперативного запоминающего устройства, выход которого соединен с информационным входом первого процессора, первые выходы второго и третьего процессоров соединены соответственно с информационными входами второго и третьего оперативных запоминающих устройств, выходы которых соединены соответственно с первыми и вторыми информационными входами коммутаторов с первого по четвертый, выходы первого и второго коммутаторов соединены соответственно с информационными входами пятого коммутатора, выход которого соединен с первым информационным входом второго процессора, выходы третьего и четвертого коммутаторов соединены соответственно с информационными входами шестого коммутатора, выход которого соединен с первым информационным входом третьего процессора, второй выход второго процессора соединен с вторым информационным входом третьего процессора, второй выход третьего процессора соединен с вторым информационным входом второго процессора, выход блока микропрограммного управления соединен с управляющими входами пятого и шестого коммутаторов и с первыми управляющими входами второго и третьего процессоров, первый выход блока постоянной памяти соединен с управляющим входом первого коммутатора и с вторым управляющим входом второго процессора, второй выход блока постоянной памяти соединен с управляющим входом третьего коммутатора и с вторым управляющим входом третьего процессора, третий выход блока постоянной памяти соединен с управляющим входом второго коммутатора и с третьим управляющим входом второго процессора, четвертый выход блока постоянной памяти соединен с управляющим входом четвертого коммутатора и с третьим управляющим входом третьего процессора, причем в первый процессор введены первый и второй сдвигающие регистры, при этом в первом процессоре вход кода микрокоманды соединен соответственно с входом кода операции арифметико-логического узла, с управляющими входами первого и второго сдвигающих регистров, с управляющим входом блока локальной памяти, выход которого соединен с первым информационным входом арифметико-логического узла, второй информационный вход которого соединен с информационным входом первого процессора, первый и второй выходы арифметико-логического узла соединены соответственно с информационными входами первого и второго сдвигающих регистров, выходы которых соединены соответственно с первым и вторым выходами первого процессора, третий выход арифметико-логического узла соединен с информационным входом локальной памяти и с третьим выходом первого процессора, при этом во второй и третий процессоры введены по три коммутатора, причем во втором и третьем процессорах входы кода микрокоманды соединены соответственно с входом кода операции арифметико-логического узла, с управляющим входом блока локальной памяти, выход арифметико-логического узла соединен с информационным входом блока локальной памяти и с первым выходом процессора, первый информационный вход которого соединен с первым информационным входом арифметико-логического узла, выход блока локальной памяти соединен с вторым выходом процессора и с первыми информационными входами первого и второго коммутаторов, выходы которых соединены соответственно с информационными входами третьего коммутатора, выход которого соединен с вторым информационным входом арифметико-логического узла, второй информационный вход процессора соединен с вторыми информационными входами первого и второго коммутаторов, первый, второй и третий управляющие входы процессора соединены соответственно с управляющими входами первого, второго и третьего коммутаторов.