Команды управления, предназначенные для организации циклов и ветвлений.

⇐ ПредыдущаяСтр 4 из 4

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

В таблице для порядка определены типы вычисляемых операндов, однако система не различает типы и следить за их соблюдением возлагается на программиста. Таким образом, логическая ИСТИНА в системе представляется ВЕЩЕСТВЕННЫМ значением «1», а ЛОЖЬ соответственно «0». Но, если команда требует на вход значение логического типа, то результат будет верным лишь в том случае, если операнд будет равным 0 или 1.

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

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

Графическое представление команд

	Арифметические операции (сложение, вычитание, умножение и др.) На входах и выходе операции вещественные значения.
	Команда сравнения. На входах вещественные или логические значения, на выходе – 1 при истинном результате, и 0 при ложном.
	Вентиль. Может быть TRUE, как на рисунке, или FALSE (F). Первым операндом команды есть вещественное или логическое значение, вторым – логическое. Вентиль TRUE если второй операнд имеет истинное значение «пропускает» на выход первый операнд. В противном случае операнд «поглощается», т.е. операция не вернет никакого результата.
	2-Размножитель. Первым операндом есть операнд, который необходимо размножить, второй – адрес. Результатом выполнения операции есть 2 идентичных операнда но с разными адресами (номерами операций). Первый адрес извлекается из соответствующего поля команды, а второй – из второго операнда команды.
	N-Размножитель. Первым операндом есть операнд, который необходимо размножить, второй – количество (N) этих операндов. Адрес первого операнда (номер операции) определяется в соответствующем поле команды, адреса остальных определяются как адрес предыдущего +1.
	Команда вывода. Первым операндом есть число, которое выводится, вторым – номер устройства вывода.
	Повторитель входа 1. Результатом выполнения команды является 1-й входной операнд. Команда используется для синхронизации независимых веток цикла. Второй входной операнд используется для инициализации команды и при выполнении теряется (в результате не участвует)
	Повторитель входа 2. Команда аналогична предыдущей.

Ассемблер вычислительной системы

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

Тип	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».

ПРИМЕР

Фрагмент программы на Паскале:

a: =1; b: =-2; f: =2;

n: =(a+3)*(b+3);

FOR i: =1 TO n do

f: =f+2;

write(f);

Граф алгоритма на описанном языке для вычислительной системы:

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

⇐ Предыдущая 1 2 34