Система взаимораспределения ресурсов

 

Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для решения задач по взаимораспределению памяти в вычислительных комплексах. Технический результат заключается в расширении функциональных возможностей системы. Устройство содержит блок управления, 1-й, 2-й и n-й локализованные центры, магистраль передачи данных. 8 ил.

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

Известен "Контроллер обмена" (патент N 2032214, 1993 г., Бюл. N9), позволяющий осуществлять обмен информации между блоками.

Известен также "Способ суммирования чисел" (патент N 2145113, 1998 г., Бюл. N3), позволяющий производить суммирование чисел.

В качестве прототипа выбрано "Устройство для распределения заданий по процессорам" (патент N 2017206, 1994 г., Бюл. N14), позволяющее автоматическое преобразование логических адресов процессоров в физические в многозаданном режиме и обработки возникающих сбоев.

Задача заключалась в следующем: 1) расширить функциональные возможности работы системы; 2) упростить алгоритм блока управления; 3) расширить круг решаемых задач.

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

Решение задачи осуществляется тем, что система взаимораспределения ресурсов, содержащая блок управления, отличается тем, что дополнительно введены: 1-ый, 2-ой и n-ый локализованные центры, магистраль передачи данных, причем первый информационный выход блока управления соединен со вторым информационным входом локализованного центра ЛЦ1, первый информационный вход которого соединен с первым информационным выходом магистрали передачи данных, второй информационный выход которой соединен с первым информационным входом локализованного центра ЛЦ2, информационный выход которого соединен со вторым информационным входом магистрали передачи данных, n-ый информационный выход которой соединен с первым информационным входом локализованного центра ЛЦn, информационный выход которого соединен с n-ым информационным входом магистрали передачи данных, первый информационный вход которой соединен с информационным выходом первого локализованного центра ЛЦ1, второй информационный вход локализованного центра ЛЦ2 соединен со вторым информационным выходом блока управления, третий информационный выход которого соединен со вторым информационным входом n-ого локализованного центра ЛЦn, первый и второй управляющие входы "ПУСК" и "СБРОС" блока управления являются внешними входами устройства.

ЛЦ1, ЛЦ2, ..., ЛЦn - блоки служат для формирования избыточного ресурса, который необходимо распределить по ассоциативно-запоминающим устройствам (АЗУ) других блоков, а также для получения хранения и анализа определенного количества ресурса (продукта), полученного от других блоков.

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

БУ - блок служит для управления устройством.

Теоретический платформой данного изобретения является структурно-функциональное направление современной теории систем. В рассматриваемом случае под системой понимается множество локальных подсистем (вершин графа) и обменные потоки (дуги графа) или результаты функционирования названных структурных компонентов. Определим норму взаимодействия и функционирования структурных компонентов, которые условимся называть локализованными центрами (ЛЦ). Каждый локализованный центр будем представлять в виде черного ящика с множеством входов мощностью Р и множеством выходов мощностью S. По каждому входу определим дефицит соответствующего материального или информационного потока, а по каждому выходу скорость формирования материальных или информационных ресурсов заданного локализованного узла. Система локализованных узлов функционирует оптимально тогда, когда минимизирована при заданных ограничениях следующая функция: MINi ≤ Xj, (1) где MINi - объем ресурса; Xj - объем "свободного места" в локализованном центре; i - 1, 2, ..., N - число оперативно-запоминающих устройств в локализованном центре (ЛЦ); j - 1, 2, ..., Т - число ассоциативно-запоминающих устройств в локализованном центре (ЛЦ).

В оперативно-запоминающее устройство каждого ЛЦ предварительно записывается двоичный код, который соответствует объему избыточного ресурса. В ассоциативно-запоминающее устройство ЛЦ также предварительно записывается информация в виде двоичного кода, соответствующая наличию объема "свободного" места. Задача системы взаимораспределения заключается в нахождении места в АЗУ системы избыточного ресурса и передачи его для дальнейшего анализа. Если объем избыточного ресурса больше, чем наличие свободного места, то перераспределения ресурса не происходит. Процесс передачи избытка на свободное место будет возможен тогда, когда выполняется условие (1), т.е. объем избыточного ресурса равен или меньше предоставленного объема "свободного" места.

Таким образом, назначение системы взаимораспределения ресурсов должно обеспечивать такой режим управления материальными потоками или информацией, который обеспечивает оптимальное сбалансированное функционирование системы взаимодействующих локализованных узлов (СВЛУ).

При рассмотрении СВЛУ необходимо решить одну из основных задач по взаимораспределению ресурсов (продуктов) между локализованными центрами (ЛЦ). Рассмотрим один локализованный центр (ЛЦ) в отдельности. ЛЦ производит какие-то продукты (сельхоз, промышленные, добывающие, перерабатывающие и т.д.). Введем обозначения РС1, РС2, РС3, ..., РСn. У этого ЛЦ имеются места для хранения этих или других ресурсов (продуктов), обозначим как СМ1, СМ2, CM3, ..., CMt. Возможна ситуация когда "свободного" места у данного ЛЦ не хватает для хранения ресурсов (продуктов), т.е. имеет место соотношение XzPCi > УhCMt, (2)
где Х - количество избыточного ресурса;
У - количественное выражение объема свободного места;
z - порядковый номер избыточного ресурса;
h - порядковый номер объема свободного места.

Такую ситуацию с продуктами (ресурсами) запишем следующим образом:

Над чертой (в числителе) перечисляются, через знак #, все продукты (ресурсы) находящиеся в избытке, а также указано их количество. Под чертой (в знаменателе) перечисляется наличие свободного места в ЛЦ. Определено наличие свободного места и указан его порядковый номер. Такую запись будем называть избыток - свободное место. Представим систему состоящую из 4 локализованных центров. Введем некоторые обозначения и ограничения: каждый локализованный центр (ЛЦ) должен иметь порядковый номер - натуральное число, все продукты (ресурсы) будем считать дискретными, т.е. их количества измеряются натуральными числами, ресурсы (продукты), записанные в числителе одного локализованного центра (избыток), не должны быть записаны в знаменателе (свободное место).

Допустим система состоит из 5-ти локализованных центров. Количество продуктов (ресурсов) исчисляется числом 10. Запишем каждый локализованный центр с точки зрения ситуации избыток - свободное место с указанием количества ресурса и объемом свободного места.

При этой записи происходит однозначное определение избытка ресурса каждого ЛЦ и "свободного" места соответственно.

Ход решения задачи иллюстрирует схема (см. в конце описания), наглядно поясняющая алгоритм работы системы взаимораспределения ресурсов. Выпишем все "свободные" места со второго по пятый локализованный центр ЛЦ в строку. Выбирается первый избыточный ресурс РС1 1-ого локализованного центра, затем сравнивается количественный эквивалент этого ресурса со всеми "свободными" местами остальных локализованных центров. В ассоциативно-запоминающем устройстве осуществляется несколько видов сравнений: определение максимального числа, минимального, сравнение на равенство, на больше или равно. Первый режим сравнения целесообразно выбирать в качестве поиска на равенство. Если равенство установлено, то выполняется пересылка избыточного ресурса PC на "свободное" место в АЗУ другого локализованного центра. Если получен отрицательный результат сравнения, то АЗУ системы производят операцию сравнения на ближайшее большее значение. Если получен положительный результат сравнения, то на сумматоре-вычитателе находится разность между количеством избыточного ресурса и объемом "свободного" места. В это же АЗУ, где установлен положительный результат сравнения, записывается избыточный ресурс и по другому адресу записывается полученная разность. Процесс сравнения и перераспределения продолжается до тех пор, пока не будут просмотрены все избыточные ресурсы всех локализованных центров и определены все возможные варианты эффективного перераспределения ресурсов. Если не будет положительного результата сравнения ни в первом случае, ни во втором случае, то избыточный ресурс останется на прежнем месте, перераспределение в этом случае не выполняется.

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

На фиг. 1 изображена структурная схема системы взаимораспределения ресурсов.

На фиг.2 представлен вариант технической реализации локализованного центра ЛЦ1.

На фиг. 3 представлен вариант технической реализации блока памяти БП1 - определения избыточного ресурса в ОЗУ блока, а также для хранения ресурса в АЗУ блока локализованного центра.

На фиг.4 представлена структура сигнала управления СУП1. Этот информационный сигнал состоит из шести частей. Каждая составляющая часть представляет собой тоже информационный сигнал.

На фиг. 5 представлен вариант технической реализации блоков: начальной установки и формирования адресов для записи информации в ОЗУ блока памяти - БНУА1, определения адреса для считывания и записи в АЗУ полученной информации - БПУ1.

На фиг.6 представлена функциональная схема блока анализа БАН1.

На фиг.7 - содержательная ГСА работы устройства.

На фиг.8 - размеченная ГСА работы устройства.

Система взаимораспределения ресурсов (фиг.1) содержит локализованный центр 1 ЛЦ1, локализованный центр 2 ЛЦ2, локализованный центр 3 ЛЦn, магистраль 4 передачи данных, блок 5 управления.

Для описания алгоритма работы блока 5 управления используются следующие идентификаторы.

Список индентификаторов.

1. ЛЦ1 - первый локализованный центр.

2. ЛЦ2 - второй локализованный центр.

3. ЛЦn - n-локализованный центр.

4. Магистраль передачи данных.

5. БУ - блок управления.

6. ВХ1 - первый информационный сигнал.

7. ВХ2 - второй информационный сигнал.

8. BXn - n-ый информационный сигнал.

9. ВЫХ1 - первый выходной информационный сигнал.

10. ВЫХ2 - второй выходной информационный сигнал.

11. ВЫХn - n-ый выходной информационный сигнал.

12. СУП1 - первый сигнал управления.

13. СУП2 - второй сигнал управления.

14. СУПn - n-ый сигнал управления.

15. BXi - i-ый входной информационный сигнал.

16. KЛ1 - 1-ый электронный ключ.

17. ВХДi - 1-ый информационный выход (выход с электронного ключа).

18. СНУ1 - первый информационный сигнал начальной установки первого блока памяти.

19. БП1 - первый блок памяти.

20. СС1 - сигнал сравнения (на совпадения или на больше или равно блока БП1).

21. РР1 - информационный выход блока памяти БП1.

22. СУМ-ВЫЧ1 - первый сумматор-вычитатель блока ЛЦ1.

23. РЗ1 - результат разности между i-выходным информационным сигналом ВХДi и информационным выходом блока памяти БП1 РР1.

24. БНУА - блок начальной установки и формирования адресов строк и столбцов оперативно-запоминающего устройства ОЗУ.

25. НУА1 - первый информационный сигнал начальной установки и формирования адресов блока БНУА1.

