Устройство для формирования и анализа семантических сетей Советский патент 1991 года по МПК G06F15/40 G06F15/16 

(21)4656471/24

(22)28.02,89

(46) 07.01.9t. Бюл. P 1

(71)Днепродзержинский индустриаль- ный институт им. М.И.Арсеничева и Институт кибернетики им. В.М.Глушкова

(72)Н.И.Витиска, И.И.Галаган, Е.И.Ершов и Н.И.Ходаковский

(53)681.3(088.8)

(54)УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ И АНАЛИЗА СЕМАНТИЧЕСКИХ СЕТЕЙ

(57) Изобретение относится к вычислительной технике, в частности к технике представления и работе со знаниями в многопроцессорных ЭВМ, ЭВМ с перестраиваемой структурой, интеллектуальных решающих системах, предназначается также для построения параллельных процессоров баз знаний на

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

с 8

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

Цель изобретения - повышение производительности за счет параллельной и приоритетной перестройки связей в ходе решения задач.

На фиг.1 представлена блок-схема устройства для формирования и. анализа семантических сетей; на фиг.2 - функциональная схема узла фиксации захвата; на фиг.З - функциональная схема узла изменения приоритета; на фиг.4 - многокаскадная дельта-сеть, построенная из двоичных соединителей; на фиг.5 - функциональная схема двоичного соединителя.

Устройство для формирования и анализа семантических сетей (фиг.1) содержит управляющую ЭВМ 1, шины 2 системного интерфейса, процессоры 3, шины 4 резидентного интерфейса,блок 5 локальной памяти, программируемый приоритетный блок 6, формирователь 7 подтверждения захвата, сетевой коммутатор 8, узел 9 изменения приоритета и узел 10 фиксации захвата, входовой элемент ИЛИ 11,двухвходовой элемент И 12, управляющий входом 13 сетевого коммутатора, двунаправлен- 1ные информационные шины 14, входы 15 1 индивидуальной разборки, адресные

Ј

ю

00 СЈ

входы 16, входы 17 приоритета, адресные выходы 18, входы 19 фиксации пути, выходы 20 фиксации пути, вход 21 общего сброса, тактируемые вхо- ды 22-25.

Узел 10 фиксации захвата (фиг.2) содержит два трехвходовых элемента И 26 и 27, триггер 28 и одновибра- тор 29.

