Geum.ru

Лекция 1 принципы построения параллельных вычислительных систем пути достижения параллелизма

Вид материалаЛекция

Содержание


Поиск и исключение элемента списка
Подобный материал:
1   ...   23   24   25   26   27   28   29   30   31
^

Поиск и исключение элемента списка


Пусть задано имя S некоторого элемента списка, являющееся первым словом в массиве его данных, на которое указывает одна из ссылок C в массиве R троек (V, C, D). Необходимо по заданному S найти соответствующий ему элемент списка, т.е. такой, данные которого начинаются с S, и исключить его из списка. Для этого достаточно заменить значение ссылки C в одной из троек в массиве R, указывающей на исключаемый элемент, на значение ссылки, указанное в тройке, которая соответствует исключаемому элементу. При этом тройка, соответствующая исключаемому элементу, в свою очередь должна быть исключена из массива R.

Совместные действия процессоров можно организовать следующим образом.

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

Проанализируем работу программы, представленной в табл. 1.3.

Таблица 1.3.

№k
КОП
I1
A1
I2
A2
I3
A3

0
СИНХ


















1
















003

2
ЗАГ
K















3
ПРАД
DR7












010

4
ЗАП
DR7
0002









M1

5
ЗАПК
M1
0001









M2

6





M2



S



011

7
ЗАГ
K
0001












8
ЗАП
M1
0002






DR7
0002

9
ИСКЛ
DR



M1









10
В


















11


K












010

12
ИЗМАД
DR7












010

13
БП



004












По команде 0 производится синхронизация процессоров ВС.

По командам 1 и 2 модификатору K присваивается нулевое значение. Эту операцию выполняет процессор 0. Другие процессоры по команде 1, в которой номер i процессора сравнивается с нулем и выполняется условный переход по неравенству, перейдут к выполнению команды 3. (Иллюстрируется возможность параллельной работы процессоров по разным ветвям монопрограммы.)

По команде 3 осуществляется выход из программы, если значение текущего адреса в дескрипторном элементе DR7 превосходит значение текущего адреса последнего элемента массива R, записанное в DR3. Если DR7 DR3, по команде 4 в регистр M заносится ссылка анализируемого элемента списка, записанная по адресу (DR7) + 2, т.е. в поле C.

Пусть ссылка, записанная в поле C, указывает на первый адрес в тройке, составляющей некоторый элемент R. Тогда по адресу (M1) + 1 находится адрес начала "тела" соответствующего элемента списка. Команда 5 выполняет запись по косвенному адресу этого начала в регистр M2.

По команде 6 начало тела анализируемого элемента списка сравнивается с исключаемым элементом, указанным в S.

При положительном результате сравнения по команде 7 модификатору K присваивается отличное от нуля значение, служащее индикатором того, что исключаемый элемент списка некоторым процессором найден. Если (M2) S, управление передается команде 11.

По команде 8 ссылка, записанная в элементе массива R и соответствующая исключаемому из списка элементу, присваивается тому элементу, который ранее указывал на исключаемый, т.е. значение ((M1) + 2) присваивается элементу (DR7) + 2.

Команда 9 — ИСКЛючение из массива, описываемого дескриптором DR, элемента, расположенного по адресу (M1). В результате выполнения команды 4 по данному адресу находится элемент массива R, соответствующий исключаемому из списка элементу.

По команде 10 производится выход из подпрограммы.

Команда 11 получает управление в случае, если ссылка в анализируемом элементе массива R не указывает на исключаемый из списка элемент. В этом случае проверяется наличие признака того, что некоторый процессор обнаружил искомый элемент и готов исключить его из списка, т.е. если (K) 0, осуществляется выход из подпрограммы по команде 10. Если (K) = 0, необходимо перейти к анализу следующего элемента массива R, предопределенного i-му процессору.

По команде 12 выполняется переадресация (DR7) := (DR7) + (DR6), где (DR6) = Nh. Если такая переадресация приводит к выходу за пределы массива, т.е. новое значение DR7 превышает значение последнего адреса массива R, указанное в DR3, производится выход из подпрограммы по команде 10.

В противном случае по команде 13 процессор приступает к анализу очередного элемента R.

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

Это приводит к необходимости выделения одной или группы команд исключения из списка (см. команду 9 данной монопрограммы) в критический блок, не допускающий одновременного обращения к нему более одного процессора. Формирование критического блока достигается выполнением в его начале команды ЗАКРыть Семафор с указанием адреса некоторого семафора C. Если при выполнении этой команды данный семафор уже закрыт другим процессором при выполнении этого же фрагмента программы, то процессор переходит в режим ожидания, "жужжания", т.е. повторного выполнения этой команды до открытия семафора.

Критический блок заканчивается командой ОТКРыть Семафор с указанием адреса того же семафора.


Литература