Архитектура машин управляемых потоком данных
Обработка структур данных
жүктеу/скачать 0,54 Mb.
|
prorobot.ru-19-0101
2.6. Обработка структур данныхП ри рассмотрении потоковой машины мы не затрагивали вопрос о том, каким образом программы потоков данных оперируют совокупностями данных, такими, как массивы или структуры. Один из вариантов решения этой проблемы предусматривает, во-первых, введение в машину потоков данных дополнительной памяти, предназначенной для хранения не команд, а структур данных, и, во-вторых, создание средств адресации этой памяти. В языке потоков данных определены три типа данных:
Упрощенно структуру можно изобразить в виде двоичного дерева, в котором каждый элемент – узел – представляет данные типа «пусто», элементарные данные или структуру. На рис. 9 представлена структура по имени S, размещенная в пассивной памяти данных. Д ля выполнения операций над структурами вводятся четыре новых блока. Первый из них – блок выбора. Он имеет две входные линии: для имени (адреса) структуры и для двоичной строки. В результате работы блока выбора определяется значение элемента (узла) структуры, соответствующего указанному имени структуры и заданному местоположению этого элемента. Д Рис. 9. Пример представления структуры ля адресации к любому элементу структуры необходимо указать её имя и двоичную последовательность переменной длины, которая определяет маршрут поиска на двоичном дереве (0 соответствует левой ветви, а 1 – правой). Если в узле содержатся элементарные данные, то на выходной линии блока появляется значение этих данных. Если же узел является структурой (именуемой в этом случае подструктурой), то блок выбора выдает на выходную линию имя – адрес подструктуры. При подаче на входы блока выбора значения S и величины 010 на выходе блока появится величина 4,2. Вторым новым блоком, вводимым для обработки структур, является блок добавления, который служит для введения новых элементов в существующую структуру. Блок добавления имеет три входа, два из них такие же, как ми у блока выбора, а третий используется для передачи в блок значения вводимого в структуру элемента или адреса подсоединяемой структуры. На основании данных, поступающих на два первых входа, блок добавления находит нужный узел в дереве структуры. Содержимое этого узла заменяется данными, поступающими на третий вход. Т ретьим новым блоком, вводимым для обработки структур, является блок удаления, имеющий два входа, на один из которых подается имя структуры, а на другой – двоичная строка. Адресуемый узел «стирается», т. е. Ему присваивается значение «пусто». Предусмотрен также блок построения, который на основании двух входных данных (элементарных данных или структур) строит новую структуру, содержащую в качестве элементов входные данные. В результате работы блока на его выходной линии появляется адрес новой структуры. На рис. 10 представлена обобщенная схема машины потоков данных, в которую введено устройство хранения и обработки структур. Когда селекторная сеть обнаруживает наличие операционного пакета, предназначенного для одного из блоков обработки структур, она передает этот пакет в устройство хранения и обработки структур. На выходе этого устройства появятся (в зависимости от блока) один или несколько пакетов результата, которые будут направлены в распределительную сеть. На рис. 11 представлена схема устройства хранения и обработки структур. Принцип его функционирования: Когда функционирует блок выбора, селекторная сеть направляет операционный пакет в распределительную сеть устройства. Адрес структуры в команде выбора дает возможность извлечь слово из памяти хранения структур. Если значение слова определяет структуру, а не элементарные данные, то с помощью первого бита в двоичной строке, являющейся операндом для блока выбора, выбирается один из двух адресов подструктур, относящихся к данному узлу структуры. Этот адрес вместе с остатком двоичной строки помещается в новый пакет выбора и через селекторную сеть направляется вновь в распределительную сеть. Таким образом, в результате выполнения операции выбора может быть сформирована последовательность новых запросов на операцию выбора. Эти запросы последовательно обрабатываются памятью структур до тех пор, пока не встретится узел, содержащий элементарные данные. После этого формируется и выдается пакет, содержащий найденные элементарные данные и адрес пункта назначения, указанный в исходной команде выбора. Другие операции над структурами выполняются одним или несколькими блоками обработки структур данных. Эти блоки оперируют содержимым памяти структур путем формирования запросов на обращение к памяти с целью извлечения ее содержимого или записи данных на ранение. Эти запросы имеют тот же формат, что и пакет запроса на операцию выбора, и так же направляются через распределительную сеть памяти структур. Результат, извлеченный из памяти структур, опять направляется в блок обработки структур. В конечном счете, формируется пакет результата, который передается в общую распределительную сеть машины потоков данных. Рис. 10. Структурная схема машины управляемой потоком данных, обрабатывающая структуры
жүктеу/скачать 0,54 Mb. Достарыңызбен бөлісу:
|