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

П И ЗОБ оюа СоветскихиалистичеекихРеспублик) Дополнительное к ает А-ау 1100/10-2 оедннением зеваки осударственный комитет СССР по делам наобретеннй н открытий(71) Заявите ОЙСТВО ДЛЯ ВЫБОРА ЗАДАЧ В ЦЕЛЕВОЙ СИСТЕМЕ ОБРАБОТКИ ДАННЫХ 5 5(22) Завалено 22,04,76 (2 Изобретение относится к вычислительной технике и может быть использовано при автоматизации выбора задач для решения целевой системой сбора и обработки данных.Известно, что топология множества задач, решаемых целевой системой сбора и обработки данных, может быть представлена в ниде ориентированного графа, а состояния дуг графа могут быть отождестнлены с состояниями исходных данных, используемых в интересах решения задач.Известно устройство, которое содержит триггеры, ключевые схемы, схе-.1 мы ИЛИ, распределитель, счетчик, линии задержки 11., В этом устройстве с использованием тактовых импульсов производится подсчет числа путей захода для любой вершины графа, однако, 2 О оно не может быть применено для одной структуры взаимосвязанйых задач с учетом приоритетности задач по информационному вкладу данных, получаемых в результате их решения.Известно также устройство, в состав которого входят секции, имитирующие вершины графа, включающие цифровые вычислители и логические схемы 2. В этом устройстве производит-.зО ся параллельно-последовательный анализ вершин графа, анализ путей осуществляется эа счет подсчета и сравнения суммарных задержек между нершинами, а также имеется возможность выб рать кратчайшее расстояние между заданными вершинами. Однако данное устройство не позволяет осуществить слежение за прохождением данных во всей структуре задач, учет веса вершин по информационному вкладу, контроль данных и выявление источников нарушения связей между данными.Наиболее близким по технической сущности к изобретению является устройство, в состав которого входят дешифратор индекса задачи, вход которого соединен с входом устройства, регистр данных, элементы И, ИЛИ, блок имитации дуг и нершин граба, элементы запрета, элементызадержки, регистры результатов, триггерный узел памяти 33В этом устройстве также содержатся блоки индикации, программирования процесса памяти для преобразования. Устройство обеспечивает предс.авление и структурную визуализацию любого графавиде упорядоченной линейной сетки. Однако оно не позволяет664осуществить автоматический ввод изменений в состояниях дуг граФа, т.е. автоматическое слежение за состоянием исходных данных; автоматический выбор вершин в зависимости от веса вершин, длин путей и состояний дуг; автоматический контроль совместимости б входных данных с данными, Фиксируеьыми на предыдущих этапах анализа. В связи с этим при автоматизациивыбора задач в целевой системе сбора ри обработки данных в случае применения известного технического решенияможет быть затрачено значительноевремя по сравнению с временем решения задач, а исходные данные могутбыть использованы без сохранения последовательности их поступления всистему, т.е. с нарушением причинноследственных связей между ними.Целью изобретения является повышение быстродействия при выборе решаемых задач с сохранением последовательности гоступления исходных данных в систему,Достигается это тем, что в устройстве выход дешифратора индексазадачи подключен к первому входублока имитации дуг и вершин графа ичерез первый элемент ИЛИ соединен свходом первого элемента задержки,первым входом первого элемента И и 30первыми входами элементов И первойгруппы, выход первого элемента задержки соединен с первыми входамипервого элемента запрета, элементовИ второй группы, входом второго элемента задержки и вторым входом блока имитации дуг и вершин графа; выход второго элемента задержки соединен с первыми входами первого регистра результатов и второго элемента И, 40Первый выход регистра данных соединен с вторым входом первого элементаИ"и первым входом третьего элемента И(выходы которых подключены соответственнр к первому и второму выходамустройства. Второй выход регистраданных подключен к первому входу триггерного узла памяти и к вторым входам элементов И первой группы, третьивходы которых и третий вход блокаимитации дуг и вершин графа подключе- В)ны к выходу триггерного узла памяти.Выходы блока имитации дуг и вершинграфа соединены соответственно свторым входом триггерного узла памяти, первыми входами элементов И 55третьей группы и вторыми входами элементов И второй группы, выходы кОторых подключены соответственно к разрешающим и запрещающим входам элементов запрета первой группы, к первомувходу второй регистра результатов,втором входу первого регистра результатов, первым входам элементовзапрета второй группы и вторым входам элементов И третьей группы, выходы которых через элементы запрета 175 4третьей группы подключены соответственно к вторым и третьим входам элементов запрета второй группы. Выходыпоследних соединены с третьим входомпервого регистра результатов, первыйвыход которого через второй элементИ соединен с первым входом второгоэлемента запрета И с вторым входомвторого регистра результатов, выходкоторого подключен к третьеку выходуустройства и к второму входу второгоэлемента запрета, а его выход соединен с вторым входом третьего элемента И и первым входом четвертого эле"мента И, выход которого подключен кчетвертому выходу устройства, а второй вход - через последовательно соединенные второй элемент ИЛИ и третийэлемент задержки подключен к выходамэлементов И первой группы, Выход второго элемента ИЛИ соединен с вторымвходом первого элемента запрета, второй выход первого регистра результатов подключен к третьему выходу устройства, выход первого элемента запрета соединен с входом регистра данных.Иа Фиг. 1 представ"ена блок-схемаустройства; на фиг. 2-6 - составныечасти устройства.В состав предлагаемого устройствавходят дешифратор 1 индекса задачи,регистр 2 данных; элементы И.З(3, 3) первой группы, элементыИЛИ 4, элемент запрета 5, триггерныйузел памяти 6 (6, 6 ), блок имитации дуг и вершин графа, включающийтриггеры 7 (7, ,7 ) и элементы И 8(13, 13 ),регистры 14,15 результатов, элементы И 16,17,18, элементИЛИ 19, элементы задержки 20-22,элементы И 23 и 24, вход 25 и выходы 26-29 устройства,Устройство работает следующим образом.При поступлении по входу элементаИЛИ 19 импульса с выхода дешифратора1 производится сравнение состоянийтриггеров регистра 2 данных с состояниями триггеров имитации входныхдуг графа узла памяти 6 и при совпадении состояний хотя бы пары триггеров, через элемент ИЛИ 4 на вход элемента запрета 5 подается импульс запрета переписи входным импульсом,через элемент задержки 20единицс триггеров регистра 2 данных натриггеры имитации входных дуг графаузла памяти 6,По одному из выходов дешифраторапроизводится опрос одного иэ элементов И 8, а его выходным импульсомтриггеры, соответствующие входнымдугам вершины, устанавливаются в по-,ложение 0, а триггеры, соответстнующие выходным дугам этой же вершины, устананлинаются н положениеф 1по отношению к своим элементами имитации вершин.Импульсом с выхода элемента задержки 20 производится опрос группыэлементов И 9. С их помощью процзводится отбор вершин графа па отнсыецию к элементам И, для кот Рых триггеры имитации выходных дуг находятсяв состоянии 1, а триггеры имитации выходных дуг находятся в состоя- Онии фО.С помощью элементов И 10 производится выделение вершин, последующихвершинам, выделенным с помощью элементов И 9 и по отношению к элементам И имитации, для которых триггерыимитации входных дуг находятся в состоянии 1,Согласно структуре ориентированного графа одной вершине, выделенной спомощью группы элементов И 9, могут,следовать несколько вершин, Поэтомувыход одного элемента И группы можетбыть соединен с опрашинающими входаминескольких двухвходовых элементов И10, выходы которых, соединены с раз- Мрешающими входами элементов запрета 11,Подключением выходов элементов И10 на запрещающие входы элементонзапрета 11 реализуется следующий алгоритм оценки вершин, выбранных с помощью элементов И 10:из нескольких вершин выбираетсяодна, принадЛежащая более высокомууровню обобщения данных; 35в случае принадлежности вершинодному уровню обобщения данных выбирается одна, имеющая большее суммарное число путей захода в нее, апри равном количестве суммарных путей захода выбирается наиболее предпочтительная по инФормационному вкладу для данного уровня обобщения данных, исходя из услоний построенияграфа для множестна взаимосвязанных45задач, решаемых системой.По подгруппам, соответствующимэлементам И 9, выходы элементов запрета 11 объединены, Объединения выходов элементов запрета 11 и выходов элементов И 9, соответствующие 50вершинам, не имеющим последующих вграФе, за исключением элементов И 9,соответствующих конечной вершине,подсоединены на разрешающие входыэлементов запрета 12. 55Иа запрещающие входы элементовзапрета подсоединены объединениявыходов элементов запрета и выходыэлементов И 9, соответствующие вершинам, не имеющим последующих в графе.При этом реализуется следующий алгоритм оценки вершин, отобранных с помощью элементов И 9.По результатам оценки последующейвершины, выбранной с помощью элементов запрета 11 определяются предыдуб 5 щие ей из множества вершин, выбран ных с помощью элементов И 9; из определившихся вершин выбирается одна, принадлежащая более высокому уровню обобщения данных, а в случае их принадлежности одному УРовню обобщения данных выбирается одна, им.ющая большее суммарное число путей захода в нее, а при равном количестве суммар- ных путей захода выбирается наиболее предпочтительная по информац ионному вкладу для данного уровня обобщения данных.Выходы элемента запрета 12 и выход элемента 11 за исключением элементов И 9, соответствующих конечной вершине графа, соединены с единичными входами триггеров регистра 14, так что одной вершине графа соответствует один триггер регистра.Выходы элементов И 9 соединены с разрешающими входами элементов запрета 13.Кроме того, выходы этих элементов И соединены с запрещающими входами элементов запрета 13 так, что реализуется следующий алгоритм оценки вершин, выбранных с помощью элементов И 9: выбирается та вершина, которая имеет максимальное число исходов(выходных дуг) на более высоком уровне обобщения данных; при равном количестве исходов ца этом уровне из них выбирается та, которая имеет максимальное число исходов на предыдущем уровне; при равном числе исходов на первом последующем уровне выбирается вершина с максимальным числом путей захода, а при равном числе путей захода выбирается вершина наиболее предпочтительная по уровню обобщения данных либо по инФормационному вкладу на одном и том же уровне.Выходы элементов запрета 13 соединены с единичными входами триггеров регистра 15 так, что одной вершине графа соответствует один триггер регистра.Входным импульсом через элемент задержки 22 опрашивается элемент И 23, на разрешающие входы которого подключены нулевые выходы триггеров регистра 14 и устанавливаются н состояние 0 триггеры этого регистра.Если один из триггеров этого регистра находился в состоянии 1, то регистр 15 не опрашивается. Если ниодин из триггеров регистров 14, 15 не набродился в состоянии "1, то на выходе элемента И 24 появится импульс.На одном из выходов устройства появится импульс, если один из триггеров хотя бы одного из регистров 14, 15 находился в состоянии 1,Выходные элементы И 16,17,18 срабатывают в следующих случаях: элемент И 16 - при наличии комбинацииФормула изобретения Устройство для выбора задач в целевой системе обработки данных,содержащее дешифратор индекса задачи, вход которого соединен с входом устройства, регистр данных, элементы И,ИЛИ, блок имитации дуг и вершин графа, элементы запрета, элементы задержки, регистры результатов, триггерный узел памяти, о т л и ч а ющ е е с я тем, что, с цельо повышения быстродействия при выборе решаемых задач с сохранением последовательности поступления исходных данных в систему, в нем выход дешифратора индекса задачи подключен к первому входу блока. имитации дуг и вер 30 шин графа и через первый элемент ИЛИсоединен с входом первого элементазадержки, первым входом первого элеИ мента И и первыми входами элементов первой группы, выход первого элемента задержки соединен с первыми вхо"дами первого элемента запрета, элементов И второй группы, входом второго элемента задержки и вторым входом блока имитации дуг и вершин графа, выход второго элемента задержкисоединен с первыми входами первогорегистра результатов и второго эле"мента И, первый выход регистра данных соединен с вторым входом первогоэлемента И и первым входом третьегоэлемента И, выходы которых подключены соответственно к первому и второму выходам устройства, второй выходрегистра данных подключен к первомувходу триггерного узла памяти и ковторым входам элементов И первой 40 45 в регистре данных 2 и отсутствии импульса на одном из выходов 29 (К КК) устройства (см.фиг.б); элемент И 17 - при отсутствии комбинации в регистре данных 2 и отсутствии импульса на одном иэ выходов 29 (К К,К) устройства; элемент 5 И 18 - при наличии входного импульса и отсутствии комбинации в регистре данных 2.Выходы регистров 14,15 и элементов И 16,17,18 предназначены для ис пользования при организации управления процессом решения задач как в одной, так и в сопрягающих целевых системах сбора и обработки данных. группы, треты входы которых и третий вход блока имитации дуг и вершинграфа подключены к в 1 ходу триггерного узла памяти, выходы блока имитациидуг и вершин графа соединены соответственно со вторым входом триггерногоузла па яти, первыми входами элементов И третьей группы и вторыми входами элементов И второй группы, выходы которых подключены соответственнок разрешающим и запрещающим входамэлементов запрета первой группы, кпервому входу второго регистра результатов, в.орому входу первого регистра результатов, первым входамэлементов запрета второй группы ивторым входам элементов И третьейгруппы, выходы которых через элементы запрета третьей группы подключенысоответственно к вторым третьим входам элементов запрета второй группы,выходы которых соединены с третьимвходом первого регистра результатов,первый выход которого через второйэлемент И соединен с первым входомвторого элемента запрета И с вторымвходом второго регистра результатов,выход которого подключен к третьемувыходу устройства и к второму входувторого элемента запрета, выход которого соединен с вторым входом третьего элемента И и первым входом четвертого элемента И, выход которогоподключен к четвертомУ выходу устройства, а второй вход через последовательно соединенные второй элементИЛИ и третий элемент задержки подключен к выходам элементов И первой группы, выход второго элемента ИЛИ соединен с вторым входом первого элементазапрета, второй выход первого регистра результатов подключен к третьемувыходу устройства, выход первого элемента запрета соединен с входом регистра данных. Источники информации, принятые во внимание при экспертизе1, йвторское свидетельство СССР Р 408312, кл. С 06 Р 15/20, 1974.2. Реферативный журнал Лвтоматика, телемеханика и вычислительная техникаф, реферат 7 Б 266 Специализированная комбинаторно-секционная ЭВМ для определения кратчайших и длиннейших путЕй в графе Р 7, 1976.3. Патент Франции Р 2186151, кл. С 06 Р 3/00, - 186151, 1974,664175 фиа 6Составитель А. ЖереновТехред Э. Фанта Корректор И. Муска Редактор Е. Гонч 3001/4 Тираж 779 ПодписноеИПИ Государственного комитета СССРо делам изобретеьий и открытийМосква, Ж, Раушская наб., д. 4/5 Филиал ЛПП Патент, г, Ужгород, ул. Проектная