26. ОЗУ - оперативно-запоминающее устройство.

27. С/З1 - сигналы записи/считывания.

28. ВК1 - сигнал выбор микросхемы.

29. ШД - шина данных ОЗУ блока БП1.

30. ШАС - шина адреса строк ОЗУ блока БП1.

31. ШАСТ - шина адреса столбцов ОЗУ блока БП1.

32. СУО1 - первый информационный сигнал выбора кристалла и считывания/записи ОЗУ.

33. БПУ - блок первоначальной установки и формирования адресов строк и столбцов ассоциативно-запоминающего устройства АЗУ блока памяти БП1.

34. СНУ1 - информационный сигнал обнуления счетчиков и прямоугольные импульсы блока БПУ1.

35. ИНУ - выходной информационный сигнал блока БПУ, состоящий из шины адреса и шины данных.

36. ИЛИ - логический элемент ИЛИ.

37. РЗ1 - результат разности, поступивший с выхода сумматора-вычитателя блока ЛЦ1.

38. ВИР - выходная информация с выхода логического элемента ИЛИ.

39. АЗУ - ассоциативно-запоминающее устройство блока памяти БП1.

40. СУА1 - информационный сигнал маскирования и управления записью и считывания информации из АЗУ.

41. УПА1 - информационный сигнал управления работой арифметического процессора АРЛП1 блока анализа БАН1.

42. УПС1 - информационный сигнал управления работой специализированных устройств символьной обработки ПРСО1 блока анализа БАН1.

43. СчУД - двоичный счетчик, формирующий шину данных блока БНУА1.

44. ТИ1 - тактовые импульсы счетчика СчУД.

45. УО1 - сигнал обнуления счетчика СчУД.

46. ШД1 - шина данных, выходной сигнал счетчика СчУД.

47. СчСЛ - двоичный счетчик, формирующий адреса строк ОЗУ блока БНУА1.

48. ГИ1 - генератор импульсов счетчика СчСЛ.

49. СБ1 - сигнал обнуления счетчика СчСЛ.

50. АСТ1 - адреса строк ОЗУ блока памяти БП1.

51. СчСТ - двоичный счетчик, формирующий адреса столбцов ОЗУ блока БНУА1.

52. ГИМ1 - прямоугольные импульсы счетчика СчСТ.

53. СРС1 - сигнал обнуления счетчика СчСТ.

54. АСТл1 - адреса столбцов ОЗУ блока памяти БП1.

55. СчД - двоичный счетчик, формирующий шину данных АЗУ блока памяти БП1.

56. ПИ1 - прямоугольные импульсы счетчика СчД.

57. СБО1 - сигнал обнуления двоичного счетчика СчД.

58. ШДА1 - шина данных АЗУ блока памяти БП1.

59. СчА - двоичный счетчик, формирующий адреса АЗУ блока памяти БП1.

60. ПИМ1 - прямоугольные импульсы счетчика СчА.

61. СБР1 - сигнал обнуления двоичного счетчика СчА.

62. ШАА1 - адресная шина АЗУ блока памяти БП1.

63. АРЛП1 - арифметический процессор блока анализа БАН1.

64. ПРСО1 - специализированные устройства символьной обработки.

65. АРЛ1 - выходная информация арифметического процессора АРЛП1.

66. СИМ1 - выходная информация специализированных устройств символьной обработки ПРСО1.

67. Стандартное устройство вывода.

68. РЕЗ1 - итоговый результат обработки блока анализа БАН1.

69. ПР - признак выхода из цикла при загрузки всех запоминающих устройств системы.

70. АПР - признак работы арифметического процессора.

71. РАВ - сравнения данных в АЗУ на равенство.

72. W/R - сигнал считывания/записи АЗУ блока памяти БП1.

73. М0 - 0-ой входной сигнал маски в АЗУ блока памяти.

74. M1 - 1-ый входной сигнал маски в АЗУ блока памяти.

75. М2 - 2-ой входной сигнал маски в АЗУ блока памяти.

76. М3 - 3-ий входной сигнал маски в АЗУ блока памяти.

77. N - конечное количество оперативно-запоминающих устройств в системе.

78. Т - конечное количество ассоциативно-запоминающих устройств в системе.

79. i - счетчик текущего значения количества оперативно-запоминающих устройств в системе.

80. j - счетчик текущего значения количества ассоциативно-запоминающих устройств в системе.

Работа алгоритма системы взаимораспределения ресурсов.

Содержательная ГСА управления приведена на фиг.7 и отражает работу блока управления (фиг.1).

По сигналам УОО и СБРОС:=1 (блоки 2 и 3 схемы алгоритма) (фиг.1) происходит установка в нуль всех элементов памяти устройства.

В блоке 4 алгоритма происходит анализ сигнала ПУСК. По этой команде начинается работа всей системы взаимораспределения ресурсов.

В блоке 5 алгоритма происходит предварительная установка счетчиков i и j в состояние единицу i:=1, j:=1. Значение счетчика i изменяется от единицы до значения N и означает количество всех оперативно-запоминающих устройств системы. Значение счетчика j изменяется от единицы до значения Т и означает количество всех ассоциативно-запоминающих устройств системы. По сигналам УO: =1, СБ:=1, СБС:=1, СБО:=1, СБР:=1 происходит обнуление всех элементов памяти системы. Обнуляются счетчики блоков БНУА1 и БПУ1.

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

