Выполнение арифметико-логических операций на однородной вычислительной среде

СОДЕРЖАНИЕ

Введение

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

1.1 Вычисление числа К

1.2 Определение параметров задания

1.3 Постановка задачи на выполнение курсовой работы

1.3 Этапы вычислительного процесса

2.1 Структура вычислительного процесса

2.2 Блок-схемы алгоритмов

3. Схемы ОВС для разработанных алгоритмов

3.1 ОВС для числа А*

3.2 ОВС для числа В*

3.3 ОВС для числа С

3.4 Временные диаграммы работы ОЭ ОВС и их описание

4. Полная схема ОВС, коды команд ОЭ, схема цепей программирования

4.1 Коды команд операционных элементов

4.2 Схема цепей программирования

4.3 Программа на ОВС

Заключение

Перечень условных сокращений

Литература

ВВЕДЕНИЕ

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

Во времени вычислительный процесс можно представить в виде одинаковых временных интервалов, называемых тактами.

Каждый операционный элемент содержит синхровходы. Через синхровходы поступают тактовые импульсы.

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

Входы и выходы представляют собой:

- 00 - юг;

- 01 - запад;

- 10 - север;

- 11 - восток.

В промышленности выпускаются микросхемы ОВС содержащие матрицу 3х3 ОЭ из которых набираются ОВС необходимого размера.

ВЫБОР ВАРИАНТА ЗАДАНИЯ

1.1 Вычисление числа К

Для предупреждения повторов, определение варианта проводится по формуле, которая учитывает количество групп на потоке и количество человек в группе. Формула выглядит следующим образом:

(1)

где n - порядковый номер группы, m - номер студента в группе (по журналу);

1.2 Определение параметров задания

Теперь выберем задания по параметрам X, Y и Z, вычисленным по формулам:

(2)

(3)

(4)

По параметру Х выберем формулу вычисления результата С, реализуемую на ОВС. Для нашего варианта, формула выглядит:

(5)

По параметрам Y и Z определяются системы счисления для операндов А и В, используемых в формуле вычислений. Для нашего варианта параметр Y = 0, а параметр Z = 4, таким образом, по таблицам вычисляем, что система счисления для операнда A=A_2-5, а для операнда B=B_2-13.

Для нечётных К вычисления в формуле осуществляются в обратном коде. В нашем случае К = 123 и является не четным числом. Направления поступления операндов А и В, а также выдачи результата С определяются указанными выше двухразрядными кодами, составляющими вместе (справа налево) шестиразрядный код V, вычисляемый в двоичной системе счисления по формуле:

(6)

.

ОВС составляется из описанных выше микросхем. После задания команд для отдельных ОЭ определяются цепи программирования, исходя из требования ко времени программирования в тактах:

(7)

1.3 Постановка задачи на выполнение курсовой работы

Таким образом, ставится задача выполнения вычисления по формуле

, (5)

в которой числа А и В представляются в (2-5) и (2-13) системах счисления, т.е. A=A_2-5, B=B_2-13, обрабатываются в обратном коде и поступают с востока и севера соответственно, а результат С выдаётся на восток. Программирование ОВС необходимо выполнить за время, не превышающее 192 такта.

2 ЭТАПЫ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА

2.1 Структура вычислительного процесса

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

Структура вычислительного процесса:

Рис. 4

Индекс «2» означает перевод чисел в двоичную систему счисления (СС), индексы «об» и «пр» означают перевод чисел в обратный и прямой коды. Числа А* и

В* вычисляются параллельно, а результат С вычисляется последовательно с вычислением А* и В*.

2.2 Алгоритм вычисления А*

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

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

Алгоритм вычисления числа А*

Рис. 5

Число А_2-5 поступает с востока. Выделение старшей тетрады производится путём логического умножения А_2-5 на константу вида 11110000₂ или F0₁₆. Это наглядно иллюстрирует пример:

Младшая тетрада выделяется аналогичным способом:

Двоичное число находится по формуле: A₂=H_n*S+L, где S-система счисления двоично-кодированного числа, L-его младшая тетрада, а Hn -нормализированная старшая тетрада двоично-кодированного числа:

а8 а7 а6 а5 0 0 0 0=H

0 0 0 0 а8 а7 а6 а5=H_n

Для 123 варианта формула A₂=H_n*S+L выглядит следующим образом:

А₂=5*H_n+L. (10)

