Устройство для сортировки чисел

)5 6 06 Р 7/06 ПИСАНИ РЕТЕНИ ИДЕТЕЛ СКОМУ А скии чно-исследоватенститут тельство СССРР 7/06, 1984.тельство СССРР 7/06, 1985. ТИРОВКИ ЧИ к вычислительия - уменьше, Устройство ГОСУДАРСТВЕННОЕ ПАТЕНТНВЕДОМСТВО СССР(54) УСТРОЙСТВО ДЛЯ СОСЕЛ(57) Изобретение относитсной технике. Цель изобретние аппаратурных затр1 лссодеркит информационнйе входы 1, 2, тактовый вход 3, вход 4 начальной установки, вход 5 задания количества сортируемых чисел, мультиплексоры 6 - 9, блок сравнения 10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, блоки памяти (БП) 12, 13, 17, 18, регистры 14, 15, 16, триггер 19, счетчики 20, 21, элемент ИЛИ 22, элемент И 23, выходы 24, 25, 26. Числа поступают по входам 1 и 2 и записываются в БП 12 и 13. Затем из БП 12 и 13 происходит выборка двух чисел, сравнение их 11 запись по тем ке адресам в БП 12 и 13, возможна их перестановка в зависимости от результата сравнения. Порядок выборки (адреса БП 12 и 13) задается алгоритмом, хранящимся в БП 17 и 18, выполненных в виде ПЗУ. 3 ил.17849663 . 4Изобретение относится квычислитель- соединен с входом триггера 19, первым нойтехнике и может быть использовано в входом схемы 22 ИЛИ и счетным входом,вычислительных системах длярешения за- " счетцика 21, выходкоторогосоединен с втодач сортировки чисел., . рым входом блока 18 постоянной памяти иЦель изобретения - уменьшение аппа вторым входом блока 17 постояййой памяти, ратурных затрат.".:.:,:.: .,:,:,:. " первый вход которого соедийен с выходомНа фиг. 1 йредставлена схемаустройст- регистра 16, вход которого соединен с вхова для сбфтировМицисел; на фиг. 2 - граф, " дом 5 устройства, вход сбросатриггера 19 и алгорйтма сортировки; на фиг. 3 - блочная счетчика 21 соединей с входом 4 устройства структураграфа алгоритма сортировки10 и вторым входом схемы 22 ИЛИ, информа- .,Устройство для сортЪровки. чисел со-"ционный вход счетчика 20 соедийен с пер-: держит, информационные входы 1,2, такто- вым выходом блока 17 постоянной памяти, вый вход 3 вход 4 начальной установки,второй выход которого соединен спервым вход 5 задайия количества, сортируемьх чи- входом схемы. 23 "И, второй:вход которой, сел, двухвходовые мультиплексоры 6 - 9, 15 соединен свходом.3 устройства;схему 10 сравнения, схему 11 ИСКЛЮЧАЮ-:. Счетчик 20 служитдля подсцета количе- ЩЕЕ ИЛИ, блоки 12, 13 оператйвной памя- , ства выполненных тактов на одном этапе ти, регистры 14 - 16, блоки 17, 18 постоянной алгоритма сортировкй и работаетв режиме памяти, триггер 19, счетчики 20,21, схему 22 " вычитания. С ка 1 кдым тактовым импуль- .ИЛИ; схему 23 И, выходй 24 - 26. :, 20 сом, поступающим по входу 3,из содержи-Вход 1 устройства соединен спервым:мого счетчика 20 вычитается единица, информационным: входОм мультиплексораСчетчик 21 служитдля" подсчета количества 6, второй информационный вход которого. выполненйых этапов алгоритма сортйрьвкисоединен свыходом 24 устройства и выхо- и работаетв"режиме сложения. Как толькодом регистра 14, вхОд которого соединен с 25 содержимое счетчика 20 становится равнымвыходом блока 12" оперативной памяти, ин:-, нулю, что говорит об оконцании вьгполненйя формационный. вход которого соедйнен с ""этайа, сигнал с его выхода поступает на счет- выходом мультиплексора 8, первыи ин- " ный вход счетчика 21 и прибавляет к его формацйонный входкоторого соедийей с -содержимому единицу.выходом мультиплексора 6, вторым инфорВблоке 17 постоянной памяти зашито мационным входом мультиплексора Й и вто- количество тактов, вь полняемых на каждом рым входом схемы 10 сравнения; первый: иэ этапов алторитма сортировки в завйсивхад которой соединен с вторым информа- мости от количества й сортируемых чисел, ционным входом мультийдексора 8, первым, Адресом блока 17 служит содержимое реги- информационным входом мультиплексора 35 стра 16, в котором храйится значение й, и 9 и выходом мультиплексора 7, первый ин- содержимое счетчика 21, в. котбромуказан формациоййыйвходкоторого соединен с номер выполняемого этайа, Кроме того, в входом 2 устройства, а второй информаци- одном разряде блока 17 йостоянной памяти онный вход которого соединен с выходом хранится значение. управляемое схемой, устройства 25 и выходом регистра 15, вход 40 23 И, Если вДанном разряде записана которого соединен,с выходом блока 13 опе-. единица, схема 23 И открыта и через нееративйой памяти, информационный вход проходят тактовые импульсы с входа 3 ускоторого соединен с выходом мультййлек- тройства. Если в данном разряде записан сора 9, управляющий вход которого соеди- ноль, схема 23 И закрыта. Это.бывает в нен с управляющим входом мультиплек случае, когда выполнилась последняя итесора 8 и выходом схемы 1.1 ИСКЛЮЧАЮ- рация для данного И и устройство заверши- ЩЕЕ ИЛИ, первый вход которой соединенло сортировку чисел. По шине 26 данныйс выходом схемы 10 сравнения, а второйсигнал поступает йа выход устройства, совход соедййенс первым выходом блока 18 общая О готовностй ксортировкеследующепостоянной памяти, второй выход которого 50 го:массива чисел.соединен с адресным входом блока 13 опе- . В блоке 18 постоянной памяти запиративной памяти, вход зайиси/счмтьва-: саны адреса, по которым производится ния которогосоединенсвыходомсхемы 23 И,считывание и запись операндов в блоки счетным входом счетчика.20, синхровхода- . оперативйой памяти 12, 13 в каждом такте ми регистров 14, 15 л вйходом записи/счи йа всех вцполняемйх этапах. Адресом блотывания блока 12 оператйвной памяти, ка 18 служит содержимое счетчиков 20 и 21.адресный вход которого соединен стретьйм Кроме того, в одном разряде блока 18 по-., выходом блока 18 постоянной памяти, пер- стоянной памяти записан сигнал, поступавый вход которого соединен с первым выхо- ющий на схему 11 ИСКЛЮЧАЮЩЕЕ ИЛИ, дом счетчика 20, второй выход которогокоторая управляет прохокдением информации через мультиплексоры 8, 9.Алгоритм сортировки Бетчера, реализуемый устройством, ориентирован на сортировку количества чисел М, кратного степени 2, Поэтому разрядность регистра 16 равна 1= 1092(092 Ивах), ГДЕ Ивах МаКСИМаЛЬ- ный размер сортируемого массива чйсел на устройстве. Разрядность счетчика 20 Гп = Ч 092 Ивах - 1, РазРЯдность счетчика 21 К =О 92(О 92 Йва 4 О 92 Квах+ 1), ГДЕ )Х ОбОЗНачает большое целое число Х.Устоойство для сортировки чисел работает следующим образом, На входе 5 задается код количества К сортируемых чисел; По входу 4 поступает сигнал начальной установки, который устанавливает триггер 19 и счетчик 21 в состояние "0", в регистр 16 записывается код К, а в счетчик 20 из блока 17 значение количества тактов, выполняемых на первом этапе (данное значение равно К/2, так как на первом этапе произ-.водится запись в процессор сортируемых чисел по двум каналам). Затем по входам 1, 2 в процессор поступают сортируемые чис- ла, а по входу 3 таковые импульсы, поступающие через схему 23 И на сихровходы регистров 14, 15, счетный вход счетчика 20.и входы записи(считывания блоков 12, 13; оперативной памяти;На первом этапе осуществляется прием входной информации и выполнение первого этапа алгоритма сортировки Бетчера, блок-схема которого для М = 8 показана на фиг, 2. Сигнал "ноль" с выхода триггера 19 пропускает на выходы мультиплексоров 6, 7 данные с входов 1, 2. На первом такте первая пара чисел поступает на входы мультиплексоров 8, 9 и на входы схемы 10 .сравнения. В зависимости от того, какое ; число больше - на входе 1 или на входе 2 -схема 10 сравнения вырабатывает значение логического нуля или единицы; Сигнал с выхода схемы 10 сравнения проходит через схему 11 ИСКЛЮЧАЮЩЕЕ ИЛИ и поступает на управляющий вход мультиплексоров 8. 9. Через мультиплексор 9 проходитна вход блока 13 большое число, а через мультиплексор 8 проходит на вход блока 12 меньшее число, В этом случае на второй вход схемы 11 ИСКЛЮЧАЮЩЕЕ,ИЛИ поступает из блока 18 сигнал логического нуля, Если же из блока 18 постоянной памяти поступает сигнал логической единицы, то схема 11 ИСКЛЮЧАЮЩЕЕ ИЛИ инвертирует сигнал с выхода схемы 10 сравнения и на входы блоков 12, 13 поступают соответственно большее и меньшее числа.Таким образом, на блоках 6-11 устройства выполняется базовая операция алго 15 20 регистров 14, 15 30 35 40, содеркимого счетчика 20 вычитается едини 55 510 45 50 ритма сортировки Бетчера, По высокому потенциалу тактового импульса в блоки 12, 13 оперативной памяти по адресам; поступающим из блока 18 постоянной памяти записывается первая пара входных чисел, Задним фронтом первого тактового импульса из содержимого счетчика 20 вычитается единица.Во втором такте аналогичнопроизводится запись в блоки 12, 13 оперативной памяти второй пары чисел, а. из содержимого счетчика 20 снова вычитается единица. После приема последней М/2-й пары чисел содеркимое с етчика 20 становится равным нулю, что говорит о завершении первого этапа. Сигнал с выхода счетчика 20, поступает на счетный вход счетчика 21, прибавляя к ето содержимому единь цу; проходит через схему 22 ИЛИ, записывая из блока 17 в счетчик ".,2 количество тактов, выполняемых на втором этапе, а также устанавливает триггер 19 в состояние "1". Сигнал с выхода триггера 19 переключает мультиплексоры 6 7, пропуская на их выхбды информацию С На втором этапе низким потенциаломпервого тактового импульса из блоков 12, 13 оперативной памяти. по адресам из блока 18 считывается первая пара чисел, которая положительным фронтом импульса записывается в регистры 14, 15,:На блоках 6-11 выполняется базовая операция алгоритма сортировки Бетчера, и высоким потенциалом импульса по тем же адресам в блоки 12, 13 оперативной памяти "записывается большее и меньшее числа,причем выбор блока оперативной памяти определяется структурой алгоритма сортировки, Задним фронтом первого тактового импульса из ца,Во втором такте аналогично выполняется вторая базовая операция алгоритма сортировки, а из содержимого счетчика 20 снова вычитается единица. После выполнения последнейбазовой операции второго этапа содержимое счетчика 20 становится равным нулю, что говорит о завершении второго этапа, Сигналом с выхода счетчика 20 производится прибавление к содержимому счетчика 21 единицы и запись через схему 22 ИЛИ в счетчик 20 количества тактов,выполняемых на третьем этапе.Аналогично описанному выполняется третий, четвертый и последующие этапы. На последнем этапе производится выгрузка просортированных данных из блоков 12, 13 оперативной памяти через регистры 14, 15 на выходы 24,25. После выгрузки последней пары чисел содержимое счетчика 20 стано1784966 10 15 20 30 45 50 55 вится равным нулю.и сигнал с его выхода прибавляет к содеркимому счетчика 21 единицу, информация с выхода счетчика 21 поступает ча блок 17 постоянной памяти и с его выхода на схему 23 И поступает сигнал "0", который закрывает ее и прекращается подача тактовых импульсов на соответствующие блоки устройства. На выход 26 поступает сигнал о завершении сортировки чисел. Граф алгоритма сортировки может быть представлен в блочном виде (фиг. 3) состоящим из трех блоков, что позволяет сформировать правило его построения, а также разработать программурасчета содержимого блока 18 постоянной памяти управляющего схемой 11 и формирующего адреса блоков 12, 13 оперативной памяти. Блоки А,В выполняют сортировку М/2 чисел, а блок С - их слияние. Каждый из блоков А, В снова можно разбить на три блока такого ке типа, только обрабатывающие в.2 раза меньше чисел и т,д., аж до двухвходовых блоков (базовой операции). Каждый третий блок содержит 1 оц Кэтапов. где К - количество входов блока, Содержимое разряда блока 18 постоянной памяти, управляющего схемой 11. рассчитывается следующим образом. Для первого этапа вычисления блоков С, входящих в блоки А, включая й-входовой, сигнал управления схемой 1 равен О, а для остальных этапов -1, Сигналы же управления схемой 11 при выполнении итерации блоков В зеркально симметричны соответствующим значениям для блоков А. На фиг, 2 в качестве примера над кружками базовых операций показаны значения сигналов управления схемой 1 для графа сортировки 8 чисел. Содержимое двух последних выходов 40 блока 18 постоянной памяти, являющеесяадресами блоков 12, 13 оперативной памяти,рассчитывается последующему алгоритму:задать (произвольно, или исходя из удобства работы) начальчые адреса записи входных данных в блоки 12, 13 оперативной памяти;определить значение сигнала управления схемой для всех тактов работы устройства;нарисовать граф алгоритма сортировки для заданного примера массива;возле каждой базовой операции алгоритма на графе проставить значение сигнала управления схемой 11;задать на выходах графа алгоритма номерячейки (адрес), куда записывается число;Ъпроставить на обоих входах каждой базовой операции на графе алгоритма номер блока памяти и адрес, по которому записывается число, При этом исходить из следующего; если возле данной базовой операции сигнал управления схемой 11 равен О - большее число записывается в блок 13 оперативной памяти, меньшее - в блок 12 оперативной памяти, по тем же адресам, по которым считывались оба числа. Если же сигнал управления схемой И равен 1, большее число записывается в блок 12, а меньшее - в блок 13.На фиг, 2 показан пример формированияадоесов для й = 8. Здесь через А обозначен блок 12 оперативной памяти, через В - блок 13 оперативной памяти. По адресам на выходах графа считываются выходные данные.В таблице в качестве примера приведено потактное состояние устройства для следующих пэр входных чисел: 5, 8: 6, 3; 1, 2;4, 7;По сравнению с прототипом на предлагаемое устройство требуются существенно меньшие затраты оборудования. Так, если необходимо выполнить сортировку 1024 чисел, то на реализациюпрототипа потребуется 116050 мультиплексоров и 58025 схем сравнения, тогда как для предлагаемого устройства при увеличении й увеличиваются только объемы оперативной и постоянной памяти. формула изобретения Устройство для сортировки чисел, содержащее четыре мультиплексора и блок сравнения, причем информационные входы первой и второй групп устройства соединены с информационными входами первой группы соответственно первого и второго мультиплексоров, выходы которых соединены с информационными входами соответственно первой и второй групп третьего мультиплексора и блока сравнения, а также с информационными входами соответственно второй и первой групп четвертого мультиплексора, управляющие входы третьего и четвертого мультиплексоров объединены, отл ича ющеес ятем, что, С целью уменьшения аппаратурных затрат, оно содеркит четыре блока памяти, три регистра, два счетчика, триггер, элемент И, элемент ИЛИ и.элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, причем выходы третьего и четвертого мультиплексоров соединены с информационными входами соответственно первого и второго блоков памяти, выходы которых соединены с информационными входами соответственно первого и второго регистров, выходы разрядов которых являются информационными выходами соответственно1784966:. 1:О 9первой и второй групп устройства и: соеди-: разрядов которого соедийены садресными нены с информацйонными,входами вторых, входами первой группы четвертого блока групп соответственно первого и второго памяти,адреснь 1 евходы второй группы комультиплексоров, управляющие входы ко- торого соединены с выходами разрядов втоторыхподключены к выходутриггера входы: 5 рого счетчика и адресными входамивторой установки в нулевое и-единичное состояйиегруппы третьего блокапамяти, выход кото- которого подключены соответствейно кпер-".:;:.- рого явля е гся выходомокончания работы вому и второму входам элемента ИЛИ, вы- ., устройства-и"соединен с первым входом Блок 13: Выходы 24. 25 Блох 12 Адрес блока 12 Такт Адрес блока 13 Сигнал уп- рав. ления схемой1 Этап О О х х х х х 4 4 6 . 2 6 2 6 .2 6 2 6 . 7 5 5 4 5 5 3 3 2 7 7 3 2 2 2 2 2 О О О 6 О 1 1 1 3 8 1 2 5 4 7,85 6.2 3 8 3 2 2:"2 х х 4. 3 2 6 1,2 5, 7.О ход которого соединен с входомустановки элемейта И; вьиод которого соединен сов нулевое состояние первого счетчика,вы счетным входом первого.ечетчика, входа- ход переполнения которого соединен с пер-ми синхронизации первогои.второго реги- вым входом элемента ИЛИ и счетным ". стровиуправляющймивходами первого.и входом второго счетчика, вход установки в второго блоков памяти, адреСные входы нулевое состояние которого соединен скоторых соедийены С выходами соответствторым входом элемента ИЛИ и входом 15 венно первой и второй групп четвертого начальной установки устройства, входы . блока памяти; выход которого и выход задания количества сортируемых чисел.ус- блока сравнейия соединенй соответетвентройства соединены с информационными но с первым и вторым входами"элемента входами третьего регистра, выходы разря- ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого дов которого соединены с адресными вхо соединен с управляющймвходом третье- дами первой группы третьего блока памяти, .го мультиплексора, второй вход элеменвыходы которого соединены с информаци-: та И подключейк тактовому входуустройонными входами первого счетчика, выходыства,1784966 ставитель А. Мельнихред М.Моргенталтор О, Кравцова тор Производственно-издательский комбинат "Патент", г. Ужгород ина, 101 4365 Тираж ПодписноеНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС113035, Москва, Ж, Раушская наб 4/5