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

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

Цель работы:

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

Задание:

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

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

Таблица 1.Набор функций

а2 а1 а0	Функции
0 0 0	f1, f2, f3
0 0 1	f1, f2, f4
0 1 0	f1, f3, f4
0 1 1	f2, f3, f4
1 0 0	f2, f3, f5
1 0 1	f1, f2, f5
1 1 0	f3, f4, f5
1 1 1	f1, f3, f5

Таблица 2. Количество устройств ввода

а4 а3	n
0 0
0 1
1 0
1 1

Примечание: размещение слов для ввода выполнить самостоятельно учитывая особенности алгоритма

Таблица 3. Вывод на устройства

а6 а5	вывести функции Х, Х, Х на устройства вывода, № устройства
0 0	1, 2, 3
0 1	1, 3, 4
1 0	2, 3, 4
1 1	1, 2, 4

Примечание: Для всех вариантов количество устройств вывода равно четырем

f1=y²+by+2ab+4

f2=sqrt(b+5a+c²)+2ac

f3=a-b-ca+12sqrt(b²+a²)

f4=(a²+b²+c²+d²)ab

f5=скалярное умножение векторов размерностью 5.

Данные для всех функций задать самостоятельно.

2. Определить ЯПФ каждой функции.

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

4. Написать программу совместного выполнения всех функций

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

Выполнение работы:

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

2. Исследование системы.

· Установить в «Набор операций» большие значения количества шагов выполнения операций (примерно 30) и в «параметрах системы» минимально возможные значения количества вычислительных устройств (1) и размеров БПД и БПК (2). Запустить программу на автоматическое выполнения при алгоритме опроса «Последовательный по порядку ввода», а затем «со свободной ячейкой БПД». Сделать выводы.

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

· Уменьшая количество процессоров определить динамику уменьшения производительности, определяя на каждом шаге Ку=Т₁/Т_i, где Т - количество тактов выполнения программы.

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

3. Сделать выводы по работе.

Лист

лабораторная работа 2

Описание системы.

Вычислительная система содержит устройства 1.1,..., 1.k ввода данных, информационные входы которых через соответствующие входы коммутатора 2 подключены к блоку 3 буферной памяти данных, каждое устройство 1.1,..., 1.k ввода соединено с блоком 4 управления управляющим входом и выходом, а коммутатор 2 — управляющими входами. (рис. 1)

рис1. Вычислительная система с буферной памятью данных.

Управляющие входы блока 3 буферной памяти данных, которые обеспечивают занесение информации и продвижение очереди, подключены ко входам блока 4 управления, соответствующие входы которого соединены с выходами сигнала блока3 буферной памяти данных, характеризующей степень его заполнения (“буфер занят”, ”буфер пуст”). С информационным входом регистра 5 данных и регистра 6 адреса подключены соответственно первая и вторая группы информационных выходов блока 3 буферной памяти данных. Управляющие входы занесения информации регистра 6 адреса и регистра 5 данных соединены с выходами блока 4 управления. а выход одного разряда регистра 5 данных (признак типа информации) подключен к соответствующему входу блока 4 управления. Информационные выходы регистра 6 адреса связаны с адресными входами блока7 памяти операндов, и блока 8 памяти управляющих слов. Информационные выходы регистра 5 данных ко входам данных блока 7 памяти операндов, блока 8 памяти управляющих слов и первой группе информационных входов 9 буферной памяти команд. Вторая и третья группы информационных входов 9 буферной памяти команд соединены соответственно с выходами данных блока 7 памяти операндов и блока 8 памяти управляющих слов. Входы управления записью и чтением блока7 памяти операндов и блока8 памяти управляющих слов подключены соответствующие выходы блока 4 управления. Один выход блока 4 управления подключен ко входу одного разряда данных блока7 памяти операндов, выход одноименного разряда данных которого соединен с одним входам блока 4 управления. К соответствующим входам блока 4 управления подведены выходы сигналов блока буферной памяти команд 9, указывающих на степень его заполнения, а также выходы группы разрядов, характеризующих тип команды и номер устройства вывода. Управляющие входы записи и продвижения по очереди (чтения) блока 9 буферной памяти команд связаны с соответствующими входами блока 4 управления. Информационные выходы блока 9 буферной памяти команд подключены к информационным входам вычислительных блоков 10.1,..., 10.n и информационным входам устройств вывода данных 11.1,..., 11.m, управляющие входы и управляющие выходы которых подключены к соответствующим входам и выходам блока 4 управления. Информационные выходы каждого вычислительного блока 10.1,..., 10.n соединены соответствующие группы информационных входов коммутатора 2.

