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

« Г б Ой На правах рукописи

; ? ФЕВ 1936

ИСМАИЛОВ Шейх-Магомед Абдуллаевич

ТЕОРИЯ И ПРИМЕНЕНИЕ РАЗРЯДНО-ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОРНЫХ ЭЛЕМЕНТОВ ОБРАБОТКИ ЧИСЛОВЫХ ДАННЫХ В КОМПЛЕКСЕ СИСТЕМ СЧИСЛЕНИЯ

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

Автореферат

диссертации на соискание ученой степени доктора технических наук

С.-Петербург-! 996

Работа выполнена в Дагестанском государственном техническом университете

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

доктор технических наук, доктор технических наук, доктор технических наук,

профессор Смирнов Ю.М. профессор Байков В.Д. профессор Очин Е.Ф.

Ведущее предприятие - Научно-исследовательский институт многопроцессорных вычислительных систем при Таганрогском государственном радиотехническом университете им. В.Д. Калмыкова.

Защита состоится " / " л?а/? '/'С/" 1996 г. в // час. на заседани диссертационного совета Д 063.36.02 Санкт-Петербургского государственног электротехнического университета им. В.И. Ульянова (Ленина) по адресу: 19737< Санкт-Петербург, ул. Проф. Попова, 5.

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

Автореферат разослан января 1996 г.

Ученый секретарь диссертационного совета

Исаков А.Б.

общая' характеристика работы

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

Несмотря на значительнее успехи, достигнутые в теории архитектуры вычислительных устройств (БУ), традиционно функционирующих в двоичной системе.счисления ССС), еще недостаточно исследованы' возможности, связанные с оптимизацией способов кодирования потоков числовых данных (ПЧД). Это служит дополнительным резервом роста производительности ЭВМ. Так. представляется целесообразным использование в.ВУ не только двоичной сс; главный недостаток которой наличие "длинных" межразрядных переносоз, влияющих на быстродействие выполнения арифметических операций. ,а некоторого комплекса, систем счисления (КСС), вклйчающего как позиционные,, так и непозк- ' ционные системы счисления. Это способствует значительному сокращению времени реализации .арифметических операций над ПЧД за счет их выполнения в наиболее рациональной СС.

С другой стороны, представляется целесообразной разработка арифметических узлов ЭВМ, ориентированных на.реализацию n-арной операции 'суммирования, часто встречающейся при выполнении широкого спектра арифметических выражений. Степень значимости указанной операции отмечена в. работах Й.В.Прангишвили, Я.И.Фета, Б.Н.Малиновского, В.'Муртафа. Отсутствие в настоящее время таких узлов приводит к необходимости организации попарной обработки ПЧД. что существенно снижает производительность параллельных ЭВМ.

Рассмотренные подхода могут быть использованы совместна для построения высокопроизводительных ЭВМ.' функционирующих б КСС и содержащих арифметические узлн, выполнявшие операцию параллельного суммирования чисел, с использованием разряд-но-параллельных способов обработки ПЧД. Очевидно, что такая

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

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

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

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

срезы, состоящие из одноименных разрядов.

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

До сих пор разрядно-параллельные вычисления и вычисления в ССОК развивались независимо друг'от друга. Представляет практический и научный интерес проблема объединения достоинств обоих направлений развития структур ЭВМ. Все вышеперечисленное определяет необходимость исследования принципов построения разрядйо-параллельных . процессоров безошибочной обработки вещественных .чисёл в недвоичных СС,'.обладающих вы-' сокой производительностью прежде всего за.счет ' автоматической коррекции результатов вычидлений. •

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

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

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

Указанная проблема решалась в соответствии с Постановлением "MB И ССО СССР И АБ СССР N 1473/146 от 29.12.80/31.12.80 "О совместных научно-исследовательских работах ' в области ВТ" 'я приказом■ N 535 Минвуза СССР от 20.05.81 (тема N 2.12 "Разработка теории и реализация эффективно-диагностируемых ассоциативных вычислительных устройств и систем с аппаратной поддержкой математического обеспечения"), ' по госбюджетной тематике в соответствии с приказом N 520 от 10,08.92 года Госкомитета по высшей школе, регистра-■ционный номер 1.7.92 "Математические и технические аспекты организации массовой обработки числовой информации в процессорных элементах с изменяемой системой счисления" -1992-1995 гг., а также в рамках Государственной научно-технической программы РФ- "Радиоэлектронные системы и приборы прогнозирования и контроля чрезвычайных ситуаций" - проект 4С.104 "Применение аппарата нечетких множеств для представления и обработки геофизической информации" 1993-1995 гг.

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

В соответствии с поставленной целью о'сновные задачи работы формулируются следующим образом: .

- анализ способов параллельной обработки информации с точки зрения ее кодирования в ВУ;

, - повыше ж производительности ВУ параллельной обработки числовых данных.

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

- исследование структурной организации разрядно-параллельных арифметических устройств в КСС;

- получение оценок эффективности организации вычисли-

тельных процессов в КСС;

- разработка способов ■ комплексирования арифметических устройств, использующих КСС;

- разработка методики автоматизированного проектирования разрядно-параллельных АУ;

- разработка разрядно-параллельного процессорного элемента. функционирующего в КСС; .

- исследование возможности практической реализации раз-. рядно-параллельных АУ на современной элементной базе.

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

Научная новизна выполненных исследований определяется развитием теории разрядно-параллельных вычислений и структур в направлении разработки: • • .

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

- алгоритмов и структур разрядно- параллельной обработки комплексных чисел, представленных двоичным кодом с основанием (-1+1). а также операций, с дробями Фарея;

- алгоритмов и структур устройств прямы^ и обратных, преобразований числовых данных в КСС;

- способа органйзации вычислительных процессов решения задач в КСС (доказательство целесообразности их организации);

- структуры ПЭ, функционирующего в КСС;

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

Апробация работы. Основные результаты работы докладывались и обсуждались на:'

- Всесоюзной научно-технической конференции "Теория и практика конструирования и обеспечения надежности и качества РЭА", Махачкала-Москва. 1980 г.; .

- Всесоюзном совещаний "Высокопроизводительные системы", Москва. 1981 г.;

- Всесоюзной конференции "Специализированные микропроцессорные системы". Челябинск, 1981 г.;

- Второй Всесоюзной конференции молодых приборостроителей, Москва, 1983 г.:

- Научно-практической конференции "Радиоэлектроника народному хозяйству", Махачкала, 1983 г.;

- Научной сессии Дагестанского филиалу АН СССР, посвященной итогам.фундаментальных и.прикладных исследований. Махачкала, 1985-1994 ГГ.:

- Всесоюзной научно-технической конференции "Образное представление данных в управлении и научных исследованиях". Грозный, 1987 г.;

- Всесоюзной научно-технической конференции "Проблемы развития аппаратных и- программных средств вычислительной техники для машинного моделирования", Москва. 1987 г.;/

- Всесоюзном научно-техническом семинаре "Математическое обеспечение систем с машинной графикой", Ижевск-Махачкала. 1989г.. Ижевск. 1992 г.;

