Содержание к диссертации
Введение
Глава 1. Аналитический обзор существующих средств сложения чисел и сущность предлагаемого подхода 12
1.1. Общие сведения. Краткая историческая справка 12
1.2. Классификации методов сложения 14
1.3. Аппаратные средства поддержки методов сложения 15
1.3.1. Аппаратная поддержка методов сложения в RISC процессорах 16
1.3.2. Аппаратная поддержка методов сложения в цифровых сигнальных процессорах 17
1.3.3. Аппаратная поддержка методов на основе ПЛИС 19
1.3.4. Аппаратная поддержка методов сложения в специализированных устройствах 20
1.4. Побудительные причины исследования и сущность предлагаемого подхода к созданию сумматоров массивов чисел 24
1.5. Выводы по главе 25
Глава 2. Разработка и структурно-лингвистическое исследование алгоритмической продукционной схемы сложения 27
2.1. Основные положения организации процесса сложения 27
2.2. Основные понятия параллельных вычислений операций 29
2.3. Разработка специализированной продукционной системы для сложения чисел в знакоразрядной системе счисления 33
2.3.1. Алфавит (базис), слово, языки и продукции 33
2.3.2. Синтез алгоритмической схемы символьного сложения 36
2.4. Структурно-лингвистический анализ продукционной схемы сложения 40
2.5. Выводы по главе 59
Глава 3. Разработка алгоритма, реализующего способ сложения, его проверка с применением математических моделей и данных эксперимента 60
3.1. Построение параллельного алгоритма сложения с помощью продукционного подхода 60
3.1.1. Алгоритм Фі (продукция Пі) 61
3.1.2. Алгоритм Ф2 (продукция П2) 62
3.1.3. Алгоритм Ф3 (продукция Пз) 62
3.1.4. Алгоритм Ф4 (продукция Щ) 64
3.1.5. Алгоритм Ф5 (продукция П5) 64
3.1.6. Алгоритм Фб (продукция П6) 65
3.1.7. Алгоритм Ф7 (продукция П7) 66
3.1.8. Алгоритм Ф8 (продукция П8) 67
3.1.9. Алгоритм Ф9 (продукция П9) 68
3.1.10. Алгоритм Фю (продукция П]0) 69
3.2. Сочетание алгоритмов Ф] тф|0 69
3.3. Алгоритм параллельных подставок, используемых при суммировании массива 70
3.4. Реализация способа продукционного сложения 73
3.5. Сравнительная оценка скорости работы продукционной алгоритмической схемы 74
3.6. Выводы по главе 82
Глава 4. Разработка и исследование аппаратных средств символьного сложения 83
4.1 .Формализация и синтез продукционного сумматора 83
4.2. Базовая ячейка сумматора. Триггер с тремя устойчивыми состояниями 90
4.3 .Структурная схема сумматора 91
4.4. Функциональные схемы узлов и блоков 93
4.4.1 Функциональная схема сумматора 32X32 93
4.4.2 Функциональная схема регистра выборки 97
4.4.3. Функциональная схема регистра нуля 97
4.4.4. Функциональная схема блока приоритетов 99
4.4.5. Функциональная схема коммутатора 99
4.4.6. Функциональная схема устройства управления сдвигом 103
4.5. Оценка скоростных характеристик разработанного устройства и сравнение их с аналогом 109
Выводы по главе 113
Заключение 114
Основные публикации по теме диссертации 116
Список использованной литературы 119
Приложения
- Аппаратная поддержка методов сложения в цифровых сигнальных процессорах
- Разработка специализированной продукционной системы для сложения чисел в знакоразрядной системе счисления
- Алгоритм параллельных подставок, используемых при суммировании массива
- Базовая ячейка сумматора. Триггер с тремя устойчивыми состояниями
Введение к работе
Актуальность. Сложение занимает доминирующее место среди арифметических операций. Обработка сигналов, функционирование цифровых фильтров, решение задач наведения и робототехники, мониторинга различных процессов, статистическая обработка, маршрутизация информационных потоков и т.д. требуют применения высокопроизводительных цифровых и символьных средств обработки информации. Очевидно, что повышение скорости выполнения операции сложения дает возможность ускорить все другие арифметические операции.
Сложение массивов чисел в знакоразрядной системе счисления, имеющей ряд положительных свойств (интервал распространения переносов, контроль операндов и результатов выполнения операции сложения, отсутствие преобразований в обратный или дополнительный коды и др.) не нашло целостного отражения в современных исследованиях по проблемам вычислительной техники, что составляет основную проблемную ситуацию. Основная решаемая задача данного диссертационного исследования заключается в разработке символьных продукционных алгоритмов сложения массивов чисел в позиционной знакоряз-рядной системе счисления (ПЗСС) и устройства, реализующего операцию сложения.
Вопросам скоростной обработки числовой информации посвятили свои работы Каляев А.В., Марков А.А., Бойков В.Д., Смолов В.Б., Бандман О.А., Ачасова С.Н., Kung N.T., Book R.V. и другие отечественные и зарубежные ученые.
Для решения основной задачи диссертационного исследования имеются необходимые предпосылки и основания. За сравнительно короткий срок были созданы высокоскоростные арифметические алгоритмы и соответствующие устройства последовательной, параллельной и конвейерной обработки. Мировой опыт показал, что традиционные методы, разработанные для компьютеров с неймановской архитектурой имеют низкий уровень эффективности в услови-
ях возросших требований к скорости обработки данных. Поскольку значительные объемы информации хранится в символьных формах представления в виде баз данных, текстовых файлов, электронных таблиц, все чаще находят применение методы обработки символьной информации, базирующиеся на продукционных алгоритмах.
Научный аспект данной диссертационной работы связан с исследованием и разработкой алгоритмической продукционной системы для сложения массивов чисел и обоснованием завершаемости и корректности выполняемого вычисления на всем множестве значений операндов. Практическая часть диссертационной работы включает в себя, разработку технического решения конвейерного устройства сложения массивов чисел в ПЗСС.
На основании изложенного следует вывод об актуальности и перспективности темы диссертационного исследования.
Работа выполнялась в рамках госбюджетных НИР по гранту Г02-4.2-5 «Методы системно-структурной организации архитектур семейства процессоров нового поколения и многопроцессорных систем высокоскоростной обработки символьной информации и исследование их скоростных характеристик» при непосредственном участии автора.
Цель диссертационной работы заключается в создании эффективной по времени продукционной алгоритмической схемы и устройства сложения массивов чисел в позиционной знакоразрядной системе счисления и исследовании скоростных характеристик алгоритмов и сумматора. Поставленная цель достигается решением следующих задач:
Создание схемы продукционного алгоритма для выполнения операций сложения массива чисел в формате с фиксированной точкой в ПЗСС.
Исследование продукционной схемы сложения для обеспечения условий корректности, завершаемости и однозначности вычислений.
Синтез элемента структуры сумматора и реализация его структурно-функциональной организации.
4. Исследование, скоростных характеристик алгоритмов и сумматора, а также определение уровня аппаратных затрат.
Объектом исследования диссертационной работы являются алгоритмические средства быстрых символьных вычислений на основе продукционной парадигмы и аппаратные средства их реализации.
Предметом исследования являются процессы и устройства сложения массивов чисел в ПЗСС с использованием продукционных алгоритмических схем.
Методы исследования основаны на положениях конструктивной математики, методах современной теории алгоритмов, теорий конечных автоматов и проектирования ЭЦВМ.
Научная новизна заключается в том, что впервые получены следующие результаты:
Разработана новая форма представления продукций, отличающаяся заданием образцов и модификаторов в виде двухмерных конструктивных объектов, что обеспечивает обработку массивов чисел, заданных в ПЗСС.
Впервые создана суммирующая продукционная алгоритмическая схема, которая выполняет одновременное сложение множества операндов слагаемых в рассматриваемой системе счисления. Проведено исследование алгоритмической схемы и установлено, что разработанная схема имеет двукратное снижение вычислительной сложности по отношению алгоритму-аналогу, построенному на основе параллельных подстановок.
По результатам теоретических исследований установлена корректность, завершаемость и однозначность разработанной суммирующей продукционной алгоритмической схемы сложения массива операндов.
Синтезирован элемент однородной структуры и осуществлена системно-структурная организация конвейерного сумматора, сокращающего затраты времени на суммирование в 8 раз по отношению к устройству аналогу.
Практическая ценность работы заключается в том, что по результатам теоретических исследований продукционных алгоритмов сложения массивов знакоразрядных чисел реализованы технические решения устройства (схемы) сложения на основе быстрых символьных вычислений с использованием матричных схем с малым временем задержки элемента, определяющих целесообразность создания СБИС с высокой рабочей тактирующей частотой. Результаты проведенных исследований и выполненных разработок открывают пути для дальнейших опытно-конструкторских разработок и могут быть рекомендованы для использования в учебном процессе студентов и аспирантов профильных специальностей.
Апробация результатов работы. Результаты работы отражены в докладах на научных конференциях: V Научно-техническая конференция с международным участием «Материалы и упрочняющие технологии-97», Курск, Россия, 1997 год; Международная техническая конференция «Медико-экологические информационные технологии», Курск, Россия, 1998 год (2 доклада); I Всероссийская научно-техническая конференция, часть {II} «Компьютерные технологии в науке, проектировании и производстве», Нижний Новгород, Россия, 1999 год (2 доклада); VIII Международная научно-техническая конференция «Физические и компьютерные технологии», Харьков, Украина, 2004 год (2 доклада); Международная научно-техническая конференция «Экология и защита окружающей среды», Курск, Россия, 2004 год (2 доклада).
Реализация результатов. Результаты работы внедрены в филиале СЭС ОАО «Курскэнерго», а также в учебный процесс Курского государственного технического университета.
Основные положения, выносимые на защиту:
1. Формы представления продукций и алгоритмическая продукционная схема на их основе для выполнения операции сложения массивов чисел в ПЗСС, отличающаяся тем, что в ней впервые используются продукции с двухмерными образцами и модификаторами.
Результаты структурно-лингвистического анализа продукционной схемы, обосновывающие корректность, завершаемость и однозначность ее работы.
Технические решения элемента и структурно-функциональная организация устройства конвейерного сумматора, обеспечивающего быстрые символьные вычисления массивов чисел в ПЗСС.
4. Результаты исследования вычислительной сложности алгоритмов и
скоростных характеристик устройств конвейерного сложения массивов чисел в
ПЗСС.
л Публикации по работе. По материалам диссертации опубликовано 8
печатных работ и получен патент на изобретение.
Личный вклад автора в работах, написанных в соавторстве, состоит в . том, что им разработаны продукционная алгоритмическая схема сложения массивов чисел в ПЗСС и базовые технические решения.
Структура и объем работы. Диссертация состоит из введения, четырех
. глав и заключения, изложенных на 128 страницах машинописного текста, со-
держит 37 рисунков, 4 таблиц, список литературы из 99 наименований и приложений объемом в 39 страниц. Общий объем диссертации 167 страниц.
ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ Во введении обоснованы важность и актуальность темы, определены и сформулированы цель, задачи и методы исследования, приводятся научная новизна и практическая ценность работы, обоснованность и достоверность научных положений, апробация и реализация результатов, основные положения, выносимые на защиту, структура и объем диссертационной работы.
Первый раздел носит обзорный характер и посвящен анализу сущест
вующих алгоритмических средств сложения и аппаратных средств с учетом
специфики решаемых задач. По итогам анализа в данной главе приводится
*V сущность и отличительные характеристики предлагаемого подхода, а также его
место и роль при решении проблем сложения. Приводятся хронологические
сведения развития средств сложения и результаты анализа специфики задач
сложения, даются сопоставительные характеристики аппаратных платформ
( реализации сложения. Производится анализ известных технических решений
задач сложения на основе универсальных процессоров Spars, программируемых логических интегральных схем, цифровых сигнальных процессоров и специализированных устройств. В процессе обзора установлено, что в средствах сложения не использовались разработки в области продукционных алгоритмов, принципов символьных вычислений, применение которых открывает перспек-тивы в создании новых путей высокоскоростной реализации сложения.
Сущность предлагаемого подхода к созданию сумматора заключается в разработке символьных, а не числовых методов алгоритмической реализации процессов сложения и аппаратной поддержке разработанной продукционной алгоритмической схемы. Из конструктивной математики известно, что в рамках продукционной парадигмы арифметические операции осуществляются сравнительно медленно ввиду доминирующей ориентации продукционных ал-горитмов на обработку символьной информации. Важно подчеркнуть, что операция сложения не нашла своего воплощения в рамках продукционной парадигмы, поэтому представляемые в данной диссертационной работе алгоритмы, способы и технические решения удовлетворяют критериям новизны и существенных отличий.
Второй раздел диссертационной работы включает в себя разработку
логического и терминологического базиса исследования, модели данных в
рамках продукционной парадигмы, обоснования и доказательства ряда положе
ний. Осуществляется синтез продукционной алгоритмической схемы, выполня
ется исследование ее основных свойств (корректность и завершаемость). На
основе проведенных теоретических исследований сформулированы перспек
тивные пути совершенствования и развития символьных вычислений при реа-
"Т лизации операции сложения в знакоразрядной системе счисления.
Третий раздел диссертационной работы посвящен разработке алгоритмов, реализующих продукционный алгоритм символьного параллельного сло-жения чисел, которая была разработана во втором разделе, а также экспериментальной проверке разработанного способа на персональном компьютере для различных вариантов размерности массива слагаемых (4x4, 8x8, 16x16, 32x32). Проведены исследования вычислительной сложности продукционной схемы и схемы сложения на основе параллельных подстановок.
Четвертый раздел диссертационной работы включает в себя этапы раз-
~ работки аппаратных средств продукционного сложения массивов знакоразряд-
ных чисел и приводятся результаты исследования скоростных характеристик и аппаратных затрат в сопоставительном аспекте. Кроме того, в данном разделе приводятся особенности структурно-функциональной организации устройства сложения массивов знакоразрядных чисел. Технические решения, разработанные в данной диссертационной работе, имеют явные признаки новизны и существенных отличий, что позволяет заключить о становлении нового направления в рассматриваемой специальной области знаний: нечисловых средств компьютерной арифметики. В конце раздела приводятся и анализируются временные и аппаратные затраты технических решений специализированных устройств.
Разработанный продукционный сумматор превосходит по скорости в 2^5 раз известный сумматор.
Заключение содержит в себе основные результаты диссертационной ра-боты и выводы.
В приложениях приводятся листинги программ, моделирующих алгоритмы и устройства продукционного сложения и некоторые технические решения.
1'
Аппаратная поддержка методов сложения в цифровых сигнальных процессорах
Производительность сигнальных процессоров DSP зависит от многих факторов. При решении задач, требующих интенсивного обмена с внешними устройствами (разного рода анализаторы, контроллеры, многопроцессорные системы), предпочтение отдается процессорам фирмы ТІ (Texas Instrument), которые оснащены высокопроизводительными интерфейсными подсистемами. Лидирующее положение в производстве сигнальных микропроцессоров также занимает компания Motorola. В большинстве своем она производит сравнительно недорогие и достаточно высокопроизводительные для большинства приложений микропроцессоры 16-ти и 24-х битовой разрядности с фиксированной точкой [5].
Необходимость обработки сигналов в режиме реального времени инициировали фирмы Analog Devices и Texas Instrument на выпуск транспьютерных семейств микропроцессоров ADSP2106x и TMS320C4x, которые ориентированы на мультипроцессорный режим [76]. Следует отметить российскую разработку фирмы Модуль - «Neuro Matrix», работающую в формате операндов с фиксированной точкой. Данная разработка занимает достойное место среди сигнальных процессоров. Имея тактовую частоту 59 МГц, «Neuro Matrix» не только не уступает ведущим мировым разработкам, но в отдельных задачах превосходит их по ряду параметров.
Характерной особенностью сигнальных процессоров является наличие аппаратного сумматора и умножителя, позволяющих производить обслуживание двух операндов за один такт [15].
Техническая реализация однотактного сложения и команд, которые используют в качестве операндов содержимое ячеек памяти, позволяет использовать сравнительно низкие тактовые частоты работы сигнальных процессоров. Между тем их специализация не дает возможности увеличивать производительность за счет быстрого выполнения коротких команд, как это происходит в универсальных процессорах. Это объясняется тем, что таких команд нет в программах цифровой обработки сигналов.
Основную массу сигнальных процессоров, созданных различными компаниями-производителями, можно разбить на два класса, которые значительно различаются в цене: сравнительно дешевые микропроцессоры для обработки данных в формате с фиксированной точкой и значительно более дорогие микропроцессоры, выполняющие операции над данными с плавающей точкой.
Типовые DSP операции требуют выполнения значительного количества простых сложений и умножений, которые в свою очередь требуют: выборки двух операндов, выполнения арифметической операции (сложения или умножения или обоих действий сразу), сохранения результата операции и хранения его до повторения [77].
Компания Analog Devices производит исследование и разработки как в области совершенствования характеристик существующих устройств, так и в области возрастания производительности за счет создания принципиально новых архитектур. Первый путь имеет ограниченные пределы акселерации производительности не более 6-8 раз. Второй путь основан на совершенствовании архитектурных особенностей, приспособленных и оптимизированных для конкретного языка программирования. За основу нового ряда устройств был принят микропроцессор ADSP-21020 с производительностью 30MFLOPS. Дальнейшее совершенствование этой концепции привело к появлению процессора ADSP-21065L с максимально возможной производительностью 192-198 MFLOPS. Одной из последних разработок данного ряда является новый сигнальный микропроцессор ADSP-2116X, имеющий тактовую частоту 100 МГц и производительность в 400 MFLOPS [5].
Учет специфичности алгоритмов производится за счет применения логических программируемых интегральных микросхем, которые удешевляют устройства в малых партиях, повышают их производительность и дают простор в реконфигурации, используемых схем в случае изменения интенсивности процессов обработки, математического обеспечения без замены самих схем.
С появлением на рынке элементной базы программируемых логических интегральных схем, имеющих высокое быстродействие и высокую степень интеграции (ПЛИС), открылась возможность выполнения арифметических операций в виде микромодулей для ПЛИС Altera, Xilinx, AMD [12]. ПЛИС Xilinx ХС 4000 Е можно создавать вычислители с быстродействием более 200 ІУЕГц и располагать более 100 модулей операционных схем в одном кристалле [78].
В серии ПЛИС ХС 4000 Е архитектура позволяет операцию мультиплексирование с последующим суммированием объединить в одном конфигурируемом логическим блоке (КЛБ), в котором используется по одному функциональному генератору для каждой операции. Довольно близкое расположение данных элементов функциональной схемы позволяет выиграть в сокращении длины межсоединений, что увеличивает ее быстродействие. Применение логики ускоренного переноса также позволяет увеличить производительность схем [79].
Немаловажный вклад в увеличение быстродействие вносит регулярность и однотипность структуры схем. Это позволяет перейти на конвейеризацию каждой ступени. При этом следует отметить, что конвейерными регистрами помимо сумматоров разделяются и мультиплексоры. Такой принцип ускоряет быстродействие при большой разрядности операндов. Матричный конвейер обеспечивает на каждой стадии суммирования мак симальное быстродействие, т.к. одноразрядные сумматоры каждой ступени напрямую связаны с триггерами регистров конвейера. Между тем следует отметить, что рост производительности вынуждает задействовать все более возрастающие объемы логики ПЛИС, что особенно выражено для больших разрядностей [17], [18].
Рассмотренный инженерный подход позволит получить довольно высокую производительность полученной структуры при компактной топологии размещении модуля на кристалле. Применение различных типов логики практически не влияют на быстродействие и топологию макроса модуля [80], [81].
В последних разработках применяется широкий класс специализированных устройств, в которых совмещены операции группового суммирования, умножение и деление, дающие возможность производить самовосстановление в случае отказа частей вычислительных схем, но с потерей производительности. Такие модификации позволяют работать с операндами, представленными как в прямых, так и в обратных или дополнительных кодах, в режиме реального времени с минимальными задержками прохождения сигналов и т.п. [2], [4], [12], [16], [17].
Разработка специализированной продукционной системы для сложения чисел в знакоразрядной системе счисления
Любые тексты в информатике принадлежат к так называемым знаковым системам. Семиотика исследует их свойства и закономерности. К текстам относят любую символьную информацию, в том числе математические выражения, формулы и т.п. Фундаментом любой знаковой системы является алфавит, который можно представить в виде конечного набора ЗНАКОВ (букв) [1]. Заранее предполагается, что существует механизм, определяющий графическое равенство и различие букв в алфавите. Конечные упорядоченные последовательности букв в фиксированном алфавите называются словами [1]. Слова, содержащие хотя бы одну букву некоторого фиксированного алфавита А являются непустыми, иначе — слова будут пустыми. Слова задаются следующим рекурсивным определением: 1) Пустое слово Л считается словом в алфавите А; 2) Присоединение любой буквы из А к любому слову справа порождает слово.
Правилами 1 и 2 задается конструктивный процесс формирования слов. Изложенные правила применяются конечное число раз. Поэтому в последствии будем рассматривать только слова, которые имеют конечную длину. Под длиной слова будет понимать число букв, которое содержится в этом слове. Слова являются конструктивными объектами общего вида.
Определим правило сопоставления двух или более слов в А с целью установления их графического равенства (неравенства) двух или более слов, а также правило вхождения одного слова в другое. Существует понятие графического равенства двух слов. Графическое равенство двух слов определено тогда и только тогда, когда они построены из одинаковых букв, которые расположены в одинаковом порядке. Из условия графического равенства следует условие графической транзитивности, утверждающее, что если каждое из двух слов равные третьему слову, то два исходных слова графически равны между собой.
Сопоставим два слова О и Р для распознавания вхождения одного из этих слов в другое. Полагают, что слово О входит в слово Р тогда и только тогда, когда слово Р можно представить в виде: где Qj ,Q2 - некоторые произвольные слова в алфавите А, называются левым и правым крылом вхождения соответственно, а «=» - символ графического равенства слов.
Составляющие язык слова удовлетворяют ряду заранее заданных свойств, отличающих их от других слов, заданных в этом же алфавите, и удовлетворяющих определенным требованиям. Такие слова называются ФОРМУЛАМИ. Инструмент генерации и распознавание формул носит названия СИНТАКСИСА языка. Синтаксис языка будем задавать посредством ПРОДУКЦИЙ (слов) вида где О и М - произвольные непустые и графически неравные слова в алфавите А; причем символ «—»» не принадлежит А; О является образцом, а М - модификатором. После однократной модификации обрабатываемое слово (2.3) будет иметь вид:
Работа продукции (2.2) над словом Р в алфавите А определяется сопоставлением слов О и Р для того, чтобы обнаружить вхождения О в Р. Если такое вхождение существует при чтении слова слева направо, то тот фрагмент слова, который совпадает (графически равен) С и расположен первым слева в слове Q, должен быть заменен словом М (выполняется подстановка). Иначе исходное слово Р не изменяется. После срабатывания продукции (замены фрагмента), чтение слова, исследуемого данной продукцией, выполняет с его начала.
На практике часто требуется удаление (аннуляция) букв, слов или каких-либо фрагментов текста. В этом случае осуществляется их замена на пустое слово Л.
Средства синтаксиса задаются конечным списком формул (2.4), которые обрабатывают слово Р по следующему правилу: 1) в начале работы выполняется первая, стоящая в списке продукция, которая выполняет все возможные подстановки, затем выполняется переход на вторую продукцию данного списка и процесс повторяется для второй продукции и т.п.; 2) после переработки слова последней продукцией в списке в процесс включается вновь первая продукция и функционирование системы продукций будет продолжаться до тех пор, пока выполняется хотя бы одна продукция. Из практики известно, что продукции, входящие в синтаксис, можно классифицировать по содержанию левых частей: - левые части состоят из стандартных формул данного языка; - левые части состоят из формул, образованных на базе известных формул. Итак, синтаксис порождает класс формул языка, но их понимание (толкование) не определено. Непосредственно понимание формул (СЕМАНТИКА) не имеет строгих определений и задается списком соглашений. Итак, язык целиком и полностью определяется алфавитом, синтаксисом и семантикой.
Алгоритм параллельных подставок, используемых при суммировании массива
В работе [2] был предложен способ суммирования с помощью параллельных подстановок. Фактически каждые параллельная подстановка является символьной продукцией в алфавите {0, 1}. а) Алгоритм Фц (продукция Пц) Алгоритм Фц реализует продукцию Пц 1. Начало алгоритма. Перейти к шагу 2. 2. Загрузить массив операндов ф(1, J), перейти к шагу 3. 3. Присвоить переменной J значение 0. Перейти к пункту 4. 4. Присвоить переменной I значение 1. Перейти к шагу 5. 5. Выполнить проверку истинности конструктивного высказывания ((Ф(1, J) = 0)) & (Ф(1, J +1) = 0) & (Ф(1, J + 2)) = ) & (Ф(1 +1, J) = 0) & & (ф(1 +1, J +1) = 1)) = 1 и перейти к шагу 6, иначе - к шагу 7. 6. Выполнить присвоения ф(1, J) := 1, ф(1, J + 2) := , ф(1 + 1, J + 1) := О, ф(1 + 1, J + 2) := 0 Перейти к шагу 7. 7. Увеличить номер столбца на единицу 1: = 1 + 1. Перейти к шагу 8. 8. Выполнить проверку истинности конструктивного высказывания 1 2М-1. Если неравенство является верным, то перейти к шагу 4, иначе - к шагу 9. 9. Увеличить номер строки на единицу J := J +1. Перейти к шагу 10. Ю.Выполнить проверку истинности конструктивного высказывания J М -1. Если неравенство является истинным, то перейти к шагу 4, иначе - к шагу 11. 11.Вывод массива ф(1,т) на печать. Перейти к шагу 12. 12.Конец алгоритма. Шаги 1 -4 позволяют произвести загрузку значений алфавитной переменной массива операндов-слагаемых разрядности М х 2М, где М є N - множество натуральных чисел. Производится присвоение целочисленной переменной J значения 0, переменной I значения 1. Шаг 5 осуществляет проверку вхождений соответственно 0 и 1 в ячейки М-й строки с координатами (I,J), (1 + 1,J), (I,J+ 2), (I + 1,J), (I + 1,J + 1), (I +1, J + 2). Если конъюнкция ((ф(І, J) = 0) & (ф(І, J +1) = 0) & & (ф(І, J + 2) = ) & (ф(І +1, J) = 0) & (ф(І +1, J + 1) = 1) & (ф(І +1, J + 2) = 1)) = 1 выполняется, то осуществляется условный переход к шагу 6, если нет - к шагу 7. ячейках (I, J +1), (I, J + 2), (I +1, J +1), (I +1, J + 2) соответственно. Шаги 1—4 позволяют произвести загрузку значений алфавитной переменной массива операндов разрядности М х 2М, где М є N - множество натуральных чисел.
Производится присвоение целочисленной переменной J значения 0, переменной I- значения 1. Шаг 5 осуществляет проверку вхождений соответственно 0 и 1 в ячейки с координатами (I, J), (I, J +1), (I, J + 2). (I +1, J +1), (I +1, J + 2). Если конъюнкция ((ф(І, J) = 0) & (ф(І, J +1) = 1) & (ф(І, J + 2) = 0)) = 1 выполняется, то осуществляется условный переход к шагу 6, если нет - к шагу 7. Шаг 6 осуществляет выполнение продукции П.2 : 1 - 0 в ячейках (I, J +1), (I, J + 2) соответственно. и выполнение про Для реализации способа продукционного сложения числовых массивов были разработаны программы на языке VISUAL BASIC. Было проведено моделирование поведения алгоритмов с использованием генератора случайных чисел, дающего выборочный набор входных данных-слагаемых на разрядностях массивов операндов МхМ при М = 2, 4,8,16,32. Моделирование проводи лось в операционных средах Windows-2000AS, Windows -95, 98 на процессо рах Intel Pentium IV -1800, Intel Pentium HI -700. Весь массив входных данных подвергался арифметическому контролю в виде контрольных сумм промежуточных значений массива. Оценивая скорость работы продукционных алгоритмов на универсальных символьных процессорах, можно отметить, что способ, отраженный в алгоритмической схемы на основе продукций П -=-П имеет ряд преимуществ перед схемой параллельных подстановок П -4- П : - алгоритмы продукция П П имеют более широкий спектр примене ния при поиске нужных вхождений в массиве операндов-слагаемых по сравне нию с алгоритмами продукций П -т-П ; - алгоритмы продукций П -f-П в отличие от продукций П -т-П не требуют перехода в дополнительный или обратный коды при выполнении вычитания операндов; - алгоритмы продукций П - -П имеют свойство работать как в базисе \ {-1,0,1}, так и в базисах {-1,1}, {-1,0}, {0,1}, в отличие от продукций П -т которые работают на массивах чисел, заданных в канонической двоичной позиционной системе счисления в алфавите {0,1}; - алгоритмы продукций П -s-П не требуют наличия нулевых разрядов в нижней строке записи продукций в отличие от продукций П -т-П .
Базовая ячейка сумматора. Триггер с тремя устойчивыми состояниями
Блок-схема устройства показана на рисунке 4.8. Данные поступают из ОЗУ (либо промежуточного устройства, организо ванного по принципу стека) и заносятся в ячейки сумматора по строкам через коммутатор. Коммутатор осуществляет запись данных в те строки сумматора, которые содержат нули, т.е. четные. Последовательность записи по строкам определяется схемой приоритетов. Регистр выборки представляет собой сдвиговый регистр, который осуще ствляет стробирование пары смежных столбцов сумматора, активизируя таким образом декодер и цепи переноса. По каждому синхроимпульсу происходит сдвиг на один разряд вправо, и стробируется следующая пара столбцов. Регистр нуля хранит информацию о строках с нулевым содержимым. Информация в него поступает от цепочки индикатора нуля четной строки. Схема приоритетов управляет коммутатором, получая информацию о строках с нулевым содержимым от регистра нуля. Схема управления сдвигом включается в работу по сигналу конца потока данных, получаемому извне. После прихода этого сигнала в нечетных строках сумматора находятся промежуточные суммы, а четные строки хранят нули. Работа сумматора организована по конвейерному принципу, то есть в ос вобождающиеся строки постоянно подгружаются новые слагаемые до тех пор, пока не будет получен сигнал окончания входного потока данных.
В сумматоре реализован такой набор подстановок, который при каждом горизонтальном просмотре обеспечивает полное обнуление строк, используемых для второго слагаемого пары. Строки сумматора группируются попарно (1 и 2, 3 и 4 и т.д.), - всего 16 пар. Сложение происходит в каждой паре одновременно, начиная со старших разрядов (слева-направо), что позволяет уменьшить количество возникающих переносов. По окончании горизонтального просмотра в нечетных строках находятся промежуточные суммы, а четные строки содержат нули, и в них можно загружать следующие числа. Завершение операции сложения происходит следующим образом: - каждая вторая ненулевая строка сдвигается вверх на одну позицию (3-я во 2-ю, 7-я в 6-ю,..., 31-я в 30-ю); - происходит сложение по основному алгоритму, после которого остается восемь ненулевых строк; - каждая вторая ненулевая строка сдвигается вверх на три позиции (5-я во 2-ю, 13-я в 10-ю, 21-я в 18-ю, 29-я в 26-ю); - обычное сложение и остается четыре ненулевых строки; - сдвиг 9-й строки во 2-ю и 25-й строки в 18-ю; - сложение, после которого остается две строки: 1-я и 17-я; - сдвиг 17-й строки во 2-ю; - сложение. В итоге результат размещается в 1-й строке сумматора, остальные строки содержат нули. Во время вертикальных сдвигов регистр выборки блокируется схемой управления сдвигом. Синхронизация работы осуществляется тактовым генератором OSC. Сумматор представляет собой матрицу 32x32 разряда. Каждый разряд реализован на 3-стабильном элементе (триггере на 3 состояния). На рисунке 4.9 показан фрагмент функциональной схемы сумматора. Триггеры У1-УЗ - ячейки нечетной строки, У4-У6 - ячейки четной строки. Элементы У7,У9,У11 осуществляют формирование и распространение переноса по -1 согласно выражению [4.7], элементы У8,У10,У12 - делают то же самое по 1 в соответствии с выражением [4.6]. Элементы У22,У24,У26 реализуют функцию F2 (выражение [4.2]), а У23,У25,У27-функцию F5 (выражение [4.5]). Схемы совпадения У28-У31 обнуляют ячейки сумматора при активизации функций F1-F4, что соответствует микрооперации М(Аі)2:=0). Рассмотрим более подробно выражение [4.14] для ячейки на триггере У2. Сомножитель (A.vB.) реализован на нижнем (по схеме) элементе сборки У9, сомножитель (А2 vB2) - на нижнем (по схеме) элементе сборки У10, произведение (A, vB,)&(A2 vB.) -на сборке У24. Все эти сомножители объединяются на схеме совпадения У29 и произведение подается на один из элементов сборки У17. Произведение (A- vP_)&(A. vP ) реализовано на двух других элементах У17. На выходе У17 формируется сигнал, соответствующий выражению [4.14]. Теперь рассмотрим микрооперацию М(В2:=0) для ячейки на триггере У5.
Первые четыре сомножителя аналогичны сомножителям из выражения [4.14]. Поэтому произведение берется с выхода схемы совпадения У29. Сомножитель [А2 v(B2 &В2)] формируется на сборке У25 и логически умножается на сигнал с выхода У29 на схеме У36. Таким образом, на выходе схемы совпадения У36 формируется сигнал в соответствии с выражением (4.15). Микрооперации M(Ai:= 1) и М(А]:= 1) задаются выражениями (4.16) и (4.17): Сигналы (А2 VB2)H (A- vB.) формируются на сборках У11, У12 и поступают на входные сборки элементов У16 и У18. На другие входы этих же сборок поступает сигнал Aj с выхода триггера У2. На выходе У16 получается сигнал, соответствующий выражению (4.16), на выходе У18 - сигнал, соответствующий (4.17). Последние две микрооперации М(А2:= 1) и М(А2:= -1) задаются выражениями (4.18) и (4.19)