Описание системы.

Вычислительная система содержит устройства 1.1,..., 1.k ввода данных, информационные входы которых через соответствующие входы коммутатора 2 подключены к блоку 3 буферной памяти данных, каждое устройство 1.1,..., 1.k ввода соединено с блоком 5 управления управляющим входом и выходом, а коммутатор 2 — управляющими входами. (рис.2)

С информационным входом регистра 3 данных и регистра 4 адреса подключены соответственно первая и вторая группы информационных выходов блока 2 коммутатора. Управляющие входы занесения информации регистра 4 адреса и регистра 3 данных соединены с выходами блока 5 управления, а выход одного разряда регистра 3 данных (признак типа информации) подключен к соответствующему входу блока 5 управления. Информационные выходы регистра 4 адреса связаны с адресными входами блока 6 ассоциативной памяти. Информационные выходы регистра 3 данных подключены ко входам данных блока 6 ассоциативной памяти. Вторая и третья группы информационных входов 7 выходного регистра соединены соответственно с выходами данных блока АП, а первая - с входом управляющего слова. Входы управления записью и чтением ассоциативной памяти подключены соответствующие выходы блока 5 управления. Один выход блока 6 АП подключен ко входу блока 5 управления, который определяет состояние тега ячейки АП или готовности команды к обработке. К соответствующим входам блока 5 управления подведены выходы сигналов блока выходного регистра 7, указывающих на возможность записи в него, а также группы разрядов, характеризующих тип команды и номер устройства вывода. Управляющие входы записи и чтения блока 7 выходного регистра связаны с соответствующими входами блока 5 управления. Информационные выходы блока 7 выходного регистра подключены к информационным входам вычислительных блоков 10.1,..., 10.n и информационным входам устройств вывода данных 11.1,..., 11.m, управляющие входы и управляющие выходы которых подключены к соответствующим входам и выходам блока 5 управления. Информационные выходы каждого вычислительного блока 10.1,..., 10.n соединены соответствующие группы информационных входов коммутатора 2.

Форматы слов данных

Формат управляющего слова:

Формат слова данных.

· Тип слова - для управляющего слова - «1», для слова данных - «0».

· Номер операции определяет адрес в памяти управляющих слов и памяти операндов или в АП для соответствующих систем.

· Номер операнда используется в операциях вычитания, деления и в других, где имеет значение порядок вычисления. При этом слово со значением поля «0» делится, например, на слово со значением «1». Однооперандные операции (например sqrt) производятся над аргументом с номером «0», другой не имеет смысла. В операциях, где порядок вычисления ничего не меняет (сумма, произведение) все равно необходимо разделять аргументы с номером «0» и с номером «1». В командах управления потоком (ветвления) порядок операндов так же строго определен.

Для управляющего слова это поле определяет номер вычисляемого операнда.

· КОП определяет код операции.

· В поле Операнд слова данных определяют конкретное значение операнда.

· Номер следующей операции определяет адрес вычисляемого операнда.

· Устройство ввода указывает на устройство, с которого должен производиться ввод слова.

· Порядок ввода должен исключать ситуации ввода управляющего слова после слов данных.

· Поле К определяет для слова данных является ли оно константой. При создании команды (если управляющее слово и оба операнда с различными номерами поступили в систему) операнды удаляются из соответствующих блоков, за исключением констант.. Для управляющих слов это поле означает принадлежность к классу констант вычисляемого командой операнда. Однако необходимо помнить, что команда может иметь только одну константу их двух операндов (поскольку лишь одна память операндов в системе с БПД)

Команды и их описание

Тип	ASM	КОП	Операнды	Результат	Описание
A	B
Вывод	Out		R	I	Out A to B	Вывод операнда А в устройство вывода В
Сложение	Add		R	R	R(A+B)
Вычитание	Sub		R	R	R(A-B)
Умножение	Mul		R	R	R(A*B)
Деление	Div		R	R	R(A/B)
Возведение в квадрат	Sqr		R	R	R(A²)	Используется один операнд, второй операнд необходим для инициализации команды и может быть любым числом
Извлечение корня	Sqrt		R	R	R(sqrt(A))	Используется один операнд, второй операнд необходим для инициализации команды и может быть любым числом