- Межреспубликанской конференции "Методы и средства управления технологичёскими процессами.", 'Саранск. 1989 г.:

- Всесоюзном научно-техническом семинаре "Мвдгопро.цес-сорные вычислительные системы". Таганрог. ¿991 г.;

- Международной научно-технической конференции "Актуальные проблемы фундаментальных наук". Москва, 1991,1994 гг.;

- Российской научно-технической конференции "системный анализ и принятие решений в . задачах автоматизированного обеспечения качества и надежности изделий приборостроения, и радиотехники", Москва- Махачкала, .1991 г,;

: - Международной конференции и школы молодых учёных и специалистов "САПР-ЭЗ". "САПР-94".' Гурзуф-Ялта, 1993-1994 гг.:

- Международной конференции.по компьютерной графике и визуализации иГрафиков", Санкт-Петербург. 1993-1994 гг.:

- Российской научно - технической конференции,. Ульяновск, 1993 г.;

- Всероссийской научно-технической конференции с участием зарубежных представителей "Интеллектуальные САПР-94",

Россия. Геленджик. 1994 г.;

- Первом международном симпозиуме "Интеллектуальные системы - 94". Махачкала, 1994 г.;

- Республиканской научно-технической конференции "Актуальные проблемы информатики, управления и радиоэлектроники". Махачкала, 1994 г.;

- На выездной сессии Академии естественных наук. Махачкала, 1994 г.:

- Всероссийской научно-технической конференции "Состояние и перспективы развития термоэлектрического приборостроения", Махачкала 1995 г. '

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

Структура и обьем раРота. Диссертация состоит из введения, 6-ти разделов, заключения, списка литературы, включающего 255 наименований и двух приложений. Основная часть диссертации изложена на 295 страницах машинописного текста. Работа содержит 138 рисунков. 36 таблиц.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ ' •

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

В' первой глав? рассматриваются особенности'вычислительных задач большого объема, характеристики существующих и предлагаемых в' перспективе высокопроизводительных вычислительных средств (ВС), ориентированных на их решение.

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

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

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

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

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

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

Формулируется задача минимизации времени, выполнения операции параллельного суммирования с учетом способов кодирования входных и выходных ПЧД (элементный уровень) и вычисления арифметических выражений (АВ) на ее основе {системный ■уровень), заключающая в следующем.. ' ■ • .

. Время выполнения операции параллельного 'суммирования I зависит в общем случае от выбранного способа кодирования 5 входного . ПЧД.. . числа операндов в'потоке N. разрядности чисел п и алгоритма выполнения .операции. Будем'предполагать, что . наиболее быстродействующие алгоритмы параллельного ' суммирования и состветствуюазю им структуры АУ известны для каждого способа кодирования данных из, набора: 9 -{бг.... , бп ). Кроме того, известны формульные зависимости времени реализации операции от параметров входного потока:^ = Г (б.N,11).

Пусть в состав АУ входит универсальный преобразователь системы счисления, выполняющий преобразования типа

5ц.12(Н.пи-, п1г) » С5и( Л.Пц) ==-> б1г(«.п12)}, для У (би,б1г) Е 8. .Указанная запись означает преобразование потока из N операндов разрядности пи . представленных" в системе счисления 5(1 в поток из N операндов разрядности п1г в систему счисления б1гс сохранением заданной точности

представления данных (в пределах имеющейся разрядной сетки)

Тогда задача минимизации формулируется как задача нахождения кратчайшего пути на ориентированном графе в (V, II), вершинам V которого поставлены в соответствие состояния потоков данных, а дугам и - времена выполнения операций преобразования и параллельного суммирования. Каждому пути на графе б (V, и) соответствует одна из возможных реализаций операции параллельного суммирования. Решение задачи • минимизации времени выполнения операции параллельного,суммирования фактически сводится' к перебору всех возмокных путей на графе, количество которых не превышает числа СС. входящих в КСС.

Производится анализ ПЧД и потока операций (ПО) по степени их однородности, на основе которого показывается возможность разработки различных ' классов ' вычислительных уст-, ройств. предназначенных для обработки неоднородных ПЧД. и указывается их место в общей классификации. ■ Обосновывается выбор КСС, включающего.двоичную, двоично-десятичную и систе- ' му счисления в остаточных классах. (ССОК). а 'также дроби Фа- ' рея. Предложена структура процессорного "элемента, представляющего собой ЭУО числовых данных в КСС,. и сформулированы общая цель и задачи диссертационной работы. ■'■:'■

Исходя из проведенного в: работе анализа - параллельных вычислений • и структур, определены следующие требования к -структуре.разрядно-параллельного АУ: Г : - .

-экономическая 'целесообразность .1фименейия таблично-алгоритмических методов для организации .разрядао-парал-лельных вычислений; ♦ .

- раздельное выполнение функций хранения и обработки РС потока числовых данных, опирающиеся на'ддев¡"трубопровода данных"; ;;

- получение линейной зависимости аппаратурных и временных затрат на обработку аргументов от арности их функции;.

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

- сохранение- прбстоты и эффективности табличной обработки РС ПЧД. с реализацией ее на аппаратурном уровне.

- возможность' организации вычислений в КСС.

• С учетом этих требований на рис.1, приведена обобщенная .

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

кед операции

код настройки

| в={51(...,6п}

Местное устройство управления • *

адресная часть 1-ый разрядный, срез

НЕ

X

динамическая память

ХИ

универсальный преобразователь

рг. переносов

РГ. результ.

-Г~~"

поток данных ; ;. ' ; ' '

Рис.1. Обобщенная структура разрядно-параллельного процессорного элемента. .

Адресную часть АУ образуют цифры РС массива данных'и значение переносов из младшего РС, а информационную часть - перенос в старший РС и'цифра результата. В структуре устройства имеется также динамиче$кая память с очередным доступом. . , Рторой раздел посвящен разработке райрядно-параллельных алгоритмов и ■ устройств выполнения арифметических операций параллельного суммирования (ПС).в двоичной, двоично-десятичной, системе счисления в остаточных' классах. Предлагается разрядао-пардллельный способ суммирования ПЧД в двоичной системе кодирования с различной организацией Фиксации и обработки 'межразрядных переносов и показана возможность реали-. заданна ее основе других операций. Разработанные алгоритмы и структуры" базируются на таблично-алгоритмических методах обработки информации по правилу: параллельно по / словам и последовательно", до разрядам (разрядно-пзраллельные алгорит-

мы). Разработанные способы, алгоритмы и структуры используются также и при разработке алгоритмов и структур , ориентированных На разрядно-параллельнне вычисления над комплексными числами, представленными по основанию (-1+1).

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

Пусть Р - ... . Гц) - множество слагае-

мых. представленных в двоичной СС по способу с Фиксированной

' ' з з з з

запятой, где V-Г,:Г € Г, 13> О. 1у = (г,. ггг....г3. г„).

з

Г1 е {0.1}- 1-ый двоичный разряд ¿1-го слагаемого, 1=1.____п.