В блоке 6 алгоритма происходит анализ признака ПР - все запоминающие устройства загружены или нет. Если ПР принимает значение НЕТ, то происходит переход на блок 11 алгоритма и система начинает работать по взаимораспределению ресурсов. Если ПР равен ДА, то цикл загрузки еще не завершен и происходит предварительная запись значений ресурса в ОЗУ и АЗУ системы. Под условием ПР следует понимать результат логической функции (i ≤ N and j ≤ Т). Выход из цикла осуществляется при загрузке всех запоминающих устройств системы предварительной (начальной) информацией.

В блоке 7 алгоритма на входы счетчиков СчУД, СчСЛ, СчСТ, СчД, СчА блоков БНУА1 и БПУ1 подаются сигналы прямоугольных импульсов. Происходит подсчитывание двоичными счетчиками количества этих импульсов: ТИi:=1; ПИi:=1; ГИi: =1; ПИМi:=1; ГИМi:=1.

В блоке 8 алгоритма происходит запись информации в оперативно-запоминающие устройства (ОЗУ). При подачи сигналов на разрешающие входы значение нуля ВКi:=0; С/Зi:=0 происходит разрешение записи информации в ОЗУ. На входную шину ОЗУi поступает информационный сигнал ШД (шина данных) ОЗУi:=ШД. На адресные входы ОЗУi подаются адреса строк и столбцов: ОЗУi:=ШАС; ОЗУi:=ШАСТ.

В блоке 9 алгоритма происходит разрешение записи и запись информации в ассоциативно-запоминающие устройства системы. По сигналу WRj:=0 осуществляется запись в AЗУj информации. По командам: AЗУj:=ШДAj, AЗУj:=ШAAj, AЗУj:=CУAj осуществляется подача на шину данных, адресные входы и входы маски соответствующей информации: данных, адресов и сигнала маски.

В блоке 10 счетчики i и j изменяют свое значение на единицу: i:=i+1, j:= j+1. При этом осуществляется переход на блок 6 алгоритма.

В блоке 11 алгоритма счетчики i и j принимают единичные значения: i:=1, j:=1.

Блоки 12-22 представляют собой процесс перераспределения ресурсов между локализованными центрами ЛЦ. Информация считывается из ОЗУi и записывается в соответствующие AЗУj системы.

В блоке 12 алгоритма анализируется признак ПР - выход из цикла. По выходу НЕТ происходит переход на блок 23 алгоритма. В этом случае все оперативно-запоминающие устройства (ОЗУ) и ассоциативно-запоминающие устройства (АЗУ) системы просмотрены. Выход ДА означает, что перераспределение ресурсов между локализованными центрами продолжается. Признак выхода из цикла следует понимать как результат логической операции конъюнкции ПР=(i ≤ N and j ≤ T).

В блоке 13 алгоритма на входы оперативно-запоминающих устройств подаются разрешающие сигналы для считывания информации из ОЗУ системы: сигнал считывание/запись принимает значение единицы С/Зi:=1, а сигнал выбор микросхемы равен нулю ВКi:=0.

В блоке 14 алгоритма по командам: ОЗУi:=ШАС, ОЗУi:=ШАСТ, МАГ:=ВЫХi происходит подача на входы оперативно-запоминающих устройств адресов строк и адресов столбцов из блока БНУА, а также магистраль передачи данных принимает значение выходных данных из ОЗУi системы. Происходит процесс считывания информации из оперативно-запоминающих устройств.

В блоке 15 алгоритма по командам WRj:=0, AЗУj:=BXi происходит подача разрешающих сигналов на записывание информации в ассоциативно-запоминающие устройства (АЗУ) системы и осуществляется запись поступивших на входную шину AЗУj данных.

В блоке 16 алгоритма происходит анализ сигнала сравнения СС. Если сигнал сравнения СС равен единице, то происходит переход на блок 18 алгоритма, в системе произошло совпадение по равенству или больше или равно. Если СС равен нулю, то это означает, что совпадения на равенство или на больше или равно не произошло.

В блоке 17 алгоритма по команде j:=j+1 происходит увеличение счетчика j - количества ассоциативно-запоминающих устройств системы - на единицу, т.е. переход к следующему АЗУ. По алгоритму осуществляется переход на блок 12.

В блоке 18 алгоритма анализируется условие РАВ на равенство или на больше или равно входных данных ОЗУi и содержимого AЗУj. Условие РАВ анализируется только тогда, когда произошло совпадение на равенство или на больше или равно, сигнал СС блок 18 алгоритма равен только единице. Если произошло сравнение на равенство, признак РАВ соответствует выходу ДА, то осуществляется переход на блок 21 алгоритма. Если произошло сравнение на больше или равно данных - выход условной вершины 18 по НЕТ, то переход будет осуществлен на блок 19 алгоритма.

В блоке 19 алгоритма по команде PЗj:=BXДi-PPj происходит определение разности входного сигнала ВХДi и содержимой ячейки AЗУj - информационного сигнала PPj. Такая операция производится в случае сравнение данных на больше или равно в AЗУj, при этом PPj ≥ BXДi. По алгоритму работы системы входная информация ВХДi записывается по установленному адресу, а полученная разность PЗj записывается в этот же AЗУj, но по другому адресу.