Сравнение	Cmpe		R/B	R/B	B(a=b)	На входе команды сравнения два операнда, результатом выполнения команды будет 1 если условие истинно и 0 в противном случае
	Cmpm		R/B	R/B	B(a> b)
	Cmpl		R/B	R/B	B(a< b)
	Cmpme		R/B	R/B	B(a> =b)
	Cmple		R/B	R/B	B(a< =b)
Вентиль	If		R/B	B	a if b	Вентиль TRUE. На входе – операнд любого типа (Операнд1) и операнд логического типа. Если последний будет равен TRUE, результатом команды будет первый операнд, в противном случае команда результата иметь не будет.
	Ifnot		R/B	B	a if not b	Вентиль FALSE. Обратный предыдущей команде
Размножитель	X2		R/B	I	-	2-Размножитель. Результатом команды будут два операнда, значение с равным значением и различными адресами. Адрес первого определяется из соответствующего поля актора команды, а адрес второго определяется из второго операнда команды.
	Xn		R/B	I	-	N-Размножитель. Результатом команды есть N операндов с равным значением. Адрес первого определяется из актора команды, адрес остальных оперделяется наращиванием адреса предыдущего результата на единицу.
Повторитель	Eq1		R/B	R/B	a	Повторитель входа 1. На вход команды подаются любые значения, результатом операции является первый операнд, второй операнд поглощается. Команда используется для синхронизации независимых ветвей цикла.
	Eq2		R/B	R/B	b	Повторитель входа 2. Команда является обратной предыдущей.

6.2 Формальное описание языка программирования:

< Программа>:: =

Program < имя_программы >

[Constant

< список переменных и их значений> ]

Begin

< список команд>

End

< список переменных и их значений>:: =

< имя переменной > =< значение переменной> | [< список переменных и их значений> ]

< список команд>:: =< команда>

| [< список команд> ]

< команда >:: =

< номер операции>: < имя команды> < операнд А>, < операнд В>,! < номер вычисляемого операнда> to < номер следующей операции>

< имя команды>:: = < идентификатор команды> [ < признак константы> ]

< признак константы >:: =” *”

< операнд>:: = < переменная> | < заместитель>

< заместитель>:: =” _”

< переменная >:: = < имя переменной> | < значение переменной> [ < признак константы> ]

< имя переменной>, < имя программы>:: =”a”..”z”, “A”..”Z”, “0”.. ”9”, “_”

< идентификатор команды>:: =out, add, sub, mul, div, sqr, sqrt, cmpe, cmpl, cmpm, cmpme, cmple, if, ifnot, x2, xn, eq1, eq2

< комментарий>:: =”; ”

Примечания:

1. Заместитель операнда («_») ставится на место того операнда, который вычисляется на одном из предыдущих шагов

2. Константа обозначается как «*»

3. После операндов в команде ставится символ «! » и после него – номер вычисляемого операнда, затем слово to и номер следующего операнда.

4. Порядок ввода и устройство ввода определяется при компиляции автоматически.

5. Номер операнда А – 0, номер операнда В – 1.

6. Ассемблер не чувствителен к регистру.

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

6.3 Пример программы на ассемблере циклов и условных переходов из примера

Программа на ассемблере алгоритма, представленного в п. 8 данного описания:

program example

constant

A=1

B=3

C=-2

D=3

begin

1: add a, b, ! 0 to 3

2: add c, d, ! 1 to 3

3: mul* _, _, ! 1 to 4

4: cmple 1, _, ! 0 to 5

5: xn _, 3*, ! 1 to 6

6: ifnot 2, _, ! 0 to 16

7: if 2, _, ! 0 to 9

8: if 1, _, ! 0 to 10

9: add _, 2*, ! 0 to 11

10: add _, 1*, ! 0 to 12

11: x2 _, 7*, ! 0 to 13

12: x2 _, 8*, ! 0 to 14

13: x2 _, 6*, ! 0 to 15

14: eq1 _, 1*, ! 1 to 15

15: eq2 _, _, ! 0 to 4

16: out _, 2, ! 0 to 16

end

Пример программирования последовательно-параллельных алгоритмов

Этапы выполнения:

1. Выразить заданные функции в ЯПФ.

