Устройство для исследования графов

(51) 4 С 06 Р 15/20 ОСУДАРСТВЕННЫЙ НОМИТО ИЗОБРЕТЕНИЯМ И ОТНРЫТРИ ГКНТ СССР ПИСАНИЕ ИЗОБРЕТЕНИ с1 я Ь".э 1 радиотатикинов 6,1985.во СССР(57) Изобматике имолет бытго 8 компараторов 11, второго эле пе и втор СТВО вто о элемент ИЛИ 13, ч ертого 17, пятоседьмого 20 иент о 1 ось) етение относи ычислительной я к авто ехнике и шестого 19ого 21 элеме в эадержк использовано целера сснф.ссср Гр.ц К А 8 ТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Патент США Р 45546кл. С 05 Р 9/00, опубл.Авторское свидетельсУ 1238099, кл. С 06 Г 1 пределения, для исследования графов.Цель изобретения состоит в повышениибыстродействия устройства. Поставленная цель достигается путем исключения потерь времени на записьэлементов опорного решения во внешние блоки памяти и потерь времени наобращение к внешним операционнымустройствам для осуществления арифметических операций, что обеспечивается введением третьего блока 3памяти, блока 4 вычитания, первого5 и второго 6 вычитающих счетчиков,ректор И.Муск при ГКНТ СС тета по и ва, Ж,Ваиют ЕЕВ комбинат "Пате агарина,101 г. Ужгоро Яар, и 123 Янр.хС 5 1231462345 Изобретение относится к автоматике и вычислительной технике, в частности к устройствам для вычисления начального опорного решения задачи целераспределения, и может быть использовано для исследования графов.Цель изобретения - повышение быстродействия устройства.На фиг.1 представлена блок-схема 1 О предлагаемого устройства;на фиг.2 - блок-схема первого блока памяти; нафиг.З - блок-схема второго блока "памяти; на фиг,4 - блок-схема тре: тьего блока памяти; на фиг.5 - блок схема блока вычитания; на фиг.6- временная диаграмма работы, реализуемая устройством при следующих исходных данных; и = 2; ш = 2; Р,10; Р =20; Я 1=5; Я=25. 20Особенностью поставленной задачи является то обстоятельство, что задача целераспределения в канонической форме представляется задачей определения таких пав неизвестных 25х11 1 т Сх 3 х, ххиз условий; 30 35 с; х;(2) 40 Второй блок памяти (фиг.З) содержит дешифратор 62, группу регистров 63, 64, первую 65, вторую 66, третью 67 и четвертую 68 и пятую 69 группы элементов И, первую 70, вторую 71 и третью 72 группы элементов ИЛИ, первый 73 и второй 4 элементы И, первый 75, второй 76 и третий 77 элементы ИЛИ, первый 78 и второй 79 элементы задержкиНа фиг.З также показаны синхронизирующие входы 80- 82, адресный вход 83, информационный вход 84, группа информационныхвходов 85,86,и информационный выход 87.) сх .0; 1 ( 3. ( и;11 ( ш11что значение выражения минимально, причем выполнены следующие сооотношения При этом значение набора р " Р, Р,Р называется мощностями поставщиков, значения набора. Ы 3 " й.а:д,- .щ"- потребителей, а набор неизвестных удовлетворяющих соотношениям (1), называется опорным решением или опорным планом задачи целераспределения.Устройство (фиг.1) содержит первый 1, второй 2 и третий 3 блоки памяти, блок 4 вычитания, первый 5и второй 6 вычитающие счетчики, первый 7 и второй 8 компараторы, триггер 9, первый 10 и второй 11 элементы И, первый 12 и второй 13 элементы ИЛИ, первый 14, второй 15, третий16, четвертый 17, пятый 18, шестой19, седьмой 20 и восьмой 21 элементызадержки. На фиг.1 также показаныпервый 22, второй 23, третий 24 ичетвертый 25 информационные входы,синхронизирующий вход 26, первая(27, 28) и вторая (29, 30) группыинформационных входов, группа информационных выходов 3 1-34 и синхронизирующий выход 35,Первый блок памяти (фиг,2) с держит дешифратор 36, группу регистров37, 38, первую 39, вторую 40, третью 41, четвертую 42 и пятую 43 группы элементов И, первую 44, вторую 45, и третью 46 группы элементов ИЛИ,первый 47 и второй 48 элементы И,первый 49, второй 50 и третий 51 элементы ИЛИ, первый 52 и второй 53 элементы задержки, На фиг.2 также показаны синхронизирующие входы 54-56, адресный вход 57, информационный вход 58, группа информационных входов 59, 60 и информационный выход 61.1462345 Третий блок памяти (фиг4) содер" жит первый 88 и второй 89 дешифраторы, матрицу регистров 90"93 (количество строк этой матрицы равняет-5 ся числу регистров 37, 38 в группе, первого блока памяти, а количество столбцов этой матрицы равняется числу регистров 63, 64 в группе второго блока памяти), первую 94 1 О и вторую 95 группы элементов И, группу 96 элементов ИЛИ, первый 97, второй 98, третий 99 и четвертый 100 элементы И, первый 101, второй 102, третий 103 и четвертый 104 элемен ты ИЛИ и элемент 105 задержки На фиг.4 также показаны синхронизирующие входы 106 и 107, адресные входы 108 и 109, информационные входы 110, 111 и группа информационных выходов 20 112-115.Блок вычитания (фиг,5) содержит сумматор 116, суммирующий счетчик 117, вычитающий счетчик 118, первую 119 и вторую 120 группы элементов И, 25 группУ 121 элементов ИЛИ, первый 122 и второй 123 элементы И, первый 124, второй 125, третий 126 и четвертый 127 элементы задержки. На фиг.5 также показаны информационные ЗО входы 128 и 129, синхронизирующий вход 130, синхронизирующие выходы 131 и 132, информационные выходы 133-135.Начальное опорное решение вычисля- З 5 ется с помощью процедуры, состоящей из последовательности шагов.На каждом шаге ресурс (мощность) одного из поставщиков полностью или частично передается одному из потре- . 40 бителей таким образом, чтобы либо исчерпать мощность данного поставщика (и тем самым исключить его из дальнейшего рассмотрения), либо удовлетворить полностью потребность . 45 (мощность) потребления (и тем самым исключить его из дальнейшего рассмотрения) .Известно, что в опорных решениях содержится ровно и+шзначащих ком" 50 понент. Незначающне компоненты х .111 опорного плана хмы идентифицируем числами -1. Перед началом процедуры заполним матрицу хчислами -1, зададимся наборами Р и О и положим= и, 3 = ш. Перед началом каждого шага мы проверяем, рав- . няется ли нулю хотя бы один из индексов д и 1. В случае, когда оба индекса положительны, мы выполняем оче"редной шаг процедуры, в противномслучае мы заканчиваем процедуру. На каждом шаге процедуры мы вначале выбираем наибольшее иэ чисел Р, и цЕсли Р не меньше Я , то элементух; мы присваиваем значение ,уменьшаем значение Р, на число Я иуменьшаем на единицу индекс 1, т.е.исключаем из дальнейшего рассмотрения потребителя с номером 1,Если ( больше Р., то элементу х .,(мы присвайваем значение Р;, уменьшаем значение Я. на число Р; и3уменьшаем на единицу индекс , т,е.исключаем из дальнейшего рассмотрения поставщика с номером д.Устройство работает следующим образом.Перед пуском устройства на информационном входе 22 должна быть установлена константа 0 (нчлевое слово),которая должна присутствовать навходе 22 в течение .всего времениработы устройства, на информационном входе 23 - значение и, не превосходящее числа Н регистров 37, 38группы первого блока памяти, на информационном входе 24 - значение ш,не превосходящее числа М регистров63, 64 группы второго блока памяти,на информационном входе 25 - константа -1, на первые и информационныхвходов 27, 28 группы - значения мощ-ностей поставщиков Р 1, Р,еРна первые ш информационных входов29, 30 группы " значения мощностейпотребителей (1Устройство начийает работать после поступления на синхоонизиочющийвход 26 импульса 13 (фиг.б,поз.1),который устанавливает триггер 9в единичное состояние (фиг.б,поз,2),что разрешает прохождение импуль-.сов через элемент И 10, ИмпульсП . поступает на синхронизирующиевходы счетчиков 5 и 6, вследствиеэтого в счетчики 5 и 6 записываются числа и и ш соответственно.Импульс П , поступает на синхронизирующий вход 54 блока 1 памяти (фиг.2), с выхода 51 - на группы39 и 40 элементов И, вследствие этого информационные слова с группыинформационных входов 27 и 28 проходят через группы 39 и 40 элементовИ и группы 44 и 45 элементов ИЛИ навходы группы регистров 37, 38 и записываются в эти регистры с помощьюимпульса Б , прошедшего с синхронизирующего входа 54 через элементыИЛИ 49 и 50 на синхронизирующие входь регистров,Импульс Приск поступает на синхронизирующий вход 80 блока памяти2 (фиг,З), с входа 80 - на группы65 и 66 элементов И вследствие это 1;информационных входов 29, 30 прохо, .дят через группы 65 и 66 элементовИ и группы 70 и 71 элементов ИЛИ на, входы группы регистров 63 и 64 и за,писываются в эти регистры с помощью.импульса ПУ , прошедшего с синхро"низирующего входа 80 через элемен; ты ИЛИ 75 и 76 на синхронизирующиевходы регистров.Импульс БрУтакже поступает насинхронизирующий вход 1.07 блока 3памяти (фиг.4), с выхода 107 - на. входы группы 94 элементов И, вслед; ствие этого информационное слово с:,через группу 94 элементов И и группу 96 элементов ИЛИ на входы всех: регистров 90-93 матрицы и записывается в эти регистры с помощью импульса Б , поступившего на синруск фхронизирующие входы регистров ссинхронизирующего входа 107 черезэлементы ИЛИ 101-104,Таким образом, импульс Бобеспечивает запоминание числа н строкматрицы х 1 в счетчике 5, числа шстолбцов матрицы х- в счетчикеб, набора мощностей поставщиков Р-в регистрах первого блока памяти,набора мощностей потребителейв регистрах второго блока памяти изанесение во все регистры третьеголока памяти числа -1. Кроме этого, импульс Б русск, задержанный на элементе 14 задержки на времясчитывания и запоминания информацйи, проходит через элемент ИЛИ. 12, после чего задерживается на элементе 16 задержки на время (это время равно времени возможного переброса триггера 9 в нулевое состояние), и, поскольку триггер находится в единичном состоянии, ня выходе элемента И 10 образуется тактовый импульс 0 ,(фиг.б,поз.З).Обозначим содержимое регистра 5 через 1, а содержимое регистра 6- через 1. С выхода элемента И 10 импульсБ, поступает на синхронизирующийвход 55 первого блока памяти (фиг.2),Через элемент ИЛИ 51 импульс Б кпоступает на синхронизирующийвход дешифратора 36, который в соответствии с адресным словом, находящимся на адресном входе 57 (т,е, в 10 соответствии с содержимым счетччка 5), выставляет на одном из своих выходов высокий потенциал, темсамым разрешая прохождение черезодну из групп 41 и 42 элементов И со.15 держимого одного из регистров 37,38 группы в момент прихода импуль"са Ц , задержанного на элементе52 задержки на время срабатываниядешифратора. После этого на выходе 20 только одной из групп 41, 42 элементов И будет находиться содержимое соответствующего регистра, ана выходах всех остальных групп41, 42 будут выставлены нулевые 25 слова, поэтому на выходе группы 46элементов ИЛИ будет выставлено слово, хранящееся в регистре, опреде-.ляемом адресным словом на адресномвходе 57. Таким образом, с помощьюимпульса 0 , на информационномвыходе 61 блока 1 памяти выставляется значение Р;.ТЯКТОВый импульс Б т.акт также поступает на синхронизирующий вход81 второго блока памяти (фиг.З). Через элемент ИЛИ 77 импульс Бтпоступает на синхронизирующий входдешифратора 62, который в соответствии с адресным словом, находящимся на адресном входе 83 (т.е, в соответствии с содержимым счтетчика6), выставляет на одном из своих выходов высокий потенциал, тем самымразрешая прохождение через одну из 45групп 67 и 68 элементов И содержимого одного из регистров групп 63, 64в момент прихода импульса Пзадержанного на элементе 78 задержки на время срабатывания дешифратора. После этого на выходе только 50однои из групп 67, 68 элементов Инаходится содержимое соответствующего регистра, а на выходах всех остальных групп 67, 68 выставлены нулеВые СЛОВя поэтому ня Выходе группы 72 элементов ИЛИ выставлено слово, хранящееся в регистре, определяемом адресным словом на адресномвходе 83, Таким образом, с помощью97, 98, 99, 100, входы которого соединены с выходомдешифратора 88 и выходомдешифратора 89, и проходит через один из элементов 1015 104 на синхронизирующий вход одного из регистров.Таким образом, в регистр матрицы 90-93, соответствующий элементу х,1 начального опорного решения, в случае Р;Я записывается значениеа в случае Р; ( Ц записывает: ся значение Р,.Если на синхронизирующем выходе 131 блока 4 был сформирован импульсто этот импульс поступает на синхронизирующий вход 56 блока 1 (фиг,2),на информационном входе 58 которого сформировано значение Р, - Ч в пря 20 мом коде. Импульс Ур через элемент ИЛИ 51 проходит на синхронизирующий вход дешифратора 36, который выставляет высокий потенциал на своем выходе с номером , поскольку на адресном входе дешифратора по-прежнему выставлено содержимое счетчика 5, т.е. . Импульс 11 р разрешает прохождение значения Р - Я .с выс хода 58 через группу 43 элементов И и группы 44 и 45 элементов ИЛИ на информационные входы всех регистров 37 и 38 группы. Импульс Бр, задер, жанный на элементе 53 задержки на время срабатывания дешифратора 36, проходит через один из элементов 35 И 47, 48 и один из элементов ИЛИ 49, 50 на синхронизирующий вход регистра, соответствующего выходу с номеромдешифратора 36. Таким образом, в регистр, в котором храни лось значение Р , будет записано значение Р; - ЯИмпульс Пр, будучи задержанным на элементе 21 задержки на время Гзаписи значе,ния Р, - Я в блок 1, формирует на , 45 выходе элемента 21 задержки импульс 0 , (фиг,б, поз.8), который постур 1пает на вычитающий вход счетчика 6, уменьшая тем самым его содержимое, т.е. в счетчике б будет после 50 этого находиться число 1-1.Если на синхронизирующем выходе 132 блока 4 был сформирован импульс П, то этот импульс поступает на синхронизирующий вход 82 блока 2 55 (фиг.З), на информационном входе 84 которого сформировано значение Я - Р в прямом коде, Импульс 11через элемент И 77 проходит на синхронизпрующий вход дешифратора 62, который выставляет высокий потенциал на своем выходе с номером 1, поскольку на адресном входе дешифратора по-прежнему выставлено содержимое счетчика 6, т.е. . Импульс Б разрешает прохождение значения Я - Р; с выхода 84 через группу 69 элементов И и группы 70, 71 элементов ИЛИ на информационные входы всех регистров 63, 64 группы. Импульс Б, задержанный на элементе 79 задержки на время срабатывания дешифратора 62, проходит через один из элементов И 73, 74 и один из элементов ИЛИ 75, 76 на синхронизирующий вход регистра, соответствующего выходу с номером 1 дешифратора 62. Таким образом, в регистр, в кото- ром хранилось значение Ц , будет записано значение Я - Р;. Импульс Ц, будучи задержанным на элементе 20 задержки на время ь, записи значения Я - Р; в блок 2, формирует на выходе элемента 20 задержки импульс ц , (фиг.б, поз,9), который поступает на вычитающий вход счетчика 5, уменьшая тем самым его содержимое на единицу, т,е, в счетчике 5 будет после этого находиться значение -1.Итак, каждый импульс Б , обеспечивает осуществление цикла работы блоков 1-4, причем в результате этого цикла выполняется один шаг процедуры вычисления начального опорного решения. После уменьшения на еди" ницу содержимого одного из счетчиков 5 и 6, значения, записанные в этих регистрах, сравниваются с нулем в компараторах 7 и 8, что обеспечивается приходом на синхронизирующие входы компараторов тактового импульса У с выхода элемента И 10,тактпричем этот импульс был задержан на элементе 17 задержки на время работы блоков 1-4 и на время обновления содержимого одного из счетчиков 5 и 6 (фиг.1).1Если в обоих счетчиках хранятся положительные величины, то на выходах обоих компараторов будет низкое значение потенциала. Низкое значение потенциала будет также присутствовать на выходе элемента ИЛИ 13, что запрещает прохождение через элемент И 11 импульсов с выхода эле мента ИЛИ 12 (т.е. тактовых импуль 1462345 12Устройство для исследования гра" фов; содержащее первый блок памяти, первый синхронизирующий вход которого является синхронизирующим входом устройства, информационные входы группы первого блока памяти являются первой группой информационных входов устройства, второй блок памяти, первый синхронизирующий вход которого соединен с синхронизирующим входом устройства, информационные входы группы второго блока памяти 50 сон 0задержанных на элементе15 задержки на время Гг работыблоков 1-4, счетчиков 5 и 6 и компараторов 7 и 8). Следовательно,5триггер 9 остается в единичном состоянии и на выходе элемента И 10формируется новый тактовый импульсэ)тант (фиг.б, поз.3), что влечет засобой выполнение нового цикла работыблоков 1-4,Если же содержимое хотя бы одного из счетчиков 5 и 6 станет равнымнулю, это приведет к появлению высокого потенциала на выходе элемента 15ИЛИ 13, что в свою очередь разрешитпрохождение через элемент И 11 импульса с выхода элемента ИЛИ 12,Сформированный на выходе элементаИ 11 импульс Б ., (фиг.б,поз.10) 20поступает на вход установки в нольтриггера 9 и переводит триггер в нулевое состояние, что запрещает прохождение импульсов через элементИ 10, т.е. запрещает формирование 25новых тактовых импульсов.Импульс Б а, с синхронизирующего выхода 35 используется в качестве сигнала прерывания вычислительного комплекса, по которому вычислительный комплекс запускает программуопроса группы информационных выходов31-34, на которых сформированы значения компонент начального опорногорешения задачи целераспределения.Таким образом, введение новых узлов и элементов позволяет существенно повысить быстродействие устройства. Время решения задачи вычисления начального опорного плана на 40устройстве-прототипе при различныхисходных данных составляет 18-23 мин,то же на предлагаемом устройствезанимает 8,5-12 мин,45Формула изобретения являются ээторой группой ицформаииоццых нхопон устройства, перээый элемецт задержки, нхол которого подключен к сицхроциэируюшему нхолуустройства, первый элемент ИЛИ,первый вход которого соединен с ньэходом первого элемента задержки,второй элемент задержки, выход которого подключен к второму нходупервого элемента ИЛИ, третий элемент задержки, вход которого соединен с выходом первого элемента ИЛИ,первый элемент И, первый вход которого подключен к выходу третьегоэлемента задержки, а выход соединенс входом второго элемента задержки,с вторым синхронизирующим входомпервого блока памяти и с вторым синхронизирующим входом второго блокапамяти, триггер, вход установки в"1" которого подключен к синхроМизирующему входу устройства, а выход соединен с вторым входом первого элемента И, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия, оно содержит с четвертогопо восьмой элементы задержки, первый и второй компараторы, вторые элементы И и ИЛИ, первый и второй вычитающие счетчики, блок вычитания,третий блок памяти, причем вход четвертого элемечта задержки соединенс выходом первого элемента И, синхронизирующие входы первого и второго компараторов соединены с выходом четвертого элемента задержки,первые информационные входы первогои второго компараторов являются первым информационным входом устройства, первый и второй входы второгоэлемента ИЛИ соединены соответственно с выходом первого и второго компараторов, первый и второй входывторого элемента И соединены соответственно с выходами первого и второго элементов ИЛИ, а выход соединенс входом установки в "0" триггераи является синхронизирующим выходомустройства, выходы первого и второговычитающих счетчиков соединены соот-.ветственно с вторыми информационнымивходами первого и второго компараторов, информационные входы первого ивторого вычитающих счетчиков являют-,ся соответственно вторым и третьиминформационными входами устройства,выход первого вычитающего счетчикасоединен с адресным входом первого1462345 14 О р,ФпадЙ Зрссн У Ю Ривьер, й66 и первым адресным входом третьего блоков памяти, синхронизирующие входы первого и второго вычитающих счетчиков соединены с синхронизирующим входом устройства, выход второго5 вычитающего счетчика соединен с ад ресным входом второго и вторым адрес. ным входом третьего блоков памяти, ,выход первого элемента И соединен через пятый элемент задержки с синхронизирующим входом блока вычита ния, выходы первого и второго бло: ков памяти соединены соответственно : с первым и вторым информационными 15 :, входами блока вычитания, первый и второй синхронизирующие выходы которого соединены с третьими синхро: низирующими входами соответственно первого и второго блоков памяти, вы О ,ход первого элемента И соединен через шестой элемент задержки с первым синхронизирующим входом третьегоблока памяти, второй синхронизирующии вход которого соединен с синхронизирующим входом устройства, первый,второй и третий информационные выходы блока вычитания соединены с первыми информационными входами соот"ветственно первого, второго и третьего блоков памяти, второй информационный вход третьего блока памяти.является четвертым информационнымвходом устройства, а информационныевыходы групп третьего блока памятиявляются группой информационных выходов устройства, второй и первыйсинхронизирующие выходы блока вычитания соединены соответственно черезседьмой и восьмой элементы задержкис вычитающими входами первого и вто-.рого вычитающих счетчиков.