Процедура умножения старшей тетрады на пять может быть представленной в виде:

5Hn=Hn+4Hn.

Блок 6 выводит полученный результат, т.е. число А*.

2.3 Алгоритм вычисления числа В*

Операнд В обрабатывается аналогично операнду А. На рис. 6 показан алгоритм вычисления числа В*. При поступлении числа В_2-13 (блок 2) производится перевод его в двоичную систему счисления путем вычисления младшей и старшей тетрад числа В_2-13 логическим умножением на константы 0F₁₆=00001111₂ и F0₁₆=11110000₂ соответственно, а затем вычисления 13НВ+LВ=В', что выполняется на блоках 3-5.

На блоке 6 производится вычисление числа B''= B'*5. На блоке 7 производится деление

B'' на 4 путем логического умножения на константу FC₁₆=11111100₂ и умножения на 2^-2. На блоке 8 производится вычисление числа В*= ¬(В'''), а на блоке 9 число В* выводится.

Алгоритм вычисления числа В*

Рис. 6

2.4 Алгоритм вычисления числа C

На блоке 2 поступают обработанные числа А* и В*, блок 3 вычисляет число С`, которое образуется при сложении чисел А* и В*. Получение числа С` в обратном коде осуществляется путем его сложения с самим собой с задержкой ровно в 8 тактов, это показано на блоке 4. Блок 5 переводит число С`` полученное в блоке 4 из обратного кода в прямой путем сложения его со знаком, при этом задержка должна быть не менее 7 тактов. Блок 6 выводит полученный результат, т.е. число С. Подробно эти действия представляет алгоритм на рис. 7.

Алгоритм вычисления числа С

Рис. 7

3.Схемы ОВС для разработанных алгоритмов

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

3.1 ОВС для числа А*

Схема ОВС, показанная на рисунке 8, показывает обработку и получение числа А^*. Из рисунка видно, что А_2-5 поступает с востока на операционный элемент 4.6 на девятом такте. После того, как А_2-5 поступило, оно транзитом с задержкой на 1 такт поступает на ОЭ 4.5.

ОВС для числа А*

Рис. 8

Схема ОВС, показанная на рисунке 8, показывает обработку и получение числа А^*. Из рисунка видно, что А_2-5 поступает с востока на операционный элемент 4.6 на девятом такте.

После того, как А_2-5 поступило, оно транзитом с задержкой на 1 такт поступает на ОЭ 4.5. Одновременно с числом А_2-5 на этот же элемент поступает сгенерированная константа F0₁₆=11110000₂, после чего выделяется старшая тетрада Н_А числа А_2-5, путем обнуления младших разрядов.

После выделения старшей тетрады она сдвигается на четыре позиции вправо, для чего используется четыре такта задержки. На пятнадцатом такте из ОЭ 4.5 на запад поступает старшая тетрада.

После того, как число А_2-5 поступило на ОЭ 4.6, выделяется младшая тетрада обнулением старшей тетрады с помощью побитового умножения на сгенерированную константу 0F₁₆ = 00001111, которая подается на этот же ОЭ одновременно на 9 такте. Затем LA проходит транзитом через ОЭ 4.3, 4.2, 4.5 и на 17 такте попадает на ОЭ 4.2 , слаживается с 5H_A.

После выделения старшей тетрады, число H_A умножается на 5 путем сложения учетверенной тетрады с H_A на сумматоре ОЭ 4.4. Учетверение осуществляется задержкой на 1 такт во время транзита через ОЭ 4.4 и 4.6. 5H_A выдаются на север, проходят с задержкой такта через ОЭ 4.1 и выдаются на 17 такте на ОЭ 4.2, где складываются с LA. Таким образом получается число A*, равное операнду А в двоичной системе счисления. Число А* выходит на север на 19 такте из ОЭ 4.2.

3.2 ОВС для числа В*

Схема ОВС для алгоритма получения В^* показана на рисунке 9. Из рисунка видно, что В_2-13 поступает с севера на операционный элемент 1.2 на девятом такте. После того, как число В_2-13 поступило, оно транзитом с задержкой на 1 такт поступает на ОЭ 1.5. Одновременно с числом В_2-13 на этот же элемент поступает сгенерированная константа F0₁₆=11110000₂, после чего выделяется старшая тетрада Н_В числа В_2-13, путем обнуления младших разрядов. После выделения старшей тетрады она сдвигается на четыре позиции вправо, для чего используется четыре такта задержки. Затем Н_В попадает на ОЭ 1.8.

После того, как число В_2-13 поступило на ОЭ 1.2, выделяется младшая тетрада обнулением старшей тетрады с помощью побитового умножения на сгенерированную константу 0F₁₆ = 00001111, которая подается на этот же ОЭ одновременно на 9 такте. Затем Lв на 10 такте попадает на ОЭ 1.3 (DD), где задерживается на 9 тактов и выдаётся на юг. L_B попадает на сумматор ОЭ 1.6, где вскоре сложится с Н_В.

Нв логически умноженное с самим собой на ОЭ 1.8 выдается на восток, где проходит транзитом через ОЭ 1.9 и на 19 такте попадает на ОЭ 1.6, где слаживается с Lв, результат выдается на юг. Нв ОЭ 1.9 происходит логическое умножение (L+H) само с собой и результат выдается на ОЭ 3.3. Из ОЭ 1.8 На поступает с задержкой на 1 такт в виде 4Нв на ОЭ 3.2 на 14 такте, а также с задержкой на 2 такта в виде 4Нв на ОЭ 1.7, где задерживается на 1 такт и в виде 8Нв на 15 такте поступает на ОЭ 3.1, где суммируется

с 4Нв, поступившим с ОЭ 3.2 на 15 такте после логического умножения с самим собой. Где 12Нв выходят на юг, где на ОЭ 3.4 проходят логическое умножение с самим собой и транзитом через ОЭ 3.1 и 3.2 поступают на ОЭ 3.3, где суммируются с (L+H) и на 22 такте на юг выводится В'. В' проходит транзитом через ОЭ 3.6 и на ОЭ 3.5 слаживается

с 4В'. Результат поступает на ОЭ 3.8 на 24 такте, где складывается с Fс₁₆ = 11111100₂, которая поступает с запада с ОЭ 3.7. Результат выводится на ОЭ 3.9, где инвертируется. В* транзитом через ОЭ 3.6 и 3.3 выводится на 30 такте на восток с ОЭ 3.3.

ОВС для числа В*

Рис. 9

3.3 ОВС для числа С

Числа А* и В* поступают на ОЭ 4.1 на 30 такте, где складываются используя 1 такт задержки и получая число С` на 31 такте поступающее на ОЭ 2.4 транзитом через ОЭ 2.7. На элементе 2.4 происходит сложение числа С' с переносом, полученным после сложения А^* и В^*. Для этого число С' складывается с самим собой, задержанным ровно на 8 тактов. Получается число С'', выходящее на 44 такте на север.

ОВС для числа С

Рис. 10

Число С'' нужно перевести в прямой код и взять по модулю, поэтому его складывают с самим собой с задержкой не менее 7 тактов с помощью операции сумма по модулю два. В этом случае число задерживается на 10 тактов: транзитом ОЭ 2.2 на 1 такт и цифровой задержки ОЭ 2.3 на 9 тактов. Получаем число С на 56 такте которое выдается на север.

3.4 Временные диаграммы работы ОЭ ОВС и их описание

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

Рассмотрим временную диаграмму для А*, которая изображена на таблице 1, приведенной ниже. Заметно, что как и на схеме ОВС число А_2-5 поступает на 9 такте, после чего логически умножается на константу 00001111₂. Временные диаграммы делаются для входов в ОВС и для выхода каждого операционного элемента. Ниже в таблицах 2 и 3 будут приведены временные диаграммы для чисел В* и С. Временные диаграммы не представляют собой ничего сложного, поэтому не требуют подробного описания.

Таблица 1

Имена диаграм	№ОЭ	Задержка	Такты
			9	10	11	12	13	14	15	16	17	18	19	20
A2-5			A1	A2	A3	A4	A5	A6	A7	A8
A* 28	28	9т>
5HA 17	31т	1т>									5H	5H	5H	5H
A* 19	32	2т>											A*	A*
LA 15	32т	2т>							A1	A2	A3	A4	0	0
LA 13	33т	2т>					A1	A2	A3	A4	0	0	0	0
5HA 16	34	1т>								5H	5H	5H	5H	5H
2HA 15	34т	1т>				0	0	0	0	A5	A6	A7	A8	0
HA 15	35	1т>			0	0	0	0	A5	A6	A7	A8	0	0
LA 17	35т	2т>									A1	A2	A3	A4
LA 11	36	2т>			A1	A2	A3	A4	0	0	0	0
A2-5 10	36т	1т>		A1	A2	A3	A4	A5	A6	A7	A8
4HA 15	37т	1т>					0	0	0	0	A5	A6	A7	A8
F016 10	38		1	0	0	0	0	1	1	1	1	0	0	0
0F16 9	39		1	1	1	1	0	0	0	0	1	1	1	1

Временные диаграммы для А*

Таблица 2

Имена диаграмм	№ОЭ	Задержка	Такты
			9	10	11	12	13	14	15	16	17	18	19	20
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
B2-13			B1	B2	B3	B4	B5	B6	B7	B8
0F16 9	11		1	1	1	1	0	0	0	0	1	1	1	1
LB 10	12	1т>		B1	B2	B3	B4	0	0	0	0
B2-13 10	12т	1т>		B1	B2	B3	B4	B5	B6	B7	B8
LB 19	13	9т>											B1	B2
F016 10	14		1	0	0	0	0	1	1	1	1	0	0	0
HB 15	15	1т>			0	0	0	0	B5	B6	B7	B8	0	0
L+H 20	16	1т>												LH
8HB 15	17т	1т>						0	0	0	0	B5	B6	B7
HB 17	18	2т>					0	0	0	0	B5	B6	B7	B8
4HB 14	18т	1т>				0	0	0	0	B5	B6	B7	B8	0
4HB 15	18т2	2т>					0	0	0	0	B5	B6	B7	B8
L+H 21	19	1т>
HB 19	19т	2т>							0	0	0	0	B5	B6
12HB 16	31	1т>								12H	12H	12H	12H	12H

4.ПОЛНАЯ СХЕМА ОВС, КОДЫ КОМАНД ОЭ, СХЕМА ЦЕПЕЙ ПРОГРАММИРОВАНИЯ

Полная схема ОВС

Рис. 11

На (рис.11.) показана полная схема ОВС для всех трех алгоритмов, она представляет собой объединенные во едино три предыдущие схемы для чисел А*, В*, С, разбитые на четыре микросхемы. Это схема не требует подробного описания, поскольку каждая из ее составляющих была описана ранее.

4.1 Коды команд

В первом столбце таблицы 4 записываются номера ОЭ в схеме. В следующем - коды операций (КОП), выполняемых в ОЭ. Далее столбец У, где У - бит, который определяет задержку выдачи из ОЭ результатов - один или два такта соответственно, при У=0 и У=1. Коды управления А1-А2 задают направления первого и второго операндов поступающих на АЛУ, А3 - направление поступающего транзита, А4 - направление выдачи результата, А5 и А6 отвечают за направление выдачи транзитов с задержкой на 2 такта и на 1 такт. В последнем столбце коды команд ОЭ, представлены в 16-ричной СС.

4.2 Схема цепей программирования

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

На (рис.12.) показана схема цепей программирования для данной ОВС, она состоит из 4-ех микросхем, а также временем программирования 192 тактов и имеет 3 входа и 3 выхода программирования

Коды команд ОЭ ОВС

Таблица 4

ОЭ	КОП	У	А1	А2	А3	А4	А5	А6	Q16
11	1	1	0	0	0	0	1	0	0	0	0	1	1	1	1	1	C21F
12	0	0	0	0	1	0	0	1	1	0	1	1	0	1	0	0	09B4
13	1	1	0	1	0	1	0	0	0	0	0	0	0	0	0	0	D400
14	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	C3C3
15	0	0	0	0	1	0	0	1	0	0	0	0	0	1	1	0	0906
16	1	0	0	0	1	0	0	0	1	1	0	0	1	1	0	1	88CD
17	0	0	0	0	0	0	0	0	1	1	0	1	1	0	0	0	00D8
18	0	0	0	1	1	0	1	0	1	0	1	1	0	0	0	1	1AB1
19	0	0	0	0	1	0	1	0	0	1	0	0	1	0	0	1	0A49
21	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0007
22	0	1	1	0	0	1	1	1	0	1	1	0	0	0	1	1	6763
23	1	1	0	1	0	1	0	0	0	0	0	0	0	0	0	1	D401
24	1	0	0	0	1	1	0	1	0	0	1	0	1	1	0	1	8D2D
25	1	1	0	1	0	1	0	0	0	0	0	0	0	0	0	1	D401
26	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	0006
27	0	0	0	0	0	0	0	0	1	1	1	0	0	1	0	0	00E4
28	1	1	0	1	0	0	0	0	0	0	0	0	0	0	0	1	D001
29	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	0006
31	1	0	0	0	1	0	1	1	0	0	0	0	0	1	1	1	8B07
32	0	0	0	0	1	0	1	0	0	1	0	1	1	1	0	0	0A5D
33	1	0	0	0	1	0	0	1	0	0	0	0	0	1	1	1	8907
34	0	0	0	0	1	1	1	1	1	0	1	1	1	0	0	0	0FB8
35	1	0	0	0	0	1	1	1	1	1	0	0	1	0	0	1	87C9
36	0	0	0	0	0	0	0	0	1	0	1	0	0	0	0	1	00A1
37	1	1	0	0	0	0	0	0	1	1	1	1	1	1	1	1	C0FF
38	0	0	0	0	0	1	1	0	0	0	1	1	0	0	0	1	0631
39	0	0	1	0	0	1	0	1	0	0	1	0	0	0	0	1	2521
41	1	0	0	0	0	1	1	0	0	0	1	0	0	0	1	1	8623
42	1	0	0	1	0	0	0	1	1	1	1	0	0	0	0	1	91E1
43	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0	0006
44	1	0	0	0	0	0	1	1	1	1	1	0	0	1	0	0	83E4
45	0	0	0	0	0	0	1	1	1	0	0	1	1	0	0	0	0398
46	0	0	0	1	0	0	1	1	1	1	1	0	0	0	0	1	13E1
47	0	0	0	0	0	0	0	0	1	0	0	0	0	1	1	0	0086
48	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	0	C3C2
49	1	1	0	0	0	0	1	0	0	0	0	1	1	1	1	0	C21E

Схема цепей программирования ОВС

Вход 1

Вход 2

Вход 3

Рис. 12

4.3 Программа на ОВС

Пpограмма для ОВС (Таблица 5.) представляется двухмерным массивом бит с количеством строк равным количеству входов программирования. В каждой строке записываются коды команд ОЭ в порядке их очередности в цепи программирования. Коды команд ОЭ удобно представлять в 16-ричной системе счисления.

Таблица 5

Цепь 1	ОЭ	11	12	13	21	22	23	14	15	16	24	25	26
	Команды	C21F	09B4	D400	0007	6763	D401	C3C3	0906	88CD	8D2D	D401	0006
Цепь 2	ОЭ	17	18	19	27	28	29	31	32	33	41	42	43
	Команды	00D8	1AB1	0A49	00E4	D001	0006	8B07	0A5D	8907	8623	91E1	0006
Цепь 3	ОЭ	34	35	36	44	45	46	37	38	39	47	48	49
	Команды	0FB8	87C9	00A1	83E4	0398	13E1	C0FF	0631	2521	0086	C3C2	C21E

Программа на ОВС

ЗАКЛЮЧЕНИЕ

Во время выполнения данной работы была разработана ОВС, которая проводит вычисления по формуле (5), в которой числа А и В представляются в (2-5) и (2-13) системах счисления, т.е. A=A_2-5, B=B_2-13, обрабатываются в обратном коде и поступают на 9 такте с востока и севера соответственно, а результат С выдаётся с 56 по 63 такт на восток. Вычисления в ОВС производятся последовательно-параллельно. Параллельное вычисление А* и В*, затем вычисление С. А*, В* и С разработаны алгоритмы вычисления и отдельные ОВС. ОВС соединены в одну общую, которая занимает 4 чипа и состоит из 36 ОЭ. Для каждой ОВС построена временная диаграмма. ОВС запрограммирована и программа переведена в шестнадцатеричный код. Программа внесена в ОВС тремя параллельными цепями программирования. Все программирование ОВС произведено за 192 такта.

ПЕРЕЧЕНЬ УСЛОВНЫХ СОКРАЩЕНИЙ

- ОВС - однородная вычислительная среда;

- ОЭ - операционный элемент;

- АЛУ - арифметико-логическое устройство;

- СС - система счисления;

ЛИТЕРАТУРА

1. А.В. Дрозд - «Методические указания к курсовой работе по теме: Выполнение арифметико-логических операций на однородной вычислительной среде».

2. Методические указания по оформлению дипломных и курсовых работ для студентов дневной и заочной формы обучения специальности 0915/

Сост.: М.Н.Подлегаев - Одесса. ОНПУ, 2003, - 14 с.