В блоке 20 алгоритма по командам: WR:=0, АЗУj:=ВХДi, AЗУj:=PЗj происходит разрешение на записывание информации в AЗУj подачей нуля на вход WR, а также осуществляется запись входной информации ВХДi и полученной разности PЗj в AЗУj. При этом осуществляется переход на блок 22 алгоритма.

В блоке 21 алгоритма по командам WR:=0 и AЗУj:=BXi происходит разрешение на запись информации в AЗУj, и по установленному адресу записываются входные данные ВХi в ассоциативно-запоминающее устройство (AЗУj).

В блоке 22 алгоритма происходит увеличение счетчиков i и j на единицу: i:=i+1; j:=j+1. Таким образом, осуществляется считывание информации следующего оперативно-запоминающего устройства и ассоциативно-запоминающего устройства системы. По алгоритму осуществляется переход на блок 12.

В блоке 23 алгоритма счетчик количества ассоциативно-запоминающих устройств j устанавливается в начальное состояние - единицу j:=1.

В блоках 24-29 алгоритма организован цикл, в котором осуществляется процесс анализа перераспределенной информации системы. Информация считывается из ассоциативно-запоминающих устройств (АЗУ) и обрабатывается в блоке БАН анализа (фиг.6) системы.

В блоке 24 происходит сравнение текущего значения счетчика j с конечным значением количества ассоциативно-запоминающих устройств системы - Т. Если j > T, то осуществляется переход по алгоритму на блок 30. Это условие является выходом из цикла. Если j ≤ T, то процесс обработки информации продолжается блоками анализа системы. Это условие для продолжения работы цикла и означает, что не вся информация из АЗУ обработана.

В блоке 25 алгоритма происходит считывание информации из ассоциативно-запоминающих устройств системы для дальнейшей обработки в блоках анализа. По командам: ПИMj: =1, AЗУj:=ШAAj происходит подача на счетчик CчAj блока БПУj (фиг. 5) прямоугольных импульсов. На выходе двоичного счетчика формируются адреса ШAAj ассоциативно-запоминающих устройств (АЗУ). По этому адресу происходит считывание информации из AЗУj системы. По командам WR:=1, БAHj:=PPj осуществляется подача разрешающего сигнала на считывание информации из AЗУj и передача ее в блок анализа БAHj для дальнейшей обработки (фиг.6).

В блоке 26 алгоритма осуществляется анализ признака АРП. Этот признак соответствует работе арифметических процессоров APЛПj или анализируется информация из AЗУj процессорами символьной обработки ПPCOj блока анализа БAHj (фиг. 6). Если выход этого блока соответствует утверждению ДА, то выходная информация из AЗУj обрабатывается арифметическим процессором APЛПj. Если выход соответствует НЕТ, то данные обрабатываются процессором символьной обработки ПPCOj.

В блоке 27 алгоритма происходит подача на вход арифметического процессора APЛПj сигналов управления по команде APЛПj:=УПAj из блока управления. По команде APЛПj:=PPj на вход арифметического процессора поступает информационный сигнал для дальнейшей обработки.

В блоке 28 алгоритма осуществляется подача управляющих сигналов на вход процессора символьной обработки ПPCOj по команде ПPCOj:=УПCj. По команде ПPCOj: = PPj поступает на вход процессора символьной обработки информация из ассоциативно-запоминающих устройств AЗУj блока памяти БПj.

В блоке 29 алгоритма счетчик j изменяет свое значение на единицу по команде j:=j+1. При этом осуществляется переход на блок 24 алгоритма.

Блок 30 алгоритма соответствует конечной вершине блок-схемы алгоритма.

Работа устройства поиска вхождений заключается в следующем.

Внешние управляющие сигналы "Пуск" и "Сброс" поступают в блок 5 управления. Работа системы заключается в следующем.

Каждый локализованный центр (ЛЦ) на первой стадии работы системы должен определиться со своими ресурсами (продуктами). Определить какие ресурсы будут в избытке и в каком количестве. Двоичный эквивалент количества избыточного ресурса будет предварительно записан в оперативно-запоминающее устройство каждого локализованного центра. Также каждый центр формирует объемы "свободных" мест. Эта информация записывается в виде двоичного кода в ассоциативно-запоминающее устройство каждого ЛЦ.

Система взаимораспределения ресурсов может работать в двух режимах: безприоритетном и приоритетном. Безприоритетный режим работы системы осуществляется по очередном порядке перераспределения ресурсов. Этот режим характерен тем, что процесс считывания и сравнения двоичного эквивалента количества избыточного продукта (ресурса) из ОЗУ локализованного центра будет проходить с 1-ого по n-ый в очередном порядке. Сначала происходит перераспределение ресурсов 1-ого центра, затем 2-ого и т.д. до последнего.

Второй режим определяется приоритетным считыванием и сравнением ресурсов из ОЗУ локализованных центров. Блок управления может формировать сигналы управления выбором микросхемы и считывание/запись ОЗУ ЛЦ системы в приоритетном порядке. Вначале с наивысшим приоритетом, затем по убыванию. Отметим, что первым считывается 2-ой ресурс из 1-ого ОЗУ 1-ого ЛЦ. Затем 3-ий ресурс из 2-ого ОЗУ 3-ого ЛЦ и т.д. Это пример приоритетного перераспределения ресурсов представленной системы. Режимы работы системы формируются в блоке управления. Синтез комбинационной схемы приоритетного дешифратора не представляет затруднений [6, 7].

