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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву— (22) Заявлено 22,04,76 (21) 2351100/10-24 с присоединением заявки HP

Государственный комитет

СССР по делам наобретеннй н открытий (23) Приоритет—

Опубликовано 2 05.79. Бюллетень М 19

Дата опубликования описания 28,0579 (72) Авторы изобретения с.А. Девяткин, В.Н. Кузнецов, А.М. Потапенко и A.Â.Xìåëåàñêîé (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫБОРА ЗАДАЧ В ЦЕЛЕВОЙ

СИСТЕМЕ ОБРАБОТКИ ДАННЫХ

Изобретение относится к вычислительной технике и может быть использовано при автоматизации выбора задач для решения целевой системой сбора и обработки данных.

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

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

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

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

В этом устройстве также содержатся блоки индикации, программирования процесса памяти для преобразования.

Устройство обеспечивает предс.авление и структурную визуализацию любого графа виде упорядоченной линейной сетки. Однако оно не позволяет

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

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

Целью изобретения является повышение быстродейстния при выборе решаемых задач с сохранением последовательности гоступления исходных данных н систему.

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

И второй группы, входом второго эле- 85 мента задержки и вторым входом блока имитации дуг и вершин графа; выход второго элемента задержки соединен с первыми входами первого регистра результатон и второго элемента И. 40

Первый выход регистра данных соединен с вторым входом первого элемента

И"и перным входом третьего элемента И

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

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

175 4 третьей группы подключены соответственно к вторым и третьим входам элементов запрета второй группы. Выходы последних соединены с третьим входом первого регистра результатов, первый выход которого через второй элемент

И соединен с первым нходом второго элемента запрета И с вторым входом второго регистра результатов, выход которого подключен к третьеку выходу устройства и к второму входу второго элемента запрета, а его выход соединен с вторым входом третьего элемента И и первым входом четвертого элемента И, выход которого подключен к четвертому выходу устройства, а второй вход — через последовательно соединенные второй элемент ИЛИ и третий элемент задержки подключен к выходам элементов И первой группы. Выход второго элемента ИЛИ соединен с вторым входом первого элемента запрета, второй выход первого регистра результатон подключен к третьему выходу устройства, выход перного элемента запрета соединен с входом регистра данных.

На фиг. l представ" ена блок-схема устройства; на фиг. 2-6 — составные части устройства.

В состав предлагаемого устройства входят дешифратор 1 индекса задачи, регистр 2 данных; элементы И.З (3, ...3„) первой группы, элементы

ИЛИ 4, элемент запрета 5, триггерный узел памяти 6 (б, ...б ), блок имитации дуг и вершин графа, включающий триггеры 7 (7, ...7 ) и элементы И 8 (8, ...8„), элементы И нторой группы, 9 (9, ...9„) и третьей группы 10 (10, ...10п,); элементы запрета третьей, второй и первой группы 11 (13. ° ° ° 11- )s12 (12 . ° ° 12р) 1 13 (13, ...13 ),регистры 14,15 результатон, элементы И 16,17 18, элемент

ИЛИ 19, элементы задержки 20-22, элементы И 23 и 24, вход 25 и выходы 26-29 устройства.

Устройство работает следующим образом.

При поступлении по входу элемента

ИЛИ 19 импульса с выхода дешифратора

1 производится сравнение состояний триггеров регистра 2 данных с состояниями триггеров имитации входных дуг графа узла памяти б и при совпадении состояний хотя бы пары триггеров, через элемент ИЛИ 4 на вход элемента запрета 5 подается импульс запрета переписи входным импульсом, через элемент задержки 20 единиц с триггеров регистра 2 данных на триггеры имитации входных дуг графа узла памяти 6.

По одному из выходов дешифратора производится опрос одного иэ элементов И 8, а его выходным импульсом триггеры, соответствующие входным дугам вершины, устанавливаются в по-,: ложение 0, а триггеры, соответ664175 ствующие выходным дугам этой же вершины, устанавливаются в положение 1 по отношению к своим элементам и имитации вершин.

Импульсом с выхода элемента задержки 20 производится опрос группы элементов И 9. С их помощью производится отбор вершин графа па отнсыению к элементам И, для кот >Рых триггеры имитации выходных дуг находятся в состоянии 1, а триггеры имитации выходных дуг находятся в состоя- )Q 0, С помощью элементов И 10 производится вы еление вершин, последующих вершинам, выделенным с помощью элементов И 9 и по отношению к элементам И имитации, для которых триггеры имитации входных дуг находятся в состоянии 1 .

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

10, выходы которых, соединены с разрешающими входами элементов запрета 11.

Подключением выходов элементов И

10 на запрещающие входы элементов запрета 11 реализуется следующий ал- 30 горитм оценки вершин, выбранных с помощью элементов И 10: из нескольких вершин выбирается одна, принадлежащая более высокому уровню обобщения данных; 35 в случае принадлежности вершин одному уровню обобщения данных выбирается одна, имеющая большее суммарное число путей захода в нее, а при равном количестве суммарных пу- 40 тей захода выбирается наиболее предпочтительная по информационному вкладу для данного уровня обобщения данных, исходя из условий построения графа для множества взаимосвязанных

45 задач, решаемых системой.

По подгруппам, соответствующим элементам И 9, выходы элементов запрета 11 объединены. Объединения выходов элементов запрета ll и выходов элементов И 9, соответствующие вершинам, не имеющим последующих в графе, за исключением элементов И 9, соответствующих конечной вершине, подсоединены на разрешающие входы элементов запрета 12. 55

На запрещающие входы элементов запрета подсоединены объединения выходов элементов запрета и выходы элементов И 9, соответствующие вершинам, не имеющим последующих в графе. 60

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

tlo результатам оценки последующей вершины, выбранной с помощью элементов запрета 11 определяются предыду65 щие A из множества вершин, выбранных с помощью элементов И 9; из определившихся вершин выбирается одна, принадлежащая более высокому уровню . обобщения данных, а в случае их принадлежности одному уровню обобщения данных выбирается одна, им.ющая большее суммарное число путей захода в нее, а при равном количестве суммар- ных путей захода выбирается наиболее предпочтительная по информац бронному вкладу для данного уровня обобщения данных.

Выходы элемента запрета 12 и выход элемента 11 за исключением элементов И 9, соответствующих конечной вершине графа, соединены с единичными входами триггеров регистра 14, так что одной вершине графа соответствует один триггер регистра.

Выходы элементов И 9 соединены с разрешающими входами элементов запрета 13.

Кроме того, выходы этих элементов

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

И 9: выбирается та вершина, которая имеет максимальное число исходов (выходных дуг) íà б.атее высоком уровне обобщения данных; при равном количестве исходов на этом уровне из них выбирается та, которая имеет максимальное число исходов на предыдущем уровне; при равном числе исходов на первом последующем уровне выбирается вершина с максимальным числом путей захода, а при равном числе путей захода выбирается вершина наиболее предпочтительная по уровню обобщения данных либо по информационному вкладу на одном и том же уровне.

Выходы элементов запрета 13 соедин ены с единичными входами триггеров регистра 15 так, что одной вершине графа соответствует один триггер регистра.

Входным импульсом через элемент з адержки 2 2 опр аши в ает с я эл емент

И 23, на разрешающие входы которого подключены нулевые выходы триггеров регистра 14 и устанавливаются в состояние 0 триггеры этого регистра.

Если один из триггеров этого регистра находился в состоянии l, то регистр 15 не опрашивается. Если ни один из триггеров регистров 14, 15 не набродился в состоянии " 1, то на выходе элемента И 24 появится импульс.

На одном из выходов устройства появится импульс, если один из триггеров хотя бы одного из регистров 14, 15 находился в состоянии 1 .

Выходные элементы И 16,17,18 срабатывают в следующих случаях: элемент И 16 — при наличии комбинации

6641 75

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

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

45 в регистре данных 2 и отсутствии импульса на одном из выходов 29 (K,, К ° ° ° ° К ) устройства (см.фиг.6); элемент И 17 — при отсутствии комбинации в регистре данных 2 и отсутствии импульса на одном иэ выходов 29 (К,, К,....К„) устройства; элемент 5

И 18 — при наличии входного импульса и отсутствии комбинации в гегистре данных 2.

Выходы регистров 14,15 и элементов И 16,17,18 предназначены для ис- 10 пользования при организации управления процессом решения задач как в одной, так и в сопрягающих целевых системах сбора и обработки данных. группы, треты входы которых и третий вход блока имитации дуг и вершин графа подключены к вчходу триггерного узла памяти, выходы блока имитации дуг и вершин графа соединены соответственно со вторым входом триггерного узла па яти, первыми входами элементов И третьей группы и вторыми входами элементов И второй группы, выходы которых подключены соответственно к разрешающим и запрещающим входам элементов запрета первой группы, к первому входу нторого регистра результатов, н орому входу первого регистра результатов, перным входам элементов запрета нторой группы и вторым входам элементов И третьей группы, выходы которых через элементы запрета третьей группы подключены соответственно к вторым третьим входам элементов запрета второй группы, выходы которых соединены с третьим входом первого регистра результатов, первый выход которого через второй элемент И соединен с первым входом второго элемента запрета И с вторым входом нторого регистра результатов, выход которого подключен к третьему выходу устройства и к второму входу второго элемента запрета, выход которого соединен с вторым входом третьего элемента И и первым входом четвертого элемента И, выход которого подключен к четвертому выходу устройства, а второй вход через последовательно соединенные второй элемент

ИЛИ и третий элемент задержки подключен к выходам элементов И первой группы, выход второго элемента ИЛИ соеди- . нен с вторым входом первого элемента запрета, второй выход перного регистра результатов подключен к третьему выходу устройства, выход первого элемента запрета соединен с входом регистра данных.

Источники информации, принятые во внимание при экспертизе

1. йвторское свидетельство СССР

Р 408312, кл. С 06 F 15/20, 1974.

2. Реферативный журнал Лвтоматика, телемеханика и вычислительная техника, реферат 7Б266 Специализированная комбинаторно-секционная

3ВМ для определения кратчайших и длиннейших путей в графе Р 7, 1976.

3. Патент Франции Р 2186151, кл. G 06 F 3/00, — ?186151, 1974.

66417

Закаэ 3001/46

Тираж 779 Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретеьий и открытий

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

Филиал ЛПП Патент, r. Ужгород, ул. Проектная, 4

Ас.

Составитель А. Жеренов

Редактор E. Гончар Техред Э. фанта Корректор И. Муска