где п - разрядность исходных суммируемых чисел.. Обозначим г={31( 5г,....За.....2п+иб8 множество час-

г

тичных сумм по модулю два по разрядным ' срезам (РС) с учетом переносов из предыдущих РС, [X] целая часть выражения X. Очевидно, что результат Б операции, параллельного суммирования равен ■ . и • . ' ■

г »• I Г]. (1)

Рассмотрим сумму С1 элементов одного'РС без учета переносов из предыдущих РС • . ■ '

: С14«-Г 'Г|1-ТГп, Л-ТГы. (2)

м

Формула (2) определяет количество единиц, содержишься в 1-ом РС. Тогда (1) с учетом (2) можно, представить как .

» 1-1 '■'■ '■■ '.'.

Б « I С, • 2 . . (3)

1-1-'

сумму элементов одного РС без учета переносов из предыдущих РС можно записать в виде

К 3 (108 N1 Пог.И!-« . л о

2 г, = ч, 2 • 2 * <• .., + а, • 2 . • (Л)

3-1

Обозначим: '.

- лг -

1 о и з ■ н 3 «

S,», q. • 2 "( Z rt) mod 2: Pj= I rt - St.

' . ' 3*1 ' .. 1"» .

Значение S^ является суммой по модулю два, a. Pj -многоразрядным двоичным переносом, формируемым в 1-ом PC.

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

Для определения разрядности результата S и многоразрядного' переноса Р запишем*-выражение для суммы и Pt с учетом распространения келсразрядных переносов .

i Л 2 Sj - S, - Ti © Tj

■ ■ Г z i(ri + г, +

.. + Ti + Р0)/2].

4 & ©

© и .©.... © r2 © mod2 Рх,

С(г

+ г.

+ Г2 +• . .. + Г2 + Р,)/21.

(5)

S„ ri © Г* ©...

© гв © :.© rn © raod2 Рв.,,

Рп= Кгв + Г„ +... _+ Г, + ... + Гв + Рп.! )/2],

Бп^! -то<32 Рв.

Рпм"1Р»/2], :

¿в^-шоа^ РП+К.,. » .

Здесь К-число разрядов, необходимых для представления максимального значения переноса. Величина Р^ изменяется от О до некоторого максимального, значения, которое определяет требуемое число двоичных разрядов, и находится на основании следующего правила.

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

* rt +

s

2

1 г з N

ББ! = Г, + Г! + . . . + Г! + . . . + Г, = к

Р, - [( БЭ, + Р1м )/2].

Утверждение 1. Максимальное арифметическое значение переноса равно N-1, где N - число операндов одновременно участвую!дих в. "операции суммирования.

Доказательство. Предположим, что значение переноса достигло величины N-2, т.е. Р1м ».N-2. Утверждение будет верным. если в ходе вычислений получается еще большее значение переноса. В соответствии с (6) « [(Н + N - 2)/2]=М-1.'

Введенное предположение будет верным, поскольку Р, > Р^,.

Затем • ■ . .

Р1М - [Ш+Р^/Й] » С(И+Н-1)/2] - N-1+11/2] = К-1 и дальнейшее' увеличение переноса невозможно.

Следствие 1. Для представления.многоразрядного Р, переноса требуется К битов.