Локализованный центр ЛЦ1 состоит (фиг.2) из электронного ключа, блока памяти и сумматора-вычитателя. На фиг.2 показана структура первого локализованного центра ЛЦ1. Все локализованные центры системы состоят из однотипных блоков, выполняющих одинаковые функции. На вход блока памяти БП1 поступает входной сигнал (двоичный код избыточного ресурса) - ВХi. Одновременно этот сигнал поступает на вход электронного ключа КЛ1. На остальные входы блока памяти БП поступают информационные входы из блока управления: СУА1 - информационный сигнал маскирования и управления записью и считывания информации из АЗУ, СНУ1 - информационный сигнал обнуления счетчиков и прямоугольные импульсы блока БПУ1 предварительной установки, СУO1 - информационный сигнал выбора кристалла и считывания/записи из ОЗУ, НУА1 - информационный сигнал начальной установки и формирования адресов блока БНУА1 начальной установки и адреса. В блоке памяти БП1 происходит сравнение вначале на равенство входного сигнала ВХi с предварительно установленной информацией в АЗУ локализованных центров системы. Если результат сравнения положительный, то входная информация записывается в АЗУ этого локализованного центра. Если результат сравнения отрицательный, то устанавливается режим сравнения во всех АЗУ системы на ближайшее большее. Если результат сравнения положительный, то выходной сигнал CCi - сравнения устанавливается в единицу i-ого АЗУ j-ого локализованного центра. Это означает, что "свободного" места имеется больше, чем затребовано при распределении избыточного ресурса. Электронный ключ КЛi открывается и входной сигнал ВХДi поступает на вход сумматора-вычитателя. На второй вход сумматора-вычитателя поступает двоичный код РР из АЗУ блока памяти БПi (фиг.2). При этом справедливо неравенство:
РР > Bxi. (9)
На выходе сумматора-вычитателя СУМ-ВЫЧi формируется разность PЗj между входными сигналами: PPj и BXi. Входная информация BXi и полученная разность PЗj записываются по соответствующим адресам в AЗУj по приходу сигнала из блока управления CУAj данного локализованного центра ЛЦk (фиг.2). Если результат сравнения отрицательный, то это означает что "свободного" места меньше, чем необходимо, перераспределение ресурса в этом случае не происходит. По алгоритму работы системы выполняется считывание из i-ого ОЗУ по очередному адресу следующего двоичного кода, эквивалентного избыточному ресурсу.

Блок памяти БП1 (фиг. 3) состоит из оперативно-запоминающих устройств ОЗУ, ассоциативно-запоминающих устройств АЗУ, блока БНУА начальной установки и формирования адресов строк и столбцов оперативно-запоминающего устройства ОЗУ, БПУ - блок первоначальной установки и формирования адресов строк и столбцов ассоциативно-запоминающего устройства АЗУ, логической схемы ИЛИ. Перед перераспределением ресурсов, т. е. основной работы системы в ОЗУ и АЗУ записывается предварительная информация. В ОЗУ вносится информация об избытке ресурса (продукта). В АЗУ записывается двоичный код, соответствующий объему "свободного" места в локализованном центре ЛЦ. По приходу из блока управления информационного сигнала НУА1 - сигнала начальной установки и формирования адресов (фиг.3) вначале происходит обнуление счетчиков, формирующих адреса для записи информации в ОЗУ. Счетчики блока БНУА1: СчУД1, СчСЛ2, СчСТ3 (фиг.5) установлены в нулевое состояние. По приходу сигналов из блока управления: ТИ1, ГИ1, ГИМ1 блока БНУА1 на входы счетчиков СчУД1, СчСЛ2, СчСТ3 формируются шины данных ШД, адреса строк ШАС, а также адреса столбцов ШАСТ, которые поступают на вход ОЗУ блока БП1 памяти. По адресам строк и столбцов данные записываются в оперативно-запоминающее устройство блока памяти. Эти данные соответствуют информации об избыточном ресурсе конкретного локализованного центра ЛЦ. Запись в ОЗУ происходит при установлении сигналов выбора микросхемы ВК равными нулю, а также сигнала считывание/запись С/З равным нулю [5]. По приходу информационного сигнала СНУ1 - обнуления счетчиков и предварительной установки - на вход блока БПУ (фиг.3) происходит вначале обнуление счетчиков: СчД и СчА сигналами СБО1 и СБР1 (фиг.5). Затем на вход вышеупомянутых счетчиков поступают прямоугольные импульсы ПИ1 и ПИМ1, формируя шину данных ШДА1 и адресную шину ШАА1. Выходы счетчиков СчД и СчА блока БПУ1 предварительной установки поступают на вход логической схемы ИЛИ (фиг. 3). Выходная информация логической схемы ИЛИ - ВИР поступает на вход ассоциативно-запоминающего устройства АЗУ и записывается. Это предварительный этап работы системы, при котором записывается двоичная информация в АЗУ, соответствующая "свободным" местам в ЛЦ. Другими словами это можно сказать так: обнуление и запись соответствующей информации в элементы памяти локализованных центров системы.

