Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

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

Сложность реализации вычислительных устройств определяется затратами оборудования, которые для матричных структур растут в квадратичной зависимости с увеличением разрядности чисел. В этих условиях целесообразно применять сокращенные методы выполнения операций. Они позволяют вдвое снизить затраты оборудования и времени на выполнение операции. В сравнении с полноразрядным вычислительным устройством затраты оборудования снижаются приблизительно в n²/(n²-k²/2) раз, а время вычислений в 2n/(2n-k) раз, что с ростом n приближается к двум.

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

Метод сокращенного умножения основан на анализе матрицы конъюнкций произведения (МКП). Контрольное соотношение для проверки округленного результата умножения составляется на основе разбиения старшей части МКП на фрагменты. Минимальное количество фрагментов разбиения МКП и слагаемых в контрольном соотношении составляет n_k=k+1. Этот минимум достигается только в том случае, если все фрагменты являются индексируемыми, т.е. фрагменту в качестве индекса ставится в соответствие номер строки МКП, содержащей в составе фрагмента только один граничный элемент. Указанный граничный элемент является индексным и используется для обозначения фрагмента в разбиении МКП. Разбиение МКП, составленное из индексируемых фрагментов, называется нормальным.



1. Выбор варианта задания

Разбиения характеризуются наличием центрально-симметричного фрагмента (фрагмент 14 рис. 1) и фрагментов, которые изменяют размер одной из образующих с постоянным шагом (нижние 2, 4, 6, 8, 10, 12 и верхние 16, 18, 20, 22, 24, 26 рис. 1 изменяют размер образующих на шаг 2 по сомножителем В и А соответственно).

Вид разбиения на рис. 1 определен для номера варианта Z = 13. По номеру Z определяются так же два параметра:

операнд алгоритм блок контроль

Y = Z mod 4 = 13 mod 4 = 1;

X = Z mod 9 = 13 mod 9 = 4.

По параметру X определяется шаг изменения размеров образующих фрагмента: для значения 4 шаг составляет 2 для верхнего и нижнего фрагмента соответственно.

Параметр Y определяет сомножители, по которым образующие верхних и нижних фрагментов меняют свой размер (табл. 1). В данном случае для верхнего фрагмента сомножитель А, а для нижнего фрагмента сомножитель В.

Таблица 1. Выбор варианта задания

Верхние	А	В	В	А
Нижние	А	А	В	В

Разбиение на рис. 1 получено для Z = 13, что определяет X = 4, частные и остаток равные, равные 1, шаг 2, а также Y = 1.



Рис. 1 Разбиение МКП



2. Анализ задачи

2.1 Описание фрагментов разбиения

Минимальное количество фрагментов разбиения МКП и слагаемых в контрольном соотношении равно (к+1) и достигается, если все фрагменты являются индексируемыми, т.е. фрагменту в качестве индекса ставится в соответствие номер строки МКП, содержащей в составе фрагмента только один граничный элемент. Указанный граничный элемент является индексным и используется для обозначения фрагмента в разбиении МКП.

Фрагмент Vi - часть МКП, определяемая произведением

Индексация фрагментов МКП представлена на Рис. 1.

Фрагменты разбиения:



2.2 Описание контрольных кодов фрагментов разбиения

Контрольные коды КАi, КВi частей Аi, Вi разделяются на составляемые и вычисляемые. Составляемые контрольные коды определяются по частям Аi, Вi операндов А и В, если длина этих частей не превышает 2 (для модуля 3). Вычисляемые контрольные коды формируются при большей длине частей операндов.

Составляемые контрольные коды для КА_i:

Составляемые контрольные коды для КB_i:



Вычисляемые контрольные коды для КА_i и КВ_i:



3. Разработка схемы устройства контроля

Рассмотрим для наглядного представления разрабатываемых блоков схему устройства контроля (УК). Структура устройства контроля представлена на Рис. 2.

Рис. 2 Устройство контроля

В состав устройства контроля входят:

· Блоки БКа и БКв контроля сомножителей А и В, которые сравнивают их по модулю с входными контрольными кодаи КА и КВ. Результаты сравнения являются кодами контроля операндов ККа, ККв. В процессе проверки также формируются контрольные коды Аi, Вi.

· Контрольный блок КБ, содержащий:

А) Узел УМ умножения контрольных кодов КАi, КВi (выч. контрольные коды фрагментов KVi).

Б) Формирователь ФК контрольного кода KVу {n+12n-k} отбрасываемых разрядов Vу {n+12n-k} усеченного произведения Vу.

В) Формирователь ФКv контрольного кода KVу округленного произведения Vo (складывает контрольные кодыфрагментов KVi).

Г) Узел Уввычитания кода KVу {n+12n-k} из кода KVу (вычисляет контрольный код KVo усеченного произведения Vу).

Д) Блок БКv контроля округленного произведения Vo (сравнивает его по модулю с контрольным кодом KVo и вычисляет код контроля ККv).

