Архитектура и семантика элементов формата СВМ

Автоматическая трансляция Си-программ в числовой формат

Сопряженно-Внешних Множеств (СВМ)

1. Цель работы:

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

Требования к средствам спецификации

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

· алгоритмическая интерпретируемость;

• непосредственная схемная интерпретируемость;
• временная и функциональная конструктивность;
• сложностная инвариантность;
• машинная представимость.

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

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

Временная конструктивность – это возможность представления средствами спецификации динамики функционирования устройства во времени.

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

Машинная представимость – это возможность непосредственного (без применения конверторов) представления машинным кодом всех элементов спецификации, а также спецификации алгоритма в целом.

Архитектура и семантика элементов формата СВМ

Поясним семантику элементов формата СЧС с помощью следующих примеров.

Пример 1.1. Исходный текст неразветвляющейся Си-программы

(Текст 1.1).

#include < stdio.h>

void main(void)

{

int a, b, c, d, e, f;

int m, x, y;

scanf(" %d %d %d", & a, & b, & c);

scanf(" %d %d %d", & d, & e, & f);

m = b * d - a * e;

x = (b * f - c * e) / m;

y = (a * f - c * d) / m;

printf(" %4d %4d\n", x, y);

}

Текст 1.1 – Исходный текст неразветвляющейся Си-программы

Таблица 1.1 - Базовый Файл (БФ 1.1)

Примечания:

1. Операторы Р_j с номерами j = 0, 1, 2, 3, 4, 5 интерпретируют входы значений переменных a, b, c, d, e, f; операторы-имена этих переменных имеют номера j = 6, 7, 8, 9, 10, 11.

2. Операторы Р_j с номерами j = 37, 38 интерпретируют выходы для переменных x, y; операторы-имена этих переменных имеют номера j = 13, 14.

Поясним семантику идентификаторов Базового Файла:

N - массив номеров j оператор Р_j (данные и операции считаются операторами и нумеруются подряд от j = 0 до j = n - 1; n - количество операторов);

MET - массив меток операторов (содержит метки, задаваемые в тексте Си-программы, и автоматически вводимые метки в процессе синтеза формата СВМ);

NSJ - массив указателей nsj(j) на младший из номеров i -й строки ФС, с которой начинается цепочка сопряженных операторов Р_i для оператора Р_j;

SJD - массив значений sjd(j) мощностей сопряженных множеств S_j операторов Р_i для оператора Р_j;

BJ - массив номеров естественных частей (фрагментов) Си-программы, значение элемента bj(j) задает номер естественной части, к которой принадлежит оператор Р_j;

NWJ - массив указателей nwj(j) на младший из номеров i -й строки ФС, с которой начинается цепочка внешних операторов Р_i для оператора Р_j;

WJD - массив значений wjd(j) мощностей внешних множеств W_j операторов Р_i для оператора P_j;

MP1 - массив меток операторов безусловного перехода и перехода по значению " истина" Си-программы (" 0" означает отсутствие метки);

MP2 - массив меток операторов перехода по значению " ложь" Си-программы (" 0" означает отсутствие метки);

VH - массив, элементы которого vh(j) задают количество входов оператора Р_j (принимается, что для операторов Р_j, интерпретирующих имена входов исходных данных (a_in, b_in, …), переменных (a, b, c,...) vh(j) = 0; vih(j) = 1; значение vh(j) для операторов-операций/функций равно числу операндов соответствующей операции; оператор stop имеет один вход vh (36) = 1);

VIH - массив, элементы которого vih(j) задают количество выходов оператора Р_j (принимается, что для операторов Р_j, интерпретирующих имена выходов (x_out, y_out); оператор stop не имеет выходов vih(j) = 0);

RES массив, содержащий имена входов данных (например, а_in, b_in), имена исходных переменных, констант, символов операций языка Си, имена промежуточных и окончательных результатов решения задачи, имена выходов (например, x_out, y_out), а также имя оператора stop.

Таблица 1.2 - Файл связей (ФС 1.1)

Поясним семантику идентификаторов Файла связей (ФС 1.1):

N - массив номеров k строк (k = 0, 1, 2,..., sn -1; sn – количество связей по данным и по управлению между " n " операторами алгоритма, представляемого исходной Си-программой);

