автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Теоретическое обобщение и разработка методов построения непозиционных модулярных спецпроцессоров

ИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

9

Курский государственный технический университет

На правах рукописи УДК 681.142

, Ирхин Валерий Петрович

РГБ ОД

V 1 д;]р гт

ТЕОРЕТИЧЕСКОЕ ОБОБЩЕНИЕ И РАЗРАБОТКА МЕТОДОВ ПОСТРОЕНИЯ НЕПОЗИЦИОН11ЫХ МОДУЛЯРНЫХ СПЕЦПРОЦЕССОРОВ

Специальность 05.13.05 «Элементы и устройства вычислительной техники и систе': управления»

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Курск, 1999

Работа выполнена в Военном институте радиоэлектроники, г.Ворогс-х Научный консультант: доктор технических наук, профессор Бухарин C.B.

Официальные оппоненты:

доктор технических наук, профессор Уразбахтин И .Г.

доктор технических наук Бурмака A.A.

доктор технических наук, профессор Сысоев В.В.

Ведущая организация: Таганрогский государственный радиотехнич ский университет.

Зашита состоится 16.{1.99 1999 г. в 15 часов на заседании диссер ционного совета Д 064.50.02 при Курском государственном техническом ун верситете по адресу: 305040, г.Курск, ул.50 лет Октября, 94, конференц-зал.

С диссертацией можно ознакомиться в библиотеке университета.

Отзывы на автореферат в двух экземплярах, заверенные печатью, проба отсылать по адресу: 305040, г.Курск, ул.50 лет Октября, 94, Курский го ' дарственный университет, ученому секретарю специализированного сот Д064.50.02 .

Автореферат разослан « 1» \о 1999 г.

Ученый секретарь диссертационного совета Д064.50.02 К.т.н., доцент ^ Довгаль В.М.

Wn.L-okli-Ob-h-QÇ {)

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Основными путями к повышению производительности и расширению »ункциональных возможностей ЭВМ являются совершенствование технологи производства средств вычислительной техники и внедрение новых, более ффективных способов оргашпации и проведения вычислений, т.е. новых вы-ислительных структур. Анализ известных подходов, испо.'Д'Зуемых при раз-аботке высокопроизводительных вычислительных структур, показывает, что се они имеют общую отличительную особенность, суть которой состоит в аироком применении тех или иных форм параллельной обработки. Главный ¡уть увеличения производительности - повышение уровня совмещения опе-1аций в ЭВМ, т.е. повышение уровня параллелизма.

В отличие от общепринятого, существует два перспективных направле-еня б области разработки вычислительных средств, использование которых фииодит к кардинальному повышению производительности и надежности ЭВМ. Первым направлением является применение непозиционных кодовых труктур в модулярной системе счисления (МСС). В таких ЭВМ обесиечи. гтея решение задачи существенного повышения производительности (за счет распараллеливания процесса вычисления на уровне операндов) и задачи обес* 1ечения отказоустойчивости и живучести (путем введени" избыточных моду-гей МСС). Ко второму направлению относится подход, связанный с использо-мшисм систем счисления с иррациональными основаниями (коды Фибоначчи и коды золотой пропорции), одним ю свойств которых является возможность маскирования отказов типа константа 0 или 1.

Синтез этих направлений приводит к значительному улучшению ош ных характеристик ЭВМ В этом случае вычислительные структуры реали клея в виде отдельных трактов, каждый та которых использует, например, 1 ды Фибоначчи. Подобные структуры представляют ЭВМ, функционируют в позиционно-осгаточной системе счисления. Вследствии малоразрядно< остатков МСС в подобной комбинированной вычислительной системе мол быть повышено быстродействие операций базового набора (сложение, вы< тание и умножение) за счет использования табличных методов, а одиночн отказы в каждом тракте не влияют на ее функционирование. Дальнейшее р витие этого подхода приводит к построению многоуровневых вычислите, ных структур, в которых эти свойства многократно усиливаются.

Существует ряд областей техники, в которых назрела острая необхо; моегь в кардинальном повышении отказоустойчивости и производительно« средств обработки данных. В связи с этим исследования, связанные с раз боткой многопроцессорных ЭВМ с параллельной структурой, а также выч; лительных систем на базе оптических ЭВМ отнесены в настоящее врем; числу приоритетных направлений развития науки и техники Российской < дерации и считаются критическими технологиями федерального уровня.

Эта обстоятельства и предопределяют постановку в данной работе П] блемы повышения надежности и быстродействия вычислительных струю путем использования модулярной и фибоначчиевой систем счисления.

Работы по их практическому применению начались рядом ученых у давно, однако, проводились лишь по отдельным частным вопросам. При эт не учитывались особенности построения алгоритмов выполнения операщ характерные для МСС. Не решена задача оптимального выбора основан системы счисления для любых методов проектирования СП. Аналга получ! ных схемотехнических решений проводился исходя га существующего урог развития технологической базы ВТ. В настоящее время отсутствуют систе! газированные исследования по обобщению современного состояния непо цнонных вычислительных структур. Практическому внедрению МСС так препятствует отсутствие оптимальных структур СП для различных диапазо» разрядных сеток. Главной научной задачей является разработка алгоритм» ских и аппаратных структур блоков, реализующих модульные операции ба вого набора с минимизацией аппаратурных или временных затрат. Ключе! вопрос - создание быстродействующих устройств с высокой пропускной о собностью, выполняющих немодульные операции, т&ккг к&х арзобразосн кодов чисел между МСС и ПСС.

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

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

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

Для реализации поставленной цели необходимо решение следующих оеных задач:

1) формирование методологии единого системного подхода при раз-отке основ теории структурного синтеза непозиционных СП и вычислимых трактов; п

2) разработка и классификация патентоспособных схемотехнических 1ений вычислительных трактов комбинационного и посл^довательностного ов;

3) оптимизация аппаратурных затрат при проектировании арифмети-сих устройств комбинированного типа;

разработка:

4) методики рационального выбора оснований системы счисления различных методах проектирования спецпроцессоров;

5) способа совмещения в вычислительной структуре модулярной и оначчиевой систем счисления для повышения ее отказоустойчивости;

6) алгоритмических процедур реализации операций табличной {шетнки, позволяющих существенно сократить' аппаратурные затраты при-гроснии вычислительных трактов СП;

7) алгоритмов повышенной производительности дм проведения немодных операций в модулярной системе счисления;

8) алгоритмов выполнения операций базового набора для построения целительных трактов на основе метода кольцевого вращения;

9) многоуровневых операционных устройств и анализ их основ« характеристик по предложенным критериям.

Методы исследования. При решении оставленных задач исгюльзова методы теории надежности, математического программирования, теории • сел, элементы комбинаторики и математическою анализа, методы тсор групп и полей, теории конечных разностей, элементы теории возвратных i следоватсльностей и теории функциональных уравнений

На защиту выносятся следующие основные научные положения:

1. Основы теории структурного синтеза непозиционных СИ, ра»| ботанные на базе известной математической модели надежное! и спецпрон соров, функционирующих в МСС. Использование этой теории позволило i лучить оптимальные, в надежностном плане, структуры СП для различи диапазонов разрядных сеток.

2. Методика рационального выбора оснований МСС для различи методов проектирования СП, которая явилась следствием постановки и реп ния общей задачи минимизации количества оборудования при заданных j бованиях и точности вычислений.

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

4. Методшш определения граничных параметров затрат обирудо • низ при шбсстных методах построения сепозиционных СП. область приме

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

5. Сравнительная оценка эффективности и теоретическое обосно míe предлагаемого комплекса патентоспособных технических решения оси пых узлоа спецпроцессоров.

Научная ueeuvta состоят с следующем:

1. Проведенный енллиз путей улучшения осношалх технических раэтернстнк средств вычисшггельноЯ техники доказал их гл><х>хуго в>а.н: связь со свойствами шэдудярноП н фибоначчкевой систем счислешо, что зшхззет предложить нозый полход к построению кепозиционкых спгшгрс. сороа, осношшыП ю согдаесткоы кепаяьзеггнмл зтгн с.етси.

2. Впервые сформулирована и решена серия обратных задач опти-шыюго резервирования в МСС для различных методов построения спештро-ссоров и диапазонов разрядных сеток, результаты, решения которых поз воли разработать теоретические основы синтеза структур СП и получить оп-мальные, в надежностном плане, структуры.

3. Разработан и теоретически обоснован оригинальный метод выбора здулей системы счисления, реализация которого способствует значитсльно-/ сокращению затрат оборудования при проектировании СП на основе раз-4х методов, отличных от первоначально используемого сумматорного.

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

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

6. Сформулированы основные принципы построения многоуровне-.IX вычислительных структур в МСС, в результате развития которых выведе-л и доказаны основные математические соотношения, определяющие пре-:лм1ые оценки аппаратурных затрат и скоростных характеристик как нспо-щионных СП так и их вычислительных трактов.

7 Обоснована илснтнчность архитектурных решений спецпроцессоре и модульных трактов, при условии их рашюнольной организации, что по-юляет исполмовап. большинство известных и полученных в работе научных пультатов при проектировании вычислительных структур в МСС на двух плг.чных уровнях.

Практическая ценность работы:

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

1. Стгтезированы высоконадежностные струкг; ы СП для различ-их вадов резервирования и точностных характеристик процесса вычислений.

2. При анаипе результатов структурного синтеза СП получены дан-ыс о целесообразных областях применения непозиционных спецпроцессоров.

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

4. Введены и обоснованы пригодные для инженерной практики к терии для сравнительной оценки характеристик вычислительных трактов.

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

6. Разработан ряд эффективных алгоритмических процедур техни ской реализации непозиционных операций в МСС.

7. Создан и классифицирован комплекс патентоспособных блок о узлов СП, работающих в МСС.

Реализация и внедрение результатов работы.

Представленные в диссертации исследования являются результатом учной работы, проведенной в ряде научно-исследовательских институт предприятий и вузов (Воронежском НИИ связи, НИИ электронной техни Харьковском НПО «Импульс», Воронежском госуниверситете. Ставропо ском ВВИУС, Воронежской лесотехнической академии и др.). Работы вып мялись в рамках 18 научно-исследовательских работ, проводимых по закат Министерства обороны. Реализацию данной работы также можно представ двумя направлениями: первое связано с использованием результатов в про водстве, второе - в учебном процессе.

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

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

Кроме того, научные результаты работы включены в учебное пособие « гказоустойчивость специализированных процессоров автоматизированных стем управления и средств связи», изданное Ставропольским ВВИУС.

Апробация работы. Научные результаты и положения диссертационной боты докладывались и обсуждались на 24 научно-технических конференци-

