Основы бортовых вычислительных машин
 Скачать 3.2 Mb.
|
|
Т 3 , количество кон- тролируемых участков – N. Тогда время реализации одного контро- лируемого участка алгоритма t = Т 3 / N. (6.1) Следует учесть, что при организации контроля способом двой- ного просчета затрачивается дополнительное время t Д на каждом кон- тролируемом участке задачи на контрольное суммирование, сравне- ние контрольных сумм, принятие решений на третий просчет или продолжение вычислений. При принятых допущениях и введенных обозначениях время реализации алгоритма Т А = 2N (t+t д ) + 2N (t+t д ) λ (t+t д ) = 2N (t+t д ) + 2 (t+t д ) 2 λ N. (6.2) Подставляя значение t из (6.1) в (6.2), получим Т А = 2N (Т 3 / N + t д ) + 2 (Т 3 / N + t д ) 2 λ N. (6.3) Выберем N из условия минимального времени реализации алго- ритма. Продифференцировав выражение (6.3) по N и приравняв про- изводную нулю, получим dT A / dN = t д – (Т 3 2 λ ) / N 2 + t д 2 λ = 0. Отсюда 3 Т N опт = )] 1 ( /[ Д Д t t λ λ + При экспоненциальном законе распределения сбоев и оптималь- ной длине участка программы вероятность бессбойной работы на од- ном участке будет: ( ) ( ) λ λ λ λ λ / )] 1 ( [ / Д Д опт з t t N Т t е е е t Р + − − − = = = На основании теоремы о повторении опытов можно определить вероятность правильной реализации алгоритма при наличии двойно- го- тройного просчета. 232 Она равна: ( ) ( ) ( ) ( ) [ ] ( ) ( ) ( ) ( ) [ ] ( ) { } ( ) [ ] 1 2 1 1 2 2 N t t t N А е е е t Р t Р t Р t Р t Р t Р t Р t Р Т Р λ λ λ − − − − + = − + − + = Способ контрольных соотношений. Позволяет определить не только ошибки, появляющиеся за счет случайных сбоев, но и ошибки, появляющиеся за счет отказов. Сущность способа заключается в том, что в общий алгоритм включаются различные математические соот- ношения, позволяющие проверить правильность решения основной задачи путем их реализации. Такими соотношениями могут, напри- мер, быть зависимости вида 1 cos sin 2 2 = + α α или ∑ = = n t i Р 1 1 . т.е. сумма вероятностей всех возможных значений случайной величи- ны в полной группе событий равна единице. При выполнении кон- трольных соотношений с заданной точностью проводится дальней- шее решение основной задачи. При невыполнении контрольных со- отношений либо повторяется данный участок задачи, либо машина останавливается о чем сообщается экипажу. Способ контрольных со- отношений может дать значительный выигрыш во времени по срав- нению со способом двойного просчета. Способ «усеченного» алгоритма. Данный способ позволяет вы- являть и устранять ошибки за счет случайных сбоев и систематиче- ских отказов, если «усеченный» алгоритм значительно отличается от основного. Этот способ предполагает наличие упрощенного алгорит- ма основной задачи. Упрощенный алгоритм должен быть меньше ос- новного. Реализация «усеченного» алгоритма совместно с основным и совпадение результатов в пределах заданной точности позволяют су- дить о правильности хода вычислительного процесса. Способ логического анализа результатов решения. Способ по- зволяет выявлять как случайные, так и систематические ошибки. Сущность его заключается в сравнении некоторых параметров задачи и их приращений, вычисленных в ходе решения задачи, с заранее из- вестными пределами их изменения. Способ используется в том слу- чае, если заранее известны законы изменения некоторых параметров. 233 Способ подстановки. Заключается в том, что после получения ряда искомых величин решается обратная задача. В качестве исход- ных данных выбираются найденные значения неизвестных и опреде- ляются некоторые величины, которые при прямых вычислениях ис- пользовались в качестве исходных данных. Затем сравнивают эти ве- личины с исходными данными при прямом вычислении. Совпадение в пределах заданной точности свидетельствует об отсутствии ошибок в вычислениях. Например, при решении систем алгебраических урав- нений в качестве исходных данных могут быть приняты полученные в вычислении корни х 1 , х 2 , …, х k ; в качестве неизвестных – какие-либо коэффициенты, определяемые при обратном решении задачи. Срав- нение полученных коэффициентов с имеющимися в пределах задан- ной точности говорит о том, что система решена верно. Аналогичным способом можно воспользоваться при решении систем дифференци- альных уравнений. При разработке общего алгоритма бортовой ЦВМ необходимо использовать наиболее эффективные способы контроля правильности вычислений, позволяющие значительно повысить надежность обра- ботки информации на борту самолета с минимальными затратами машинного времени. Все рассмотренные способы контроля вычислений являются эффективными лишь при условии правильности хода реализации про- грамм БЦВМ. Контроль хода выполнения программ БЦВМ: каждая программа, реализующая тот или иной режим работы БЦВМ и системы в целом, составляется из отдельных подпрограмм программой-диспетчером. Правильность хода выполнения программы определяется: контролем последовательности включения подпрограмм; контролем длительно- сти работы подпрограмм; контролем выполнения переходов и преры- ваний программы. Контроль последовательности включения подпрограмм: режим работы БЦВМ и системы обеспечивается соответствующей програм- мой, состоящей из отдельных подпрограмм S 1 , выполняемых пооче- редно. Способ контроля заключается в следующем. За время t 1 подпрограмма S i включается в работу не менее чем один раз и в результате каждого выполнения подпрограммы S i изме- няется некоторый параметр R i (t), хранящийся в оперативной памяти БЦВМ. Проверкой соотношения R i (t) ≠ R i (t + τ i ) можно установить, 234 что подпрограмма S i выполнялась. Для каждого выполняемого режи- ма работы БЦВМ заранее известны связи между отдельными подпро- граммами. Детерминированность связей между подпрограммами ис- пользуется для контроля последовательности их выполнения. В этом случае каждая подпрограмма при выполнении фиксирует в опреде- ленной ячейке памяти заранее закрепленный за данной подпрограм- мой условный код. Выполнение следующей подпрограммы начинает- ся лишь после анализа условного кода, записанного при выполнении предшествующей подпрограммы. Контроль длительности работы подпрограмм: предполагает кон- троль длительности работы отдельных участков программы и позво- ляет обнаруживать нарушения реализации программ за счет зацикли- вания и других причин, приводящих к увеличению времени реализа- ции отдельных подпрограмм программы. Для этой цели используются счетчики относительного времени, предназначенные для подсчета временных интервалов. В этом случае накладываются определенные ограничения на длительность τ i выполнения подпрограммы S i . В на- чале каждой подпрограммы на счетчик относительного времени спе- циальной командой заносится код, соответствующий допустимой от- носительной длительности исполнения данной подпрограммы. При каждой реализации подпрограммы S i из содержимого счетчика отно- сительного времени вычитается единица. При наличии в счетчике от- носительного времени нуля вырабатывается сигнал ошибки, который вызывает прерывание программы и переход к подпрограмме анализа ошибок. В противном случае происходит переход к выполнению сле- дующей подпрограммы. Контроль правильности выполнения переходов и прерываний программы: осуществляется с помощью команд условной и безуслов- ной передач управления и основан на программном блокировании сигнала ошибки. Идея этого контроля заключается в том, что перед выполнением перехода специальной командой в цепь модификации адреса и выполнения перехода подается сигнал ошибки, поступление которого может быть заблокировано с помощью команд блокировки, располагаемых во всех местах программы, куда происходит переход. При неправильном выполнении перехода сигнал ошибки не бу- дет заблокирован и вызовет при этом прерывание и включение в ра- боту подпрограммы анализа сбоев. Способ обеспечивает высокую ве- роятность обнаружения как случайных, так и систематических 235 ошибок любой кратности, но требует дополнительного оборудования и специальных команд в программе. Прерывание программы является характерной особенностью ра- боты БЦВМ, реализующей свои алгоритмы в реальном масштабе времени. В процессе работы БЦВМ в зависимости от режима работы системы и объема поступающей и выдаваемой информации произво- дятся многочисленные прерывания программы, насчитывающие сот- ни прерываний в секунду. Для контроля правильности выполнения прерываний программы часто используется рассмотренный способ программного блокирова- ния сигнала ошибки. Отличие состоит лишь в том, что формирование сигнала ошибки осуществляется схемным путем, а прерывание может быть в любом месте программы. Блокирование сигнала ошибки осу- ществляется одной из первых команд вклинивающейся подпрограм- мы. Контроль перехода к основной программе после прерывания осуществляется проверкой правильности восстановления состояния основных результатов регистров и ячеек памяти БЦВМ, использо- вавшихся вклинивающейся подпрограммой. Для этой цели применя- ют метод многократного хранения переменной информации в памяти машины и последующее её сравнение. Сигнал ошибки вырабатывается при не сравнении содержимого хотя бы одного регистра или ячейки памяти машины. Тестовый контроль. Программно-логический контроль, предна- значенный для защиты алгоритмов от ошибок, возникающих в ходе вычислительного процесса, не ставит своей целью установление фак- та наличия неисправности в каком-либо устройстве, обнаружение и устранение имеющейся неисправности. С помощью тестового контроля обнаруживают в каком-либо устройстве неисправности, выполняют их локализацию и сигнализа- цию о них. В настоящее время он является основным средством про- верки правильности функционирования БЦВМ на всех этапах ее экс- плуатации и применения. Основным назначением тестового контроля является обнаружение систематических ошибок, возникающих в уст- ройствах вследствие внезапных и постепенных отказов. В процессе эксплуатации БВМ используются: испытательные тесты комплексной проверки БВМ и диагностические тесты. Испытательные тесты комплексной проверки БВМ. Они приме- няются для обнаружения неисправностей в машине и позволяют 236 контролировать совместную работу всех устройств машины. В каче- стве испытательных тестов часто используют одну или несколько из решаемых БВМ задач. Исходными данными при этом выбирают та- кие, результаты решения для которых заранее известны. Испытатель- ные тесты в этом случае позволяют проверить не только работоспо- собность БВМ, но и функционирование системы в целом. Тестовые программы этого типа не требуют дополнительной емкости памяти. Диагностические тесты. Их применяют для определения места неисправности и используют после установления факта наличия не- исправности с помощью испытательных тестов комплексной провер- ки БВМ. Эти тесты представляют собой программы специально по- добранных примеров, которые требуют для своей реализации выпол- нения всех операций, имеющихся в системе команд машины. При правильном выполнении теста вырабатывается сигнал «исправно». При наличии отказа этот сигнал не вырабатывается. Тестовые программы хранятся в постоянном запоминающем устройстве (ПЗУ) и включают в себя тесты, проверяющие АЛУ, ПЗУ, ОЗУ, УУ, УВВ и т.д. 6.3 Помехоустойчивое кодирование сигналов и его применение для схемного контроля БВМ Схемный контроль обеспечивает контроль машины или отдель- ных ее устройств с помощью дополнительного оборудования, вклю- ченного БЦВМ. Схемный контроль включает в себя: контроль с использованием корректирующих кодов и контроль по модулю. 6.3.1 Общие сведения об избыточном кодировании сигналов Работа цифровых устройств невозможна без передачи информа- ции по различным каналам информационного обмена. Передачу ин- формационных сообщений всегда можно свести к передаче двоичных чисел, представленных в виде кодов. Исследованием свойств кодов ограниченной длительности и по- иском оптимальных структур технически реализуемых кодов занима- ется теория кодирования. Теория кодирования развивается в двух главных направлениях: 237 поиск кодов, позволяющих в каналах без помех максимально устранить избыточность источника и тем самым повысить эффектив- ность передачи информации (теория экономичного кодирования); поиск кодов, повышающих достоверность передачи информации в каналах с помехами (теория помехоустойчивого кодирования). Поскольку под помехой для информационного канала может быть принято не только мешающее передаче информации внешнее воздействие, но и сбои в оборудовании, приводящие к потере инфор- мации, то в общем виде все информационные каналы можно считать каналами с помехами. Рассмотрим общую постановку задачи помехоустойчивого ко- дирования при ограниченной длительности кодируемых сообщений. От источника сообщений поступают последовательности символов 1 2 , ,..., n b b b , которые называют информационными последовательно- стями. При кодировании каждой информационной последовательно- сти 1 2 , ,..., n b b b приводится во взаимно-однозначное соответствие пе- редаваемое сообщение (кодовая последовательность) 1 2 , ,..., n β β β . В результате действия помех на выходе канала будет принято сообще- ние 1 2 ' , ' ,..., ' n β β β , часть символов которого может отличаться от символов передаваемого сообщения: ' ν ν β β ≠ . Если при приеме каж- дый символ обязательно идентифицируется с одним из символов ал- фавита канала (канал без стирания), т.е. всегда ' B ν β ∈ , то единствен- ной формой ошибки может быть трансформация символов. Если же по некоторым из принятых символов решение об их идентификации с определенным символом алфавита B не принимается и они оказыва- ются вовсе не опознанными (канал со стиранием), то могут иметь ме- сто два вида ошибок: трансформация символов и неопознание (стира- ние) символа. Неопознанные (стираемые) символы обозначим Ф , где Ф B ∉ Помехоустойчивое кодирование сообщений имеет задачей обес- печить с достаточно высокой вероятностью либо обнаружение оши- бок, либо обнаружение и исправление этих ошибок. Соответственно различают коды с обнаружением ошибок и коды с исправлением ошибок. Код с обнаружением ошибок обеспечивает стирание или особую отметку той части сообщений, в которой обнаружены ошиб- ки. Такой код эффективней в системах с обратными информацион- ными связями, когда имеется возможность повторно запросить часть 238 сообщения, в котором обнаружены ошибки. При отсутствии обрат- ных информационных связей код с обнаружением ошибок эффекти- вен лишь в таких системах, которые менее критичны к пропуску (сти- ранию) части сообщения, чем к неверному его приему. Код с исправ- лением ошибок позволяет получить верные сообщения, несмотря на наличие искажений отдельных символов (в пределах корректирую- щей способности кода). Не существует кодов конечной длины, позво- ляющих обнаружить и, тем более, исправить все возможные ошибки. Можно построить лишь коды, обнаруживающие или исправляющие некоторое число ошибок определенного вида (наиболее вероятных или наиболее опасных). Коды, обнаруживающие и исправляющие ошибки, называются помехоустойчивыми или корректирующими. Корректирующая спо- собность кода основывается на его избыточности. При отсутствии из- быточности, когда любая комбинация символов алфавита канала мо- жет представлять передаваемое сообщение, достоверное обнаружение ошибок невозможно: на приемной стороне неизвестно, какое именно сообщение могло передаваться (в противном случае его передача не несла бы информации и была бы лишена смысла). Для того чтобы из- быточностью сообщения можно было воспользоваться для обнаруже- ния или исправления ошибок, она должна вноситься по определен- ным правилам. При рассмотрении корректирующей способности ко- дов будем учитывать лишь избыточность, вносимую в сообщение при кодировании, сообщения же, поступающие от источника, будем счи- тать безызбыточными. В частном случае, когда алфавиты источника и канала имеют одинаковый объем m , внесение избыточности означает увеличение числа символов в передаваемой последовательности по отношению к информационной последовательности. Например, для двоичного кода ( m = 2) с длиной информационного сообщения n и числом контрольных разрядов l передаваемое сообщение имеет вид: { } 0 1 1 1 ( 1) , ,..., , , ,..., n n n n l X x x x x |