JSD - массив указателей jsd(j) на множество номеров сопряженных операторов Р_i для оператора Р_j, начинающийся с указателя jsd(j) = nsj(j) строки с номером nsj(j) массива SPJD и заканчивающихся k -й строкой массива JSD, имеющей jsd(k) = -1 (при этом каждый указатель jsd(k) = -1 указывает на некоторый элемент массива SPJD, задающий номер очередного оператора Р_i, сопряженного для Р_j;

SPJD - массив, задающий для каждого оператора Р_j (j = 0, 1, 2,..., n -1) его сопряженное множество S_j (то есть номера i операторов P_i, выходы которых являются входами для Р_j (указателями на элементы множества S_j являются значения элементов соответствующей цепочки указателей jsd(j), jsd(k) массива JSD, начинающейся с указателя jsd(j) = nsj(j) из массива NSJ файла БФ);

SNWIH - массив, задающий для каждой пары операторов Р_i, Р_j (рассматриваемых соответственно как сопряженный и внешний операторы), соединенных связью по данным, связью по управлению и/или осведомительной связью (либо некоторым сочетанием связей перечисленных типов), номер выхода оператора Р_i, соответствующий рассматриваемой " сопряженной связи";

SNWHO - массив, задающий для каждой пары операторов Р_i, Р_j (рассматриваемых соответственно как сопряженный и внешний операторы), соединенных связью по данным, связью по управлению и/или осведомительной связью (либо некоторым сочетанием связей перечисленных типов), номер входа оператора Р_i, соответствующий рассматриваемой " сопряженной связи";

JWD - массив указателей jwd(j) на множество номеров внешних операторов Р_i для оператора Р_j, начинающийся с указателя jwd(j) = nwj(j) строки с номером nwj(j) массива WPJD и заканчивающихся kw -й строкой массива JWD, имеющей jwd(k) = -1 (при этом каждый указатель jwd(k) = -1 указывает на некоторый элемент массива WPJD, задающий номер очередного внешнего для Р_j оператора Р_i;

WPJD - массив, задающий для каждого оператора Р_j (j = 0, 1, 2,..., n -1) его внешнее множество W_j (то есть номера i операторов P_i, для которых входами являются выходы оператора Р_j (указателями на элементы множества W_j являются значения элементов соответствующей цепочки указателей jwd(j), jwd(k) массива JWD, начинающейся с указателя jwd(j) = nwj(j) из массива NWJ файла БФ);

WNWHO - массив, задающий для каждой пары операторов Р_i, Р_j (рассматриваемых соответственно как внешний и сопряженный операторы), соединенных связью по данным, связью по управлению и/или осведомительной связью (либо некоторым сочетанием связей перечисленных типов), номер входа оператора Р_i, соответствующий рассматриваемой " внешней связи";

WNWIH - массив, задающий для каждой пары операторов Р_i, Р_j (рассматриваемых соответственно как внешний и сопряженный операторы), соединенных связью по данным, связью по управлению и/или осведомительной связью (либо некоторым сочетанием связей перечисленных типов), номер выхода оператора Р_j, соответствующие рассматриваемой " внешней связи".

Пример 1.2. Исходный текст разветвляющейся Си-программы

(Текст 1.2).

#include < stdio.h>

void main(void)

{

int a, b, c;

int x, k, s;

scanf(" %d %d %d", & a, & b, & c);

x = a * b;

if(x < 0)

k = x * c;

else

k = x + c;

s = k % 2;

}

Текст 1.2 – Исходный текст разветвляющейся Си-программы

Спецификация Текста 1.2 в числовом формате СВМ с детализацией до переменных и операций/функций Си-программы представляется Базовым файлом (БФ 1.2, Таблица 1.4) и Файлом связей (ФС 1.2, Таблица 1.5.

Таблица 1.4 - Базовый Файл (БФ 1.2)

Примечания:

1. Операторы Р_j с номерами j = 0, 1, 2 интерпретируют входы значений переменных a, b, c; операторы-имена этих переменных имеют номера j = 3, 4, 5.

2. Оператор Р_j с номером j = 21 и именем RES(21) = l.o отражает факт логического объединения двух (или нескольких - в общем случае) управляющих связей, интерпретирующих передачу управления на соответствующий оператор по его меткам.

3. Оператор Р_j с номером j = 22 и именем RES(22) = а.o отражает факт арифметического объединения двух (или нескольких - в общем случае) связей по данным, соответствующих передаче значений переменных на соответствующий оператор по меткам.

Константы " 0" и " 2" представлены операторами Р₁₄ и Р₂₃ с именами С0_ и С2_ соответственно.

Таблица 1.5 - Файл связей (ФС 1.2)

Контрольные вопросы

1) В чем состоит сущность проблем, обусловивших кризис в САПР?

2) Назовите основные методы параллельной обработки данных и поясните их семантику.

3) Поясните различие в целевом назначении файлов БФ, ФС.

4) Поясните понятия сопряженного множества и внешнего множества операторов числового формата СЧС.