Устройство для моделирования изменения объема сетевой базы данных

 

Изобретение относится к вычислительной технике. Цель изобретения - расширение класса решаемых задач. Для этого в устройство введены блок контроля времени моделирования, блок формирования адреса, регистраторы вершин, блок моделирования активной вершины. Процесс изменения объема базы данных рассматривается как процесс смены ее поколений. Блок контроля времени моделирования служит для задания и контроля числа моделируемых поколений базы данных. Моделирование осуществляют следующим образом. В блоке формирования адреса формируется следующий адрес ячейки памяти, определяющий порядок моделирования базы данных. Процесс порождения экземпляров сегментов задается в блоке моделирования активной вершины. Число порождаемых экземпляров случайно и характеристики распределений заданы в блоке памяти. 4 з.п. ф-лы, 7 ил., 1 табл.

1479942 шифратор 7 номера порождающей вершины, датчик 8 случайных чисел, блок

9 регистрации вершин, состоящий из и регистраторов вершин, блок 10 моделирования активной вершины, генератор 11 импульсов, блок 12 задержки.

Блок 9 регистрации вершин предназначен для имитации процесса роста числа экземпляров вершин (сегментов) п типов и регистрации их количества в каждом поколении базы данных и состоит из п регистраторов вершин. Каждый регистратор (фиг.2) вершины содержит первый триг- 15

rep 13, первый элемент HE 14, первую группу элементов И 15, сумматор 16, второй элемент НЕ 17, регистр 18, третью группу элементов

И 19 и второй триггер 20.

Блок 10 моделирования активной вершины (фиг.3) предназначен-для реализации числа циклов моделирования процесса порождения новых экземпляров активной вершины (сегмента) B данном поколении базы данных и содержит триггер 21, счетчик 22 и элемент HE 23.

Блок 2 контроля времени моделирования (фиг.4) служит для задания и.контроля числа моделируемых поколений базы данных и состоит из счетчика 24 и группы элементов И 25.

Блок 3 Aoðìèðoâàèèí адреса (фиг.5) служит для формирования следующего. адреса ячейки памяти, в которой хранится информация о номерах порождающей и активной вершин (сегментов), моделируемых в данном поколении базы данных, и содержит триггер

26, формирователь 27 импульсов, счет- 40 чик 28 и элемент НЕ 29.

Регистр 1 адреса предназначен для хранения и выдачи максимально- го адреса ячейки первого блока 4 памяти.

Первый блок 4 памяти предназначен для хранения и выдачи номеров типов порождающей i и активной j вершин (сегментов) базы данных. Пример заполнения первого блока 4 памяти для 50 заданной логической модели базы данных приведен в таблице.

Дешифратор 5 номера активной вершины при поступлении на его вход 55 кода номера активной вершины выдает на соответствующем выходе единичный сигнал.

Второй блок 6 памяти предназначен для хранения и выдачи при поступлении сигнала на его управляющий вход множеств= значений вероятностей в соответствии с заданным адресом (ij) на адресном входе. Второй блок

6 памяти состоит из п страниц, i-я страница соответствует i-й порождающей вершине, каждая страница содержит п адресуемых областей, соответствующих j-й активной вершине.

Каждая из областей содержит определенное число ячеек. Число заполненных ячеек области и их содержимое определяется интервалом распределения случайной величины Ы, и ви3 дом функции распределения F (o, ) соответственно, На фиг.6 изображена структура второго блока памяти.

Датчик 8 случайных чисел формирует случайные числа о, (t) соответствующие числу экземпляров сегмента типа Х в поколении t+1 порождаемых одним экземпляром сегмента типа Х; в поколении t, с вероятностями $P

Генератор 11 вырабатывает импульс с фиксированным периодом следования только при нулевом сигнале на входе, Блок 12 задержки задерживает прохождение единичного импульса с управляющего выхода блока 3 формирования адреса на временной интервал, достаточный для записи содержимого сумматора 16 накапливающего типа в регистре 18.

Формирователь 27 импульса генерирует единичный сигнал на выходе при перепаде сигнала на входе с нуля на единицу.

Ъ

Для достижения указанной цели процесс изменения объема базы данных, содержащей конечное число типов

Х, Х ...Х взаимосвязанных информационных компонентов (сегментов), рассматривается как процесс смены поколений базы данных. Состояние базы данных описывается случайным вектором p (t) = p,(t) P „(t), i-я компонента которого (ll, (t) показывает, что в момент t имеется р,(t) экземпляров типа Х,. Процесс изменения объема базы данных ача ется вероятностями переxcла Р,(t), l479942 6

35

Содержание ячейки

Адре ячей

Номер активной вершины

Номер порождающей вершины ки

6

4

2

2

2

3

4 равными вероятностям того, что один экземпляр сегмента типа Х; за время t переходит (порождает) в совокупность экземпляров сегментов, соответствующую случайному вектору о = (М,, ° ° °,ь",,),где Ы, — число экземпляров сегмента типа Х, о „ число экземпляров сегмента типа Х

" 11

При этом вероятность Р, „() может быть представлена в виде Р ()

1

Г1 PoL, где РЫ вЂ” вероятность

1 % 3 . того, что один экземпляр сегмента типа Х, порождает совокупность экземпляров сегмента типа Х равI

У ную о, где oL = О, i,.... . 1

В следующий момент времени t+1 каждый из имеющихся экземпляров сегмента Х °, где i =,1п, может породить случайное число g (t) экземпляров

5 сегмента Х, для которого распределение вероятностей Р Ы. (С) = о

= P, где о = О, 1,..., и объем

3 .1 базы данных станет равным Р (t+1) — (Ря,(t+»,..., p„(t+1)), где /и;( и И )

+» =, «k где Ы k— к 3 конкретйоке значение о . порожден3 ных экземпляров конкретным экземпля.ром иэ P,(t).

На фиг.? изображен пример процесса изменения объема базы данных для логической модели из таблицы для (g(0) = (2,2,1,1).

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

55 величин oc (t) и временем модели,1

t рования

Для определения характеристик случайного леса может быть использован ветвящийся случайный процесс с конечным числом частиц, которым и является ряд значений p (t).

При моделировании изменения объема базы данных (фиг,?) устройство работает следующим образом. Перед началом моделирования содержимое регистров 18 регистраторов вершин равно начальному числу экземпляров сегментов fu(t) = (fU,(t), to (t), P„(t)) типов Х,, Х,...,Х„соответственно в момент времени t = О ° Содержимое регистра 1 адреса равно значению максимального адреса ячейки первого блока 4 памяти.

Триггеры 13, 20 и 21 находятся в нулевом, а триггер 26 в единичном состоянии. Содержимое счетчика 24 равно числу моделируемых поколений базы данных и, содержимое сумматоров 16 и счетчика 22 равно нулю, на первый управляющий вход счетчика 24 подан сигнал логической единицы.

Так как на выходе счетчика 24 (фиг.4) присутствует сигнал "1", а триггер находится в единичном состоянии, то содержимое регистра 1 адреса будет записано в счетчик. 28 (фиг.5), после чего появившийся на его выходе сигнал "0" переведет триггер 26 в нулевое состояние и сигнал "1" с его нулевого выхода разрешит поступление информации на вычитающий вход счетчика 28. Содержимое счетчика 28 поступает на адресный вход первого блока 4 памяти и вызывает считывание из его ячейки памяти с адресом 7 кода номера порождающей вершины 1 и кода номера активной вершины 1. Код номера активной вершины, поданный на вход дешифратора 5 (фиг.1), вызывает появление на первом информационном входе регистратора вершин с номером

1 блока регистрации вершин сигнала

"1", который переводит триггер 13 первого регистратора вершин в единичное состояние, а единичный сигнал с единичного выхода триггера 13 разрешает запись информации в сумматор

16 данного регистратора вершин °

Код номера порождающей вершины, поданный на вход дешифратора 7, вы1479942 зывает появление на втором информационном входе регистратора вершин с номером 1 блока регистрации вершин сигнала " 1" который переводит тригУ

5 гер 20 первого регистратора в единичное состояние,а единичный сигнал с единичного выхода триггера 20 разрешает считывание начального числа экземпляров,(t) сегмента Х из реЗгистра 18 н счетчик 22 блока моделирования активной вершины, после чего на выходе счетчика 22 появляется сигнал "0", который переводит триггер 21 в единичное состояние, н результате чего разрешается поступление информации на вычитающий вход счетчика 22, запрещается прием инАормации на информационные входы счетчика 22 и запускается генератор

11 импульсов, единичные импульсы с выхода которого переводят в нулевое состояние триггеры 20 всех регистраторов вершин, что приводит к запрещению считывания информации из ре- 25 гистров 18 н блок моделирования активной вершины. Каждый единичный импульс с выхода генератора 11 импульсов вызывает считывание из второго блока 6 памяти н соответствии с поданным на его вход адресом с блока 4 памяти, множества вероятностей PoL 1, в конкретном случае

РО ;, которые подаются на вход датчика 8 случайных чисел, которыи. вырабатывает случайное число оС<, поступающее на вход сумматора 16 первого регистратора вершин. Этот же единичный сигнал уменьшает на единицу содержимое счетчика, 22.

Как только содержимое счетчика 22 станет равным нулю, íà его выходе появляется сигнал " 1" появление которого разрешает прием инАормации на второй информационный вход счетчика 22, переводя триггер 21 в нуле- вое состояние, запрещает работу генератора 11 импульсов и формирователь 27 импульсов в блоке Аормирования адреса генерирует единичный импульс, который уменьшает содержимое 50 счетчика 28 на единицу. Таким образом заканчивается моделирование первой активной вершины, на фиг,7 это соответствует ситуации порождения новых экземплярон eeгментов ти- 55 па Х1 экземплярами сегментов типа

Х, данная ".èòóàöèÿ задана в ячейке с адресом 7 блока 4 памяти.

После окончания моделирования всех порождающих ситуаций, заданных в блоке 4 памяти, т,е. как только со пержимое счетчика 28 станет равным нулю, на его управляющем выходе появляется сигнал "1", который при поступлении на второй управляющий вход блока регистрации вершин разрешает считывание содержимого сумматоров 16 в регистры 18 всех регистраторон вершин, а пройдя через блок задержки 12, переводит триггеры

13 в нулевое состояние и обнуляет содержимое сумматоров 16. Этот же сигнал "1" с выхода счетчика 28 уменьшает на единицу содержимое счет чика 24, а также, переведя триггер

36 в единичное состояние, разрешает прием информации счетчиком 28 из регистра 1 адреса. На этом заканчивает. ся моделирование первого поколения базы данных., в результате в регистрах 18 регистраторов вершин содержится вектор pl (t+1) = (p,(t+1), fez(t+1),..., p„(t+1)j. Далее начинается моделирование следующего поколения базы данных. Описанная процедура повторяется до, тех пор, пока содержимое счетчика 24 не станет равным нулю, что приведет к сбросу на его выходе сигнала "1" и запрету очередное считывание адреса из регистра 1 адреса. На этом моделирование заканчивается, и в регистрах

18 блока регистрации вершин содержится вектор p (t) = (p,(t+1), P < (t ), ..., p„(t)), для t. = п,где и — число моделируемых поколений базы данных.

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

1. Устройство для моделирования изменения объема сетевой базы данных, содержащее генератор импульсов, первый блок памяти и второй блок памяти, выходы которого соединены с входами настройки датчика случайных чисел, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач путем обеспечения возможности моделирования процесса изменения объема базы данных во времени, в него введены и ре гистраторов вершин, блок моделирования активной вершины, депп»фратор 33омер:.3 активной вершины, Ле33ппЬратор 33 333 ра порождающей верш3п3ь3, б I(III:33п3с.: »1479942

50 ки, блок контроля времечи моделирования, блок формирования адреса и регистр адреса, выходы которого подключень! к соответствующим информа. 5 ционным входам блока контроля времени моделирования, выходы которого соединены с соответствующими информационными входами блока формирования адреса, группа информационных выходов которого. подключена к соответствующим адресным входам первого блока памяти, первая группа выходов ,которого соединена с соответствующими входами дешифратора номера активной вершины i — и (i = 1, 2,...,п) выход которого соединен с первым информационным входом 1-го регистратора вершин, выходы всех регистраторов вершин объединены поразрядно в шину данных и подключены к соответствующим информационным входам блока моделирования активной вершины, выход которого соединен с управляющим входом блока формирования 25 адреса и с входом генератора импульсов, выход которого подключен к управляющему входу блока моделирования активной вершины, к входу синхронизации второго блока памяти и к входам блокировки вершины регистраторов вершин, группа информационных входов каждого из которых соединена с соответствующими выходами датчика случайных чисел, вторая группа выходов первого блока памяти под35 ключена соответственно к адресным . входам второго блока памяти, третья группа выходов первого блока памяти соединена с соответствующими входами дешифратора номера порождающей вершины, i-й выход которого подключен к второму информационному вхору i-го регистратора вершин, выход блока формирования адреса соединен

45 с входом счета времени блока контроля времени моделирования, с входами записи регистраторов вершин и через блок задержки с входами сброса активности регистраторов вершин.

2. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что каждый регистратор вершины содержит две группы элементов И, сумматор, регистр, два элемента НЕ и два триггера, группа информационных входов регистратора вершин соединена с первыми входами элементов И первой группы, выходы которых подключены .к входам сумматора, выходы которого соединены с входами данных регистра, выходы кo торого соединены с первыми входами элементов И второй группы, выходы которых являются выходами регистратора вершины, первый информационный вход которого подключен к единичному входу первого триггера и через первый элемент HF к первому нулевому входу первого триггера, выход которого соединен с вторыми входами элементов И первой группы, второй информационный вход регистратора вершины подключен к единичному входу второго триггера и через второй элемент НЕ к первому нулевому входу второго триггера, выход которого соединен с вторыми входами элементов И третьей группы, второй нулевой вход второго триггера является входом блокировки вершины регистратора вершины, вход записи которого подключен к входу синхронизации регистра, вход сброса активности регистратора вершины соединен с вторым нулевым входом первого триггера и с входом сбро1 са сумматора.

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

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

1! 2479942 I2 разрешения приема и входу разрешения блока, вход счета времени которого счета счетчика, входы данных которо- соединен со счетным входом счетчика, го являются информационными входами инверсный выход индикации нулевого блока. состояния подключен к первым входам

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

От

От

Ощ d8 18 ОтйУ От Ck, 11

Фиг.2

1479942

/ I a

1479942 цг ь ь ьс ь

° 1

Ъс

Ъ

Составитель А.Яицков

Редактор М.Циткина Техред А.Кравчук

К оррек т о р М. Пожо

Заказ 2544/47 Тираж 669 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 ь ь ьс ъ

ls

Фс ю

Ъ, с с

° ъ

И Ь ю

Ъ Ъ ь

Ю

° М

ss ь

Ъ ь с ь

И

Ъ ь ь

11 с ,ь

Ъ ь ь

%сф

Ц о й

Ое

Crs

1 ° 1 м

° М с в Э

ll и Ъв

У с

Ъ

% е Ф (!