2. Присвоить каждой операции уникальный номер, определиться с исходными данными. Номера должны быть уникальны для всех функций, а не только в пределах одной. Здесь необходимо уделить особое внимание нескольким моментам:

- Любая команда в системе является двухоперандной, т.е. для ее выполнения необходимо 2 операнда. Операнды либо вводятся с устройств ввода, либо вычисляются в предыдущей команде. Кроме того, операнды имеют соответствующее поле, называемое «Номер операнда». В команде один операнд должен иметь номер «0», а второй номер «1». В противном случае программа будет выполнена некорректно или не будет выполнена вовсе. При создании команды (если управляющее слово и оба операнда с различными номерами поступили в систему) операнды удаляются из соответствующих блоков, за исключением констант.

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

- Для упрощения программирования впоследствии операнды с номерами «0» размещайте к левому входу графического блока соответствующей команды, а с номерами «1» - к правому. Константы обозначаются звездочкой у соответствующего входа/выхода.

3. Определить данные для вычисления функции.

4. Составить список управляющих слов и слов данных в соответствии с ЯПФ функций и форматом акторов и слов данных.

5. Записать программу учитывая порядок ввода (следить за тем, чтобы управляющее слово шло перед словом данных).

ПРИМЕР

Выполним программирование функции f=(-b+sqrt(b²-4ac))/2a. ЯПФ этой функции будет иметь вид (совмещенные первые два этапа):

Программа представлена в файле примера «Example.alg».

Пример программирования циклов и условных переходов

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

· Команда в вычислительной системе готова к выполнению если для нее готовы управляющее слово и оба операнда. Программирование циклов связано с повторяемостью выполнения определенных команд. Операнды команд тела цикла можно разбить на два класса. Первый класс – операнды, вычисляемые на предыдущей итерации, к ним так же относится и переменная цикла (в примере – i, f). На первом шаге операнды поступают с устройств ввода, а затем с каждой следующей итерации. Так, для команды 4 (сравнение переменной цикла с конечным значением) с устройства ввода поступает начальное значение переменной цикла i=1, а следующие переменной поступают с предыдущей итерации. Второй класс операндов – константы, значение которых не меняется в цикле. К таким операндам относятся количество итераций цикла, константы для выполнения операций. При поступлении команды на вычислительный блок операнды из соответствующих ячеек памяти операндов/ассоциативной памяти удаляются за исключением констант. Они вводятся изначально из устройства ввода и находятся в соответствующей ячейке памяти. Константы на рисунке ниже обозначены звездочкой, а в программе поле «Константа» такого операнда должно содержать «1». Необходимо помнить, что двух констант у одной команды быть не может, в противном случае это приведет к постоянному выполнению одной и той же команды, которая все время будет находиться в состоянии готовности.

· Кроме того, константы могут не только вводиться с устройств ввода, но и вычисляться (например в команде 3 вычисляется константа – количество итераций цикла)

· Каждая команда должна иметь операнды с разными номерами (поле «Номер операнда»). Причем в большинстве случаях важен порядок операндов. Например команда «вычитание» выполняет операцию «Операнд№0»–«Операнд№1». А для команд управления операнд с номером 1 является служебным (например у вентиля он должен быть равен TRUE или FALSE, т.е. «1» или «0»).

· Результатом операций «2-Разветвитель» и «N-Разветвитель» является группа операндов с разными адресами и одинаковыми значениями полей «Номер операнда». Поэтому команды, для которых предназначались эти операнды должны их принимать на одинаковые входы (например команда №11 вычисляет операнды с номером «0» для команд 13 и 7).

· Как видно из рисунка цикл содержит 3 независимые ветви: вывод результата, накопление результата и инкрементирование переменной цикла. Важным элементом цикла является синхронизация независимых ветвей, в противном случае (см. пример) при большом объеме вычислений в теле цикла переменная цикла может быть инкрементирована несколько раз, и результат вычислений будет неверным. Роль синхронизации выполняет «Повторитель» или в примере команда №15. Эта команда «задерживает» инициализацию новой итерации цикла до тех пор, пока не будет выполнено тело цикла на текущей итерации.

· Команда №14 является вспомогательной, служит для преобразования поля «Номер операнда» (см. пункт 3), поскольку команда №12 результатом имеет операнд с номером «0», а для команды №15 требуется операнд с номером «1».