3.1 Блоки контроля операндов

Для рассматриваемого разбиения МКП блок контроля БК_А показан в дополнение А.

На сумматорах по модулю три 0 - 15 выполняется свертка операнда А с формированием вычисляемых контрольных кодов КАi. Последний вычисляемый контрольный код КА₁₃ является результатом свертки. Он сравнивается на сумматора по модулю три 15 с входным контрольным кодом КА операнда А. Для этого входной контрольный код подключен инверсно: первый разряд - к входу с весом 2, а второй разряд - к входу с весом 1. На первом прямом и инверсном втором выходах сумматора по модулю три 15 формируется код контроля КК_А операнда А.

В силу симметричности разбиения МКП на фрагменты (разбиение не изменяется при перемене мест сомножителей) блок контроля БК_В имеет схему, аналогичную блоку БК_А.

3.2 Контрольный блок и блок контроля БКv

Контрольный блок выполняется на конъюнкторах, умножителях по модулю три, полных сумматорах и сумматорах по модулю три.

На выходы контрольного блок БК поступают разряды контрольных блоков КА_i, и КВ_i частей множимого и множителя.

На узле умножения УУ формируются контрольные коды фрагментов. Формирователь ФК_V складывает контрольные коды фрагментов по мерех их получения, причем коды, вычисляемые на конъюнкторах имеют одинаковый вес и складываются сначала на полных сумматорах, а затем, как и другие коды - на сумматорах по модулю три с учетом знаков фрагментов. Знак «минус» фрагмента учитывается инверсным подключением его контрольного кода в схеме сложения: первый разряд кода соединяется с вторым разрядом сумматора по модулю три, а второй разряд кода - к первому рарзряду.

Узлы ФК и УВ вычисляют и учитывают в контрольном коде округленного результата отбрасываемые разряды усеченного произведения.

Блок БК_V контроля результата показан на рис. 3

Рис. 3 Блок контроля результата

Блок БК_V содержит узел 1, выполняющий свертку округленного результата V0, и сумматор по модулю три 2, который сравнивает результат свертки с контрольным кодом КV0 округленного результат, вычисленным по контрольным кодам фрагментов.



4. Описание блоков устройства контроля

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

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

Входы устройства контроля нумеруються числами натурального ряда:

· входы разрядов операнда - числами ;

· входы разрядов контрольного кода - числами

· входы разрядов перанда - числами

· входы разрядов контрольного кода - числами

· входы разрядов результата - числами

· входы отбрасываемых разрядов усеченного произведения - числами

С номера начинается нумерация выходов элементов.

Схема блока контроля БКА выполнена с использованием одного типа элементов (сумматоров по модулю три для сложения двухразрядных контрольных кодов) и поэтому описывается одной таблицей. Перед заполнением таблицы определяются номеравходов устройства контроля и параметр С.

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

· входы разрядов операнда - числами ;

· входы разрядов контрольного кода - числами

· входы разрядов перанда - числами

· входы разрядов контрольного кода - числами

· входы разрядов результата - числами

· входы отбрасываемых разрядов усеченного произведения - числами

Нумерация выходов элементов начинается с номера С = 106.



5. Алгоритм получения описаний

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

Таблицы представляются двухмерными массивами данных.

В рассматриваемой схеме (табл. 2) ключевыми данными являются первый d2, шестой d1 и девятый d7 элементы четвертой строки. От элемента d2 (число 18) прослеживается закономерность изменения предыдущих его трех элементов по столбцу. По которым далее могут быть определены элементы 0 - 4 первой и второй строки. С шестым элементом четвертой строки (число 6) связаны предшествующие ему 3 элемента по столбцу, по которым далее могут быть определены элементы 0 и 1 шестого столбца. Девятый элемент четвертой строки (число 32) очевидно свзяан с предшествующими ему 3 элементами по столбцу, зная эти три элемента можно заполнить строки 0 и 1 для столбцов 8 и 13 включительно. Так же стоит выделить четвертый элемент нулевого столбца d4, так как по нему прослеживается закономерность изменения 4 и 5 строк всей таблицы.

В организации таблицы можно выделить столбцы для описания свертки k-1 младшых разрядов и n-k+1 старших разрядов операнда (соответственно столбцы 0 - 4, 8 - 13 и столбцы 5,6). Описание свертки младших k разрядов в свою очередь делиться на описание свертки разрядов семмитричного фрагмента и описание свертки разрядов нижнего треугольника (соответственно столбцы 8 - 13 и 0 - 4). А также столбцы 7, 14 для обьединения этих сверток и столбец 15 для описания сравнения результата свертки операнда с его входным контрольным кодом.

К ключевым данням, отражающим организацию таблицы, достаточно отнести увеличенное на единицу количество столбцов d5 описывающие свертку нижнего треугольника, общее количество столбцов d3, количество столбцов d6 описывающих свертку по модулю старших n-k+1 разрядов операнда.