Основные результаты работы докладывались и обсуждались на конфе-нциях н семинарах, в том числе: на международной научно-технической нференцни «Передача, обработка и отображение информации» (Домбай, '94); на II международной конференции «Алгебраические, вероятностные, ометрические, комбинаторные и функциональные методы в теории чисел» оронсж,1995), на II межведомственной научно-технической конференции 1роблсмные вопросы сбора, обработки и передачи информации в сложных лиотехнических системах (Пушкин, 1995), на 111 международной конферен-щ «Современные проблемы теории чисел и ее приложения» (Тула, 1996), на эронсжской весенней математической школе «Современные методы в тео-ги краевых задач» (Воронеж, 1996), на третьей межведомственной научно-хннчсской конференции «Проблемные вопросы сбора, обработки и передачи Iформации в сложных радиотехнических системах» (Пушкин, 1997), на все-кхийской научной конференции «Современные методы П(\аготовки специа-ictob н совершенствование систем н средств наземного обеспечения авиа-1и» (Воронеж, 1997).

Публикации результатов работы. По теме диссертации опубликовано г печатных работ, в том числе монография «Проектирование непозиционных 1С1шализирова!шых процессоров».

Структура и объем диссертации. Диссертация состоит из введения, ести глав и заключения, изложенных на 273 страницах машинописного тек-а, содержит 34 рисунка, 65 таблиц, список литературы ю 152 наименова-ift и 3 приложений объемом а 8 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

Для повышения скорости работы вычислительных структур применяю ся два пути: повышение тактовой частоты элемешгной базы арифметичсско устройства и параллельное выполнение вычислений за счет перехода от одн процессорных к многопроцессорным ЭВМ. Первый путь имеет ограниченш возможности, ввиду приближения к верхней границе скорости обработки да ных, достижимой вычислительной машине, что следует из основных фижч ских законов.

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

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

Кардинально улучшить технические характеристики вычкслитсльж структуры возможно путем специалкшош и проблемой еркеигадоз I весь класс решаемых задач. При этом повышается ремонтопригодность в пр цессе эксплуатации и сводятся к шшнмуму шссогебгрнткые пзракстры сп

дотированного процессора, что является решающим, если он используется сачествс бортовой системы на транспортных средствах. В настоящее время 1 повсеместно применяются в традиционных областях • системах упраале-я, работающих в реальном масштабе времени.

Кодирование в МСС позволяет распараллелить вычислительные алго-тмы на уровне элементарных операций. Из алгоритма построения кода оче-дны следующие свойства остатков, представляющих исходный операнд: не-кнсимость, равноправность н малоразрядносп».

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

Для СП в МСС характерной особенностью является возможность осу-ветвления обменных операций между точностью, быстродействием и нежностью, что определяет путь унификации любых спецпроцессоров в соот-тствии с предъявленными к ним требованиями. Молоразрядность остатков 1во;1яст эффективно применять табличные методы реализации арифметиче-их операций, что резко повышает их быстродействие и надежность, ввиду пользования матричных схем.

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

Другой нетрадиционной системой счисления, позволяющей преодолеть д недостатков классической двоичной, является система, основанная на/ имененни кодов Фибоначчи. Она обладает «обыточносшо, которая исполь-ется для кошроля информационных процессоа в ЭВМ. Однако главным ойством, вытекающим из избыточности кода, является наличие для любого 1сла формы кода, содержащей в любом заданном разряде цифру 1 или 0, что >жет быть использовано для маскирования отказов. Это свойство (маскиро-

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

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

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

Вторая глава диссертационной работы посвящена сшгтезу структур 1« позиционных спецпроцессоров, который сведен к решению серии обратим задач оптимального резервирования. Очевидно, что результаты решения зад! чи синтеза существенно зависят от вида используемого структурного резерв! рования: постоянное и динамическое.

С целью решения задачи синтеза СП в случае постоянного структурног

резервирования введем понятое сектора X¿ — {*(}. где х, - 0, 1, 2, ... • кр;п ностъ резервирования вычислительного тракта СП в МСС гю модулю ГП, I этом случае задача синтеза спецпроцессора в модулярной системе счислеии основывается на выполнении следующего услоши

VXj € ХЭ !Хопт ex[xj = Х^. Pg^COlt = const] = шах J

формируется следующим образом: необходимо определить единственное он

тиыалъное, из совокупности X возможных значений вектора Х^щ, при кс

тором вероятность безотказной работы Рмсс^ (О СП о МСС достигла б: максимально возможного значения.

Решение данной задачи cmrrcia непосредственно связана с обратной и-чей otrinMa.ii.mvi о резервирования в МСС, аналитически представленной в ле

I рмсс H)[t = const ]-+ max, 1 (V fix- * VMCC •" MCC * П^),

где Vi*! . V¿<V . количество оборудования t - байтовых спец-oiiciiofxitt ukhbcicirchiio в позиционной и модулярной системах счисле-*. 11 м, ( - производительность СП в МСС. П тр - требуемая проюводн-

1>.|ИЧ~1Ь

I t in н качестве вычислительной системы в позиционной системе счис-пия не iio.il* |> смой для сравнения с 'ШМ в МСС, возьмем трех канальную скм>. окисшую к» грех однотипных f - разрядных ')ВМ, наиболее ши-ко ииттмусмую я настояшее время для повышения отказоустойчивости, а к-рннме нмчис.нпельныс факты СП в МСС по каждому модулю находятся им ружейном резерве, ?t> мнппнленная задача математически формируется слумшим обраюм

РмМХ = Х(х1,ч2,...,х11)]->тах<

(3-8 . =¿a,(xl + l)), (1)

i-i

с. Р, (t) = 1 - (I - с •')*' ' вероятность безотказной работы резер-

ровашшй системы по основанию ГП, МСС, ОС, = ]log2 Ш|[, X, - шгтенсив-сть отказов оборудования отнесенная к одному двоичному разряду.

Отмстим, 'по всроятость безотказной работы вычислительной системы

ПСС равна Р^-О) = I "(I" Р^'ЧО] \ где Р i" = е " . кроят

стъ безотказной работы ( - байтовой ЭВМ в ПСС, а ^псс =

Решение ттой задачи удобно iccth к многошаговому процессу дина-гческог о программирования. Подход с использованием этого метода являет-весьма гибким для решения общих задач оптимального резервирования. С лью получения конкретных числовых значений при решении задачи (1)

имем Я, = Ю '[1 /час]. /. = lOr'M. При этом P,(t„)=0,99 - верояг-

ностъ безотказной работы ЭВМ, отнесенная к одному двоичному ра«р*д> В табл. I представлены исходные данные, необходимые при решении поставленной задачи для

1аб.1жи I

Исходные данные для задачи оптимального резервирования

( к) ( - \ 1«. •л') '/к X

(П) м >•1

I 3.4.5.7 10 24

(4)

2 2.5.7,9.11,13 19 4в

(6)

3 3.4.5,7.11,13,17,19 2« 72

(8)

4 2,3,5.7.11.13.17.19,23,29 37 %

(Ю)

Для сравнительной оценки эффективности двух рстервмрованных систем предложена величина

К»

1 - (О 1-р ¿£(0

Результат решения обратной задачи оптимального резервирования для с . байтовых разрядных сетох ЭВМ и соответствующие значения

К. „ (1Я ) сведены о табл. 2.

С целью уменьшения объема вьгагсленнй при ^ =8 использован метол покоординатного наискорейшего спуска. Приведенный расчет показывает. что

МСС уже при ^ >1 обеспечивает более высокую надежность, чем широхо применяемое о позиционных системах счисления тронроааиие каналов СП Это объясняется простотой применения поэлементного резервирования по ¡х-ядому основанию МСС, которые функционально независимы, еьцд) ссгоа-фнчссюа особенностей функционирования СП о модулярной «гстеке сягегдг-

кия С увеличением I эффективность использования МСС существенно возрастает по сравнению с троированием СП в ПСС.

Таблица 2

Регулыаты решения обратной задачи методом оптимального резервирования

t X«, О'.) Ov КЮ

<П)

1 (1.1.1.2) 0.99827 0.9994« ф

(4)

2 (1.2. 2.1,1,2) 0.99658 0,99625 1.09825

(6)

Î (1.2. 1. 1,1,2.2,2) 0,99588 0,99020 2,38089

(8)

4 (1,2.1.1.1.1.2.2.2, 0,99440 0.97875 3,79728

(10) 2)

8 II. 1. 1.2. 1. 1, 1.2. 2. 0.99173 0.89457 12,77752

<16> 2. 2. 2. 2. 2. 2. 2. 2)

Исходя hi характера изменения во времени вероятностей безотказной работы синтезированных структур можно сделать вывод oi м. что использование непозицнонных CII имеет смысл тогда, когда P|y|Q_(l) ниже некоторого определенного значения Дальнейшим развитием синтета оптимальных стругтур CI I в МСС является введение одного контрольного модуля с распределением резерва отимальным образом между всеми модулями, включая и контрольный Данная задача является задачей динамического резервирования.

H работе получен алгоритм определения уровней резервирования для различных случаев, если при модернизации спецпроцессора в МСС необходимо уменьшить его изгтенсивность отказов Го раз. Выведены соотношения, on, елсляющис необходимые уровни мажорирования, а также дублирования и троирования при использовании нагруженного резерва. Их можно использовать ках в случае ужесточения требований к интенсивности отказа вычисли^ тельной структуры, так и увеличении времени ее функционирования в Го роз.

Для рассмотрения влияния позищюнно-остаточной системы счисления (путем кодирования каждого остатка CCi по модулю П1{ МСС кодом Фибоначчи) на надежность СП сформулируем соответствующую обратную задачу оп-

тимального резервирования в комбинированной системе. I дс роервные ИI г каждому модулю находятся в нагруженном роерве

Необходимо определить такой вектор X = (х |, X 2.....X п ) с<к и

ва резерва, для которого при допустимых 1аграгах У обор^лованн* иомГи нироаанной вычислительной системы яостжалось бы чакснчльмос пмчеш вероятности безотказной работы (Р?'[х] • верояшость беимкаиш

работы ЭВМ, функционирующей ■ МСС. вычислшсльныс 1р.ил и коюро реализованы в I - коде Фибоначчи Следовательно, имеем слсл>нш|>к> млн магическую запись обратной задачи отималыкм о резервирования

Р<.п)(Х-Х<х,.х2.....хп)]-Р^п) Прх((«)

Ь"!

• шах

Уц-Еа,««,*!)*^,

1-1

где X, ¡-я компонента вектора X рсюрвируемой комбинированной вычнси тельной системы, которая численно характернает количество рск-рвных щ. числительных трактов, подключенных к рабочему Н1 по ланночч основант ГП, МСС ( X» ■ 0,1,2...); <1« - количество двоичных рафялов. необходимых л кодирования остатка по модулю ГП, МСС в I - коле Фибоначчи. П количсс во оснований комбинированной систем и.

х, •»!

вероятность беютка

ноД работы по основанию ГП, МСС комбинированной вычислительной сиси мы при условии маскирования любой однократной ошибки в В1 »а счет н< пользования 1 - кода Фибоначчи; • интенсивность огкаюв оборуловэдг ЭВМ, отнесенная к одному двоичному разряду разрядной сетки Для срлии ния надежности комбинированного СП возьмем трехкян&льный спсипроцо сор в ПСС.

Сравнительный еныю надежности (по вероятности бекпкаыюй рзб<

ты) показах, что при / г 2 комбинированная вычислительная система каля

нее, чем широко цромекяемгя в ПСС вычнелнгедьыгя структура. Пра ^ 2 данная систол надежнее не только трехкшальной ЭВМ в ПСС. но и СТ функционирующего в МСС.

С задачей синтеза структуры непозиционного СП тесно связан выбор »бора оснований (модулей), отделяющих его рабочий диапазон и аппара-фные шрагы Первоначально оптимальный набор оснований МСС был оп-глелен ;tm суммагорного варианта непозицнонногэ СП н впоследствии, без )лжных на то оснований, распространен на другие методы проектирования îeiutpoiteccopoB (1абличный и кругового вращения).

Сформулируем общую задачу минимизании количества оборудования

П гтрн заданных требованиях к диапазону разрядной сетки в следующем виде

■

м-гьaconst» ft

* (2) VÏÏre- -»min ft

гле M • диапазон разрядной сетки СП, П - число модулей; Дш,) -ункння связи аппаратных затрат i-ro модуля с его значением.

11ри методе круговою вращения имеем ftm,)=m, Используя неравен-то Коши. что минимальное значение аппаратурных затрат будет в случае шешлна модулей ш, МСС Аналогичный результат получим н при таблич->м метле построения непозиционного СП.

г»

Следовательно, для отделения набора модулей МСС в ряду простых

исел фиксируется модуль, бли!кий к значению Ч/м~, затем справа и слева

п

г него выбираются остальные так. чтобы выполнялось условие |~Jm, £ M.

i-l

Количество оборудования V(n) спецпроцессора согласно (2), ввиду patienta модулей определяется соотношением

V(n)=£f(mj)=nf(iyM)t i=l

лахо остается открытым во!фос о числе оснований. При многоуровневой ^числительной структуре необходимо вместо П ввести параметр П| равный ,-ммарному числу подмодулей ниж :го уровня. Если производится дихото-ическое деление равных модулей, то П|=П-2Г"' (Г - величина уровня в струк->Т>с Cil) В пом при использовании табличного метода построения спецпро-ессора

dV(n1)i dnj

2

N

J. 1 oj •МП| -M'l +n,M"'

lnM-4- M К nfj '

откуда минимальная величина VT будет равна VT(nT)=2 e lnN при nJ=nr=21nM.

Метод кругового вращения позволяет достичь значения аппаратных м трат V,(n,)=e-lnM при П|-П,=|ПМ.

Полученные параметры являются предельными и определяют ннжнкя границу аппаратных затрат для соответствующих методов построения (.11 пр оптимальных величинах ГЦ н П, Г>ги количественные оценки предельны значений инвариантны к числовому диапазону, погтому их можно нспольк воть при теоретической разработке вычислительных трактов CI 1, основании на различных методах реализации модульных операций

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

Оснозной характеристикой затрат оборудования, необходимого для ж

строения табличного вычислителя является число его узлов V = m 2 . i л V - КШ51ГЧССГСО логических злемиттов, ш - модуль операции Существуют»! cpinepjui срсгтггельноЛ оценки табличных алгоритмов не учиш&ски реал» 32U3SO симметрия Т&блНЦЫ КЭЛН, СОЗМОЖИОСТН ОрГШПГШШИ СНСЦИаЛЬНОГО «

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

ОПРЕДЕЛЕНИЕ Под коэффициента W ' шгарзтурного выигрыша оборудовании тгблшш следует погашать произведение сглнчини к • числ операций на отношение количества уздоз V полной теблнцы и количеству f узлов сокращенной тсблицы, т.е.

v/=k-V/N (3

Выражение для заачешш V согласно (3) указывает два пуге, шаод.сзс щнх сократил» оборудование, требуемое для построения rcdansom вшясл; теля: 1) снижение показателя степени, 2) умош&ешк величины модула ВТ.

Обычно в схемах модульного сложения используются свойства симмстог арифметической таблицы относительно левой диагонали, а в схемах мольного вычитания ~ относительно правой. Это определяет вовможностъ реа-гшпин аддитивных операций путем использования 0,5 части таблицы Кэли. шчсния а (р). колируются как ГП-а (р), если они принадлежат диапазону

-11. Отличительной частью диапазона является индекс

|. Отличительной частью диапазона является индекс У а (Ур ] Га(тр)=

О, если 0 £ а(р)£

т +1 ' <4)

1,еслн —-— й а(р)5 т -1

4»

В дянном случаз I ■ т2----х = 4~~т1 . при т-11

(т -1) ^га-М

, | - 2.42 Более эффективным является алгоритм, основанный на