Узел 9 изменения приоритета (фиг.З содержит группу элементов И 30-36, схему 37 сравнения и счетчик 38, шины 39 питания и шины АО земли.

Приведенный на фиг.4 пример сетевого коммутатора 8 реализован для случая соединения между собой четырех процессоров 3, причем основой для построения многокаскадной дельта-сети 8 служат четыре одинаковых двоичных соединителя 41-44, первый 45 и второй 46 каскады сетевого коммутатора 8.

Двоичный соединитель 41 (фиг„5) содержит группу двойных коммутаторов 47, блок 48 фиксации каналов,блок 49 выбора направления и блок 50 дешифрации приоритета.

В блок 48 фиксации каналов входят два регистра 51 и 52, группа элементов И 53-62, элемент ИЛИ 63 и элемент 64 задержки.

Блок 49 выбора направления содержит два регистра.65 и 66, дешифратор 67 адреса, узел 68 переключения направления и элемент 69 задержки.Дешифратор 67 адреса выполнен на основе элементов И 70-73. Узел 68 переключения направления содержит много- входовые элементы И 74-81 и двухвхо- довые элементы ИЛИ 82-85. Каждый двоичный коммутатор 47 связан со своей группой входов и выходов в зависимости от той информации, которая коммутируется через него.

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

0

5

0

5

0

5

0

5

0

5

процессору 3 через многокаскадную дельта-сеть 8, при этом разрешение конфликтных ситуаций, возникающих в процессе обмена, происходит за счет программируемого приоритетного блока 6 и формирователя 7 подтверждения захвата.

Первоначально обрабатываемая информация и программы загружаются через шины 2 системного интерфейса во внутреннюю память процессоров 3, а затем через шины 4 резидентного интерфейса они перезаписываются в свои локальные памяти 5. После этого на управляющем выходе управляющей ЭВМ формируется сигнал, который поступает на вход 21 общего сброса многокаскадной дельта-сети 8. По нему устанавливаются непосредственно в нулевое состояние регистры 51 и 52 и через элементы ИЛИ 63, элемент 64 задержки - регистры 65 и 66 в каждом .двоичном соединителе 41-44 многокаскадной дельта-сети 8. Затем на { адресных выходах управляющей ЭВМ 1 сформируются коды, по которым будут последовательно записаны соответствующие коды приоритета в счетчике 38 узлов 9 изменения приоритета. Будем считать, что если во все разряды счетчика 38 записаны единицы, то это соответствует наивысшему приоритету. Далее более низкий приоритет предполагает запись кода вида 11110 и т.д. Нужный счетчик 38 выбирается по коду, сформированному на адресных входах узлов 9 изменения приоритета и далее на входах схем 27 сравнения, из которых включается та, где происходит совпадение данного кода с кодом, зашифрованным на шинах 39 питания и минах 40 земли. С выхода включенной схемы 37 сравнения сформируется потенциал на управляющий вход счетчика 38, поэтому в следующий момент времени с адресных входов в счетчик 38 запишется соответствующий код приоритета (фиг.З). На этапе подготовки устройства к работе каждый процессор 3 формирует .на своих управляющих выходах сигналы. Так, на первом управляющем выходе формируется нулевой потенциал Разрешение за- хвата, на втором - единичный или нулевой потенциал Выбор направления, на третьем - единичный потенциал Признак индивидуальной разборки и на четвертом - единичный потенциал Индивидуальная разборка, по - которому через входы сброса в каждом узле 10 фиксации захвата произойдет установка в нулевое состояние триг- , гера 28 (фиг.2).

Если процессор 3 сформирует нулевой потенциал Разрешение захвата и единичный потенциал Выбор направления, то в узле 9 изменения приорите- водится в каждом двоичном соедините15

25

30

та появится высокий потенциал на выходе элемента И 30, который откроет элементы И 32-34. При этом первый тактируемый импульс, пришедший с управляющей ЭВМ 1 на входы синхронизации узлов 9 изменения приоритета, пройдет через открытый элемент И 32 на счетный чход счетчика 38, в котором код приоритета изменится на единицу. В тех счетчиках 38, в разрядах которых .0 были записаны только единицы, возникнет сигнал переполнения на выходе переноса счетчика 38. Послений пройдет через открытый элемент И 34 на выход кода приоритета узла 9 изменения приоритета. Таким образом возбуждены будут выходы кодов приоритета тех узлов 9 изменения приоритета, в которых был записан код наивысшего приоритета, и наоборот, нулевые сигналы на выходах тех узлов 9 изменения приоритета, в которых записаны коды более низких приоритетов, и, следовательно, не возникнет сигнал переполнения с соответствующих счетчиков 38.

Одновременно с этим процессоры 3, в зависимости от выполняемой команды, выставят на свои двунаправленные информационные шины адреса тех процессоров 3, с которыми им необходимо связаться через многокаскадную дельта- сеть 8.Данные коды адресов проходят через открытый элемент И 33 на адресные выходы узлов 9 изменения приоритетов, а затем далее на адресные входы 16 многокаскадной дельта-сети 8, на входы 17 приоритета которой также поступят в это время единичные и нулевые потенциалы с выходов кода приоритета узлов 9 изменения приоритета. С этого момента в многокаскадной дельта-сети 8 (фиг.4) начинается процесс параллельной фиксации каналов, причем данные каналы, отмеченные пунктирными линиями, образуются в Данных соединителях 41-44 покаскадно за счет последовательного формирования на тактируемых входах 22-25 импульсов с управляющей ЭВМ 1. При этом

35

40

45

50

55

ле 41 или 42 следующим образом.

Сигнал с первого тактируемого входа (фиг.5) включает элементы И 70-73 дешифратора 67 адреса и блок 50 дешифрации приоритета, а затем через элемент 69 задержки подается на управляющие входы регистров 65 и 66, в разряды которых должны быть записаны единица или нуль. Здесь, если единица запишется в первый разряд регистра 65, то обеспечивается подключение второго адресного входа 16 к первому адресному выходу двоичного соединителя 41 или 42; если переведется в единичное состояние второй разряд этого регистра 65, то к первому адрес ному выходу двоичного соединителя

41или 42 подключается первый адресный вход 16. В свою очередь, единица фиксируется в первом разряде регистра 66, если подсоединяется второй адресный вход 16 к второму адресному выходу двоичного соединителя 41 или 42. Когда единица запишется во второй разряд регистра 66, то обеспечивается связь первого адресного входа 16 к второму адресному выходу двоичного соединителя 41 или

42(нулем обозначается первый адресный выход, а единицей - второй адресный выход двоичного соединителя 41 или 42).

Используя приведенные выше положения, рассмотрим ситуацию, когда на адресные входы 16 поступили следующие двоичные коды адресов: 10, 11, 00, Ot. Как видно из фиг.4, для этой ситуации должны быть образованы каналы, обозначенные пунктирными линиями от группы входов к группе выходов, закодированных следующим об- разом: 00, lpj, р{,Щ. Сле- довательно, в первом каскаде 45 двоичные соединители 41 или 42 устанавливают соединения параллельно,рас сматривая и параллельно обрабатывая двоичный код 0101, образованный младшими разрядами от поступивших

в первую очередь подается импульс на тактируемый вход 7.7., который в люча- ет в первом каскаде 45 через первый тактируемый вход двоичные соединители 41 и 42. В каждом из них путь может быть выбран прямо или накрест. Если пути пересекаются, то один из них должен быть отсечен, что произ-

водится в каждом двоичном соедините15

25

30

.0

5

0

5

0

5

ле 41 или 42 следующим образом.

Сигнал с первого тактируемого входа (фиг.5) включает элементы И 70-73 дешифратора 67 адреса и блок 50 дешифрации приоритета, а затем через элемент 69 задержки подается на управляющие входы регистров 65 и 66, в разряды которых должны быть записаны единица или нуль. Здесь, если единица запишется в первый разряд регистра 65, то обеспечивается подключение второго адресного входа 16 к первому адресному выходу двоичного соединителя 41 или 42; если переведется в единичное состояние второй разряд этого регистра 65, то к первому адресному выходу двоичного соединителя

41или 42 подключается первый адресный вход 16. В свою очередь, единица фиксируется в первом разряде регистра 66, если подсоединяется второй адресный вход 16 к второму адресному выходу двоичного соединителя 41 или 42. Когда единица запишется во второй разряд регистра 66, то обеспечивается связь первого адресного входа 16 к второму адресному выходу двоичного соединителя 41 или

42(нулем обозначается первый адресный выход, а единицей - второй адресный выход двоичного соединителя 41 или 42).

Используя приведенные выше положения, рассмотрим ситуацию, когда на адресные входы 16 поступили следующие двоичные коды адресов: 10, 11, 00, Ot. Как видно из фиг.4, для этой ситуации должны быть образованы каналы, обозначенные пунктирными линиями от группы входов к группе выходов, закодированных следующим об- разом: 00, lpj, р{,Щ. Сле- довательно, в первом каскаде 45 двоичные соединители 41 или 42 устанавливают соединения параллельно,рас сматривая и параллельно обрабатывая двоичный код 0101, образованный младшими разрядами от поступивших

двоичных л одов .адресов выходов, т.е. 1-Пл 1 П лП1

1 L.-J L:j L.VJ u L.UВ этом случае, например, в двоичном соединителе 41 (фиг.5) по коду 01 на адресных входах 16 возбуждают- ся выходы элементов И 70 и 73, потенциалы которых пройдут через от- . крытые многовходовые элементы И 74 и 77 и далее через элементы ИЛИ 82 и 85 перебросят в единичные состояния второй разряд регистра 65 и первый разряд регистра 66. Потенциалы с единичных выходов данных разрядов откроют элементы И 53 и 57 и соответствующие ключи в третьем двоичном коммутаторе 47-3, через которые пройдут далее на следующий каскад

46старшие разряды 11 поступивших двоичных кодов адресов выходов. Аналогичным образом в двоичном соединителя 42 на его адресных входах 16 будет анализироваться также код 01 и через его третий двоичный коммутатор

47пройдут старшие разряды 00 двоичных кодов адресов выходов. В результате этого на адресных входах 16 двоичных соединителей 43 и 44 будут присутствовать коды 10, по которым, согласно фиг.5, открываются элементы И 71 и 72. Возбуждение их выходов произойдет в момент подачи с управляющей ЭВМ 1 на тактируемый вход 24 импульса, который через первый тактируемый вход откроет элементы дешифратора 67 адреса и блока 50 дешифрации приоритета. Импульсы с возбужденных выходов элементов И 7t и 72 пройдут через открытые многовходовые элементы И 75 и 76 и перебросят в единичное состояние через элементы ИЛИ 83 и 84 соответственно первый разряд регистра 65 и второй разряд регистра 65. Это состояние, как по10

15

20

25

30

35

40

ры 3 формируют нулевые потенциалы на своих двух управляющих выходах, в результате чего изменяется напра ление движения информации через уз лы 9 изменения приоритета, так как в них уже открываются элементы И 3 35 и 36. В свою очередь, по данным нулевым потенциалам возбуждаются в ходы трехвходовых элементов И 26 в узлах 10 фиксации захвата, на ин формационных выходах которых появя ся импульсы, поступающие соответствующим образом на входы 19 фикса ции пути многокаскадной дельта-се ти 8. С этого момента управляющая ЭВМ 1 формирует потенциал на такти емом входе 25 многокаскадной дельт сети 8, который поступает на вторы тактируемые входы двоичных соедини телей 43 и 44 второго каскада 46. этому потенциалу включаются регист ры 51 и 52 и импульсы с входов 19 фиксации пути пройдут через открыт элементы И 55 и 59 и перебросят в единичное состояние первый разряд регистра 51 и второй разряд регист ра 52. Тактируемый потенциал пройд через элемент ИЛИ 63, элемент 64 з держки и сбросит в нулевое состоян регистры 65 и 66. Таким образом, п изойдет перезапись единичных состо ний из регистров 65 и 66 в регистр 51 и 52. После этого с выходов эле ментов И 61 и 62 сформируются нуле :вые потенциалы, которые закроют мн говходовые элементы И 74, 75, 78 и 79, а также И 76, 77, 80 и 81 узла 68 переключения направления.

Потенциалы с включенных разрядов регистров 51 и 52 откроют соответствующие ключи в двоичных коммутато рах 47-1, 47-2 и 47-5. Через пятый двоичный коммутатор 47-5 импульсы с

казано на фиг.4, соответствует соеди- входов 19 фиксации пути пройдут на

..-.. - Э а t l ч

нению накрест, а не прямо, как в первом каскаде 45. Поэтому откроются элементы также и 55 и 59.

После выбора возможных путей процессоры формируют на своих двунаправленных информационных шинах .импульсы, которые пройдут через выбранные пути многокаскадной дельта-сети 8 и появятся на соответствующих адресных выходах 18, с которых затем поступят на первые информационные входы узлов 10 фиксации захвата и откроют в них трехвходовой элемент , И 26. Одновременно с этим процессо50

55

необходимые входы 19 фиксации пути двоичных соединителей 41 и 42 первого каскада 45. В них произойдет по потенциалу, сформированному с управ ляющей ЭВМ 1 на тактируемом входе 23, аналогичный процесс перезаписи единичных состояний разрядов регист ров 65 и 66 через открытые элементы И 53 и 57 в регистры 51 и 52. После этого открываются соответствующие ключи в двоичных коммутаторах 47-1 47-2 и 47-5 двоичных соединителей 41 и 42. Импульсы с входов 19 фикса ции пути пройдут на соответствующие

5

0

5

0

5

0

ры 3 формируют нулевые потенциалы на своих двух управляющих выходах, в результате чего изменяется направ ление движения информации через узлы 9 изменения приоритета, так как в них уже открываются элементы И 31, 35 и 36. В свою очередь, по данным нулевым потенциалам возбуждаются выходы трехвходовых элементов И 26 в узлах 10 фиксации захвата, на информационных выходах которых появят ся импульсы, поступающие соответствующим образом на входы 19 фиксации пути многокаскадной дельта-сети 8. С этого момента управляющая ЭВМ 1 формирует потенциал на тактируемом входе 25 многокаскадной дельта- сети 8, который поступает на вторые тактируемые входы двоичных соединителей 43 и 44 второго каскада 46. По этому потенциалу включаются регист- ры 51 и 52 и импульсы с входов 19 f фиксации пути пройдут через открытые элементы И 55 и 59 и перебросят в единичное состояние первый разряд регистра 51 и второй разряд регистра 52. Тактируемый потенциал пройдет через элемент ИЛИ 63, элемент 64 задержки и сбросит в нулевое состояние регистры 65 и 66. Таким образом, произойдет перезапись единичных состояний из регистров 65 и 66 в регистры 51 и 52. После этого с выходов эле-: ментов И 61 и 62 сформируются нуле- :вые потенциалы, которые закроют многовходовые элементы И 74, 75, 78 и 79, а также И 76, 77, 80 и 81 узла 68 переключения направления.

Потенциалы с включенных разрядов регистров 51 и 52 откроют соответствующие ключи в двоичных коммутаторах 47-1, 47-2 и 47-5. Через пятый двоичный коммутатор 47-5 импульсы с

а t l ч

необходимые входы 19 фиксации пути двоичных соединителей 41 и 42 первого каскада 45. В них произойдет по потенциалу, сформированному с управляющей ЭВМ 1 на тактируемом входе 23, аналогичный процесс перезаписи единичных состояний разрядов регистров 65 и 66 через открытые элементы И 53 и 57 в регистры 51 и 52. После этого открываются соответствующие ключи в двоичных коммутаторах 47-1, 47-2 и 47-5 двоичных соединителей 41 и 42. Импульсы с входов 19 фиксации пути пройдут на соответствующие

выходы 20 фиксагдеи пути многокаскадной дельта-сети 8 и через открытые трехвходовые элементы И 27 перебросят требуемые триггеры 28 в узлах 10 фиксации захвата в единичное состояние. На единичных выходах триггеров 28 сформируются длинные потенциалы, по которым одновибраторы 29 образуют единичный импульс,поступающий далее в свой процессор 3 по цепочке: управляющий выход узла 10 фиксации захвата, открытый элемент И 35 узла 9 изменения приоритета и двунаправленная информационная шина процессора 3. Таким образом пришедший импульс подтвердит образование пути и процессор 3 далее выставляет требуемые данные на свои остальные информационные полюса, с которых коды поступают на соответствующие двунаправленные информационные шины 14 многокаскадной дельта-сети 8. В последней обмен информацией по образованным каналам производится через соответствующие ключи включенных пер вы двоичных коммутаторов 47-1 двоичных соединителей 41-44.

По окончании процесса обмена каж- дый процессор 3 может самостоятельно или индивидуально разобрать построенный ранее путь в многокаскадной дельта-сети 8. С этой целью каждый процессор 3 формирует на своих третьих и четвертых управляющих выходах потенциалы. Потенциал с третьего управляющего выхода процессора 3 проходит через многовхх довой элемент ИЛИ 11 и открывает двухвходовой элемент И 12, выход которого возбуждается в момент возникновения на втором тактируемом выходе управляющей ЭВМ 1 импульса, возбуждающего, в сво очередь, управляющий вход 13 многокаскадной дельта-сети 8. Импульс с управляющего входа 13 в каждом двоичном соединителе 41-44 открывает элементы И 54, 56, 58 и 60 (фиг.5). Одновременно с этим потенциал с четвертого управляющего выхода процессора 3 поступит на соответствующий вход 15 индивидуальной разборки и вход сброса своего узла 10 фиксации захвата, в которых сразу установится в нулевое состояние триггер 28. С соответствующего входа 15 индивидуальной разборки потенциал пройдет по своему пути в двоичных коммутаторах 47-2 двоичных соединителей 41,

44 или 42, аЗ. При этом он поступит с выходов двоичных коммутаторов 47-. на вторые входы одного из элементов И 54, 56, 58 или 60, возбудит один ( из выходов этих элементов,импульс с которого сбросит в нулевое состояние необходимый разряд регистров 51 и 52. В результате выполнения опиg санных процедур произойдет индивидуальная разборка процессором 3 своего ранее собранного пути.

Выше рассмотрена ситуация построения путей по двоичным кодам адре5 сов в многокаскадной дельта-сети 8, когда отсутствовали конфликтные ситуации. Однако в общем случае возможны на адресных входах 16 двоичных соединителей комбинации кодов 00

0 либо 11, т.е. возникает требование подключения разных групп входов к одной группе выходов, закодированной О или 1. Тогда в случае конфликтных ситуаций срабатывает блок 50

5 дешифрации приоритета, который формирует единичный потенциал с выхода элемента ИЛИ на свой первый выход, если на его входах возникают комбина4- ции кодов 00, 11 или 10. Следователь0 но, при равенстве приоритетов или когда первая группа входов двоичного соединителя 41 имеет более высокий приоритет, то подключают первую группу входов, а вторую группу входов отсекают. Наоборот, единичный потенциал на втором выходе в блоке 50 дешифрации приоритета возникает при появлении на его входах кода 01, по которому включается элемент И. В этом случае вторая группа входов будет иметь более высокий приоритет и она будет подключаться к одной из групп выходов двоичного соединителя 41 .

Раэбор приведенных конфликтных ситуаций осуществляется, как показано на фиг.5, в узле 68 переключения направления. Действительно, потенциал с первого выхода блока 50 дешифрации приоритета открывает многовходовые элементы И /4-77, с выходов которых есть обратные связи на входы друг друга. Так, если возбудятся одновременно выходы многовходовых элементов И 74 и 75, то потенциал с выхода И 75 заблокирует через инверсный вход элемент И 74, на выходе которого будет отсутствовать единичный потенциал. Аналогичным1 образом блокиру5

0

5

0

5

ется единичный потенциал на выходе многовходового элемента И 76 за счет наличия единичного потенциала на выходе многовходового элемента И 77, поступающего на инверсный вход И 76. Аналогичный анализ происходит на входах многовходовых элементов И 78-81, которые открываются потенциалом с вт рого выхода блока 50 дешифрации приоритета. Так, единичный потенциал с выхода многовходового элемента И 78 закрывает через инверсный вход мно- говходовый элемент И 79 и открывает многовходовые элементы И 74 и 75, а едини лный потенциал с выхода многовходового элемента И 80 - многовхо- цовый элемент И 81 и открывает многовходовые элемен-ы И 76 и 77.

При каждой фиксации пути возбуждается выход элемента И 36 в соответствующем узле 9 измэнения приоритета, импульс которого сбрасывает в нулевое состояние счетчик 38. В том случае, если сигнал фиксации пути не возбудил выход элемента И 36, то предыдущий код приоритета остается в счетчике 38, и поэтому на следующем шаге поиска данный процессор 3 будет иметь более высокий приоритет чем тот, который уже образовал на предыдущем этапе свой путь и участ- вовгп в обмене информацией между выбранным другим процессором 3 устройства. Поэтому в данном устройстве для формирования и анализа семантических сетей имеется возможность с помощыо управляющей ЭВМ 1 динамически изменять приоритеты подключаемых процессоров 3. За счет этого (по сравнению с базовым вариантом, например многопроцессорной ЭВМ с общей магистралью, на которую одновременно подключаются Н процессоров и локальные блоки памяти) повышается производительность при обработке структурно-сложных и больших размеров семантических сетей, обеспечивается равномерная загрузка процессоров 3, что повышает надежность при реализации сильно связанных участков программ. В разультате параллельной обработки знаний, организованных ь виде семантических сетей, рассредоточенных N блоках локальных памяти, расширяются функциональные возможности.

Преимущество предлагаемого устройства особенно видно на примере построения и анагиза н нем пирами

0

5

0

дальных семантических сетей (ПС), отличительная особенность которых состоит в возможности эффективного отображения динамических процессов, протекающих в реальных средах. Модели реальных сред на основе ПС отражают иерархическую структуру составных объектов, например ситуаций, являющихся композициями других объектов и отношений. Это дает возможность значительно сократить поиск нужной информации за счет его локализации в относительно небольшом участке модели среды. ПС обеспечивает экономное, иерархическое и ассоциативное хранение знаний о задачах и средах. При построении ПС автоматически устанавливают связи между объектами путем выделения пересечений описаний объектов и ввода в сеть элементов, соответствующих этим пересечениям. На ПС определены процессы формирования понятий, в основе кото-; рых лежат методы индуктивного обучения. Информация в ПС хранится не в виде кодов, а в виде структур, отображающих компоненты объектов и их связи.

На предлагаемом устройстве можно реализовать, к примеру, горизонтальное распараллеливание ПС, при котором сеть располагается в нескольких блоках локальной памяти (ЛП) , В пределах каждой ЛП 5 реализация алгоритма построения сети и операций ассоциативного анализа осуществляется отдельным процессором 3. В каждой из ЛП входные элементы сети (рецепторы) дублируются, а связи и узлы (ассоциативные элементы) рав- номерьо распределены.:

Наиболее удобной формой представления ПС в ЛП 5 являются списковые структуры. Входы и выходы ассоциативных элементов образуют ассоциативные списки, указатели на головы которых содержатся в ячейке ассоциа- тивного элемента (A3). В ячейке АЭ имеются также зоны, содержащие -имя ys ла, метки и т.п. За счет равномерного распределения АЭ и их связей по различным ЛП операции просмотра сети и в тол нения правил алгоритма построения распараллеливаются по горизонтали, несмотря на то,что в пределах каждой ЛП операции выполняются п следовательно по вертикали.

Если при выполнении операций просмотра сети процессором 3 в одной ЛП встречается адресная ссылка на дргую JDI, то, она передает соответствующему процессору 3 этот адрес по образованному автоматически каналу в многокаскадной дельта-сети 8, а сама продолжает работу дальше. Процессор 3,получивший адресную ссылку, выполняет эту же операцию в своей ЛП параллельно с передающей. Возможность такой параллельной коммутации процессоров 3 по принципу каждый с каждым обеспечивается введением многокаскадной дельта-сети 8, программируемого приоритетного блока 6 и фомирователя 7 подтверждения захвата.

Алгоритм построения ПС в устройстве работает в соответствии со следующими правилами:

Правило I. Если при вводе нового описания в сети имеются частично возбужденные A3, связанные по входам с двумя и более возбужденными элементами, то эти связи ликвидируются и в сеть вводится новый АЭ,входы кото- рого соединяются с выходами возбужденных элементов, а выход - с одним из пассивных входов частично возбужденного АЭ. Новый АЭ находится в состоянии возбуждения. После введения новых АЭ во все участки сети, где выполняется условие правила I, выполняется правило II.

Правило II. Если в сети имеется более одного полностью возбужденного элемента (рецепторног о или ассоциативного) , то к сети присоединяется новый АЭ, входы которого соединяются с выходами возбужденных элементов, не имеющих связей по входу с другими возбужденными элементами. Новый АЭ находится в возбужденном состоянии и его описание помещается в той ЛП, базовый адрес которой определяется по формуле А ;+( mod щ (А,1 + + 1), где N - число ЛП в устройстве.

Формула изобретения

Устройство для формирования и анализа семантических сетей, содержащее управляющую ЭВМ, N процессоров с блоками локальной памяти и сетевой коммутатор для обмена сообщениями, причем адресные, управляющие и информационные входы-выходы процессоров с первого по N-й соеди0

5

0

5

Q

,

0

5

0

5

нены с соответствующими входами-выходами управляющей ЭВМ через линии шины системного интерфейса, с соответствующими входами-выходами сетевого коммутатора для обмена сообщениями через двунаправленные информационные шины, отличающееся тем, что, с целью повышения производительности за счет параллельной и приоритетной перестройки связей в ходе решения задачи, в него введены программируемый приоритетный блок и формирователь подтверждения захвата, причем первый тактирующий выход управляющей ЭВМ соединен с входом синхронизации программируемого приоритетного блока, второй тактирующий выход соединен с входом выборки программируемого приоритетного блока, одноименный выход которого соединен с входом выборки сетевого коммутатора для обмена сообщениями, адресный выход управляющей ЭВМ соединен с одноименным входом программируемого приоритетного блока, первый и второй управляющие выходы N-ro процессора соединены с N-ми входами управления включением программируемого приоритетного блока и формирователя подтверждения захвата, адресный выход сетевого коммутатора для обмена сообщениями подключен к одноименному входу формирователя подтверждения захвата, вход и выход фиксации пути которого подключены к одноименным соответственно выходу и входу сетевого коммутатора для обмена сообщениями, третий управляющий выход готовности N-ro процессора подключен к N-му разряду входа готовности программируемого приоритетного блока, а выход индивидуальной разборки N-ro процессора подключен к N-му разряду одноименного входа сетевого коммутатора для обмена сообщениями и N-му входу сброса формирователя подтверждения захвата, второй адресный выход сетевого коммутатора для обмена сообщениями соединен с одноименным входом программируемого приоритетного блока, выход кода приоритета которого соединен с одноименным входом сетевого коммутатора для обмена сообщениями, вход и выход фиксации пути которого соединены с соответствующими выходом и входом формирователя подтверждения захвата,-выход общего сброса управляющей ЭВМ

15-16

1614289

подключен к входу сброса сетевого первого по четвертый которого соеди- коммутатора для обмена сообщениями, йены с одноименными выходами управля- входы выбора направления передачи с ющёй ЭВМ.

Фиг. .1

Фи..3

щ

Фиг. 2

Й SSSS Ј8

S Sfc ЯЯ

14/