Следующий этап работы системы заключается в считывании информации из ОЗУ одного локализованного центра и сравнении с двоичным кодом АЗУ других ЛЦ системы. По установленным адресам ШАС и ШАСТ блока БНУА и соответствующим сигналам выбора микросхемы ВК, равным нулю, и считывание/запись (С/З), равным единице, выбранного для работы ОЗУ происходит считывание информации из памяти. На выходе ОЗУ формируется выходной информационный сигнал ВЫХ1, который соответствует избытку ресурса (фиг.3). Этот сигнал поступает на вход магистрали передачи данных (фиг.1). Через магистраль эта информация поступает на входы блоков памяти других локализованных центров. Входная информация ВХi поступает на вход логического элемента ИЛИ блока памяти ЛЦ. С выхода схемы ИЛИ двоичный код поступает на вход ассоциативно-запоминающего устройства АЗУ (фиг. 3). В АЗУ системы происходит сравнение поступившей информации с ранее записанной в запоминающие ячейки двоичном кодом. Если сравнение на равенство установлено, то данная ячейка АЗУ блокируется и в дальнейшем процессе перераспределения ресурсов не участвует. Информацию из ОЗУ в АЗУ другого ЛЦ не переписывается, т.к. она одинаковая. Если сравнения на равенство не установлено, то выполняется режим поиска на ближайшее большее значение. Этот режим формируется с помощью информационного сигнала СУА1, поступающего на вход АЗУ из блока управления. При положительном результате на выходе АЗУ формируется сигнал СС1 сравнения, равный единице. Полученная разность с выхода сумматора-вычитателя РЗ1 записывается по другому адресу в это же АЗУ, при дальнейшем процессе сравнения данные этой ячейки участвуют.

На фиг. 1 на входы локализованных центров ЛЦn поступают из блока управления только по одному информационному сигналу СУПn - сигналу управления. Множественный поток сигналов между блоками значительно затрудняют чтение чертежей. В связи с этим на фиг.4 представлена структура сигнала управления СУП1 (под номером 1-ым взяты все блоки и сигналы для примера). В состав этого информационного сигнала входят также информационные сигналы: НУА1 - сигналы обнуления и формирование данных и адресов блока БНУА1 начальной установки, СНУ1 - сигналы обнуления и формирования данных и адресов блока БПУ1 предварительной установки, СУА1 - сигналы маски ассоциативно-запоминающих устройств, СУO1 - сигналы выбора микросхемы и считывания/записи, УПА1 - управление работой арифметического процессора, УПС1 - управление работой специализированными устройствами символьной информации. Основная задача информационных сигналов - осуществление связей между блоками и надежная передача двоичного кода между блоком управления и остальными устройствами системы.

Блок БНУА1 - начальной установки и формирования адресов строк и столбцов оперативно-запоминающего устройства ОЗУ состоит из двоичных счетчиков: СчУД - установки данных, СчСЛ - формирователя адресов столбцов, СчСТ - формирователя адресов строк (фиг.5). На входы двоичных счетчиков поступают сигналы из блока управления - установки в нулевое состояние: УO1 - сброс в нуль счетчика СчУД, СБ1 - обнуление счетчика СчСЛ, СБС1 - обнуление счетчика СчСТ (фиг. 5). Перед началом загрузки элементов памяти все счетчики должны быть обнулены. По приходу сигналов прямоугольных импульсов: ТИ1 - тактовые импульсы, ГИ1 - генератор импульсов, ГИМ1 - генератор прямоугольных сигналов на входы соответствующих двоичных счетчиков происходит формирование шины данных ШД1 с выхода счетчика СчУД, адресов строк АСТ1 с выхода счетчика СчСЛ и адресов столбцов АСТл с выхода счетчика СчСТ (фиг.5). Все выходные сигналы двоичных счетчиков поступают на входы оперативно-запоминающих устройств (фиг.3).

БПУ1 - блок первоначальной установки и формирования адресов строк и столбцов ассоциативно-запоминающего устройства АЗУ блока памяти БП1 состоит из двоичных счетчиков: СчД - счетчика данных ШДА1 и СчА - счетчика адреса ШАА1 (фиг. 5). На входы счетчиков поступают сигналы СБО1- сброс в нуль и СБР1 - обнуление, которые устанавливают эти устройства в нулевое состояние. По приходу сигналов ПИ1 - прямоугольные импульсы и ПИМ1 - тактовые прямоугольные импульсы - на входы счетчиков происходит формирование на их выходах: шины данных ШДА1 счетчика СчД, адресной шины ШАА1 счетчика СчА (фиг.5). Выходные сигналы двоичных счетчиков поступают на вход логической схемы ИЛИ, выход которой является входом данных и адресным входом ассоциативно-запоминающих устройств (АЗУ) системы.

Блок анализа БАН1 состоит из арифметического процессора АРЛП1, специализированного устройства обработки информации ПРСО1 и стандартного устройства вывода. Основная задача этого блока - анализ поступившей на вход информации РР1 из ассоциативно-запоминающего устройства (АЗУ) локализованного центра ЛЦ. Арифметический процессор АРЛП1 предназначен для выполнения всех арифметических операций с входными данными РР1. Это может быть универсальный процессор, а также ряд специализированных решающих устройств. На вход этого процессора поступают входные данные - РР1 из АЗУ и управляющие сигналы УПА1 из блока управления. Выходными данными этого процессора могут быть результаты арифметических операций - АРЛ1, которые поступают на вход стандартного устройства вывода. Специализированные устройства символьной обработки ПРСО1 предназначены для решения поисковых задач, операций, связанных с функциями поиска и замены, сортировочными операциями входной информации и т.д. В качестве примера можно привести ряд специализированных устройств по обработке символьной информации [10, 11, 12, 13, 14]. По приходу сигнала РР1 из АЗУ ЛЦ и управляющих сигналов УПС1 из блока управления на вход ПРСО1 происходит выполнение операций по символьной обработке в зависимости от конкретно поставленной задачи. Выходная информация из специализированных устройств СИМ1 поступает на вход стандартного устройства вывода. Стандартным устройством вывода могут быть любые периферийные устройства: дисплей, принтер, стриммер, накопители на гибких магнитных лентах и дисках т.д.

