КОНТРОЛЬ РАЗВЕТВЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ И СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ Крылов Ю.Д.

Санкт-Петербургский Государственный университет аэрокосмического приборостроения


Номер: 4-8
Год: 2016
Страницы: 23-30
Журнал: Актуальные проблемы гуманитарных и естественных наук

Ключевые слова

Просмотр статьи

⛔️ (обновите страницу, если статья не отобразилась)

Аннотация к статье

Текст научной статьи

Рассмотрим контроль разветвлённых вычислительных процессов. Наиболее полным контролем разветвлённых программ является контроль при введении избыточности в задачу. Часто введение избыточности в задачи осуществляется на основе метода избыточных переменных [1, 234]. Для уверенного применения метода избыточных переменных необходимо иметь математическое описание решаемой задачи [2,128]. Общее описание, необходимое для решения разветвлённой программы может быть представлено следующим образом где - выходные переменные; -входные переменные; U… - параметры управления; F - оператор, обеспечивающий требуемые вычисления. Зависимость выходных переменных Y от управляющих параметров U определяет разветвлённый процесс, который приводит к тому или другому варианту решения задачи. При этом можно выбрать два типа разветвлений: разветвлённых программ с постоянным управлением и разветвлённых программ с переменным управлением. В первом случае вектор U принимает постоянные значения из заданного множества векторов . Каждому соответствует свой оператор. Выбор конкретного вектора из множества C осуществляется программистом и вводится в программу. По вектору организуется разветвлённая программа. Наиболее общим случаем являются задачи с переменным управлением разветвлений. Эти задачи предполагают непрерывную зависимость управляющих параметров от входных переменных задачи: U При этом вектор U вычисляется в процессе решения задачи и заранее не известен. Организация разветвления осуществляется построением логического оператора L(U). Примером может служить разветвление вычислительного с помощью дерева сравнений. Математическое описание задач рассматриваемого типа удобно представить таблицей 1. Таблица 1 Разветвления вычислений на основе дерева сравнений Вектор управляющих параметров U Вид вектора управления L(U) ) … Характер решаемой задачи … Вычисления на i -ой ветви определяются оператором а сама ветвь выбирается видом Способ разветвления не указан и может быть основан на использовании дерева сравнений, либо таблиц переходов. Важным является то, что разветвление зависит от переменного вектора U и определяется логическим оператором L(U). Для контроля n исходных переменных задачи можно ввести одну дополнительную переменную такую, что где -матрица контрольного условия. Избыточная переменная вычисляется по формуле: причём оператор строится по следующему правилу: Если оператор M сделать одинаковым для всех ветвей алгоритма, то переходы по разветвлениям не контролируются. Рассмотрим, как можно исправить положение дел применительно к постоянному и переменному управлению. Предположим, что имеется разветвлённая программа с постоянным управлением, которое определяется r -мерным вектором, принимающим любое значение из множества Будем для определённости полагать, что r .Тогда целесообразно выбрать следующим образом: Это означает, что для каждой N ветвей алгоритма будет свой определённый оператор ,1,…,1] ………………………………… . Теперь контрольным условием обнаруживают только арифметические, но и логические ошибки. Например, если при заданном параметре вычислительный процесс ошибочно пошёл по ветви, соответствующей то получим Таким образом, за счёт введения избыточности, зависящей от параметров разветвления, удаётся контролировать арифметические и логические ошибки алгоритма. Это удаётся за счёт того, что управление разветвлениями постоянно. Поэтому дополнительные операторы могут быть построены заранее, и их реализация может быть предусмотрена в избыточной программе. Предположим, что дана разветвлённая программа с переменным управлением, параметр которого есть действительная вектор-функция входных переменных задачи: U=f(X). Теперь нужно проверить не только выбор ветви, но и проверить вычисление функций . Поэтому, рассматривая составляющие вектора как выходных переменных задачи, введём контрольную переменную так, чтобы где M[1,…,1] - оператор контрольного условия, обычно состоящий из единиц; - оператор, учитывающий разветвления и состоящий из постоянных чисел Тогда избыточная переменная вычисляется по формуле: причём дополнительный оператор строится согласно выражению которые должны вычисляться при любых X . С помощью оператора задача контроля разветвлений с переменным управлением сводится с постоянным управлением. Отличие заключается в том, что нет необходимости задавать оператор , так как он учитывается при составлении избыточной разветвлённой программы. Таблица 2 Задача с постоянным управлением и с оператором Вектор управляющих параметров U U Вектор управления L(u) … Характер задачи … Избыточная переменная … Контрольное условие … Схема избыточного алгоритма приведена на рисунке 1. При этом - предельно-допустимое пороговое значение величины Пример избыточного алгоритма приведён в таблице 3. Таблица 3 Пример избыточного алгоритма Управляющий параметр u Вид управления u u Характер решаемой задачи Избыточная переменная Контрольное условие Пусть =1. Тогда правильный результат имеет вид 2 и, следовательно, = 1 + 0 - 2 + 1 =0. Если в результате ошибки логических операций вычислен первый вариант задачи =5, то контрольное условие будет Таким образом, избыточный алгоритм является помехоустойчивым относительно арифметических и логических ошибок при его реализации. Рис. 1. Схема избыточного алгоритма с переменным управлением Рассмотрим способы контроля и коррекции ошибок при решении линейных алгебраических уравнений методом Гаусса [3,155]. Пусть дана система линейных алгебраических уравнений ……………………………………………………… ………………………………………………………. (1) ……………………………………………… Для контроля правильности вычислений можно вычисленные значения подставить в уравнения (1) и проверить выполнение указанных равенств, но такая проверка требует большого количества дополнительных ячеек памяти и дополнительных операций. Можно осуществить проверку правильности вычислений более экономным методом, а именно: проверить выполнение контрольного условия ) (2) где - сумма всех элементов j-го столбца матрицы системы уравнений (1); - cумма свободных членов в уравнениях (1). При этом контролируются все решения При вычислении контрольного условия дополнительно требуется n операций умножения и ячеек памяти для запоминания сумм коэффициентов каждого столбца. Рассмотрим алгоритм решения системы линейных алгебраических уравнений методом Гаусса с выбором главного элемента. Пусть в системе уравнений (1) есть главный элемент. Умножим строку, где находится главный элемент, последовательно на и вычтем из i - ой строки, причём В результате получим систему (n-1) уравнений с (n-1) неизвестными: ) , …………………………………………………… ) , (3) …………………………………………………… ) . Пусть первоначально была вычислена сумма коэффициентов и свободного члена каждой строки системы n уравнений с n неизвестными а при переходе к системе (n-1) уравнений с (n-1) неизвестными эта сумма была преобразована по формуле (4) где сумма коэффициентов и свободного члена I-ой строки. При получении системы (n-1) уравнений с (n-1) неизвестными сравниваются суммы коэффициентов и свободного члена i -ой строки ) + (5) c рассчитанными прежде суммой и свободным членом. Не должно быть большого расхождения при отсутствии грубых ошибок где - допустимое расхождение контрольных сумм (4) и (5). При несовпадении сумм элементы i-ой строки могут быть вычислены вновь (повторный счёт). Указанный метод позволяет успешно бороться с кратковременными сбоями, но не с отказами, поскольку неизвестно место возникновения неисправности. Будем вычислять суммы коэффициентов не только по строкам, но и по столбцам последовательно, начиная с 1-го столбца и кончая столбцом сумм. Затем сравним расхождения по строке и столбцам. Кроме того, предусмотрим возможность вычисления суммы коэффициентов (n+1) -ой строки, элементами которой будут суммы коэффициентов столбцов, Покажем, что при одиночной неисправности (сбое или отказе) возможна диагностика и коррекция ошибки, т. е. определение места неисправности и численного значения ошибки. Сумма элементов j-го столбца (j=1,…,n+1) для системы уравнений с n неизвестными будет реходе к системе (n-1) уравнений с (n-1) неизвестными эта сумма должна быть преобразована по формуле (6) где - сумма коэффициентов J-го столбца. При получении системы (n-1) уравнений с (n-1) неизвестными сравниваются суммы элементов j -го столбца, где j=1,…,n+1. = (7) = вычисленной заранее суммой . При отсутствии ошибок должно быть где -допустимое расхождение контрольных сумм (6) и (7). При наличии несовпадения сумм только в строке (строках) или только столбце (столбцах) или же одновременно и в строках и столбцах необходимо учесть следующее. Пусть величина несовпадения сумм при проверке i -ой строки (i=1,…,n) с точностью до равна величине несовпадения сумм при проверке j-го столбца. То есть Если при этом число нарушенных строк и столбцов равно 1, то это указывает на искажение элемента, расположенного на пересечении i-ой строки и j-го столбца. Необходимо провести коррекцию этого элемента и сумм и , добавив к их значению величину или с учётом знака. Если , причём число нарушенных строк равно 1, а число нарушенных столбцов больше 1, то это указывает на размножившуюся ошибку. Эта ошибка может быть исправлена путём добавления величин рассогласования по столбцам, и наоборот, если число нарушенных столбцов равно 1, а число нарушенных строк больше 1, ошибка может быть исправлена путём добавления величин рассогласования по строкам. Кроме того, рассмотрим некоторые особые ошибки и признаки, по которым можно судить об их возникновении, а также коррекцию этих ошибок. Если ошибка возникла при вычислении суммы элементов i-ой строки в формуле (4), то при этом несовпадение сумм будет наблюдаться только в i -ой строке и в последней (n+1) -ой строке. Ошибка будет исправлена, если вместо принять . Если ошибка возникла при вычислении суммы элементов i-ой строки в формуле (5), то несовпадение сумм будет только в i-ой строке. В этом случае в расчёт не принимается. Если ошибка возникла при вычислении суммы элементов j -го столбца в формуле (6), то несовпадение сумм будет только в j-м столбце и последнем (n+2) -м столбце. Ошибка может быть исправлена, если вместо принять . Если ошибка возникла при вычислении суммы элементов j -го столбца в формуле (7), то несовпадение сумм будет только в j-м столбце. В этом случае в расчёт не принимается. Если несовпадение сумм наблюдается не только у i-ой строки и (n+1)-ой строки или у j-го столбца и (n+2)-го столбца, то это указывает на искажение главного элемента и на распространение ошибки не только по строке или столбцу, а на часть или всю матрицу коэффициентов. Если имеются неискажённые столбцы или строки, то возможно исправление главного элемента даже при устойчивой неисправности ячейки ЗУ, где он хранился, путём восстановления значения главного элемента и перезаписи его в другую ячейку. После этого вся матрица коэффициентов на данном шаге может быть рассчитана вновь. Так может быть проведены контроль, диагностика и коррекция вычислений в процессе исключения коэффициентов (прямой ход) при наличии неисправности (отказа или сбоя) в любом элементе при условии исправности устройства коррекции, т. е. той части АУ, с помощью которой осуществляется коррекция. Контроль решения систем с треугольной матрицей (обратный ход) можно осуществить с помощью замены столбца свободных коэффициентов на столбец сумм. В результате этого взамен должны получаться величины Произведём оценку вводимой избыточности при прямом ходе. Увеличение сложности алгоритма будем оценивать по относительному увеличению количества сложных операций типа умножения или деления и по относительному увеличению объёма памяти При очередном шаге прямого хода порядок системы равен При этом требуется операций умножения при вычислении сумм по формуле (4) и операций умножения при вычислении сумм по формуле (6). Тогда относительное увеличение количества сложных операций , а относительное увеличение объёма памяти . Вероятность обнаружения ошибки на любом шаге а вероятность исправления (коррекции) кратковременного сбоя Вероятность того, что отказ не будет исправлен (если он наступил) на очередном шаге при условии равной вероятности возникновения его в абсолютно любом элементе матрицы коэффициентов составит = где - вероятность возникновения отказа именно в главном элементе; относительное время проведения вычислений по формулам (4), (5) и первой строки матрицы коэффициентов в очередном шаге прямого хода. метода контроля может быть предложен метод, основанный на применении блоковых циклических кодов, обладающих корректирующими свойствами [4,337]. Но этот метод не охватывает ошибки, которые могут возникнуть в процессе вычислений в арифметическом устройстве (АУ), поэтому его целесообразно дополнить другими методами контроля, например, осуществить двойной счёт. Кроме того, необходим хотя бы один добавочный разряд в арифметическом устройстве для контроля правильности передач информации. Совокупность этих мер образует комбинированный метод контроля. таблице 4. Таблица 4 Сравнение методов контроля и коррекции ошибок Параметр Метод контроля по строкам и столбцам Комбинированный метод контроля Относительное увеличение времени вычислений прямого хода Вероятность коррекции отказа ЗУ Специальные затраты в АУ Объём ЗУ Нет 1 1 Добавочный разряд Одинаково в обоих методах Таким образом, предложенный метод обеспечивает существенное сокращение времени вычислений по сравнению с комбинированным методом контроля, хотя уступает ему незначительно по вероятности осуществления коррекции устойчивых отказов ячеек ЗУ.

Научные конференции

 

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