• . К- = [1оБг •(N-1)3+1.. ' .(7)

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

К' = а +"(1ое2 (N-1)3+1. ■•'.-■. (8) '

■ Недостатком предлагаемого способа суммирования чисел с общей организацией переноса является, время формирования и обработки: многоразрядного переноса в'форме-(5), устранить который предлагается посредством разбиения ?1 на:;две составу ляющие П^ и С^.- соответственно на основной-и-дополнительный переносы, что приводи? к значительному сокращению аппаратурных затрат на реализации структуры разрядно-параллельного сумматора. В выводе необходимых для этого формул используются следующие,, известные из теории чисел, соотношения, Если А, В, с - целые числа и А-В+С. то

то(Зг А - шос1г В + шоб2 С (9)

[ (В+С) /23 - [В/2] + [(вой2 В+С) /2] .' (10)

1 • г • « 1 г ы

ПЩ$>. (^ * Г1 + .. . + Г4 ) е Г1 © Г1 © . .. © Г} . .. (И)

Последнюю сумму по модулю ■ два в (11) обозначим через Н8гаг .

Как показьшается в работе, используя соотношения (5), (9)-(И), можно получить выражения для определения Пц. Qt, S1+1.

п, = 1(1 r?)/2], qi-((rad2 + ht.j + qi-i >/23=0.

3-1 ;

1*1

S^! > R3m2 +■ modg Щ + mod2 Qj.

Приведем оценки временных и аппаратурных затрат предлагаемых суммирующих устройств, для чего введем понятие условного бита Vye и условного такта Ту1. под которыми будем по. нимать' соответственно двухвходовой логический элемент И-НЕ и время считывания информации из постоянной памяти.

М-1 2 .

• ^в словах "2-[2 .,.,+ ЦЫ/21+1> I,- T,.t.= n+[l0g2Nl.

л'у.б.-2 {Wz)+\)-[z~\+ + гн,

Реализация n-арной операции суммирования чисел в двоично-десятичной сс. представленных в коде 8.4.2,1 заключается ■в суммировании i-ых тетрад по PC по вьшерассмогренным правилам с последующие выделением очередной цифры результата StT .'суммы 1-ых тетрад.и многоразрядного' маэтетрадного двоичного переноса PtT. : который необходимо учитывать при суммировании l+1-щ тетрад. В этом случае структура процессорного элемента содержит межтетрадный блок коррекции (постоянная память), аппаратурные затраты ; которого . в словах Vc и условных битах Vyi оцениваются выражениями: ' '

10B„J ЭКС. 1 .log 19Н1

Vc - 2 2 ','•• V»6 - 2 _ 2 v (4+log2]9N/10C).

а временные затраты, в условных тактах, работы процессорного . элемента, при N<16 • :

Т» 4-(n + logjjil) + is 9N

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

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

В третьем разделе на основе предлагаемых разрядно-па-раллельных арифметических устройств разработаны алгоритмы и устройства обработки ПЧД в недвоичных СС. в частности. ССОК с использованием дробей Фарея:

1. Приведены разрядно-параллельные'алгоритмы и структуры выполнения арифметических операций в ССОК с числовыми данными, представленными в формате с фиксированной и плавающей запятой, • .

2. Разработаны алгоритмы' и структуры разрядно-парал-лельных устройств одновременного выравнивания порядков fi-no-зиционных дробей, прямого и обратного преобразования дробей Фарея в целые .числа, вычисления обратного элемента и его ранга по модулю р. -. вычисления, целой части числа по модулю и вычисления' рангов суммы N-чисел и произведения двух чисел.'

3. Даны формульные и экспериментальные оценки эффективности разработанных алгоритмов и структур, .- ./ :

Реализация n-арной операции разрядно-параллельного суммирования чисел в ССОК по: модулю Р4 заключается в их суммировании по правилам двоичной арифметики с последующим преобразованием полученного результата по модулю Pt.. . В качестве блока преобразования используется постоянная ламять с соответствующей прошивкой.* ■ , ' <-.;. v

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

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

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

Утверждение 2. Если в нормированный ССОК с -основаниями р1( ра.....ри., системой ортогональных базисов ^. В2......Вщ

га,, диапазоном Р = П Р-,

3«!

с соответствующим весами щ. гаг. . заданы числа А4 - (а^.'-Ог1..... с^1). Аг - (сц2, «г2

атг),.,., А„ - (аЛ «г"..»'•. а,/) с рангами г,;, г.;.

-г»

зоответственно. то ранг суммы г3 этих чисел определяется как;

(12)

Н в!

Г«' - I. п ' I-

Н

1 С^ 1=1

р 1

га,.

Утверждение, 9,,' Ёали й Нормированной СОК с основаниями

р». р2...... Ри. диапазоном р => П р, и системой ортогональных

базисов В1,В2,..\,би с соответствующими весами т1,шг,...,шП1

заданы числа А, - (о^1 .Ог1.... ,а„1), Аг - {а^.а^,____щ*)

с рангами Г! и гг,соответственно, то ранг произведения чисел Ах и Аг вычисляется как: /.'

или

Г 'V V

Г(А„х А ]

г 1

^Аг - I 3-1

ГгА1 - I 3-1

М)1

Мл2

пц.

(13)

(14)

Величины Аг, А! в формулах (13) и (14) должны быть представлены 'в ПСС, что;не оказывает влияния на продолжительность вычислений ввиду одновременности определения результата произведения чисел в ССОК и. его ранга. Используя предложенную методику контроля результатов вычисления в•ССОК

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

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

■ В четвертом разделе на основе рассмотренных разряд-но-параллельных процессорных элементов обработки ПЧД в позиционных и НСС исследуются вопросы построения алгоритмов и устройства прямых и обратных преобразований в принятом КСС. Наиболее трудоемкими . по Еременным и аппаратурным затратам являются преобразования из ССОК в ПСС. В работе предлагаются алгоритмы й устройства, позволяющие в несколько раз ускорить преобразования по сравнении с существующими способами..

Рассмотрим алгоритм преобразования чисел из системы остаточных классов'в двоичный код с вычисляемыми слагаемыми.

Пусть задан набор модулей CCOfi Р *■ (Pj, Р2.'____ Р„). В

этом случае диапазон .представления чисел ограничен числом

п

d - п pj. • v t-i

■ В системе остаточных классов для каждого модуля ?t введем понятие базиса следующим образом

• (1,-1. dj =1 П1 Рк. 1= 2.....п.

к-1

Очевидно, что представление базиса -в СОК дает остатки по модулям Р,.Рг_____.Р1-1 равные нулю, т.е.

Й! - (О. О.....О, Щ. . СС^.....Да).

Следует также заметить,. что величины, кратные базисам к к • _ '- ■ к

Е1 Ь^,- (1=.1,п,-К-1.РХ-1. 1?! € { 1.2...., Р^П) . также обладают тем свойством, что их представления в ССОК содержат нулевые остатки по модулям Р,. Рг Т1.1. Величины Ь, выбраны так. что к к

•'Е,- - Ьд-Й! — (0..0.....0, К, 1^2...-., 1„)',

. ■ *

т.е. для числа Е1 .остаток па модулю Р1 представляет собой *

= к. Величины Ь1 назовем весовыми коэффициентами базиса. Предлагаемый метод преобразования чисел из ССОК в двоичный код заключается в разложении исходного числа

. ' 1 Г ■.■■: 1 •

А « (а, , вг ...... осп! , 1 «1,...,п. , .

на сушу следующего вида '

'. . А' - X С^ • (15)

. 1-Х

Частичные суммы 1 Л х

С! - (о^: ..... ц,) , 1 «;1.Г..П (16)

выражают величины, соответствующее остаткам сц в представлении числа А в ССОК, Слагаемые С1 определяются последовательно. причем алгоритм вычисления зависит от величин Р, , а1 и от слагаемых,. полученных на предыдущих шагах разложения (Ск. к - 1,..,1к - 1). ' • '

Исходное число А на основании формул (15) и (16) может быть представлено в ССОК в следующем виде:

в п '■ '■' 11 1

А - 2 С! - X Щ ,02 —. а„ ) -1 »1 1

12 в 1 г п

(ц + <*1 +... + а,, щ + Оц +...+ «4.

г г п

«п + Оп ва )•

Параллельно с суммированием в ССОК выполняется суммирование слагаемых Сг в двоичном коде с целью получения двоичного представления числа А. .....■' Алгоритм вычисления С1. 1 = 1...,п выглядит следующим образом. Пусть для сц известно его позиционное представление

сц = С1р где с, б (ол.....Р! - 1).

Пусть также известно представление (Ц в ССОК по модулям Р).. Рг____. Рп. Пусть А' будет отображать приближение-по первому остатку к исходному числу А, ■ представленному в ССОК.

А' » (сц, а 2.....а'„ )- (13)

Если А' совпадает по всем остаткам с ; исходным числом, т.е. а'1 «стогда Сх « 0 для 1 - 2....П и исходное число А в двоичном коде будет равно

А - г с4. ■ •

Допустим, что- а'3 * а}, причем а к - а,, для к < тогда Сц - о.-с3 * о для К - 2.'____\J-i_

Слагаемое С3 определяется следующим образом.. Для определения в разложении числа А остатка сс3 по модула Р} необходимо к.А' добавить частичную сушу С3,' такую. чтобы скорректировать остаток а'3 до а5 на величину г = а3 - а'3, если а3 - а 3 >0 или г3 = а3 - а 3 + Р . если' а3 - а 3 < 0. Используя весовой коэффициент Ьг3. находю1 ; ' I

С3-(Ь3-с13)г -(0.0....,0.г.с5м. с[)С0К (19)

Вычисляем новое значение А' .Г ■,

А':- А'+ С3-(а1,аг.....а3' .а,*,'..-.! ,ав}+.._ -

+ (0.0.....г. сзм,....сп)- аг......а'3 +

+ . * ;..., а'„ + с*). (?.о>

Здесь а' 3 + г = а3. Введем обозначения а'лм:- + ,..., а'я : = с*. + а'п .

- 20 -

О ' -

тогда А' = (Oj. ctj..... <х:. a ¡tí.— «'¿)-

Если в результате операции суммирования А'и А совпадают по всем остаткам с^'и a¡ для 1=3+1. ...п. тогда ct = 0 для 1= 3+1,...п. Если же имеются несовпадающие остатки a¡ и а," для 1>J, тогда CJtI =С3»г . .= Cj.,'0. определение значения слагаемого Cj аналогично алгоритму вычисления С.,. •

После того, как слагаемые C¡, 1 - 1....П определены, находим позиционное представление числа А операцией суммирования в двоичной системе счисления: ... „ .

А •>.! Ct. •

í-i «

В разделе также рассмотрены вопросы алгоритмической и • структурной организации устройства преобразования чисел из ССОК в позиционный код в случае наличия ограничений, накладываемых на'выбор системы модулей ССОК Pt ,Рг,..., Р„, что в реальных условиях не всегда выполнимо, но как показывается в работе его в ряде случаев можно использовать в специализиро-' ванных ВУ, где необходимо высокое быстродействие. ' : ¡

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

В пятом разделе представлены результаты, служащие основой для построения разрядно-параллельных устройств для реализации сложных арифметических выражений, на примерах построения преобразователей Уолша и Хаара ■ и других устройств. Полученные результаты показывают, что введение в их структуры многовходовых суммирующих устройств обеспечивает: простоту и удобство подготовки входных и промежуточных данных;. повышение быстродействия обработки на 1-2 порядка за.счет раз-рядно-параллзльной реализации операции группового суммирования; выделение инвариантной части, присущей всем функциональным преобразователям независимо от назначения, что способствует ' повышению регулярности их структур и унификации. Также исследованы вопросы реализации алгоритмов и устройств обработки ПЧД на основе разрядно-параллельных процессорных элементов применительно к следующим задачам:

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

- решение систем линейных уравнений;

- вычисление квадратного корня; .

- ортогональный преобразования..'. -

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

Исследуются способы обработки ПЧД с применением разработанных структур.' • Приведены сравнительные оценки эффектив-. ности алгоритмов и структур, реализунлзих конкретные аряфмети-. ческив,Еырахения как в отдельной СС. так и в КСС. Разработан процессорный элемент, функщ'.ош-фуюглй в КСС к показываются » возможности его наращивания;, по' зертякалий горизонтали^

Предложен форкульшв зависшости.временных ^алпара-; турных затрат операционных устройств.использующих различную . организации обработки ПЧД на основа применения в них базовых ,, модулей -з качеств е. ЭУО» : ориентированных на разрядно-пар'ал-лельную обработку данных. .

Например, с использованием иерархического способа обработки ПЧД затраты определяются следующими выражениями: ; аппаратурные затраты Vy_ j. (условный .бит - двухвходовой" логический элемент И) •

. . tjt '. . ' .. б и. ■■■■■' ■ '

Vys " vy6 * Р- ГД9 V,e - аппаратурные затраты в условных битах.базового модуля разрядно-параллельного суммирующего устройства с разбиением общего переноса на основной и дополнительный, Р - количество базовых модулей в иерархичес-'. кой. структуре . . . _

С » ^ СК/2]+1>-{2Н [N/23+l>-<3*IN/2] +2}, г к

Р » I } S/N [. r=» ]log„ А[. где г - количество ступеней

. К-1 ...--•..■

(ярусов) в иерархической структуре. S-U/NI - параметр разбиения исходного ПЧД с размерностью А на S равных компонентов. ] [ - ближайшее большее целое:

временные затраты Ту т. (условный такт - время считывания информации из постоянной памяти)

Ту.т.- п-1 + S(l+n"), где п- разрядность исходных слагаемых, a n\-]log2N[ - количество тактов, необходимых для обработки переносов в (п+1) -ый РС в базовом модуле.

Сравнительные оценки показывают, что реализация арифметического выражения вида I xt в двоичной СС, где х, - слага-

' /; . i»i .: л , ¡.v... . ' . ■ .

емые с разрядностью п-32, при А-1500,.с использованием базовых модулей в иерархической структуре требует 51 условный такт, тогда как ассоциативный параллельный процессор, использующий алгоритм Фуллера-Эстрииа, требует для этого без учета операций пересылок в памяти 1792 условных'такта. Аппаратурные затраты при этом составляют соответственно 24750 и 32000 условных битов. Выигрыш в скорости вычислений

показан ка примере реализации выражения 1 Xj-yj с разряд-• / ' ■ . i«».- ■ .■■. . .

ностью слагаемых п»32. '-при А-100 вычисления занимает 52 условных тактов в случав применения в иерархической структуре базовых ■ модулей, по сравнению.с 6659 условными тактами при выполнении на ассоциативном параллельном процессоре. Аналогичные оценки, получены и для остальных алгоритмов и струк-

Внедрение результатов. Результаты проведенных исследований, при непосредственном участии автора, нашли практическое применение в следующих.разработках, проводимых в соответствии планами работ кафедр информатики и управления в технических системах, вычислительной техники и прикладной математики Дагестанского государственного технического университета: •. "

- специализированный алгоритм и структура устройства выполнения операции умножения /разработка выполнена по заданию Института проблем управления, г. Москва, 1990 г./;

7 алгоритмы и структуры выполнения арифметических операций в системе счисления в остаточных классах, а также программный комплекс, моделирующий вычислительные процессы в комплексе систем счисления /разработка' выполнена для ГНИИ РЗСПЧС (Дагестанский филиал), г. Махачкала. 1994-1995 гг./;

- разрядно-параллельные алгоритмы и структуры арифметических устройств и устройств преобразования в комплексе систем счисления включены в теоретические разделы 6-ти дисциплин, изучаемые студентами-, специальностей 22.01 и 21.01., а такзе используются при выполнении лабораторных, курсовых, дипломных работ и НИРС в Дагестанском государственном техническом университете.

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

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

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

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

.' 4. Дана классификация потоков числовыхданных-'и потоков-операций по критерию их-, однородности и выделен класс вычис-■ лктел^ных машин". ориентированных на обработку неоднородных потоков числовых данных в комплексе.систем счисления.

5. Определен состав.комплекса СС, включающий двоичную, двоично-десятичную и систему счисления в остаточных классах с использованием дробей Фарея. • ' . '6. Предложена обобщенная структура разрядно-параллель-" кого процессорного элемента, функционирующего в комплексе систем счисления и использующего.таблично-алгоритмические' метода обработки потоков числовых данных.

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

- 24 -

г 4

неоднородных потоков числовых данных. •

'8. Разработаны алгоритмические основы построения раз-рядно-параллельных ■ процессорных элементов обработки потоков числовых данных в комплексе систем счисления, включающие:'

- алгоритм п-арного двоичного суммирования с обработкой общего многоразрядного переноса:

- алгоритм п-арного двоичного суммирования.с обработкой основного и дополнительного переносов;

- алгоритм п-арного двоичного суммирования с конвейерным способом обработки многоразрядного переноса;.

- алгоритм п-арного суммирования в двоично-десятичной и системе счисления в остаточных классах; . • ' .

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

- алгоритм, п-арного суммирования комплексных чисел, представленных в. двоичном коде;

- алгоритмы п-арного суммирования чисел, представленных з формате с плавающей запятой;; ' • '

- -разрядно-параллельные алгоритмы выполнения операции умножения чисел; ■ •.-..■. ■ • • '

алгоритмы прямых а обратных преобразований; потоков числовых данных в КСС ' вида <2 —> 10. СОЮ. {2-10 «—> 2. СОК}, {СОК —■> 2. 2-Ю}, а Также алгоритмы "связанные с преобразованием дробей Фарея и комплексных чисел;

'■■'-. сформулированы и доказаны утвбргденйй о переносе .а рангах чисел.' •

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

10. Разработаны вопросы структурной интерпретации алгоритмического базиса обработки потоков числовых данных в КСС. включая структуры операционных устройств, функционирующих в 2. 2-10 и СОК. и устройств прямых и обратных преобразований вида 12 —> 10. СОЮ. {2-10 <—>2. СОК). (СОК «О 2. 2-10), а также преобразования фобей Фарея. .

11. Приведены формульные зависимости временных и агта-

ратурных затрат разработанных структур.

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

13. Показана возможность практической реализации, процессорных элементов обработки потоков числовых данных в комплексе систем счисления'на основе . программируемых логических матриц и ПЗУ. ■ •

14. Исследованы вопрорн построения АУ с использованием разработанных структур с организацией: .

- иерархического способа' обработки' числовых данных;

- одномерной итеративной цепи;

-■варианта <гнакапливающим сумматором.

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

16. Приведены сравнительные оценки эффективности разработанных алгоритмов и структур.

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

В приложении приведены: - алгоритмы программной модели разрядяо-параллельного процессорного.элемента, имитирующая-вычислительный процесс в комплексе систем, счисления; v '7 материалы' по внедрению результатов диссертации, подк-■ репленные соответствующим!! актами.. '

Автор, выражает благодарность доктору технических наук Кокаеву Олегу Григорьевичу за вниманием поддержку в работе.

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

1. Исмаилов ffi-M. А. Магомедов И. А. . Разрядно-параллель-ные процессорные элементы для решения задач машинной графики: Тез. докл. VIII - го научно-техн. сем. "Математическое обеспечение систем с машинной графикой". Ижевск. 1992.-с.68.

- 26-

о ■

2. Исмаилов Ш-М. А., Бодан Ф. Н.. Хаспулатов Э.Х. Параллельно-разрядные арифметические устройства обработки потоков числовых данных в комплексе систем счисления: Тез. докл. Международной научно-техн. конф. "Актуальные проблемы фундаментальных наук'!. - Москва, 1991. - с.43.

3. Исмаилов Ш-М. А. -Структура параллельно-разрядного процессорного элемента обработки потоков числовых -данных в комплексе, систем счисления: Тез. докл. Всесоюзной научно-техн. сем. "Мн0Г0Щ)0цесс0рные вычислительные системы". Таганрог. 1991. -с. 74-76.

4. Исмаилов Ш-М.А. Разрядно-параллельные процессорные элемента для решения задач машинной графики: Тез. докл. Российской научно-техн. конф. - Ульяновск. 1993;- ¿'.22.

5. исмаилов Ш-М.А., Конарев E.H. Структурная организация арифметических, устройств обработки массивов числовых данных в комплексе систем счисления // сб. научных тр. "Актуальные проблемы информатики, управления и радиоэлектроники. - Махачкала. 1995. - с. 83.

6. Исмаилов 1-И.А.. Артамонов Ё.И.. Кокаев о.Г.. Хачу-' мов В.М. Специализированные алгоритмы и устройства обработки массивов данных.г Махачкала. Дагестанское книжное издательство. i993,- 301 с.

7. А.-С, N 1062689 СССР. ,ЮШ G 06 F 7/50. Суммирующее устройство /Исмаилов Ш-М. А., Айдемиров И.Ä.. Кокаев 0.Г.. Темирханов Т.Э. (СССР), - N 3502589/24-24; заявл. 20.10.82; Опубл. . 23.12.83. БВЛ. N47.

8. A.c. N-1200281 СССР, ИКИ G 06 F 7/50. Устройство для суммирования М-чисел /ИскаиЛов Ш-М.А.. Айдемиров И. А.. Ока- . ров О.М. " (СССР). - N 3758607/24-24; заявл.26.06.84; Опубл. 23.12.85. Бюл. К 47.. •

9. A.c. N 1233134 СССР, МКИ G Об F 7/50. Ассоциативное суммирующее устройство двоичных и двоично-десятичных чисел /Исмаилов Ш-М.А.. Кокаей О.Г. (СССР). - N 3850695/24-24; за-ЯВЛ. 12.01. 84; Опубл. 23.05.86, БЮЛ. N 19.

10. A.c. N 1807460 СССР. МКИ G 06 F 7/50. Суммирующее устройство /Исмаилов Ш-М.д.. Зурхаев A.A.. Курбанов Э.Н.. Кокаев 0.Г.. Магомедов И. А (СССР). - N 4954884/24; заявл. 10.06.91; опубл. 07.04.93. Бал. N 13.

11. Исмаилов Ш-М.А., Кокаев О.Г.. Кисленко B.C., Пету--хова 3. Н. Ассоциативные вычислительные устройства. Деп. ВИ- ■ НИТИ от 8. 09.87. N 6575 - В87, 1987.- 13 С.

12. А. С. Н 1807480 СССР. МКИ G 06' F 7/50. Суммирующее устройство/Исмаилов Ш-М.А.. Зурхаев A.A.. курбанов Э.Н., Магомедов И.А (СССР) . - й 4908946/24; заявл.07.02.91; Опубл. 07.04.93, БЮЛ. N 13. _

13. Исмаилов Ш-М. А.. Йокаев О.Г., Айдемиров И. А. Булевы матрицы в операции группового суммирования: Тез. докл. респ. конф."Теория и практика проектирования РЭА". . Махачкала. 1987.- 5 С.

14. A.C. N 1765891 СССР. МКИ Н 03 М 7/18. • Аналого-цифровой преобразователь в код системы остаточных классов /Исмаилов Ш-М.А., Кокаев О.Г.. Курбанов э.Н., Магомедов И.А (СССР). -N 4865149/24; ЗЭЯВЛ. 10.09.90: Опубл. 30.09.92, Бюл. N 36. .

15. Исмаилов Ш-М.А. Алгоритмы и структуры устройств преобразования чисел из позиционной системы счисления з код остаточных классов. - Научно-техн. сб. "Информатика.и вычислительная техника". Теория и приложение. - Изд. ■ Дагестанского гос. университета. 1994.- 8 с. '

16. Исмаилов Ш-М.А.. Аминов Э.,Ф: Организация массовой обработки а ЭВМ с изменяемой системой счисления: Тез. докл. юбилейной XX - ой'Международной конференции и школы молодых ученых и специалистов "САЛР-93", Гурзуф-Ялта, 1993.- с. 17.

..' 17. Исмаилов Ш-М.А. Параллельно-разрядные процессорные-элементы обработки потоков' числовых данных в комплексе систем счисления с программируемой архитектурой:. Материалы выездной сессии АЕН "Фундаментальные и прикладные вопросы естественных наук" - Махачкала, 1994.- с. 39-41.

18. Исмаилов Ш-М.А., Зурхаев A.A., Кокаев О.Г. Архитектура процессорного элемента, в комплексе систем.счисления для мультитранспьютерной сети: Тез. " докл. первого ' меадунар. симп. "Интеллектуальные системы-94. -Махачкала. 1994.- с.39.

19. Исмаилов Ш-М.А'. Организация высокопроизводительных устройств обработки потоков данных в комплексе систем счисления: Тез. докл. Российской научно-техн. конф. "Системный анализ и принятие решений в задачах.автоматизированного

- 28 -

fc" *

обеспечения качества и надежности изделий Приборостроения и .радиотехники". Махачкала,. 1991,- с. 65

20. A.c. Ы 1803912 СССР,, МНИ Q 06 F 7/50. Суммирующее устройство /Иснаилов 11ЬМ.А., Кокаев О.Г...Курбанов Э.й., Магомедов И.А {СССР). - И 4922072/24; заявл.07.02.91; Опубл. 23.03.93. Бюл. Н 11.

21. A.C., Ы 1277095 СССР, . МКИ G 06 F 7/50: Устройство для суммирования N * n-разрядных двоичных чисел /Исмаилов Ш-М.А.. Омаров О.Ы. (СССР). - N 3831716/24-24; заявл. 25.12.84; опубл. 15.12.86, Бюл. N 46.

22. А.с.' N 1267625 СССР, МКИ Н 03 М 7/18. Устройство для преобразования числа из системы остаточных классов в позиционный код /Исмаилов Ш-М.А.. Зурхаев А.А.. 'Исаева И.И-, Кокаев О.Г. (СССР), - N 3903193/24-24: заявл. 31.05.85; Опубл. 30.10.66, БЮЛ. 'К 40. *

23. A.c. N 1541783 СССР, МКИ Н 03 М 7/18.-Преобразователь чисел из кода системы счисления в остаточных классах в двоичный код /Исмаилов Ш-М.А.. Хаспулатов э.Х. (СССР). - К 4404695/24-24; заявл. 04:04.88: . Опубл. 30.10.90. Бюл. N5.

24. A.c. N 1273917 СССР. МКИ G 06 F 7/50. Н 03 М 7/00. Устройство для /суммирования, n-разрядных чисел /Исмаилов Ш-М.А.. Исаева U.U... Темирханов Т.Э. (СССР). - N 3916945/24-24; 'заявл. 22.04.85: Опубл. 30.11.86. БЮЛ. К 44.

25. A.c. К 1649567 СССР. МКИ G'■06 F 15/353. Ассоциативное устройство для линейной интерполяции /Исмаилов Ш-Ы.А.. Кокаев О.Г.. Зурхаев A.A., Магомедов И.А. (СССР).. - И 4686131/24: заявл; 03.05:89; Опубл. 15.05.91. Бол. N18.

26.сАртамонов Е.И., Исмаилов Ш-М.А-. Кокаев О.Г., Хачу-мов В.М. Параллельный алгоритм Волдера для операции поворота и его применение в машинной графике.// - УСиМ. 1990.- N 1, - с. 106-109. •■'■•■■' . .

27. А.с. .N 1322261 СССР. МКИ G 06 F 7/50. Конвейерное вычислительное устройство / Исмаилов Ш-М.А., Айдемиров И.А. (СССР). - К 3964167/24-24: заявл. 11.10.85; Опубл. 07.07.87. Бюл.' N 25.

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

1973 г. - с. 32. »

¿9. Исмаилов Ш-М.А.. Кокаев О.Г., Темирханов Т.Э. Об одном подходе к построению эффективно-диагностируемых вычислительных устройств: Тез. докл. Всесоюзной конф., Москва -Махачкала, 1980 г.- с. 47.

30. Исмаилов Ш-М.А., Магомедов K.M.. Кокаев О.Г. и др. Эффективно-диагностируемые и эффективно-программируемые ассоциативные вычислительные устройства и системы на их осно-зй: Тез.докл. Всесоюзного совещания "Высокопроизводительные системы",' часть 3. - Москву. 1981 г. - 83 с.

31. Исмаилов Ш-М. А., Темирханов Т.Э.. Гафуров И. Г.. Кондаков 0. А. Ассоциативный параллельный процессор: Тез. докл. Всесоюзной конф., Челябинск. 1931 г.- 72 с.

. 32. Исмаилов ш-м.А.. Айдемиров И.А,. Темирханов Т.Э. Параллельный процессор для задач САПР: Тез. докл. Всесоюзной конф., Махачкала, 1981. - с. 14-21.

33. Исмаилов И-М. А. Некоторые вопросы .организации параллельно-последовательного процессора для групповой обработки, информации: • Тез. докл. республ. конф., Махачкала. 1983. - с. 43-44.' ' '

34. Исмаилов И-М. А. Об одном подходе к построению высокопроизводительных арифметических устройств обработки числовой информации: Тез. докл. республ. конф., Махачкала, 1935. ■ 54 с. •

35. Исмаилов Ш-М.А., Зурхаев A.A.. Кокаев О.Г. Проектирование средств диагностирования ассоциативных вычислительных структур: Тез, докл. республ. конф., "Теория и практика: проектирования РЭА", Махачкала. 1986.- 17 с.'

36. Артамонов Е. И.. Айдемиров И. А., Исмаилов Ш-К.А., Хачумов 5.М и др. Геометрический процессор для диалогового анализа изображений: «Тез. докл. Всесоюзной научно-технической конф. "Образное представление данных в управлений и. научных исследованиях". Грозный. 1987. - S3 с.

- 37. Айдемиров И.А., Исмаилов Ш-М.А.. Хачумов В.м. Ускорение процессов визуализации графической, информации на основе быстрого преобразования вектор-растр: Тез. докл. Всесоюзной научно-техн. конф. "Проблемы развития аппаратных'и программных средств вычислительной техники для машинного модели-

рования". ii.: Радио и связь. 1937,- с. 114-115.

'38. Айдемиров И.А.. .Исмаилоз Ш-М.А.. Хачумов В.М. Быстрый алгоритм плоского поворотами его применение в машинной графике: Тез. докл. научной сессии Лаг. ФАН СССР, посвященная итогам фундаментальных и прикладных исследований. Махачкала, 1988.- 137 с.

39. Исмаилов 111-М.А., Зурхаев A.A., Кокаев О.Г.-, Магомедов И.А. .Ассоциативный параллельный процессор обработки потоков числовых данных в комплексе систем счисления: Тез. докл. vi-ro научно-техн. сем. "Математическое обеспечение систем с машинной графикой". Ижевск-Махачкала, 1989.

40. Исмаилов Ш-М.А., Миндалова Л.Г., Мачулин В.В. Таблично-алгоритмический способ быстрого извлечения квадратного корня: Тез. докл. 12-ой республ. конф., Махачкала. 1989.-61 с.

41. Магомедов И.А.. Исмаилов Ш-М.А., Кокаев О.Г. Принципы построения ассоциативных процессоров нечеткого управления: Тез. докл., Межреспубл.. конф. "Методы и средства управления технологическими процессами". Саранск, 1989.- 27 с.

42. Айдемиров И. А.. Исмаилов Ш-М'. А., Хачумов в. М. Об одном . алгоритме отсечения многоугольников.// ' Автометрия, 1990.- N 4, с. .10 - 14.

43. Исмаилов Ш-М.Д., Зурхаев A.A., Кокаев О.Г..' Магомедов И. А.' Аппаратная поддержка математического обеспечения вычислительных систем: Тез", докл. • Российской научно-техн. конф. "Системный анализ и принятие решений в задачах автоматизированного обеспечения качества и надежности изделий приборостроения И радиотехники". Махачкала,.. 1991.'-• 65 е..

44. .Исмаилов Ш-М.А., Кокаев О.Г. .и др. Функциональные модули для управляющих вычислительных систем: Тез. докл. Всесоюзной научно-технич. конф. - М.: 1982. - 36 с.

45. Исмаилов Ш-М.А.', гАйдемиров И.А., Омаров О.М. Архитектура мультипроцессорной ВС на базе ассоциативных структур: Тез. докл. Всесоюзного совещания.- М.: ЦНИИТЭИ, 1983.

46. Исмаилов Ш-М.А., Хачумов В.М, Решение задач машинной графики в системе алгоритмов Волдера: Тез. докл. 3-ей Международной конф. по компьютерной графике и визуализации. -СПб, 1993, Т. 2, 25 С.

47. A.c. -.К 1043650 СССР, МКИ G OS F 7/50. Микропрог-

раммное устройство управления /Исмаилов Ш-М. А., Кокэев О.Г.. Темирханов Т.Э.. Магомедов И.А. (СССР). -N 3418270/24-24: заявл. 07.04.82; Опубл. 10.10.83, Бюл. N 35.

48. A.c. N 1174920 СССР, МКЙ G 06 F 7/50. Ассоциативное суммирующее устройство /Исмаилов Ш-М. А., Айдемирсв К.А.. Омаров О.М. (СССР). - Я 3632515/24-24; заявл. 12.08.83: Опубл. 23.08.85. Бюл. Я 31. .

49. A.c. N 1424011 СССР, МКИ G 06 F7/50. Ассоциативное суммирующее устройство /Исмаилов Ш-М. А.. Айдемиров И. А., Зурхаев A.A., Магомедов И,А. (СССР). - Н 4165174/24-24: заявл. 23.12.86: Опубл. 15.09.88. Бюл. Н 34.

50. A.c. N 14511681 СССР. МКИ G 06 F 7/50. Суммирующее устройство /Исмаилов Ш-М.А., Артамонов Е. И.. Айдемиров И.А., Еолин Ф.Н. (СССР). - ?! 4257060/24-24: заявл. 20.04.87; Опубл. 15.01.39, БЮЛ. N 2.

51. A.c. М 1665373 СССР. МКИ G 06 F 7/50. Ассоциативное суммирующее устройство /Исмаилов Ш-М.А., Зурхаев A.A.. Хачу-иовВ.М., Магомедов И.А. (СССР). - Н 4722382/24; заявл. . 14.06.89: Опубл. 23.07.91. Еал. Н 27.

52. A.c. N 1672439 СССР. МКИ G 06 F 7/50. Устройство для суммирования М чисел. /Исмаилов Ш-М. А., Айдемиров И.А., Зурхаев A.A.. Бодин Ф.Н/, Кокаев О.Г. (СССР). - N 4689565/24: заявл. 11.04.89; Опубл. 23.08.91, Бюл. N 31.

53. A.c. Ii 1714586 СССР. МКЙ G 06 F 7/50. Суммирующее устройство.' /Исмаилов Ш-М. А.. Бодин Ф.Н., Кокаев О.Г.. Боди-наН.А, (СССР). - И 4865375/24: заявл. 27.06.90: Опубл. 23.02.92. Бюл. N 7. ■ .

54. Исмаилов Ш-М.А... Магомедов К.А.: 3\фхаев A.A. Некоторые вопросы анализа и синтеза .эффективнс-диагностируемьк вычислительных устройств: Тез; докл. Всесоюз. научн.-техн. конф."Теория и практика проектирования РЭА", Махачкала, 1986. - 18 с. .

. • 55. А, с. М 1775722 СССР. ГШ G 06 F 7/50. Суммирующее устройство. /Исмаилов Ш-М. А., Зурхаев A.A.. Кокаев О.Г., Са-идов A.C., Магомедов И.А. (СССР). - N 1062689/24: заявл. 01.08.90: опубл. 15.11.92, Бюл. N42.

56. A.c. II 1784969 СССР. МКИ G 06 F 7/50. Вычислительное устройство. /Исмаилов Ш-М.А.. Зурхаев A.A., Кокаев О.Г.,

Саидов A.C.. Магомедов И.А. (СССР). - N 4871468/24; заявл. 01.08. 90: Опубл. 30.12.92, 'Бюл. К 48.

57. A.c. и 1784970 СССР. МКИ G 06 F 7/50. Суммирующее устройство. /Исмаилов Ш-М.А., Зурхаев A.A., Кокаев О.Г., Саидов A.C.. Магомедов К.А. (СССР). - N 4907748/24; заявл. 31.10.90; Опубл. 30.12.92. Бюл. N 48.

58. A.c. К 1757106 СССР. МКИ Н 03 К 7/18. Преобразователь чисел из кода- системы счисления в остаточных классах б двоичный код /Исмаилов Ш-М.А.. Хаспулатов Э.Х. (СССР). - К 4805970/24; заявл. 08.01.90; Опубл. 23.08.92, . Бюл. К 31.

59. Исмаилов Ш-М. А., С. Б. Тальха. Быстрая реализация преобразований -Уолша и Хаара:. Тез. докл. 5-ой кеждун. конф. по компьютерной графике и визуализации "Графикон" 95. - Л..: 1995. - 43 С.

60. Патент *К 2034328 Россия, .МКИ G 06 F 7/49. Суммирующее устройство по модулю /Исмаилов 12-М. А.. Джанмурзаез А. А., Курбанов Э.Н. (Россия).-N 93011221/24; заявл. 01.03.93; Опубл. 30.04.95. Бюл. N 12.

. 61. Патент N 2030783 Россия, МКИ G 06 F 7/50. Устройство для определения количества единиц в двоичном ' восьмираз* рядном числе /Исмаилов Ш-М. А.. , Зурхаев А. А., Кокаев 0. Г., Магомедов И.А. (Россия).- N5015072/24; заявл.03.07.91; Опубл. 10.03.95, Бюл. N7. '

62. Исмаилов Ш-М.А.. Мурадов М.М. Разрядно-параллельные суммирующие устройства в кодах Фибоначчи: Тез. докл. Все-рос. научно-практической конф., Махачкала, 1995. с.59-60.

63. -Исмаилов Ш-М. А.. Кокаев о. Г., Зурхаев А. А. Алгорит-мк и структуры ' разрядно-параллельных устройств умножения двоичных чисел: Тез. докл. Всерос. научно-практической конф.. Махачкала, 1995. с.65-66.

64. Исмаилов ш-М. А. Разрядно-параллельные алгоритмы обработки массивов числовых данных. //Известия вузов. Приборостроение. 1995.- 3-4, с. 14-15.

65. Исмаилов Ш-М.А. Разрядно-параллельные алгоритмы суммирования массивов числовых данных. //Материалы 1-ой научной сессии Дагестанского отделения Международной академии информатизации "Информатика и вычислительная техника. Теория я приложения.", Махачкала, 1995. - с. 29-32.

ЛР №020269 от 12.11.1991 г.

одписано в печать 11.12.95. Формат 60x84 'Дб. Бумага тип. Печать ротапринтная 88 усл.п.л. 1,87 уч.изд.л. Тираж 100 экз. Заказ № 102. гдакционно-издательский отдел ДГТУ

ПЦ ДГТУ, 367015 г. Махачкала, пр. Калинина, 70.