Ключевые данное d1, d2 являются функцией от параметров n и k. Для рассматриваемого вида разбиения d1 = n - k +1; d2 = n - (k+1)/2.

Третье ключевое данное определяется из условия сжатия до двух разрядов операнда всех разрядов операнда, дополненных разрядами контрольного кода. Каждый столбец описывает сжатие информации на два разряда на одном сумматоре по модулю три. Поэтому количество столбцов определяется количеством сжатой информации, делением на два: d3 = n/2.

Четвертое d4 ключевое данное совпадает с параметром С: d4 = C.

Пятое d5, шестое d6 и седьмое d7 ключевые данные зависят от предыдущих ключевых данных, а так же от n и введены для наглядности алгоритма:

d5 = (d2 - d1 - 1)/2 - количество элементов сложения по модулю 3, требуемых для свертки нижнего треугольника.

d6 = (d1 - 2)/2 - количество элементов сложения по модулю 3, требуемых дя свертки n-k+1 старших разрядов операнда.

d7 = n - номер старшого разряда операнда.

5.1 Определение закономерностей

В первом столбце распологаются числа d2, d2 - 1, d2 - 2, d2 - 3, которые являются номерами разрядов операнда А, подключенных ко входам сумматора 1 по модулю три, и числа d4, d4 + 1, нумерующие выходы этого сумматора.

В пятой и шестой строках числа расположены в порядке их увеличения с шагом 2, начиная с числа d4 и d4 + 1 соответственно. (Седьмая закономерность).

В нулевой и перовой строках в пределах столбцов 0 - (d5-1), (d5+d6+1) - (d3-2) расположены числа в порядке их уменьшения с шагом два начиная со столбца 0 и столбца (d5+d6+1) соответственно (Первая и пятая закономерность). В указанных столбцах описывается свертка нижнего треугольника и ассиметричного фрагмента.

Третье и четвертое числа столбцов 1 - (d5-1), (d5+d6+2) - (n/2-1) повторяют пятое и шестое числа столбцов 0 - (d5-2), (d5+d6+1) - (n/2-2) (Вторая и шестая законоерность).

В столбце d5 располагаются числа d3-3, d3-2, d3-1. В этом, а так же следующем столбце вычисляется свертка по модулю три n-k+1 старшей части операнда А. В следующем столбце результат сложения столбца d5 складывается с оставшимися старшими битами 1 и 2 операнда А (Четвертая и третья закономерность).

В столбце (d5 + d6) складываются результаты свертки нижнего треугольника МКП и n-k+1 старшей части оперна А.

В столбце (d3 - 2) складываются результаты сложения столбца (d5 + d6) и результаты свертки по модулю три семмитричного фрагмента, который вычисляется в столбце (d3-3).

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

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

d[2] = 2*n + 2 - (k+1)/2;

d[4] = C + n;

d[7] = 2*n + 2.

5.2 Описание алгоритма

Блок 1 выполняет ввод исходных данных: разрядности операндов n и парметра сокращения вычислений k.

Блок 2 определяет все необходимые ключевые данные.

Блоки 3 - 5 заполняют строки 4 и 5 для всех столбцов матрицы М.

Блоки 6 - 8 заполняют строки 2 и 3 для столбца 0.

Блок 9 записывает в строки 2 и 3 нулевого столбца числа d2-1 и d2.

Блоки 10 - 12 заполняют строки 0 и 1 для столбца d5 - (d5+d6-1) числами в порядки их убывания с шагом два.

Блок 13 заполняет строки 2 и 3 для столбца d5 числами d1 -1 и d1 соответсвтенно.

Блок 14 копирует в строки 0 - 1 столбца (d5+d6) числа из 4 и 5 строки столбца (d[5] - 1).

Блоки 15 - 17 циклически заполняют строки 0 и 1 столбцов (d5+d6+1) - (d3-2).

Блок 18 записывает в строки 2 и 3 числа d7 и (d7-1).

Блок 19 копирует в строки 0 и 1 (d3-1) столбца данные из строк 4 и 5 столбца (d5 + d6).

Блоки 21, 24, 27 практически одинаковы. Они занимаются копированием строк 4 и 5 текущего столбца в строки 2 и 3 следующего столбца. Текущий и следующий столбец определяются парметрами циклов, которые находятся в блоках 20, 23 и 26.



Заключение

В проекте спроектированы блоки устройства контроля по модулю три матричного умножителя с сокращением вычислений для обработки мантисс чисел с плавающей точкой. Контроль выполняется так: Операнды А, В и их контрольные коды Ка, Кв поступают на соответствующие блоки контроля БКа, БКв. Эти блоки проверяют операнды и их контрольные коды на сравнимость по модулю и вычисляют коды контроля операндов ККа, ККв. В процессе проверки также формируются контрольные коды КАi, КВi частей Аi, Вi операндов.

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

Размещено на Allbest.ru

...