1ализе четности операндов (X и и соотношении четности между ними. Его ^пользование позволяет уменышгть примерно в 2 роза величину входных тераилов. но требуется применить в необходимых случаях корректно ре-/льтата операции на еднннцу. Несомненным его достоинством является

менмнение N до величины [(т+1)/2]2, ввиду чего \У,=4[ш/(т+1)]2.

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

с Уа(Ур)=г0>(1. Приняв следуюише обозначения

а ф') = а (р )шо<1 [ш / <1 ] и Л = [ш / ё ], имеем (а ± р)т<х! т = 1(а'±р') + (га ± Ур)' Д]то<1 т

Общее число табличных элементов (узлов) N при этом составит N = ^(т/а)2 + + 2(т/<1)-2<1,

тогда d^ ■ -Jm и N мнн = 5ш Следовательно, при выбор

d « >/ш" число узлов таблицы обладает не квадратичной, а линейной завн

с им остью от величины модула, что позволяет существенно повысить нале* ность и точность вычислений

Обобщением приема, основанного на анализе показателей четности отк

рандов О, Р и их соотношении стал алгоритм, использующий внутренний ми дуль К устройства. В этом случае

(o±p)modm= |к(а<±Р')+(Д. ±Ag)jmodm

где а '(р') = [а (р )/ к ]. Аа(р) = a(p)mod к

Следует отмстить, что при к-2 имеем случай, соответствующий аналиг четности операндов. Число табличных узлов для внутренне! о молу ля к

N » ^(m/к)2 + 1-к2 + 2(т/к)-2к.

тогда к „„г ж лЛтГ, а N мин = 5 m При схемной реалктании тп алгоритмы соответствуют двухуровневому построению тракта МСС 1с;и число уровней равна Г, а величина подмодуля нижнего уровня q, то

N(f.q)«i

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

ко, когда Чоот=[1п(2шг1пг)1/21пг. Величина Ц выбирается, исходя и« требований к элементной базе операционного устройства моду лярной арифметн кн. При этом минимум еппгрзтурных затрат достигается, ссл» 1

гопт =тч.

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

хеши второго операнда Э по степеням чиста 2. Для получения ретуяьгяп

терапии (a P)modm необходимо прончвсстн последовательное сложение

чисел вида (<* • 2' jmodm для тех разрядов двоичного представления числа [). S, которых ровны I.

Ann.ipíii мыс «траты на реализацию блока умножения на констагту со-;|ая,|«ни величину \fm log j ni. Получаем N»my(y<2), те указатель лепени к выражении для необходимого оборудован!» уменьшился.

[абличнос восстановление результата операции по модулю Ш ограничивает уменьшение аппаратурных затрат до величины N~m. ноаяисимо от исюлов кодирования входных операндов и применяемых алгоритмов '>го /плснясня тем. что результат модульной операции имеет ГЛ значений, «. le.iciMtc чсн> табличный вычислитель Ш узлов, что подтверждается и варницами сжатия цифровых данных при нумерационном кодировании.

(И >пч\> недостатка свободен таблично-групповой метод Оунцюсть его .«кто»» а последовательном использовании группы таблиц при проведении иоду лммтй операции Отличие его от известных в ПСТ алгоритмов заключает-;я • том. что ветчина ратряда t»2 и разрядная операция выполняется табличным путем, ввиду чею гювышается прошводитслыюсгь вычислений. Ч neto табличных у».и>» N при реализации трехразрядной схемы с учетом диаго-мльной симметрии составляет

к2

2{t2) 2 2 '

2

ни да tOUT = lfm , N^jjj, a a w'=> . Повышение npoin-

юлительмостм вычислений »mvosiio при реализашш метода, предназначении о для сложения Д чисел но модулю Прсдставкм^модульную систему опе-

uiuoa Ctj а виде

Д т\( . Л N

£ a j mod m j-l i-O

2'Xn,,mod ш J-«

mod m

где По" значение (0 и*м1) i-ro двоичного разряда соответствую исто виз СЦ. Вьфзяагяе, которое нхэочено в кругдые схожем предела-гдет

функциональное преобразование кола числа единиц (с учетом веса разряда) в модульный унитарный код. Заключительная часть операции производится последовательно на табличном вычислителе. Следует отметить, что если Jog 2 m [< (Д ~ I )• то быстродействие этого метода выше, чем у табличного варианта обработки цифровой информации.

Перевод числа из МСС в ПСС базируется "а использовании китайской теоремы об остатках либо полиадической системы счисления. В первом случае требуклея большие аппаратурные затраты ввиду применения позиционных сумматоров, а во втором существенное снижение производительности из за заключительно! о перевода числа в ПСС.

Рассмотрим разработанный алгорзгтм, основанный на нспольюванш процедуры расширения системы оснований При этом по згзвсстным остатка».

а, числа Л в МСС, соответствующим некоторым модулям т„ определяю! значение О,,. | этого же числа для дополнительного основание Шп,| 1хли i качестве ГПП«| выбрать величину (М-1), то остаток по модулю Ш„.| равен по зиционному коду числа Выбор числа Ш„.|"(М-1) не случаен, ибо он объяс нястся требованием (ПГ)П, |,FT),)=4 при (i = 1,п). а таюке npocroiofl опредс ления соответствующих инверсных множителей.

К его достоинстпам данного ил гор иг ма следует агнеезн непосредствен нос получение кола числа А в ПСС, а при технической рсплшации шиможк одновременное проведение двух различных пемндульных операций

Приведенные «шортмы преобразования кодов исполыукп оперший модульного деления, которая и МСС нронзиодтся путем умножения на о( ратую мультипликативную величину делителя. 1$ раГнмс предложены tiapi аигы се определения для простых модулей с использованием теорем Ферм; Вильсона и теории индексов.

Среди различных теорегико-чнеловых подходов к опрелелензио свертк числа по модулю швсстсн алгоритм, использующий цикличность остатков и моду лю в двоичном представлении числа А. Из теории чисел известно, чт основание весов разрядов (число 2) явля ся элемезгтом простого по; GF(m,). ядя которого сугцествует всегда такой наименьший положительш.

показатель степенн Ti, что 2Т| е Imodnij чричем Tj£m,-I. Слсдовате.-аз

последовательность чисел rjs2)modmi имеет некоторый период повтореiи«,

разный X,. Решим сравнение 2Т< и I mod Ш{ н получим

т,- -1

Т; =7-«-г

(mj-l,ind2)'

(т j - l.ind 2) • наибольший общий делитель чисел (т,-1) и ind2 индекса числа 2 но модулю т,). Быстродействие данного алгортха опреде-тяется количеством тактов R для его проведения и примерно равна рзтрядно-гти исходною числа А Для повышения эффективности процедуры представим число A mod ш, в виде

Amodríij = £ Луги»'2 '*Jmodmj

Í-0\ v=0

mod m¡ ■ i

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

1=1, Отсюда также следует и то обстоятельство, что R чиста А.

Полученные pciyльтоты тесно саятлны с теорией рзтложення лробн вида I /Ш, в бесконечную периодическую дробь по степеням числа два, in которой лелует, что если m, - простое число и g-2 - псрпообрзпшА корень, то вторая юлопнна периода охашигстся двойственной к первой. Определим расстояние 1, между двоичными рзтряд&мм. модульные остатки которых о сумме состса-сктт величину т, путем решения сразнениа

(2Ц| ♦ jjmod mj - 0mod m,,

откуда

irtd(m¡ -1) =(índ(m¡ -l),ind2)'N где (ind(m,-lX ind 2) - юябойшшей обя&З avntiель соответствую-

a« чисел Нерггяжтво * Ц| является удобным критерием про ерш

*

aoßCTsaatocm остэтсоа r¡ в периоде. Он птяаяил, тбеггя трудоемки аы-ислжнЯ, уточнить, что g=2 не сзлхется сушествоошм условием симке- рии, тгэсягеаео юяуяя, расарсаеяагкя eenrras Tj аертззХ^

Чет* ер тая глава посвящена разработке метода кольцевою вращения а модулярной арифметике. Данный метод был предложен сравнительно недавно, поэтому для сю широкого использования необходимо рснипь рял »а.чач. связанных с выбором рациональной структуры операционно! о устройства. а также с определением критерии оценки быстродействия выполнения модульных операций

Пусть произвольная алгебраическая система, представлена в вилс S = {(*>*), где G - неттустос множество; * • тип операции, определенной ли

любых двух элементов а,РбО. Операция сложения на множестве классо« вычетов, гюрожденных идеалом J, образует новое колыю, называемое коль цом классов вычетов R/J. Пго можно представить в виде Z/(m), |де / множество целых чисел 0,1,2,. . .; Ш - основание в МСС (если основание ГП простое число, то Z/(m) - поле) Данное обстоятельство обуславливает hoi можность реализации арифметической операции сложения в MCC iiyien кольцевою сдвига.

Для формирования модульной суммы (Gt4{))modm /ряпккт ((X

P)modm> достаточно код операнда а циклически сдвинуть влево (вправо! Технической основой для подобною метода реализации арифметических one раиий являются кольцевые pet негры еднша (КРС) Операции умножения (де ления) по модулю ГП может быть сведена к аддитивным модульным онераци ям, исполыуя теорию индексов.

Исходное состояние содержимого KI'C для операции (a+fi)rnod7 с< ответствует первой строке таблицы Кзли

000 - 001 -010 - 011- 100 -101 -ПО

Максимальная длшелыюсть проведения модульной операции равн Т = J.og 2 m[ m . Однако существует возможность получения резульп той модульных операций путем сдвига содержимого КРС только тю одном двоичному разряду. Пусть исходное состояние кольц.дого регистра для ГП" равно

0-0-0—1-0-I-I.

В первых трех двоичных ргзрядах КРС при последовательном сдви; \ один двоичный разряд получим все необходимые вычеты от 0 -о 6,а Т=П Для формирования исходного состояния КРС для произвольного значения Ml

|уля предложен алгоритм, основанный на построении нормальных период»«-юских систем, имесгных в теории функций с равномерным распределением (ровных шлей

Другой подход к повышению протводительности выполнения модуль-1ых операннй iipc.ua! асг алгоритм унитарною кодирования При »том исходим: сосюяиис К!Ч' состоит ю Ш - двоичных разрядов н первый операнд а за-нкится в (1-й рифял кольцевого регистра, переводя его в единичное состоя-ше «торой операнд Р укатывает на число сдвигов содержимого К1Ч', т е

Г- (V а верхняя |ра»1ь составляет величину (ГП-1). Следовательно, тралишь шный кршермй оценки быстродействия модульных операций не потволяст рат1И1ь ми два алгоритма.

К ведем шжаитель быстродействия выполнения модульных операю1Л и* сравнительно« о аналкм алгоритмов, исполыуюших метол кругового »ранения (>лним и» важных факторов при пом является простота его пркмеме-1ия » инженерной практике

< >11Р1-Д1.11НМ1 Иод интегральным критерием Я сравнительной оцени нроиннмшпьшчтн арифметических оперший условимся понимать отно-ненне о ммм «к с у едини»« кольцевого регистра для каждой пары операндов, ифслелешюм mo.iv те т и типе операции стандартного алгоритма унитарного однроммня. к соответствующей величине Та рассматриваемого алгоритма,

е К - ^ (т -!)/Тга

Для обычных алгоритмов, связанных с реализацией стюЯста симметрии гблицы К >1 н К будет иметь постоянное значение, при высот оскороспшх -I ад ист с я стспенной функцией от (Л с положительным покупателем, подобно ;о»ффинист> V.' аппаратурного выигрыша в оборудовании таблицы

Рассмотрим рал рафэботашшх циркуляитных алгоритмов алжкякых шерецкй, те таких, основой которых является метод кругового вращения. ).хнн из них предполагает нетрадиционное пепользоваиме КСР, когда пауты «ежду тактовыми кштульегми применяются для продвижения содержу «ото

«гнетра согласно первого операнда СХ При ттом существенно уменьшается хшпеслю используемого оборудования, еоигхо дяпгсзыюсть бкшрмой ете-пним рлака ГПДХ((Х,Р).

Для определения значения Тт воспользуемся теорией конечных раик стей. При анализе последовательности Т|, Тз, Т), ... получаем ранмезш

уравнение четвертого порядка Д*Тт = 0. которому соответствует »тарами уравнение четвертого пррядка

Тт+4 = 4' Тгоч 3 ~ 6Тт+2 + 4Т«п+1 ~ Тт. В результате его решения получаем

т п^т-1)(4т+1) т~ 6

откуда при т»11 Я »0,73; т.е. производительность зтого алгоритма, п^ прочих положительных характеристиках, несколько ниже, чем в случае ум тарного кодирования.

Алюрнтмичсскую процедуру, основанную на анализе чегюсти онера

доя а, (1 и их соотношении можно с успехом применить, в данном случа для уменьшения временных затрат на реализацию модульных операций С крашение диалаюна значений входных операндов до величины ((Л-1 )/2 н зволяет существенно повысить быстродействие При ГП-11 и оперши

(а-ф)тсхШ Я* 11. Аналогичные характеристики нрокмюлитслыкк-имеет алгоритм, нснользукиций свойства симметрии арифметической табл

цы. т с значения индекса операнда Уа(Ур) равные 0 и I

Для выполнения операций модульного умножения разработай ил горн множества котуров (АМК). Оператор К1'1 кольцевою слеша (ОКС) для V дульной операции сложения и вычитания определяет величину, выраженн) 7. двоичными разрядами 1СРС и направление сдвига этих рафядов Опера т

АМК представляется в виде где ! - номер ко»пура, в кагором прш

Д1ггся сдвнг содержимого разрядов КРС ^ = 1.Ш- 1), т - модуль МСС,

которому работает устройство, ^Р-номер уг энавливасмой строки матри значений (сх-Р)шо<1ш;^ - показатель ОКС, определяющий число сдвигов I держнмого разрядов КРС в '-м контуре.

Суть ЛМК состоит а том. что по значению (3 второго операнда устаная-иааетса ()-« строка таблицы значений (а*Р)то<1т путем сдвига содержимого азрялоа КРС по отдельным контурам (по отдельным модулем Ш') в кмлуре !РС. причем , так как минимальный (первый) модуль равен двум, т е

П| = 2 11ервый разряд КРС устанавливается одновременно со вторым Усыновление значения содержимого разрядов КРС проводится последовательно права налево (см рис I), начиная с (Ш-1) - п> (старшего) разряда и до второ-о включительно

(а*Р)гоо<Ьп

Ы

Ш|"2

«-2. пь-3

птМ

Ркс. 1. Сгруэтурз реаятннн ЛМК

Веедсм поютгз сбобгцггпк>го оператора кольцевого сдвига (СОКС) о «.■к матрицы = Текил образом, СОКС |К^| будет состо-

гп» 8П (Ш-2)-а ОКС н шшет &пъ рогдоген по строаам'К^ (] = 2,я|. либо

Э ШГ)р!Ш ^1 = 2,1*) В ВПК

{к^к^фМН--.*!;*1)

Время установления ^й строки матрицы (время реалкшцнн операции значений (аР)гПОС1т равна сумме показателей (ХЖС для ]-й строки, умж»-жениой на величину р — П1( '>то время можно также определить, не холя из выражения (5).

Для проведения анализа соответствующих алгоритмом необходимо он рслслиться с выбором величины 1т. Используем тог факт. чм> промежмоч мыс операции на каждом уровне вычислительной аруюурм проводят одно временно Следовательно, лотично определить на каждом уровне молифиии рованную таблицу Кзли (значения которой - величины елиш \ л для *а*,и>1 пары операндом), сумма элементов которой макс им,т.н.) 1;нсм ел мм кронам зти показатели по всем ступеням онерационною устройства, т с

г

«-1 J

где Г-чнсло уровней, Ту- )-Я покшалели модифицированной щблит Кзли ¡-го уровня. Максимальный покамисль определяет верхнюю опенку но лучения промежуточного результата операции данной ступени (Мметм. чп при табличном методе реал танин арифметических операций в случае \nmup ною кодирования бинарная операция выполняется за один такт, следователь

но. Тт=т2.

Рассмотрены алгоритмы комбинирования основных методов просктир» вання двухуровневой вычислительной структуры (табличного и круговог вращения) В этих случаях шпегральный критерий Я ог шлагт степенной зг ннснмостью с положительным показателем относительно модуля операции Наиболее перспективным является алгоритм нулевкзшдои остатков, у которог

К~3/2пг'?. т.с быстродействие проведения модульных операций в по.ттор рай выше по сравнению с обычной двухуровневой МСС. Определение вс.и чины Тт. в данном случае, сделано с помотг ю алгебраических прообразов; ннй протводящей футцнн.

Достоинством алгоритма, в основе которого лежит внутренний модуль 1 устройства, является возможность вариации между аппаратными затратами I быстродействием путем соответствующего изменения величины К. Отмены, что выбор к = -Уш является оптимальным не только по отношению к ппарагиым затратам, но и временным.

Многоуровневая структура ВТ состоит из Г уровней, а модуль устройст-а ГП разделен на (1 частей (см.рнс.2).

Т..1 Ъл . . . Ты

\ / \ У

ТЫ *

\ /

\ т,., /

Рис. 2. Мпогоуроздгевгя еыч»оппелыш структура

Элементы се Т„ = 1,П } = могут быть реализованы кз тгблич-ых вычислителях, либо Больцезых регистрах сдвига. В первом случае

„*■ , а тек ках , то запишем Тт = ПТ11(^2 2(1.

С -целью шшкшгации ершенных затрат определим оптимальную селп*

шсу с! ( т * 1о82 2а) « т^- га + ^¿у) я 0 • отауя» получаем <1^ =21пт-1п2 иТи = е^:[2 + 1<^2(!пш-1п2)].

При использовании метода кольцевого вращения и алгоритма унитарно го кодирования Тга « — ш4 log2 2d. В этом случае находим d^ следующим образом

(1 i, -,V 1 'Y 3 In m I Л darr =3lnm ln2 и Тт = |с'"Под2(б1пт !п2).

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

doni и Тт занимают промежуточное положение между определенными выш< значениями.

В пятой главе рассмотрены особенности схемотехнической реализапш разработанных алгоритмов в вычислительных трактах комбинационного типа К этому типу следует отнести ВТ, в основе которых лежит прямой логически! и табличный методы. Они позволяют строить модульные тракты с высоки» быстродействием.

Основное противоречие, влияющее на аппаратурные затраты при раз работке табличных ВТ. выполняющих аддитивные модульные операции, не посредственно связано с количеством осей симметрии соответствующе] прнфчстичсской таблицы. В схемах модульного сложения (вычитания) ис пользуются спойпьп симметрии относительно правой (левой) диагонали, то |да как в схемах модульного умножения реалитуются свойства снммсгри! таблицы Кэлн •.:,,'чс««1сльно вертикалей и горизонталей, проходящих межд числами (m-l)/? и(ГП+1)/2.

Наиболее ч,чфсктив»ым приемом, устраняющим это противоречие, яв лястся алгортггм, основ 1«лш»; •■а с шлизе челюсти операндов a, Р и соотис шепни показателе!» •tt.iocth между ними. Унивсрса. ным способом сокращс ния аппаратурных затрат при проектировали., модульных ВТ является их уг рощение. При этом улучшаются и надежностные характеристики, ввнд уменьшения числа элементов ВТ н связей между жми. Техническая рса"изг пая этого способа возможна при операции модульного умножения с помощы (rn-2)-x блоков умножения »и констшггу по модулю. Использование ropi

отельной симметрии таблицы Кэли позволяет сократить число блоков до ве-1ИЧИНЫ (ш-3)/2. а вертикальной - существенно уменьшить количество обо-•улования при их построении.

Проведение группы операций модулярной арифметики либо ряда их тапов на одном табличном вычислителе тесно связано с понятиями ппралле-1изма и конвейеризации. Трактовка этих терминов в узком смысле предпола-ает рассмотрение их на трех логических уровнях: элементарных операций шл словами, арифметических операций и вычислительных процессов. Следо-ютельно, проводимая в данной главе оценка использования таблицы на первых двух уровнях сводится к различным типам совмещения операций. К пером у относится применение табличного вычислителя для одновременного поучения результатов нескольких различных операций. Во втором случае этот гроцесс производится на одной таблице последовательно во времени.

Одно из рассмотренных устройств реализует первый вид совмещения. )но предназначено для про веления двух операций: умножения чисел по мо-[улю и определения остатка числа по модулю, равному проюведешоо двух снований в МСС. В частности. если модулярная система счисления состоит N лвух оснований, то в этом случае реализуется перевод чнссч к» МСС в по-ициоиную систему счисления. В схеме умножения чисел по модулю

2-Р)т<х1т используются свойства симметрии таблицы Кэлн. Единствсн-1ым ограничением для реализации второй операции является условие пах{т„ш,}=т; где ш,(т;) - основания МСС. Аппаратурные затраты на юстроенне общего табличного пычнелшелд состапдяют селичкиу У=т2/4,

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

П| и ГПз (т 1 -т^ ^т). а такай: третью - для восстановления результата мо-;уль»ого умножения по основанию Ш. Тсблнчиый вычислитель прсдстгзляет алояение всех трех тгблиц, количество оборудования которого состав г сг-

.. ш. -т2 +1 / > Ш|+Й1

ячину V Ш| ■ т^ +—'—-— т^) *———«-, укапывая что

Ш2- ш/ Ш|, определим Ш)= Шг-г/т. В этом случае будут минимальны! аппаратные затраты V— щ.

Один из таких ВТ предназначен для определения модульной суммы ¡ чисел. Его функционирование основано на одновременном поразрядном ело женин этих чисел, представленных в двоичных разрядах. Вначале производит ся трансформация кода числа единиц на входных шинах операндов в модуль ный унитарный код. Заключительная часть группового модульного сложени производится за ]log2tT)[ тактов на табличном вычислителе Время нроведе ния операции не зависит от числа слагаемых и определяется величиной моду ля m устройства

Шестая глава связана с анализом вычислительных структур последови тельностного типа. К ним относятся операционные устройства, при проект« ровании которых использованы сумматорный метод и метод кругового ври щения. Ряд разработанных алгоритмов реализации модульных операций носи универсальный характер, ввиду чего они могут быть применены для построс Лия вычислительных трактов обоих типов. Эти процедуры, в данном случа( направлены на повышение быстродействия операций сложения (вычитания чисел по модулю, однако их реализация способствует и снижению аппаратур ных затрат.

Для реализации мультипликативных модульных операций мстодо! кольцевого вращения существуют два варианта Первый, наиболее нзвестны( основывается на использовании теории индексов. О/раннчсннсм сю являете

ю, что тто возможно, когда П1=2, 4, рф, 2рф (р - простое число, (р - иат) ' . ральнос число), ибо только в этих случаях существуют первообразные кори g по модулю Ш. Свобо;> им от утого условия является способ, бозируюшнйе на алгоритме выбора состояния кольцевою регистра сдвига.

Известно, что повышение быстродействия выполнения арнфмстнч( еккх операций СП и снижение аппаратурных затрат при го построении явл) ются взаимоисключающими требованиями. Одним из путей их согласования тактико-техническими характеристиками, предъявляемыми к вычислительны структурам, является переход к многоуровневому построению арчфметнч! скнх устройств. При этом каждый уровень реализуется по различному мет о; проектирования, вследствие чего появляется возможность aapwuunt м<*чу количеством оборудования устройства и его быстродействием.

В составе ВТ для проведения операций конечной арифметики применяются триггер ные и логические элементы. Для выполнения анализа схемотехнических решений по затратам основного оборудования необходимо установить между ними соответствие. Аппаратные затраты триггера можно привести

к соответствующим затратам табличного элемента с коэффициентом У=4+8. Рассмотрим общий случай оптимизации двухуровневой структуры ВТ, м е2

когда N - ш| + УШ2 , где Б) и Ег - значения показателей степени функций Г (т 1 ) и ^ (ш 2 ) для различных методов построения ВТ и подмодулей Ш) и Ш2. Определяем, что

Проведен сравнительный анализ основных характеристик СП в модулярной и позиционной системах счисления. При расчетах использовались параметры синхронных суммирующих устройств и умножителей. У СГ1 в МСС для операции сложения характерны несколько выше аппаратурные затраты, но налицо вышрыш в быстродействии. Быстродействие операшш умножения, при применении многослойных матричных умножителей, существенно пыше в позиционных структурах при росте количества оборудования. Табличный napitaiгт СИ в МСС отличает значительный выигрыш как по быстродействию, тех и но аппаратурным затратам.

Предложен и обоснован критерий оценки эффективности модулярных ВТ, пригодный для анализа различных методов проектирования. Он носит комплексный характер, т.к. объединяет такие характеристики как быстродействие проведения срнфметнческих операций и затраты оборудозания. Ввиду тесной связи критерия с построением СП его моано использовать для сравнс-кия непознционных спецпроцессоров различных тнпоз.

¿.-х/иэчетше содерж1гт основные выводы и результаты. В приложениях приведены расчетные данные дяя аэгтеза структу t СП еглодом покоординатного шискорейшсго enyesa, пргшгрв «ехптамх рэ с

при этом

«и«:

повышенной плотностью распределения простых чисел и оптимальные значения подмодулей в комбинированных двухуровневых ВТ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

В ходе выполнения указанной работы были получены следующие ре зультэты:

1. В результате проведенных исследований заложены теоретически! основы структурного синтеза непозиционных СП. Их применение позволит впервые получить структуры спецпроцессоров для существующих и перепек тивных диапазонов разрядных сеток, а также различных видов рек-рвирова ния Для повышения отказоустойчивости СП предложен новый подход, за ключаюшийся в использовании кодов Фибоначчи при проектировании вмчис лительных трактов.

2. Сформулирован оригинальный д/юрнтм определения рациона,!!, но?; глубины рс -лрт-нрования СП в МСС при модернизации сушествуюшн вычислительных структур. Результаты расчета доведены до инженерно практики.

3 Описан новый подход к решению задачи минимизации аппарагурны з.праг СИ. С сю использованием получены научные результаты по выбор системы оснований МСС для известных методов построения спецпроцессс рои Л.|"1М1сйшее углубление логе подхода позволило впервые получить Iр» ннчпие параметры аппаратурных затрат при проект ироь..нин СИ. Определен! области целесообразного применения непозиционных и позиционных спет процессоров.

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

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

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

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

7 I Ipoведен анализ и классификация арифметическое устройств в МСС комбинационного и последоаагельностного типа. Ввиду того, что они выполнены на различной злсмстггной базе, предложен оригинальный прием определения взаимосвязи аппаратурных затрат между логическими и трнггсрными злемешоми. 1>то позволило провести сравнительный анализ ВТ различного типа и определттть оптимальные параметры уздоз при комбшпфозгишом построении t

8 Рассмотрение структур многоуровневых ВТ позволяет сделал, вывод о том, что они подобны мно1\гсрусньш блокам реализации немодульных операций, характерной особенностью которых является отсутствие разветвлений выходоа утла Вследствие зтого сба вернгнта струзст>р могут иметь общие средства диагностики и сходные алгоритмические процедуры. Данное обстоятельство позволяет существенна позыатть однородность к модульность чаю-зкиксиных Cil.

9 Сргзтпельиый анализ елтрлтурных и временных ззтрзт тфи построении СИ на базе жпшшонной н непозн.шонной систем счисления по езздл кгсомкешсый гыктрыш при использовании последней, особенно для та акч» ных спецпроцессоров в МСС. Прсдлсзхн а абосноаг» критерий ермнигель-

сценки тффехтизнссти сгдексалсльных третоэ дзух рэтличних т n:os Сл tsxm кпзг.'жшзьй! хгрггтер. т.к. учяпвегт быстродгйстгкг гipose. -_-h;î3

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ирхик В.П. Проектирование непозиционных специализированных процессоров. - Воронеж: ВГУ, 1999. -136 с.

2. Краснобаев В.А., Ирхин В.П. Пример решения обратной задачи оптимального резервирования в системе остаточных классов // Кибернетика.-1990,-№3.-с. 123-125.

3. Краснобаев В.А., Ирхин В.П., Кононова И.В. Методы и алгоритмы реализации арифметических операций в системе остаточных классов// АСУ и приборы автоматики. - Харьков: Виша школа. -1990. - №93. - с. 46-53.

4. Червяков Н.И., Краснобаев В.А., Ирхин В.П. Отказоустойчивость специализированных процессоров автоматизированных систем управления и средств связи. - Учебн.пособие. - Ставрополь: Ставропольское ВВИУС. -1991.-127с.

5. Ирхин В.П. Улучшение основных характеристик операционных устройств спецпроцессоров// Тематический научно-технический сборник. -Харьков: ХВКИУ РВ. - 1992. - с.31-33.

6. Ирхин В.П. Алгоритмы определения позиционных характеристик кодов в системе остаточных классов// Тематический научно-технический сборник. - Харьков: ХВКИУ РВ. - 1992. - с.33-36.

7. Краснобае» В.А., Ирхин B.II. Вариант оптимизации структуры "ЖМ. функционирующей в позиционно-осгаточной системе счисления/ материалы международной НТК «Представление, обработка и передача информации).. С'очи-Харьков: AI ПАНИ, ХВУ. - 1992.-е. 65-69.

8. Краснобае» В.А., Ирхин В.П. Варианты определения обратной мультипликативной величины числа п системе остаточных классов// Тематический ззаучно-технический сборник. - Харьков: ХВКИ". РВ. - 1992. - с. 132140.

9. Краснобаев В.А., Ирхин В.П. Алгоритм реализации операции мо-дулыюго умножения в системе остаточных классов// Электронное моделирование. - 1993. - №5. - с. 20-26.

10. Ирхин В.П. А"горнтмы табличной рс.-лизацин остаточной агчф-мегикн// Труды института: Методические основы развития способов 31 средств рлдноэлсктройной борьбы/Bi 1РЭ. - Воронеж. - 1995. - с. 37-39.

11. Ирхин В.П. Надежностный синтез вычислительных структур остаточной арифметики// Вторая межведомственная НТК «Проблемные вопросы :бора, обработки и передачи информации в сложных радиотехнических системах». Тез.докладов - Пушкин: Пушкинское ВУРЭ ПВО, 1995. - с. 71-72.

12. Ирхин В.П. Алгоритмы реализации операций модулярной арифметики/ Прикладные вопросы защиты информации: Сборник статей. - Воронеж: Воронежская высшая школа МВД России, 1996.-е. 12-16.

13. Ирхин В.П. Преобразование чисел в системе остаточных классов// Третья международная конференция «Современные проблемы теории чисел и гс приложения». Тез.докладов - Тула: Тульский госпедуниверстттет, 1996. -с.69.

14. Ирхин В.П., Табуненко В.А. алгоритмы формирования исходного состояния кольцевых регистров сдвига// Системы информационного взаимодействия. Сб.науч.тр. - Харьков: НАНУ, ПАНИ, ХВУ. - 1995. - с.23-26.

15. Ирхин В.П., Табуненко В.А. Использование остаточной арифметики при табличных методах обработки// Обработка информации. Сборник статей. - Харьков:} ГАНУ, ПАНИ, ХВУ. - 1996. - с.29-35.

16. Ирхин В.П. Граничные параметры вычислительных структур модулярной арифметики// Современные методы в теории краевых задач «Пои-грягинскис чтения- VIb>: Тез.докладов школы. - Воронеж: ВГУ, 1996 - с.87.

17. Ирхин В.П., Табуненко В.А. Алгортггм проведения двоичного числа по простому модулю// Системы информационного взаимодействия. Сб.научн.тр. - Харьков:! 1AI1У, ПАНИ, ХВУ. - 1996. - с.43-46.

18. Ирхин В.П. Реализация принципа кольцевого вращения в нспози-цнонных вычислительных структурах// Третья межведомственная НТК «Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехнических системах». Тез.докладов. - Пушкин: Пушкинское ВУРЭ ПВО, 1997.-е. 105-106.

19. Ирхин В.П., 1 (авнычко A.B. Вариант обработки социометрической информации при многокритериальном опросе// Научно-методический сборник №46. Управление военного обраюваиня МО РФ. - М.: Военное тпдагельегпо. - 1997.-с. 153-159.

20. Ирхин В.П. Модель надежности непозициоиного спецвычис иге-ля// Всероссийская научная конференция «Современные'методы подтчу мжи-специалистов и совершенствование систем и средств наземного обеспе- :ння озкзиии»: Тез.докладов. - Воронеж: Воронежское ВВАИУ, 1997. - с. 237- ЗН.

21. A.c. 1532923 СССР. МКИ5 G06 F 7/72. Устройство для сложения вычитания чисел по модулю / В.П.Ирхин и др. -1989, Бюл.№ 48.

22. A.c. 1546976 СССР. МКИ5 G06F 7/72. Устройство для сложения вычитания чисел по модулю / В.П.Ирхин и др. - 1990, Бюл.№ 8.

23. A.c. 1546977 СССР. МКИ5 G06F 7/72. Устройство для сложения вычтання чисел по модулю / В.П.Ирхин и др. -1990, Бюл. № 8.

24. A.c. 1552171 СССР. МКИ5 G06F 7/04. Устройство для сравнения 4i ссл в системе остаточных классов / В.П.Ирхин и др. - 1990, Бюл.№ 11.

25. A.c. 1571583 СССР. МКИ5 G06F 7/72 Арифметическое устройсп по модулю / В.П.Ирхин и др. - 1990, Бюл.№ 22.

26. A.c. 1615714 СССР. МКИ5 G06F 7/72. Устройство для умиожеш чисел по модулю / В.П. Ирхик и др.- 1990, Бюл.№47.

27. A.c. 1617439 СССР. МКИ5 G06F 7/72. Устройство для умножен) чисел но модулю / В.П.Ирхин и др. - 1990, Бюл.№ 48.

28. A.c. 1619403 СССР. МКИ5 НОЗМ 7/18. Устройство для перево, числа, представленного в системе остаточных классов, в полиадическую си тему счисления/В.П.Ирхин и др. -1991, Бюл.№ 1.

29. A.c. 1633399 СССР. МКИ5 G06F 7/72. Устройство для сложения вычитания чисел по модулю / В.П.Ирхин и др. - 1991, Бюл.№ 9.

30. A.c. 1633400 СССР. МКИ5 G06F 7/72. Арифметическое устройет но модулю/ В.П.Ирхин и др. -1991, Бюл.№9.

31. A.c. 1636844 СССР. МКИ5 G06F 7/72. Устройство для сложения вычитания чисел по модулю/ В.П.Ирхин и др. - 1991, Кюл.МЬ 11.

3?.. Ас. 1647563 СССР. МКИ5 G06F 7/72. Устройство для умножен -л по модулю/ В.П Ирхин н др. -1991, б:ол.№ 17.

33. . А.с 1667055 СССР. МКИ5 G06F 7/49, 7/72Устройство для умно» • <:;л чнсч-.т i;o модулю/L . J.Ирхин и др. - 1991, Бюл.№ 28.

34. Ас. 168.1!'/1 СССР. M«'C'J5 G96F 7/72. Устройство для сложения !и.:м!и;:;;ия '..¡¿ел по модулю / В.ГШрхт;:) н др. - ¡991, Бюл.М1 37.

35. A.c. 1683012 СССР. МКИ5 GÜ6F 7/72. Устроит но для сложения пычпгг.чпк чисел по модулю /' В.П.Ирхин и др. -1991, Бюл.№ 37.

36. A.c. 1683014 СССР. М1СИ5 G06F 7/72. Устройство для возведен чисел Ii степень но модулю три/ В.П.Ирхин и др. -1991, Бюл.№ 37.

37. A.c. 1689949 СССР. МКИ5 G06F 7/72. Устройство для вычитания модулю/В. П. Ирч'ни и др.- Ь'юл.ЛЬ41

38. A.c. 1697079 СССР. МКИ5 G06F 7/72. Устройство л«я умножег чисел по модуля* / В.П.Ирхин и др. -1991, Бюл.№ 45.

- 39. A.c. 1716511 СССР. МКИ5 G06F 7/72. Устройство для умножения исел по модулю / В.П.Ирхин и др. -1992, Бюл.№ 8.

40. A.c. 1755275 СССР. МКИ5 G06F 7/49, 7/72. Устройство для сложе-ня и вычитания чисел по модулю В.П.Ирхин и др. - 1992, Бюл-Ма 30.

41. A.c. 1756881 СССР. МКИ5 G06F 7/49, 7/72. Арифметическое устроП-гво по модулю / В.П.Ирхин и др. - 1992, Бюл.№ 31.

42. A.c. 1775721 СССР. МКИ5 G06F 7/49, 7/72. Арифметическое устрой-гво по модулю /В.П.Ирхин и др. -1992, Бюл.Л'з42.

43. A.c. 1807484 СССР. МКИ5 G06F 7/72. Устройство для умножения исел по модулю / В.П.Ирхин и др. -1993, Бюл.№13.

44. A.c. 1809437 СССР. МКИ5 G06F 7/49, 7/72. Арифметическое устрой-гво по модулю/ В.П.Ирхин и др. -1993, Бюл.№14.

45. A.c. 1810889 СССР. МКИ5 G06F 7/72. Устройство для сложсшы и ычитания чисел по модулю/ В.П.Ирхин и др. -1993, Бюл.№15.

46. A.c. 1820379 СССР. МКИ5 G06F 7/72. Устройство для сложения и ычитания чисел по модулю / В.ПИрхин и др. - 1993, Бюл.№ 21.

47. A.c. 1820380 СССР. МКИ5 G06F 7/72. Устройство для сложения и ычитания чисел по модулю / В.ГШрхин и др. - 1993, Бюл.№ 21.

48. Патент РФ 2023290. МКИ5 G06F 7/72. Устройство для умножешю исел по модулю/ В.П.Ирхин и др. -1994, Бюл.№ 21.

49. Патент РФ 2018936. МКИ5 G06F 7/72. Устройство для умножешм нсел по модулю/ В.П.Ирхин и др. - 1994, Бюл.№ 16.

50. Патент 2023289 РФ. МКИ5 G06F 7/49. Устройство для сложения и ычитшшя чисел по модулю / В.П.Ирхин и др. -1994, БюлЛЙ 21. г

51. Патент 2018935 РФ. МКИ5 G06F 7/72. Устройство для сложения и ычитания чисел по модулю / В.П.Ирхин н др. - 1994, Бюл.№ 16.

52. Патент 2109326 РФ. МКИ6 G06F 7/49, 7/72. Устройство для сложе-:гя и вычитания чисел по модулю / В.П. Ирхни -1998, Бюл!№ 11.

53. Патент 2110087 РФ. МКИ6 G06F 7/49, 7/72. Устройство для сложена чисел по модулю / В.П.Ирхин - 1998, Бюл.№ 12.

54. Патент 2110147 РФ. МКИ6 НОЗМ 7/18, G06F 7/49, 7/72. Устройство да форшфозания остатка до модулю / В.П.Ирхшт -1998, Бюл.Л'г 12.

55. Патент 2123202 РФ. МКИ6 G06F 11/08. Устройство для репер иро-гилз/В.П.Ирхин-1998, Бюл.Ш4.

56. Пагагг 21^16118 РФ. МКИ G6F 7/72, 7/49. Устройство для с; ожегся N чзгш! по модулю/ В.ПИрхин - 1999, ЕюяЛЬ 16.

57. Патент 2133495 РФ. МКИ вбР 7/49, 7/72. Устройство для вычита ния по модулю/ В.П.Ирхин - 1999, Бюл.№ 20.

Соискатель —В.П.Ирхин

Подписано к печати 18 С9 99_Формат 60x84 1/16

Печатных листов 2 Л Тираж 100 экз. Заказ 433 Курский государственный технический университет 305040, г. Курск, ул. 50 лет Октября, 94

ВВЕДЕНИЕ.

ГЛАВА 1. СВЕДЕНИЯ ПО ПРОБЛЕМЕ.

АНАЛИЗ ПЕРСПЕКТИВНЫХ НАПРАВЛЕНИЙ В ОБЛАСТИ ПОСТРОЕ- 16 НИЯ СРЕДСТВ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ.

1.2. МЕТОДЫ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ И НАДЕЖ

НОСТИ СПЕЦПР,—■ ОЦЕССОРОВ НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ МОДУЛЯРНОЙ СИСТЕМЫ СЧИСЛЕНИЯ.

1.3 ПРИМЕНЕНИЕ ФИБОНАЧЧИЕВОЙ СИСТЕМЫ СЧИСЛЕНИЯ ДЛЯ ПОВЫШЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ ВЫЧИСЛИТЕЛЬНЫХ СТРУК

1.4. ЦЕЛЬ И ЗАДАЧИ ИССЛЕДОВАНИЯ.

ГЛАВА 2. СИНТЕЗ СТРУКТУР НЕПОЗИЦИОННЫХ СПЕЦПРОЦЕССОРОВ.

2.1. ФОРМУЛИРОВКА И РЕШЕНИЕ ОБРАТНОЙ ЗАДАЧИ ОПТИМАЛЬНОГО РЕЗЕРВИРОВАНИЯ.

2.2. ОПТИМИЗАЦИЯ СТРУКТУР СПЕЦПРОЦЕССОРОВ С ОДНИМ КОНТРОЛЬНЫМ ОСНОВАНИЕМ.

2.3. СРАВНИТЕЛЬНЫЙ АНАЛИЗ ОПТИМАЛЬНЫХ СТРУКТУР СПЕЦПРОЦЕССОРОВ В МОДУЛЯРНОЙ И ПОЗИЦИОННОЙ СИСТЕМАХ СЧИСЛЕНИЯ.

2.4. ВАРИАНТ ОПТИМИЗАЦИИ СТРУКТУРЫ СПЕЦПРОЦЕССОРА, ФУНКЦИОНИРУЮЩЕГО В ПОЗИЦИОННО-ОСТАТОЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ.

2.5. ОПТИМИЗАЦИЯ НАБОРА МОДУЛЕЙ НЕПОЗИЦИОННОГО СПЕЦПРОЦЕССОРА

ГЛАВА 3. РАЗВИТИЕ ТАБЛИЧНОГО МЕТОДА РЕАЛИЗАЦИИ ОПЕРАЦИЙ В МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ.

3.1. АППАРАТУРНЫЕ ЗАТРАТЫ ПРИ ПОСТРОЕНИИ ТАБЛИЧНЫХ СПЕЦПРОЦЕСОРОВ.

3.2. СОВЕРШЕНСТВОВАНИЕ АЛГОРИТМОВ ТАБЛИЧНОЙ АРИФМЕТИКИ.

3.3. РЕАЛИЗАЦИЯ ОПЕРАЦИЙ БАЗОВОГО НАБОРА.

3.4. ПРОВЕДЕНИЕ НЕМОДУЛЬНЫХ ОПЕРАЦИЙ.

ГЛАВА 4. РАЗРАБОТКА МЕТОДА КОЛЬЦЕВОГО ВРАЩЕНИЯ В МОДУЛЯРНОЙ АРИФМЕТИКЕ.

4.1. ВЫБОР И ОБОСНОВАНИЕ ИНТЕГРАЛЬНОГО КРИТЕРИЯ СРАВНИТЕЛЬНОЙ ОЦЕНКИ ПРОИЗВОДИТЕЛЬНОСТИ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ. J

4.2. ЦИРКУЛЯНТНЫЕ АЛГОРИТМЫ АДДИТИВНЫХ ОПЕРАЦИЙ.

4.3. АЛГОРИТМЫ ПРОВЕДЕНИЯ МУЛЬТИПЛИКАТИВНЫХ ОПЕРАЦИЙ

4.4. МНОГОУРОВНЕВЫЕ КОМБИНИРОВАННЫЕ ОПЕРАЦИОННЫЕ УСТРОЙСТВА.

ГЛАВА 5. ВЫЧИСЛИТЕЛЬНЫЕ ТРАКТЫ КОМБИНАЦИОННОГО ТИПА.

5.1. ИСПОЛЬЗОВАНИЕ СВОЙСТВ СИММЕТРИИ АРИФМЕТИЧЕСКОЙ ТАБЛИЦЫ КЭЛИ В СХЕМОТЕХНИЧЕСКИХ РЕШЕНИЯХ. j

5.2. ОСОБЕННОСТИ ТЕХНИЧЕСКОЙ РЕАЛИЗАЦИИ ДВУХУРОВНЕВЫХ АРИФМЕТИЧЕСКИХ УСТРОЙСТВ ПО МОДУЛЮ. ]g

5.3. СОВМЕЩЕНИЕ НЕСКОЛЬКИХ ОПЕРАЦИЙ НА ОДНОЙ ТАБЛИЦЕ.

ГЛАВА 6. ВЫЧИСЛИТЕЛЬНЫЕ СТРУКТУРЫ ПОСЛЕДО-ВАТЕЛЬНОСТНОГО ТИПА.

6.1. РАЦИОНАЛЬНЫЕ СХЕМОТЕХНИЧЕСКИЕ РЕШЕНИЯ ДЛЯ ПРОВЕДЕНИЯ МОДУЛЬНЫХ ОПЕРАЦИЙ СЛОЖЕНИЯ И ВЫЧИТАНИЯ.

6.2. ПРИМЕНЕНИЕ КОЛЬЦЕВЫХ РЕГИСТРОВ СДВИГА ПРИ ВЫПОЛНЕНИИ ОПЕРАЦИИ МОДУЛЬНОГО УМНОЖЕ НИЯ (ДЕЛЕНИЯ).

6.3. ОПТИМИЗАЦИЯ АППАРАТУРНЫХ ЗАТРАТ В МНОГОУРОВНЕВЫХ КОМБИНИРОВАННЫХ АРИФМЕТИЧЕСКИХ УСТРОЙСТВАХ.

6.4. РАСЧЕТ И СРАВНИТЕЛЬНЫЙ АНАЛИЗ ОСНОВНЫХ ХАРАКТЕРИСТИК СПЕЦПРОЦЕССОРОВ В МОДУЛЯРНОЙ И ПОЗИЦИОННОЙ СИСТЕМАХ СЧИСЛЕНИЯ.

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

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

Исследования отечественных и зарубежных ученых указывают, в частности, на целесообразность применения теории чисел для целей кодирования информации в ЭВМ при построении высокопроизводительных вычислительных машин. Основная идея, предопределяющая необходимость использования теоретико-числовых методов в вычислительных структурах, состоит в распараллеливании обрабатываемой информации в независимых каналах, количество и характеристики которых связаны с числовым диапазоном и точностью вычислений.

В отличие от общепринятого, существует два перспективных направления в области разработки вычислительных средств, использование которых приводит к кардинальному повышению производительности и надежности ЭВМ. Первым направлением является применение непозиционных кодовых структур в модулярной системе счисления (МСС). В таких ЭВМ обеспечивается решение задачи существенного повышения производительности (за счет распараллеливания процесса вычисления на уровне операндов) и задачи обеспечения отказоустойчивости и живучести (путем введения избыточных модулей МСС). Ко второму направлению относится подход, связанный с использованием систем счисления с иррациональными основаниями (коды Фибоначчи и коды золотой пропорции), одним из свойств которых является возможность маскирования отказов типа константа 0 или 1.

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

Существует ряд областей техники, в которых назрела острая необходимость в кардинальном повышении отказоустойчивости и производительности средств обработки данных. К их числу относятся: управление базами данных, обработка сигналов и изображений, оптоэлектронные матричные процессоры, управление в реальном масштабе времени, восприятие речи, машинное зрение, численные расчеты большого объема и обработка текстов. Для этих целей используется, как правило, специализированные процессоры (СП), реализованные для решения узкого класса задач. При этом их технические параметры существенно выше, чем у универсальных ЭВМ, однако и они оказываются недостаточными. В связи с этим исследования, связанные с разработкой многопроцессорных ЭВМ с параллельной структурой, а также вычислительных систем на базе оптических ЭВМ отнесены в настоящее время к числу приоритетных направлений развития науки и техники Российской Федерации и считаются критическими технологиями федерального уровня.

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

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

В настоящее время отсутствуют систематизированные исследования по обобщению современного состояния непозиционных вычислительных структур. Практическому внедрению МСС также препятствует отсутствие оптимальных структур СП для различных диапазонов разрядных сеток.

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

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

В научном плане решение этой проблемы определяет необходимость разработки основ методологии алгоритмов выполнения операций базового набора непозиционных СП, а в практическом плане - разработку требований к техническим решениям узлов и блоков операционных устройств, исходя из их сравнительного анализа на основе разработанных критериев.

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

Для реализации поставленной цели необходимо решение следующих комплексных задач:

1) проведение вычислительных структур непозиционных спецпроцессоров;

2) выбор набора оснований системы счисления и параметров узлов вычислительных трактов;

3) разработка алгоритмических и аппаратурных структур блоков, реализующих модульные операции базового набора;

4) создание оптимальных по быстродействию и аппаратурным затратам устройств для выполнения немодульных операций.

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

На защиту выносятся следующие основные научные положения:

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

2. Методика рационального выбора оснований МСС для различных методов проектирования СП, которая явилась следствием постановки и решения общей задачи минимизации количества оборудования при заданных требованиях и точности вычислений.

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

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

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

Научная новизна состоит в следующем:

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

2. Впервые сформулирована и решена серия обратных задач оптимального резервирования в МСС для различных методов построения спецпроцессоров и диапазонов разрядных сеток, результаты, решения которых позволили разработать теоретические основы синтеза структур СП и получить оптимальные, в надежностном плане, структуры.

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

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

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

6. Сформулированы основные принципы построения многоуровневых вычислительных структур в МСС, в результате развития которых выведены и доказаны основные математические соотношения, определяющие предельные оценки аппаратурных затрат и скоростных характеристик как непозиционных СП так и их вычислительных трактов.

7. Обоснована идентичность архитектурных решений спецпроцессоров и модульных трактов, при условии их рациональной организации, что позволяет использовать большинство известных и полученных в работе научных результатов при проектировании вычислительных структур в МСС на двух различных уровнях.

Практическая ценность работы:

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

1. Синтезированы высоконадежностные структуры СП для различных видов резервирования и точностных характеристик процесса вычислений.

2. При анализе результатов структурного синтеза СП получены данные о целесообразных областях применения непозиционных спецпроцессоров.

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

4. Введены и обоснованы пригодные для инженерной практики критерии для сравнительной оценки характеристик вычислительных трактов.

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

6. Разработан ряд эффективных алгоритмических процедур технической реализации непозиционных операций в МСС.

7. Создан и классифицирован комплекс патентоспособных блоков и узлов СП, работающих в МСС.

Реализация и внедрение результатов работы.

Представленные в диссертации исследования являются результатом научной работы, проведенной в ряде научно-исследовательских институтов, предприятий и вузов (Воронежском НИИ связи, НИИ электронной техники, Харьковском НПО «Импульс», Воронежском госуниверситете, Ставропольском ВВИУС, Воронежской лесотехнической академии и др.). Работы выполнялись в рамках 18 научно-исследовательских работ, проводимых по заказам Министерства обороны. Реализацию данной работы также можно представить двумя направлениями: первое связано с использованием результатов в производстве, второе - в учебном процессе.

Результаты проведенных исследований по первому направлению позволили разработать ряд методик по защите и сжатию цифровой информации, повысить надежностные показатели разрабатываемых систем, определить тактико-технические требования к разрабатываемым образцам вычислительной техники. Разработанные табличные алгоритмы проведения арифметических операций использованы при разработке эскизного проекта по теме 55Ф, лазерной линии связи и в формирователе пространственно-временной и параметрической структур радиосетей.

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

Кроме того, научные результаты работы включены в учебное пособие « Отказоустойчивость специализированных процессоров автоматизированных систем управления и средств связи», изданное Ставропольским ВВИУС.

Апробация работы. Научные результаты и положения диссертационной работы докладывались и обсуждались на 24 научно-технических конференциях.

Основные результаты работы докладывались и обсуждались на конференциях и семинарах, в том числе: на международной научно-технической конференции «Передача, обработка и отображение информации» (Домбай, 1994); на II международной конференции «Алгебраические, вероятностные, геометрические, комбинаторные и функциональные методы в теории чисел» (Воронеж, 1995), на II межведомственной научно-технической конференции «Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехнических системах (Пушкин, 1995), на III международной конференции «Современные проблемы теории чисел и ее приложения» (Тула, 1996), на Воронежской весенней математической школе «Современные методы в теории краевых задач» (Воронеж, 1996), на третьей межведомственной научно-технической конференции «Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехнических системах» (Пушкин, 1997), на всероссийской научной конференции «Современные методы подготовки специалистов и совершенствование систем и средств наземного обеспечения авиации» (Воронеж, 1997).

Публикации результатов работы. По теме диссертации опубликовано 77 печатных работ, в том числе монография «Проектирование непозиционных специализированных процессоров».

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения, списка литературы и приложения.

Выводы.

1. Интегральный критерий К сравнительной оценки производительности арифметических операций, предложенный в этой главе, позволил провести точный анализ разработанных циркулянтных алгоритмов аддитивных и мультипликативных операций. В основе этих алгоритмов лежит вывод из известной теоремы Кэли о том, что отображение элементов абелевой группы на группу всех целых чисел является гомоморфным [141]. Дальнейшее развитие

47-4 этого критерия привело к его использованию для оценки проведения модульных операций на многоуровневых вычислительных структурах.

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

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

4. Следует отметить, что полученные выражения инвариантны относительно диапазона операции. Это обстоятельство позволяет использовать их не только в одном вычислительном тракте, но и в структуре всего непозиционного спецпроцессора.

ГЛАВА 5. ВЫЧИСЛИТЕЛЬНЫЕ ТРАКТЫ КОМБИНАЦИОННОГО

ТИПА

Базовыми аппаратными структурами специализированных процессоров в МСС являются вычислительные тракты. В общем случае они делятся на два типа: комбинационные схемы (дискретные автоматы без памяти) и последовательностные схемы (дискретные автоматы с памятью), основу которых составляют триггеры [129]. Выходные сигналы триггеров зависят от последовательности предыдущих событий смены состояний входных сигналов. Комбинационные узлы не содержат элементов памяти, и их состояние однозначно определяется комбинацией входных сигналов. Исходя из этого, к комбинационному типу следует отнести ВТ, в основе построения которых лежат прямой логический и табличный методы. Они позволяют строить модульные тракты с высоким быстродействием. Табличные варианты арифметических устройств используют комбинационные схемы, которые непосредственно реализуют таблицы Кэли операций базового набора в унитарном коде. При этом для уменьшения аппаратных затрат учитывается симметрия основной таблицы.

5.1 Использование свойств симметрии арифметической таблицы Кэли в схемотехнических решениях

Основное противоречие, влияющее на аппаратурные затраты при разработке табличных ВТ, выполняющих модульные операции сложения и вычитания, непосредственно связано с количеством осей симметрии соответствующей арифметической таблицы (см. табл. 3.1). В схемах модульного сложения (вычитания) используются свойства симметрии относительно правой (левой) диагонали, тогда как в схемах модульного умножения реализуются свойства симметрии таблицы Кэли не только по правой и левой диагоналям, а также относительно вертикалей и горизонталей, ш- 1 т+1 проходящих между числами —г— и ^ . Это обстоятельство и

2 ^ обусловливает существенное уменьшение (примерно в 4 раза) количества оборудования при реализации устройств модульного умножения в классе вычетов по сравнению с устройствами, выполняющими операцию сложения (вычитания) по модулю. Наиболее эффективным приемом, устраняющим это противоречие, является приведенный в параграфе 3.2 алгоритм, основанный на анализе четности операндов а, р и соотношении показателей четности между ними. Техническое решение этого алгоритма для модульного вычитания приведено на рис .5.1.

Работу устройства удобно рассматривать в трех режимах. Первый режим соответствует случаю, когда операнды ОС и р одновременно или четные, либо нечетны. При этом операнды аир поступают на входные дешифраторы Д в двоичном коде. Если числа четные, то на входах младших разрядов дешифраторов будут нули, в противном случае - единицы. Выходы дешифраторов Д попарно соединены (четные с нечетными) и являются входами элементов ИЛИ. Следовательно сигналы, соответствующие первому и второму операндам, поступают на один из входов коммутатора ПЗУ соответственно первой и второй группы входов. Так как операнды а и Р имеют одинаковый порядок четности, то с выхода элемента ИЛИ-НЕ поступит сигнал по шине Упр1 на входы элементов И.

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

Второй режим соответствует случаю, когда а нечетное, а Р четное. В этом случае на входе младшего разряда дешифратора Д будет единица. Сигнал

Рас. 3.1. Устроистбо для бычитания по модулю. поступит на вход элемента И, на другой вход которого поступит сигнал с выхода элемента НЕ. Сигнал с выхода элемента И поступит по шине Упр2 на входы элементов И. Операнды а и Р поступают до выхода коммутатора аналогично первому режиму, но в данном случае сигнал, соответствующий унитарному коду результата операции, поступает на открытый элемент И, а с его выхода - на вход соответствующего элемента ИЛИ. Соединение этих элементов ИЛИ с элементами И обеспечивает прибавление единицы к унитарному коду результата операции. Дальнейшее прохождение сигналов соответствует первому режиму.

Третий режим соответствует случаю, когда ОС четное, а (3 нечетное. В этом случае на входе младшего разряда дешифратора Д, соответствующего операнд}' Р, будет единица. Сигнал поступит на вход элемента И, на другой вход которого поступит сигнал с выхода элемента НЕ. С выхода элемента НЕ сигнал поступает по шине УпрЗ на входы элементов И. Прохождение операндов ОС и Р до выхода коммутатора аналогично первому режиму, но в данном случае сигнал, соответствующий унитарному коду результата операции, поступает на открытый элемент И, а с его выхода - на вход соответствующего элемента ИЛИ. Соединение элементов И с элементами ИЛИ в данном случае обеспечивает вычитание единицы из промежуточного результата операции.

Узел коррекции результата операции позволяет при необходимости произвести добавление или вычитание единицы из полученного результата. Ввиду того, что коррекция производится в однопозиционном коде, то эта операция сводится к соответствующей коммутации входов и выходов элементов И, общее число которых составляет ЗШ. Следующим шагом на пути уменьшения аппаратных затрат устройств сложения (вычитания) по модулю является использование табличного вычислителя, который реализует симметрию операций относительно одной из диагоналей [142]. Алгоритм, использованный в устройстве модульного вычитания, обеспечивает уменьшение величины входных операндов (реального модуля операции), то для

111=5 получаем реальный модуль ш'=3. В таблице 5.1 отражено соответствие индексов входов, обозначенных 1(П)0 -г 1(П)2 и выходов Шо Ш4 коммутатора (рис. 5.2), на которых появляется сигнал, в зависимости от входных сигналов. Коммутатор обладает симметрией относительно правой диагонали. Группа элементов ИЛИ объединяет попарно первую группу входов со второй группой входов, имеющих соответствующие индексы. Группа элементов И, выходы которых являются выходами коммутатора, реализует все сочетания пар при коммутации выходов элементов группы ИЛИ, а элементы группы И попарно объединяют первую и вторую группы входов коммутатора с соответствующими индексами.

Произведем расчет коэффициента аппаратурного выигрыша в оборудовании таблицы \¥? для устройства модульного вычитания, объединяющего при построении таблицы как алгоритм, основанный на анализе и соотношении показателей четности операндов, так и свойство симметрии полученной таблицы относительно правой диагонали. Ввиду того, что

Для 111=11 имеем \у'«5,76. Это обстоятельство свидетельствует о высокой эффективности подобного приема для снижения аппаратурных затрат устройств модульного сложения и вычитания, так как соотношение (5.1) без потери общности рассуждений можно распространить на случай модульного сложения. ш+1 где Ш — —-—, то получим т 2 у'= 8

5.1)

По

ЗАКЛЮЧЕНИЕ

1. В результате проведенных исследований заложены теоретические основы структурного синтеза непозиционных СП. Их применение позволило впервые получить структуры спецпроцессоров для существующих и перспективных диапазонов разрядных сеток, а также различных видов резервирования. Для повышения отказоустойчивости СП предложен новый путь, заключающийся в использовании кодов Фибоначчи при проектировании вычислительных трактов.

2. Сформулирован оригинальный алгоритм определения рациональной глубины резервирования СП в МСС при модернизации существующих вычислительных структур. Результаты расчета доведены до инженерной практики.

3. Описан новый подход к решению задачи минимизации аппаратурных затрат СП. С его использованием получены научные результаты по выбору системы оснований МСС для известных методов построения спецпроцессоров. Дальнейшее углубление этого подхода позволило впервые получить граничные параметры аппаратурных затрат при проектировании СП. Определены области целесообразного применения непозиционных и позиционных спецпроцессоров.

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

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

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

7. Проведен анализ и классификация арифметических устройств в МСС комбинационного и последовательностного типа. Ввиду того, что они выполнены на различной элементной базе, предложен оригинальный прием определения взаимосвязи аппаратурных затрат между логическими и триггерными элементами. Это позволило провести сравнительный анализ ВТ различного типа и определить оптимальные параметры узлов при комбинированном построении.

8. Рассмотрение структур многоуровневых ВТ позволяет сделать вывод о том, что они подобны многоярусным блокам реализации немодульных операций, характерной особенностью которых является отсутствие разветвлений выходов узла. Вследствие этого оба варианта структур могут иметь общие средства диагностики и сходные алгоритмические процедуры. Данное обстоятельство позволяет существенно повысить однородность и модульность непозиционных СП.

9. Сравнительный анализ аппаратурных и временных затрат при построении СП на базе позиционной и непозиционной систем счисления показал несомненный выигрыш при использовании последней, особенно для табличных спецпроцессоров в МСС. Предложен и обоснован критерий сравнительной оценки эффективности вычислительных трактов двух различных типов. Он но

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

За рамками проведенных исследований остались разработка алгоритмов и устройств для определения отказов в ВТ, использующих коды Фибоначчи и организации их маскирования. Представляется актуальной задачей, особенно для внедрения СП в АСУ технологическими процессами, создание датчиков и исполнительных механизмов, работающих непосредственно в МСС. Она тесно связана с разработкой алгоритмических процедур и технических решений для прямого и обратного преобразования кодов чисел между МСС и ПСС, сравнимых по быстродействию и аппаратными затратами с модульными вычислительными трактами. ш

1. Валях Е. Последовательно-параллельные вычисления: Пер. с англ.- М: Лир, 1985.-456 с.

2. Балашов Е.П. Эволюционный синтез систем. М: Радио и связь, 1985.28 с.

3. Вычислительные машины, системы и сети: Учебник / А.П.Пятибратов, ".Н.Беляев, Г.М.Козырева и др.; Под ред. Проф. А.П.Пятибратова. М: Финансы и татистика, 1984. -400 с.

4. Самодиагностика модульных вычислительных систем /Ю.К.Димитриев. -1овосибирск: ВО «Наука». Сибирская издательская фирма, 1993. 293 с.

5. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и ггказоустойчивые системы. М.: Радио и связь, 1989. - 208 с.

6. Каляев A.B. Многопроцессорные системы с программируемой рхитектурой. М.: Радио и связь, 1984. - 240 с.

7. Головкин Б.А. Вычислительные системы с большим числом процессоров. М.: Радио и связь, 1995. - 320 с.

8. Дорфман В.Ф., Иванов Л.В. Оптимизированное развитие аппаратных редств и элементной базы ЭВМ. М.: Знание, 1986. - 64 с.

9. Евреинов Э.В. Распределенная обработка информации и распределенные ¡ычислительные системы. М.: Знание, 1983. - 64 с.

10. Коуш П.М. Архитектура конвейерных ЭВМ: Пер. с англ. М: Радио и «язь, 1985.-360 с.

11. И. Водяхо А.И., Горнец H.H., Пузанков Д.В. Высокопроизводительные системы обработки данных: Учеб.пособие для вузов. -М.: Высш.шк., 1997. 304 с.

12. Макаревич О.Б., Спиридонов Б.Г. Проектирование микропроцессорных устройств. Таганрог: ТРТИ, 1985. - 52 с.

13. Введение в кибернетическую технику. Параллельные структуры и етоды / Малиновский Б.Н., Боюн В.П., Козлов Л.Г.; Отв.ред. А.В.йалагин; АН ^ССР. Институт кибернетики им. В.М.Глушкова. Киев: Наукова думка, 1989. - 248

14. Байков В.Д., Смолов В.Б. Специализированные процессоры: !терационные алгоритмы и структуры. М.: Радио и связь, 1985. - 288 с.

15. Торгашев В.А. Система остаточных классов и надежность ЦВМ, М.: 'ов.радио, 1973. - 120 с.

16. Смагин А.И. Организация сжатия информации в табличных структурах. -Маратов: Изд-во Сарат.ун-та, 1985. -124 с.

17. Балашов Е.П., Пузанков Д.В. проектирование информационно-правляющих систем. М.: Радио и связь, 1987. -256 с.

18. Специализированные ЦВМ: Учебник для вузов /Смолов В.Б., Барашенков Î.B., Байков В.Д. и др./ Под ред. В.Б.Смолова. М.: Высш.школа, 1981. - 279 с.

19. Горячев A.B., Шшнкевич A.A. Микропроцессоры. Информационно-правляющие вычислительные системы. -М.: Выеш.шк., 1984. -120 с.

20. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных лассах. М.: Сов.радио, 1968. - 440 с.

21. Долгов А.И. Диагностика устройств, функционирующих в системе »статочных классов. М.: Радио и связь, 1982. - 64 с.

22. Мультипроцессорные системы и параллельные вычисления: Пер.с англ./ 1од ред. ФГ.Энслоу. -М.: Мир, 1976. 384 с.

23. Карцев М.А. Арифметические устройства электронных цифровых машин. -М.: Физматиз., 1958. 158 с.

24. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных шгоритмов: пер. с англ. М.: Мир, 1979. - 536 с.

25. Карцев М.А. Арифметика цифровых машин. М. : Наука, 1964. - 576 с.

26. Морозов В.Н. Оптоэлектронные матричные процессоры. М.: Радио и вязь, 1986. - 112 с.

27. Орлов JI.A., Попов Ю.М. Оптоэлектронное арифметическое устройство в истеме остаточных классов// Автометрия. 1972. - №6. - с. 14-23.

28. Волоконная оптика в измерительной и вычислительной технике. Алмаза: Наука, 1989. -248 с.29. 29. Краснобаев В.А. Надежностная модель ЭВМ в системе остаточных лассов// Электронное моделирование. 1985. - т.7. - ;4. - с.44-46.

29. Краснобаев В.А. Вариант математической модели надежности ЭВМ в ГОК // Кибернетика. 1987. - №1. - с.25-26.

30. Пухов Г.Е., Евдокимов В.Ф., Синьков М.В. Разрядно-аналоговые ычислительные системы. -М.: Сов.радио, 1978.-256 с.

31. Ерофеев A.A., Ковалев B.C., Ульянов И.С. Сигнальные процессоры. М.: Знание, 1991. -64 с.

32. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с игл. М.: Мир, 1989. - 448 с.

33. Кравченко В.Ф., Крот A.M. Методы и микроэлектронные средства дафровой фильтрации сигналов и изображений на основе теоретико-числовых феобразований// Зарубежная радиоэлектроника. Успехи современной )адиоэлектроники. 1997. - №6. - с.3-31.

34. Червяков Н.И., Тынчеров К.Т., Велигоша A.B. Высокоскоростная щфровая обработка сигналов с использованием непозиционной арифметики// Радиотехника. 1997. - №10. -с.23-27.

35. Ловцов Д.А. Защита информации в информационно-вычислительной ;ети// Научно-техническая информация. 1997. №!. - с.7-12.

36. Граф Ш., Гессель М. Схемы поиска неисправностей: Пер. с нем. М.: Энергоатомиздат, 1989. - 144 с.гсч

37. Мс Clellan Н.Н., Rader С.М. Number Theory in Digital Signal Processing. Jew Jersey, Prentice Hall, 1979/

38. Trantwein M. Concurrent Error Detection/ Correction of Logical Operation, a: Fehlertoleriende Rechnersysteme, Ite GI/NTG. Fachtagung, Herausg. Grobpietsch K.E. nd M. Dal С in, Berlin, Springer Verlag 1984, S. 190-201.

39. Mandelbaum D. Error Correction in Residue Arithmetir. IEEE Trans. Сотр.21 (1972), 538-542.

40. Etzel M.h., JenKins W.K. Redundant Residue Number Systems for Error )etection and Correction in Digital Filters. IEEE Trans Acoust. Speech and Signal »rocessing ASSP 28 (1980), 538-544.

41. Смагин А.А. Организация сжатия информации в табличных структурахю Саратов: Изд-во Сарат.ун-та, 1985. 12 с.

42. Акаев А.А., Майоров С.А. Когерентные оптические вычислительные гашины. Л.: Машиностроение, 1977. - 400 с.

43. Saloum Salam N., Ibrahim Khalid M. Binary-to-residue and residue -to- binary onverters// Int.J.Electronic. 1986. Vol. 61, №1. P. 79 -84.

44. Alia G., Barsi F., Martinwlly E. A fast VL SI conversion betwin binary and esidue systems// Inf.Proces, Lett. 1984. Vol. 18. №3. P. 141-145.

45. Ирхин В.П., Навнычко A.B. Вариант обработки социометрической шформации при многокритериальном опросе// Научно-методический сборник МО >Ф (Управление военного образования). 1997. - №46. - с. 153-159.

46. Арутюнов П.А. Теория и применение алгоритмических измерений. М.: Энергоатомиздат, 1990.-256 с.

47. Путинцев Н.Д. Аппаратный контроль УЦВМ. М.: Сов.радио, 1969.48 с.

48. Дадаев Ю.Г. Арифметические коды, исправляющие ошибки. М.: Сов.радио, 1969. - 168 с.1. US

49. Ушакова Г.Н. Аппаратный контроль и надежность специализированных )ВМ. М.: Сов.радио, 1969. - 312 с.

50. Горбатов В.А. Основы дискретной математики: Учеб.пособие для вузов. -М.: Выс.шк., 1986.-311 с.

51. Стахов А.П. Введение в алгоритмическую теорию измерений. М.: Сов.радио, 1977.-288 с.

52. Стахов А.П. Алгоритмическая теория измерений. М.: Знание, 1979. - 64

53. Стахов А.П. Коды золотой пропорции. M.: Радио и связь, 1984. - 152 с.

54. Помехоустойчивые коды (Компьютер Фибоначчи). М.: Знание, 1989.4 с.

55. Савельев А.Я. Арифметические и логические основы цифровых ивтоматов: Учебник. -М.: Высш.шк., 1980. -255 с.

56. Стахов А.П. Использование естественной избыточности фибоначчиевых :истем счисления для контроля вычислительных систем// Автоматика и (ычислительная техника. 1975. - №6. - с. 12-18.

57. Шишков Г.Б. Числа Фибоначчи-Шишкова: Математические новации: Научное издание. -М.: Изд-во Рос.экон.акад., 1994. 28 с.

58. Шишков Г.Б. Развитие идеи ряда Фибоначчи (новый числовой ряд). М.: VMHX им. Г.В.Плеханова, 1991. -11с.

59. Юпочко В.И., Ткаченко A.B. Синтез устройств АСУ в Т-системах счисления. М.: Министерство обороны СССР, 1986. - 330 с.

60. Анисимов A.B. Линейные формы Фибоначчи и параллельные алгоритмы фифметики большой размерности// Кибернетика и системный анализ. №3. - 1995. -х 17-25.

61. Цымбал В.П. Теория информации и кодирования. Киев: Вшца школа, 1977.-288 с.

62. Коляда A.A., Пак И.Т. Модулярные структуры конвейерной обработки ифровой информации. Минск: Университетское, 1992. - 256 с.

63. Зайченко Ю.П. Исследование операций. К.: Высшая школа. Головное изд-о, 1988.-552С.

64. Ушаков И. А. Методы решения простейших задач оптимального езервирования при наличии ограничений,- М.: Сов.радио, 1969.-176с.

65. Краснобаев В.А., Ирхин В.П, Пример решения боратной задачи птимального резервирования в системе остаточных классов // Кибернетика.-1990.-с. 123-125.

66. Микропроцессоры.- М: Знание, 1989.-48с.

67. Коваленко А.Е., Гула В.В. Отказоустойчивые микропроцессорные системы.-:.:Технка, 1986.-150 с.

68. Арис Р. Дискретное динамическое программирование: Пер. с англ. М.: Лир, 1969.-171 с.

69. Барлоу Р., Прошан Ф. Математическая теория надежности.: Пер. с англ. -Л.: Сов.радио, 1969.-488 с.

70. Электронные промышленные устройства / Васильев В.И., Гусев Ю.М., Лиронов В.Н. и др.- М.: Высшая школа, 1988. -303 с.

71. Гнеденко Б.В., Беляев Ю.К., Соловьев А.Д. Математические методы в еории надежности. М.: Наука, 1965. -523 с.

72. A.c. 1168947 СССР. Устройство для резервирования / В.А. Краснобаев. -)публ. в Б.И., 1982, №30.

73. Колесников Н.К. Оптимальный избыточный синтез многоканальных структур ЦВМ. -М.: Сов.радио, 1975.-176 с.

74. Половко A.M. Основы теории надежности,- М.: Наука, 1964. 448 с.

75. Березюк Н.Т., Гапунин А.Я., Подлесный Н.И. Живучесть микропроцессорных систем управления. К.: Техшка, 1989.-143 с.

76. ГОСТ 27.503-81. Методы оценки показателей надежности. М.: здательство стандартов, 1982.-55 с.

77. Патент 2123202 РФ. Устройство дм резервирования / В.П. Ирхин-Опубл. в .И., 1998, №34.

78. Краснобаев В.А., Ирхин В.П. Вариант оптимизации структуры ЭВМ, »ункционирующей в позиционно-остаточной системе счисления. )Материалы еждународной НТК // Представление, обработка и передача информации. Сочи-[арьков: АНУ, ПАНИ, 1992.- с.65-69.

79. Виноградов И.М. Основы теории чисел. М,: Наука, 1981. - 256 с.

80. Артамонов Г.Т. Топология регулярных вычислительных структур и сред. -4.: Радио и связь, 1985. 192 с.

81. Ирхин В.П. Алгоритм реализации операций модулярной арифметики// 1рикладные вопросы защиты информации: Сборник статей. Воронеж: Воронежская ысшая школа МВД России, 1996. - с. 12-16.

82. Ирхин В.П. Граничные параметры вычислительных структур модулярной рифметики// «Понгрягинские чтения -VII»: Тезисы докладов школы. Воронеж, $ГУ, 1996.

83. Акаев A.A., Майоров С.А. Оптические методы обработки информации. -А.: Высш.шк.5 1988.-237 с.

84. A.c. 1571589 СССР. Арифметическое устройство по модулю/ О.Н.Фоменко, I.A. Краснобаев, В.П. Ирхин и др. Опубл. В Б.И., 1990, №22.

85. Перспективы развития вычислительной техники: В 11 кн. Справ.пособие/ 1од ред. Ю.М.Смирнова. Кн.7: Полупроводниковые запоминающие устройства/ ^.Б.Акинфиев, В.И.Миронцев, Г.Д.Софийский, В.В. Цыркин. М.: Высш.школа, 989. -160 с.

86. Бортовые цифровые вычислительные машины и системы: Учебное пособие щя ВУЗов по спец. «Вычислительные машины комплексы, системы и сети»/ia

87. Ш.Матов, Ю.А.Белоусов, Е.П.Федосеев: Под ред. В.И. Матова.- М.: Высшая школа, 988.-2116 с.

88. A.c. 1689949 СССР. Устройство для вычитания по модулю / О.Н. Фоменко, S.A. Краснобаев, В.П. Ирхин и др.- Опубл. в Б.И., 1991, №41

89. A.c. 1615714 СССР. Устройство для умножения чисел по модулю / Г.М. 1игасов, С.А. Чарковский, В.А. Краснобаев, В.П. Ирхин Опубл. в Б. И., 1990, №47.

90. A.c. 1126950 СССР. Устройство для умножения чисел по модулю / В.А Сраснобаев и др. Опубл. в Б. И., 1984, №44.

91. A.c. 1775721 СССР. Арифметическое устройство по модулю / В.А. Сраснобаев, В.П. Ирхин, Н.И. Можаев и др. Опубл. в Б. И., 1992, №42.

92. Патент 2109326 РФ. Устройство для сложения и вычитания чисел по юдулю / В.П. Ирхин Опубл. в Б.И., 1998, №11.

93. Патент 2018936 РФ. Устройство для умножения чисел по модулю / А.Краснобаев, В.П,Ирхин, М.В.Квасов, И.В.Приходько Опубл. в Б.И., 1994, №16.

94. A.c. 1697079 СССР. Устройство для умножения чисел по модулю / З.И.Глушков, В.П.Ирхин, В.А.Краснобаев и др. Опубл. в Б.И., 1991, № 45.

95. Э. Трост. Простые числа. Пер. с нем. М.: Государственное издательство шзмат. литературы, 1959. - 136 с.

96. A.c. 1807484 СССР. Устройство для умножения чисел по модулю / Э.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1993, №13.

97. A.c. 1617439 СССР. Устройство для умножения чисел по модулю / З.И.Глушков, В.П.Ирхин, В.А.Краснобаев и др. Опубл. в Б.И., 1990, № 48.

98. A.c. 1716511 СССР. Устройство для умножения чисел по модулю / З.А.Краснобаев, В.П.Ирхин, В.Д.Экста, А.А.Сахаров, М.В.Юмашев Опубл. в Б. И., 1992, № 8.

99. Ирхин В.П. Иванцов В.В. Устройство для умножения чисел по модулю. Эпубл. в Б.И., 1998. №8. - с.123.

100. Ирхин В.П. Иванцов В.В. Устройство для умножения чисел по шдулю.Опубл. в Б.И., 1998. №8. - с.124.

101. Амелькин В.А. Методы нумерационного кодирования. Новосибирск: 1аука, 1986. - 160 с.

102. Патент 2110087 РФ. Устройство для сложения чисел по модулю / Ш.Ирхин Опубл. в Б.И., 1998, № 12.

103. Ирхин В.П, Табуненко В.А. Использование остаточной арифметики при абличных методах обработки. Харьков, НАНУ, ПАНИ, ХВУ. Обработка информации. Сборник научных трудов, 1996. -с.29-35.

104. А.с. 1619403 СССР. Устройство для перевода числа, представленного в ;истеме остаточных классов, в полиадическую систему счисления / О.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1991, № 1.

105. Ирхин В.П. Алгоритмы определения позиционных характеристик кодов в системе остаточных классов. Харьков: ХВКИУРВ. Тематический научно-ехнический сборник № 337, 1992 - с. 33-36.

106. Краснобаев В.А., Ирхин В.П. Варианты определения обратной лультипликативной величины числа в системе остаточных классов. Харьков: <ВКИУРВ. Тематический научно-технический сборник № 337,1992. - с. 132-140.

107. Патент 2029434 РФ. Устройство для формирования остатка по1роизвольному модулю от числа / В.И.Петренко, А.Ф.Чепига Опубл. в Б.И., 1995, № >.

108. Патент 2110147 РФ. Устройство для формирования остатка по модулю от шсла / В.П.Ирхин Опубл. в Б.И., 1998, № 12.

109. Ирхин В.П, Табуненко В.А. Алгоритм приведения двоичного числа по 1ростому модулю. Харьков, НАНУ, ПАНИ, ХВУ. Системы информационного взаимодействия. Сборник научных трудов., 1996. с. 43-46.

110. Амербаев В.М. Теоретические основы машинной арифметики. Алма-Ата: Таука, 1976.-324 с.27 О

111. A.c. 1552171 СССР. Устройство для сравнения чисел в системе остаточных лассов / О.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1990, №11.

112. Абрамсон И.Т., Авров О.М., Лапкин Л.Я. Кодирование электрических ¡еличин в системе остаточных классов // Автометрия. 1975. - №2.- с.23-29.

113. Краснобаев В.А., Ирхин В.П., Кононова И.В. Методы и алгоритмы »еализации арифметических операций в системе остаточных классов// АСУ и фиборы автоматики. 1990. - №93. - с. 46-53.

114. A.c. 1532923 СССР. Устройство для сложения и вычитания чисел по модулю / О.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1989, № 48.

115. Ирхин В.П, Табуненко В.А. Алгоритм формирования исходного состояния ;одержимого кольцевых регистров сдвига. Харьков, НАНУ, ПАНИ, ХВУ. Системы шформационного взаимодействия. Сборник научных трудов., 1995. с. 23-26.

116. Тараканов В.Е. Комбинаторные задачи и (0,1) матрицы. М.: Наука, "л.ред. физ.-мат. лит., 1985. - 192 с.

117. Коробов Н.М. О функциях с равномерным распределением дробных *олей// ДАН СССР. Новая серия. 1948. - t.LXII. -№1. - с. 21-22.

118. Долгов В.И., Краснобаев В.А., Кононова И.В. Метод и алгоритмы >еализации арифметических операций в системе остаточных классов // Электронное лоделирование. 1989. - №5. - с. 15-18.

119. Краснобаев В.А., Ирхин В.П. Алгоритм реализации операции модульного умножения в системе остаточных классов // Электронное моделирование. 1993.1. ЧЬ5.-с.20-26.

120. A.c. 1810889 СССР. Устройство для сложения и вычитания чисел по модулю / О.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1993, № 15.

121. A.c. 1546976 СССР. Устройство для сложения и вьгчгитания чисел по модулю / О.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1990, № 8.

122. A.c. 1546977 СССР. Устройство для сложения и вычитания чисел по модулю / О.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1990, № 8.

123. Воробьев H.H. Теория рядов. М.: Наука. Гл. ред. физ.-мат. лит., 1979.08 с.

124. Гельфоид А. О. Исчисление конечных разностей. М.: Наука, 1967.-376 с.

125. Маркушевич А.И. Возвратные последовательности. -М.: Наука, 1983.- 48

126. A.c. 1633399 СССР. Устройство для сложения и вычитания чисел по юдулю / О.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1991, № 9.

127. A.c. 1683011 СССР. Устройство для сложения и вычитания чисел по юдулю / В.И.Долгов., В.А.Краснобаев., В.П.Ирхин., А.П.Крышев Опубл. в Б.И., 991, №37.

128. Зельдин Е.А. Цифровые интегральные микросхемы в информационно-вмерительной аппаратуре. Л.: Энергоатомиздат. Ленингр. отд-ние, 1986.-280 с.

129. Альтшуллер Г.С. Творчество как точная наука. М.: Сов.радио, 1979.-184

130. A.c. 1755275 СССР. Устройство для сложения и вычитания чисел по юдулю / В.А.Краснобаев, В.П.Ирхин, И.В.Милехин и др. Опубл. в Б.И., 1992, № ¡0.

131. A.c. 1820379 СССР. Устройство для сложения и вычитания чисел по юдулю / В.А.Краснобаев, В.П.Ирхин, Н.И.Можаев., М.Н.Кукушкин Опубл. в Б.И., 993, №21.

132. A.c. 1820380 СССР. Устройство для сложения и вычитания чисел по юдулю / О.Н.Фоменко, В.А.Краснобаев, В.ПИрхин и др. Опубл. в Б.И., 1993, № 21.

133. A.c. 1636844 СССР. Устройство для сложения и вычитания чисел по юдулю / О.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1991, № 11.

134. A.c. 1756881 СССР. Арифметическое устройство по модулю / В.А.Краснобаев, В.П.Ирхин, И.В.Милехин, М.В.Юмашев Опубл. в Б.И., 1992, № 31.

135. A.c. 1667055 СССР. Устройство для умножения чисел по модулю / Э.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1991, № 28.

136. Патент 2018935 РФ. Устройство для сложения и вычитания чисел по юдулю / В.А.Краснобаев, В.П.Ирхин, М.В.Квасов, И.В.Приходько Опубл. в Б.И., 994, № 16.

137. Патент 2023289 РФ. Устройство для сложения и вычитания чисел по юдулю / В.А.Краснобаев, В.П.Ирхин, М.В.Квасов, А.И.Возный, И.В.Приходько -)публ. в Б.И., 1994, № 21.

138. Виленкин Н.Я. Комбинаторика. М: Наука. Гл. ред. физ.-мат. лит., 1969128 с.

139. Ирхин В.П. Улучшение основных характеристик операционных устройств пецпроцессоров.- Харьков: ХВКИУРВ. Тематический научно-технический сборник 6337,1992.-с. 33-36.

140. Ляпин Е.С., Айзенштат А.Я., Лесохин М.М. Упражнения по теории групп.-Л.: Наука. Гл. ред. физ.-мат. лит., 1967,- 264 с.

141. A.c. 1571583 СССР. Арифметическое устройство по модулю / ).Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1990, № 22.

142. Чернявский А.Ф., Данилевич В.В., Коляда A.A., Селянинов М.Ю. высокоскоростные методы и системы цифровой обработки информации. Минск: >елгосуниверситет, 1996.-376 с.

143. A.c. 1647563 СССР. Устройство для умножения чисел по модулю/ А.Краснобаев, В.П.Ирхин, И.К.Костенко и др. Опубл. в Б.И., 1991, № 17.

144. A.c. 1683012 СССР. Устройство для сложения и вычитания чисел по юдулю / О.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл. в Б.И., 1991, № 37.

145. A.c. 1633400 СССР. Арифметическое устройство по модулю/ З.Н.Фоменко, В.А.Краснобаев, В.П.Ирхин и др. Опубл.в Б.И., 1991, №9.

146. A.c. 1809437 СССР. Арифметическое устройство по модулю/ З.А.Краснобаев, В.П.Ирхин, М.В.квасов и др. ~ Опубл.в Б.И., 1993, №14.

147. Гутников B.C. Интегральная электроника в измерительных устройствах. -I.: Энергия. Ленингр. Отд-ние, 1980.-248 с.2 73

148. Шило В.JI. Популярные цифровые микросхемы: Справочник. М.: Радио и вязь. - 352 с.

149. Карцев М.А., Брик В.А. Вычислительные системы и синхронная рифметика. М.: Радио и связь, 1981. - 360 с.

150. Самофалов К.Г., Корнейчук В.И., Тарасенко В.П. Электронные цифровые ычислительные машины. Киев: Вшца школа, 1976. - 480 с.

151. Микроэлектроника. Учеб.пособие для ВТУЗов в 9 кн./ Под ед.Л. А. Коледова. Кн.З. Базовые матричные кристаллы и программируемые огические матрицы/ М.Ф.Пономарев, Б.Г.Коноплев. М.: Высшая школа, 1987. -94