Блок 5 управления синтезируется на основе ГСА алгоритма управления (фиг. 7) известным способом [3]. Размеченная ГСА работы блока 5 управления приведена на фиг.8, где обозначено:
Логические условия:
X1: "УОО"
Х2: "ПУСК"
Х3: "ПР"
Х4: "J ≤ T"
Х5: "АРП"
Х6: "СС"
Х7: "РАВ"
Операторы:
У1: "СБРОС:=1"
У2: "i:=1"
У3: "j:=1"
У4: "УO:=1"
У5: "СБ:=1"
У6: "СБС:=1"
У7: "СБО:=1"
У8: "СБР:=1"
У9: "ТИi:=1"
У10: "ПИi:=1"
У11: "ГИi:=1"
У12: "ПИМi":=1"
У13: "ГИМi:=1"
У14: "ВКi:=0"
У15: "С/Зi:=0"
У16: "ОЗУi:=ШД"
У17: "ОЗУi:=ШАС"
У18: "i:=i+1"
У19: "j:=j+1"
У20: "WRj:=0"
У21: "AЗУj:=ШДAj"
У22: "AЗУj:=ШAAj"
У23: "AЗУj:=CУAj"
У24: "C/Зi:=1"
У25: "ОЗУi:=ШАСТ"
У26: "МАГ:=ВЫХi"
У27: "AЗУj:=BXi"
У28: "PЗj:=BXДi-PPj"
У29: "AЗУj:=BXДi"
У30: "AЗУj:=PЗj"
У31: "ПИMj:=1"
У32: "WRj:=1"
У33: "БAHj:=PPj"
У34: "APЛПj:=УПAj"
У35: "APЛПj:=PPj"
У36: "ПРСОj:=УПСj"
У37: "ПPCOj:=PPj"
ИСТОЧНИКИ ИНФОРМАЦИИ
1. Маслов С.Ю. Теория дедуктивных систем и ее применения. - М.: Радио и связь, 1986. - 136 с. (Кибернетика).

2. Марков А.А., Нагорный Н.М. Теория алгорифмов. - М.: Наука. - 432 с. Главная редакция физико-математической литературы. 1984 г.

3. Успенский В.А., Семенов А.Л. Теория алгорифмов: основные открытия и приложения. - М.: Наука. Главная редакция физико-математической литературы. 1987 г. - 210 с.

4. Блэк Ю. Сети ЭВМ: Протоколы, стандарты, интерфейсы: Пер. с англ. - М. : Мир, 1990. - 506 с., ил.

5. Большие интегральные схемы запоминающих устройств: Справочник/ А.Ю. Гордонов, Н. В. Бекин, В. В. Цыркин и др.: Под ред. А.Ю. Гордонова и Ю.Н. Дьякова. - М.: Радио и связь, 1990. - 288 с., ил.

6. Алексенко А. Г. , Шагурин И.И. Микросхемотехника: Учеб. пособие для вузов. - 2-е изд., перераб. и доп. - М.: Радио и связь, 1990. - 496 с., ил.

7. Баранов С. И. Синтез микропрограммных автоматов. - Энергия. Ленинградское отделение. 1974. - 184 с.

8. Фет Я. И. Параллельные процессоры для управляющих систем. - М.: Энергоиздат, 1981. - 160 с., ил.

9. Цифровые и аналоговые интегральные микросхемы: Справочник под ред. С. В. Якубовского. - М.: Радио и связь, 1990. - 496 с., ил.

10. Патент N 2150740, Бюл. N 16, 10.06.2000.

11. А.С. N 1667097, Бюл. N 28, 30.07.91.

12. Патент N 1837327, Бюл. N 32, 30.08.93.

13. Патент N 2067315.

14. Патент N 2067317.

15. Патент N 2017206 (прототип).

16. Патент N 2032214 (аналог).

17. Патент N 2145113 (аналог).

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

Система взаимораспределения ресурсов, содержащая блок управления, отличающаяся тем, что дополнительно введены 1-й, 2-й и n-й локализованные центры, магистраль передачи данных, причем первый информационный выход блока управления соединен со вторым информационным входом локализованного центра ЛЦ1, первый информационный вход которого соединен с первым информационным выходом магистрали передачи данных, второй информационный выход которой соединен с первым информационным входом локализованного центра ЛЦ2, информационный выход которого соединен со вторым информационным входом магистрали передачи данных, n-й информационный выход которой соединен с первым информационным входом локализованного центра ЛЦn, информационный выход которого соединен с n-ым информационным входом магистрали передачи данных, первый информационный вход которой соединен с информационным выходом первого локализованного центра ЛЦ1, второй информационный вход локализованного центра ЛЦ2 соединен со вторым информационным выходом блока управления, третий информационный выход которого соединен со вторым информационным входом n-го локализованного центра ЛЦn, первый и второй управляющие входы "ПУСК" и "СБРОС" блока управления являются внешними входами устройства.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9