Моделирование алгоритмов базовых операций ассоциативного процессора




Дата06.06.2016
Размер66 Kb.
ЛАБОРАТОРНАЯ РАБОТА №2

Тема: Моделирование алгоритмов базовых операций ассоциативного процессора

Цель работы: освоение навыков построения и верификации моделей алгоритмов базовых операций ассоциативного процессора над разрядными срезами.

3.1 Краткие теоретические сведения

Будем рассматривать ассоциативные процессоры с пословной организацией, т.е. с параллелизмом на уровне слов и обработкой их последовательно по разрядам. Множество слов образует ассоциативный массив или ассоциативно-запоминающее устройство (АЗУ) ассоциативно организованного процессора (АП). Соответственно имеется по одному процессорному элементу на каждое слово, так как весь разрядный срез АЗУ может обрабатываться параллельно.


3.1.1 Структура АП
Базовая структура пословно организованного АП содержит следующие подсистемы (рисунок 3.1):

- массив ассоциативной памяти (АМ);

- регистр поискового признака;

- регистр маски;

- регистры хранения ответов;

- регистры или буфер ввода-вывода АЗУ;

- маска (буфер) вывода слов;

- контроллер (память и программы).


Рисунок 3.1 – Базовая структура АП


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

Обычно каждый регистр хранения ответов представляет собой множество триггеров, образующее одноразрядный двоичный вектор вдоль всего массива АЗУ.



Один из регистров называется регистром меток (тегов) или отклика и служит для индикации или хранения результатов операций над массивами. Выделенное слово АЗУ, т.е. слово, отмеченное единицей в регистре меток, обычно индицирует успешное окончание поиска или хранит результат логической операции (например, перенос в текущем шаге операции сложения).

Второй регистр памяти ответов используется как временная рабочая область (или сверхоперативная память) при обработке данных или реализации логических функций.

Третий регистр памяти ответов служит для выбора слов. Он указывает для каждого слова АЗУ, участвует ли оно в подлежащей выполнению операции. Если, например, в массиве АЗУ хранятся файлы А и В и мы хотим выполнить некоторую операцию над одним из файлов, то необходимо запретить обработку всех слов другого файла путем установки в "0" всех разрядов регистра выбора слов, соответствующих второму файлу.

Регистры (или буфер) ввода-вывода АЗУ играют роль буфера при передаче данных в АЗУ или из него. Манипулирование данными может относиться к одному слову или распространяться на весь массив (при загрузке или разгрузке АЗУ).

Контроллер предназначен для управления АП. Он имеет память для программ, реализующих базовые операции, и различные регистры, логику управления шиной, механизмы прерываний и АЛУ для вычисления адресов и сдвига информации.
3.1.2 Алгоритм выполнения базовых операций АП
Отметим, что разрядный срез является основной конструкцией в пословно организованных АП. Существуют операции считывания и записи разрядного среза, пересылки содержимого одного разрядного среза и т.д.

Для описания отдельных операций АП применим синтаксис одной из систем (в частности, системы LUCAS).

Рассмотрим основные базовые операции АП.

Загрузить разрядный срез ( Load bit slice)

Эта операция пересылает содержимое некоторого разрядного среза АЗУ в один из регистров хранения ответов.

Введем следующие обозначения:

R3 – триггер регистра выбора слов в памяти ответов;

T1 – триггер регистра меток в памяти ответов;

S - позиция источника;

D - позиция назначения.

Возможны 3 варианта операции "Загрузить разрядный срез":

а) LOAD R - Загрузить разрядный срез в вектор R.

б) LOAD R [T] - Загрузить в R отмеченные метками T биты разрядного среза.

в) LOAD T [T] - Загрузить в T биты разрядного среза, отмеченные прежними значениями меток T.

Пример реализации варианта б) показан на рисунке 3.2.



рисунок 3.2


Запомнить разрядный срез (Store bit slice)

Эта операция противоположна операции загрузки.



Переслать разрядный срез (Move bit slice)

Эта операция пересылает содержимое одного разрядного среза в позицию другого. При этом используются триггеры памяти ответов, т.е. сначала выполняется операция "Загрузить", а затем - "Запомнить".


Логические операции с разрядными срезами


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

Для любой операции первый из операндов загружается в какой-нибудь триггерный вектор (например, R), заданная логическая операция выполняется между вторым операндом (т.е. соответствующим разрядным срезом) и триггерным вектором R, после чего результат, заменивший прежнее содержимое триггерного вектора, пересылается из этого вектора в позицию результирующего разрядного среза. Логической операцией может быть любая булева функция двух переменных.

Пример выполнения операции OR (ИЛИ) приведен на рисунке 3.3

К базовым операциям АП с пословной организацией относятся также следующие операции:

- выбрать первого ответчика и сбросить (Select first and reset);

- операции с байтами (Store I/O, Load I/O и др.), аналогичные операциям с битовыми срезами;

- операции с полями (Move Field, Load Field и др.), осуществляющие пересылку полей, находящихся внутри слов.
3.2 Индивидуальное задание
Построить и проверить модели алгоритмов, рассмотренных в п.3.1 базовых операций с разрядными срезами АП.

Разработанная программа должна уметь:

– строить ассоциативный массив (АМ) двоичных чисел размерностью m слов на n разрядов;

– загружать любые разрядные срезы АМ в регистры хранения ответов (R или T );

– запоминать и пересылать любые разрядные среды АМ (т. е. выполнять команды “Store bit slice” и “Move bit slice”);

– выполнять любые логические операции над любыми разрядными срезами (Si и Sj) АМ, при этом адресом (номером) назначения (D) может быть любой срез АМ или регистр хранения ответов.

Логической операцией может быть любая из 16-ти возможных логических функций 2-х логических переменных (И, ИЛИ, НЕ, неравнозначность, операция Пирса и т.д.), приведенных в таблице 3.1.
Таблица 3.1

Логические функции 2-х переменных



Логические аргументы

x1

x2

Значение истинности
0 0 1 1

0 1 0 1


Наименование

функции


Запись

функции


в ОФПС

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11
f12

f13
f14

f15

0

0

0



0

0

0



0

0

1



1

1

1


1

1
1


1

0

0

0



0

1

1



1

1

0



0

0

0


1

1
1


1

0

0

1



1

0

0



1

1

0



0

1

1


0

0
1


1

0

1

0



1

0

1



0

1

0



1

0

1


0

1
0


1

Константа 0

Конъюнкция (И)

Запрет 1-го аргумента (НЕТ)

Повторение 1-го аргумента (ДА)

Запрет 2-го аргумента (НЕТ)

Повторение 2-го аргумента (ДА)

Неравнозначность (ИЛИ-ИЛИ)

Дизъюнкция (ИЛИ)

Операция Пирса (ИЛИ-НЕ)

Эквивалентность (И-И)

Отрицание 2-го аргумента (НЕ)

Импликация от 2-го аргумента к 1-му (НЕТ-НЕ)

Отрицание 1-го аргумента (НЕ)

Импликация от 1-го аргумента ко 2-му (НЕТ-НЕ)

Операция Шеффера (И-НЕ)

Константа 1



f0 = 0

f1 = x1 x2



f3 = x1



f5 = x2



f7 = x1 + x2













f15 = 1


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница