Устройство для выбора задач в целевой системе обработки данных Советский патент 1979 года по МПК G06F15/173 

(54) УСТРОЙСТВО ДЛЯ ВЫБОРА ЗАДАЧ В ЦЕЛЕВОЙ СИСТЕМЕ ОБРАБОТКИ ДАННЫХ осуществить автоматический ввод изменений в состояниях дуг графаf т.е автоматическое слежение за состояние исходных данных; автоматический выбор верниин в зависимости от веса вер шин, длин путей и состояний дуг; авт матический контроль совместимости входных данных с данными, фиксируе№ ми на гфедыдущих этапах анализа. В связи с этим при автоматизации выбора задач в целевой системе сбора и обработки данных в случае применения известного технического решения может быть затрачено значительное время по сравнению с временем решения задач, а исходные данные могутбыть использованы без сохранения последовательности их поступления в систему, т.е. с нарушением причинноследственных связей между ними. Целью изобретения является повышение быстродействия при выборе решаемых задач с сохранением последовательности поступления исходных дан ных в систему. Достигается это тем, что в устройстве выход дешифратора индекса задачи подключен к первому входу блока имитации дуг и вершин графа и через первый элемент ИЛИ соединен с входом первого элемента задержки/ первым входом первого элемента И и первыми входами элементов И первой группы, выход первого элемента задержки соединен с первыми входами первого элемента запрета, элементов И второй группы, входом второго элемента задержки и вторым входом блока имитации дуг и вершин графа; выход второго элемента задержки соединей с первыми входами первого регист ра результатов и второго элемента И. Первый выход регистра данных соединен с вторым входом первого элемента И -и первым входом третьего элемента выходь которых подключены соответственно к первому и второму выходам устройства. Второй выход регистра данных подключен к первому входу три герного узла памяти и к вторым входам элементов И первой группы, треть входы которых и третий вход блока имитации дуг и вершин графа подключе ны к выходу триггерного узла памяти Выходы блока имитации дуг и вершин графа соединены соответственно с вторым входом триггерного узла памяти, первыми входами элементов И третьей группы и вторыми входами эле ментов И второй группы, выходы кото рых подключены соответственно к разрешающим И запрещающим входам элемен тов запрета первой группы, к первому входу второй регистра результатов, втором- входу первого регистра результатов, первым входам элементов запрета второй группы и вторым входам элементов И третьей группы, выходы которых через элементы запрета третьей группы подключены соответственно к вторым и третьим входам элементов запрета второй группы. Выходы послелних соединены с третьим входом первого регистра результатов, первый выход которого через второй элемент И соединен с первым входом второго элемента запрета И с вторым входом второго регистра результатов, выход которого подключен к третьему выходу устройства и к второму входу второго элемента запрета, а его выход соединен с вторым входом третьего элемента И и первым входом четвертого элемента И, выход которого подключен к четвертол1у выходу устройства, а второй вход - через посл(довательно ссэединенные второй элемент ИЛИ и третий элемент задержки подключен к выходам элементов И первой группы. Выход второго элемента ИЛИ соединен с вторым входом первого элемента запрета, второй выход первого регистра результатов подключен к третьему выходу устройства, выход первого элемента запрета соединен с входом регистра данных. На фиг. 1 представ гена блок-схема устройства; на фиг. 2-6 - составные части устройства. В состав предлагаемого устройства входят дешифратор 1 индекса задачи, регистр 2 данных; элементы И.З {3, ...3) первой группы, элементы ИЛИ 4, элемент запрета 5, триггерный узел памяти 6 (6 ,..6|), блок имитации дуг и вершин графа, включающий триггеры 7 (7j ...7) и элементы И 8 (8, ...8), элементы И второй группы. 9 (9 ...9„) и третьей группы 1Q (10 ...10); элементы запрета третьей, второй и первой группы 11 (li ...11„) ;12 (12, . ..12р); 1.3 (13 . .. 13 ) ,регист Ж1 14,15 результатов, элементы И 16,17,18, элемент ИЛИ 19, элементы задержки 20-22, элементы И 23 и 24, вход 25 и выходы 26-29 устройства. Устройство работает следующим образом. При поступлении по входу элемента ИЛИ 19 импульса с выхода дешифратора 1 производится сравнение состояний триггеров регистра 2 данных с состояниями триггеров имитации входных дуг графа узла памяти 6 и при совпа- , дении состояний хотя бы пары триггеров, через элемент ИЛИ 4 на вход элемейта запрета 5 подается импульс запрета переписи входным импульсом, через элемент задержки 20 единиц с триггеров регистра 2 данных на триггеры имитации входных дуг графа узла памяти 6. По одному из выходов дешифратора производится опрос одного из элементов И 8, а его выходным импульсом триггеры, соответствующие входным дугам вершины, устанавливаются в по- ; ложение 6, а триггеры, соответствуюише выходным дугам этой же вершины, устанавливаются в положение 1 по отношению к своим элементам и имитации вершин. Импульсом с выхода элемента задержки 20 производится опрос группы элементов И 9. С их помощью производится отбор вершин графа по отношению к элементам и, для которых триггеры имитации выходных дуг находятся в состоянии , а триггеры имитации выходных дуг находятся в состоянии О . С помощью элементов И 10 производится выделение вершин, последующих вершинам, выделенным с помощью элементов И 9 и по отношению к элементам И имитации, для которых триггеры имитации входных дуг находятся в состоянии . Согласно структуре ориентированно го графа одной вершине, выделенной с помощью группы элементов И 9, могут .следовать несколько вершин. Поэтому выход одного элемента И группы может быть соединен с опрашивающими входам нескольких двухвходовых элементов И 10, выходы которых, соединены с разрешающими входами элементов запрета 11.. Подключением выходов элементов И 10 на запрещающие входы элементов запрета 11 реализуется следующий алгоритм О1;енки вершин, выбранных с по мощью элементов И 10: из нескольких вершин выбирается одна, принадлежащая более высокому уровню обобщения данных; в случае принадлежности вершин одному уровню обобщения данных выбирается одна, имеющая большее суммарное число путей захода в нее, а при равном количестве суммарных путей захода выбирается наиболее предпочтительная по информационному вкла ду для данного уровня обобщения данных, исходя из условий построения графа для множества взаимосвязанных задач, решаемых системой. По подгруппам, соответствующим элементам И 9, выходы элементов запрета 11 объединены. Объединения выходов элементов запрета 11 и выходов элементов И 9, соответствующие вершинам, не имеющим последующих в графе, за исключением элементов И 9, соответствующих конечной вершине, подсоединены на разрешающие входы элементов запрета 12. На запрещающие входы элементов запрета подсоединены объединения выходов элементов запрета и выходы элементов И 9, соответствующие верши нам, не имеющим последующих в графе. При этом реализуется следующий алгоритм оценки вершин, отобранных с помощью элементов И 9. По результатам оценки последующей вершины, выбранной с помощью элементов запрета 11, определяются предыду щие ей из множества вершин, выбранных с помощью элементов И 9; из определившихся вершин выбирается одна, принадлежащая более высокому уровню обобщения данных, а в случае их принадлежности одному уровню обобщения данных х ыбирается одна, имэющая большее суммарное число путей захода в нее, а при равном количестве суммарных путей захода выбирается наиболее предпочтительная по информацчонному вкладу для данного уровня обобщения данных. Выходы элемента запрета 12 и выход элемента 11 за исключением элементов И 9, соответствующих конечной вершине графа, соединены с единичными входами триггеров регистра 14, так что одной вершине графа соответствует один триггер регистра. Выходы элементов И 9 соединены с разрешающими входами элементов запрета 13, Кроме того, выходы этих элементов И соединены с запрещающими входами элементов запрета 13 так, что реализуется следующий алгоритм оценки вершин, выбранных с помощью элементов И 9: выбирается та вершина, которая имеет максимал..ное число исходов (выходных дуг) на б..шее высоком уровне обобщения данных; при равном количестве исходов на этом уровне из них выбирается та, которая имеет максимальное число исходов на предыдущем уровне; при равном числе исходов на первом последующем уровне выбирается вершина с максимальным числом путей захода, а при равном числе путей захода выбирается вершина 1гаиболее предпочтительная по уровню обобщения данных либо по информационному вкладу на одном и том же уровне. Выходы элементов запрета 13 соединены с единичными входалчи триггеров регистра 15 так, что.одной вершине графа соответствует один триггер регистра . Входным импульсом через элемент задержки 22 опрашивается элемент И 23, на разрешающие входы которого подключены нулевые выходы триггеров регистра 14 и устанавливаются в состояние О триггеры этого регистра. Если один из триггеров этого регистра находился в состо тнии , то регистр 15 не опрашивается. Если ниодин из триггеров регистров 14, 15 не назТодился в состоянии , то на выходе элемента И 24 появится импульс. На одном из выходов устройства появится импульс, если один из триггеров хотя бы одного из регистров 14, 15 находился в состоянии . Выходные элементы И 16,17,18 срабатывают в следующих случаях: элемент И 16 - при наличии комбинации в регистре данных 2 и отсутствии импульса на одном из выходов 29 (К| , Kj,..Kj,) устроПства (см.фиг.6 элемент И 17 - при отсутствии комбинации в регистре данных 2 и отсутствии импульса на одном из выходов 29 (К,, К,....К) устройства; элемент И 18 - при наличии входного, импульса и отсутствии комбинации в регистре данных 2. Выходы регистров 14,15 и элементов И 16,17,18 предназначены для использования при организации управления процессом решения задач как в одной, так ив сопрягающих целевых системах сбора и обработки данных. Формула изобретения Устройство для выбора задач в целевой системе обработки данных,содержащее дешифратор индекса задачи, вход которого соединен с входом устройства, регистр данных, элементы И ИЛИ, блок имитации дуг и вершин графа, элементы запрета, элементы задержки, регистры, результатов, триггерный узел памяти, отличающееся тем, что, с цель|о повышения быстродействия при выборе решаемых задач с сохранением последовательности поступления исходных данных в систему, в нем выход дешифратора индекса задачи подключен к первому входу блока.имитации дуг и вершин графа и через первый элемент ИЛИ соединен с входом первого элемента задержки, первым входом первого элемента И и первыми входами элементов первой группы, выход первого элемента задержки соединен с первыми входами первого элемента запрета, элементов И второй группы, входом второго элемента задержки и вторым входом блока имитации дуг и вершин графа, выход второго элемента задержки соединен с первыми входами первого регистра результатов и второго элемента И, первый выход регистра данных соединен с вторым входом первого элемента И и первым входом третьего элемента И, выходы которых подключены соответственно к первому и второму выходам устройства, второй выход регистра данных подключен к первому входу триггерного узла памяти и ко вторым входам элементов И первой ,„ rpynnu, треть ьходы которых и третий вход блока имитации дуг и вершин графа подключены к вчходу триггерного узла памяти, выходы блока имитации дуг и вершин графа соединены соответственно со вторым входом триггерного узла паг яти, первыми входами элементов И третьей группы и вторыми входами элементов И второй группы, которых подключены соответственно к разрешающим и запрещающим входам элементен запрета первой группы, к первому входу второго регистра результатов, в-орому входу первого регистра результатов, первым входам элементов запрета второй группы и вторым входам элементов И третьей группы, выходы которых через элементы запрета третьей группы подключены соответственно к вторым третьим входам элементов запрета второй группы, выходы которых соединены с третьим входом первого регистра результатов, первый выход которого через второй элемент И соединен с первым входом второго элемента запрета И с вторым входом второго регистра результатов, выход которого подключен к третьему выходу устройства и к второму входу второго элемента запрета, выход которого соединен с вторым входом третьего элемента И и первым входом четвертого элемента И, выход которого подключен к четвертому выходу устройства, а второй вход через последовательно соединенные второй элемент ИЛИ и третий элемент задержки подключен к выходам элементов И первой группы, выход второго элемента ИЛИ соединен с вторым входом первого элемента запрета, второй выход первого регистра результатов подключен к третьему выходу устройства, выход первого элемента запрета соединен с входом регистра данных. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР № 408312, кл. G 06 F 15/20,1974. 2 Реферативный журнал Автоматика, телемеханика и вычислительная техника , реферат 7Б266 Специализированная комбинаторно-секционная ЭВМ для определения кратчайших и длиннейших путей в графе № 7, 1976. 3. Патент Франции № 2186151, кл. G 06 F 3/00, - 2186151, 1974.

I I

F

и

rp

«p

k.&SL&S t

I

чК

Xil

ii

iii

kii

лдл

.fj f/ «I