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

Изобретение относится к вычислительной технике и может быть исполь-,зовано в спецнализиронанных устройствах обработки информации, предназначенных для сортировки массивов данных в реальном масштабе времени.Цель изобретения - повышение быстродействйя.На чертеже представлена функцио Ональная схема устройства для сортировки чисел.Устройство содержит вход 1 начальной установки, вход 2 тактовых импульсов, и информационных входов 3, входной узел 4 сортировки, счетчик 5, блок 6 памяти, выходной коммутатор 7, выходы 8 устройства, 1 блоков 9шсортировки (Е = - ,где ш - количести ф 20но чисел сортируемого массива), каж)дый из которых содержит и приемныхрегистров 1 О, коммутатор 11, и регистров 12 результата, узел 13 сортиров -ки и коммутатор 14, 25Устройство работает следующимобразом.Перед началом работы импульсом свхода 1 счетчик 5 устанавливаетсяв нуль. Информация с выходов счетчика 5 поступает на адресные входы блока 6 памяти, в котором записана программа управления коммутатором 7 икоммутаторами 11 и 14 в блоках 9,9Кф35Для каждого 1-го блока 9 сорти-ровки (3=1 .,1 с) на 3-м выходе блока6 постоянной памяти формируется 4-разрядное управляющее слово, два старших разряда которого управляют коммутатором 11, а дна младших - коммутатором 14, В зависимости от значения информации на управляющих входахкоммутаторов 11 и 14, они устанавливаются в положение, когда на их выход поступает информация или с первых входов (информация на управляющих входах 00), или с вторых входов(информация на управляющих входах0,1), или с третьих входов (информация на управляющих входах 1 О), или счетвертых входов (информация на управляющих входах 11), только для коммутаторов 11,Управляющая информация для коммутатора 11 1-го блока 9сортировки нблоке 6 постоянной памяти записанаследующим образом: 00 - в ячейке поадресу 23-1; 01 - в ячейках по адресам с 0 по 3-2 и с 2 по 21 скромеблока 9,; 10 - в ячейках по адресамс 3 по 2(3-1), кроме 91, 11 - в ячейке по адресу 3-1.Управляющая информация для коммутатора 14 3-го блока 9 сортировкии блоке постоянной памяти записанаследующим образом: 00 - в ячейкахпо адресам с 3 по 2 (1-1), кромеблока 91; 01 - в ячейках по адресамс 0 по (1 - 1) и с 23 по (21 с); 10в ячейке по адресу 23-1,С (1+1)-го выхода блока бпамятисчитывается управляющая информациядля коммутатора 7, При поступлениина управляя щий вход коммутатора 7информации, равной (1-1), где 1 = 1,2. 1 с + 1, на выход коммутаторапоступает информация с 1-ых входов.Управляющая информация для коммутатора 7 в блоке постоянной памяти записана следующим образом: в ячейке поадресу (3-1) записано число (1 - 1);в ячейках по адресам с 1 по 21-2 записано число 1-1; в ячейке по адресу21- записано число 1.В первом такте и чисел первогосортируемого массива с входа 3 поступают .на входы узла 4 сортировки, гдеони сортируются и поступают на выходв порядке убывания, т,е. наибольшеечисло будет на первом выходе, следующее по величине число на втором выходе и т.д наименьшее на и-м выходе, С нулевой ячейки блока 6 постоянной памяти считывается первоеуправляющее слово, которое устанавливает: коммутатор 7 на передачу информации с первого входа; коммутатор11 блока 9 на передачу информациис четвертого входа; коммутаторы 11блоков 9 9и коммутаторы 14 блоблоков 9 .,9на передачу информации с второго входа.По переднему фронту первого тактового импульса происходит записьинформации в регистры 10 и 12 в блоках 99 к и увеличение содержимого счетчика 4 на единицу,Во втором такте и следующих чисел первого сортируемого массива поступают на входы узла 4 сортировки, на выходе которого получаем просортированные числа в порядке убывания. С первой ячейки блока 6 постоянной памяти считывается второе управляющее слово, которое устананливает: ком 15874935055 мутатор 7 на передачу информации с второго входа; коммутаторы 11 и 14. блока 9 на передачу информации соответственно с первого и третьего входов; коммутатор 11 блока 9 на передачу информации с четвертого входа; коммутаторы 11 блоков 9 . ,9 к и коммутаторы 14 блоков 99 к 1 на передачу информации с вторых входов, По переднему фронту второго тактового импульса происходит запись информации в регистры 10 и 12 в блоках 99 к и увеличение содержимого счетчика 4 на единицу,В третьем такте и следующих чисел первого сортируемого массива поступают на входы узла 4 сортировки,где они сортируются в порядке убывания,В первом блоке 9 сортировки п первых просортированных чисел с выходов регистров 12 и п торых просортированных чисел с выходов регистров 10 поступают на входы узла 13 сортировки, где они сортируются и .поступают на выходы в порядке убывания, т.е. наибольшее число на первом выходе, следующее по величине число на втором и т.д наименьшее по величине на 2 п выходе. С второй ячейки узла в постоянной памяти считывается третье управляющее слово, которое устанавливает: коммутатор 7 на передачу информации с третьего входа; коммутаторы 11 и 14 блска 9на передачу информации соответственно с третьего и первого входов; коммутаторы 11 блоков 91,9 9 к и коммутаторы 14 блоков 9,9,,9 кна передачу информации с вторых входо вПо переднему фронту третьего так- тового импульса происходит запись информации в регистры 10 и 12 в блоках 99 к и увеличение содержимого счетчика 4 на единицу.В следующих тактах устройство работает аналогичноПосле 21-го тактового импульса счетчик 5 устанавливается в нуль, в регистрах 10 и 12 устройства размещены числа первого частично просортированного массива, причем на выход коммутатора 7 поступает и наибольших чисел первого массива. По приходу следующих тактовых импульсов одновременно с сортировкой и выводом результатов сортировки первого 1 О 15 20 25 30 35 40 45 массива производится ввод и сортировка второго массива и т.д. Числа, просортированные в порядке убывания,снимаются с выхода 8,Формула и э о б р е т енияУстройство для сортировки чисел, содержащее 1 блоков сортировки, гдеш- (ш - количество чисел сортируеимого массива, и - количество информационных входов устройства), причем каждый блок сортировки содержит приемный регистр, регистр результатов и ком-, мутатор, синхровходы всех регистров всех блоков сортировки объединены и являются тактовым входом устройства,в каждом блоке сортировки выходы разрядов регистра результата соединены .с входами первой группы коммутатора,выходы коммутатора (-1)-го блока сортировки (1=2,.,1) соединены с информационными входами регистра д-го блока сортировки, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия., в него введены входной. узел сортировки, счетчик, блок памяти, выходной коммутатор, в (д)-й блок сортировки введены узел сортировки и второй коммутатор, в 1-й блок сортировки введен узел сортировки, причем информационные входы чисел устройства соединены с выходами чисел входного узла сортировки, выходы чисел которого соединены с информационными входами приемного регистра первого блока сортировки, во всех блоках сортировки выходы разрядов приемного регистра соединены с входами первых групп узла сортировки и второго коммутатора, выходы которого соединены с информационными входами регистра результата, выходы разрядов которого со. единены с входами второй группЫ узла сортировки, в (1-1)-х блоках сортировки выходы первой и второй группузла сортировки соединены соответственно с входами второй и третьей групп первого и второго коммутаторов, выходы первой группы узла сор" тировки 3-го блока сортировки Ц =11 с) соединены с входами 3-й группы выходного коммутатора, входы +1)-й группы которого соединены с,выходами разрядов регистры результата 1-го блока сортировки, в 1-м блоке сортировки выходы первой группы1587493 Составитель В. КозловРедактор Н. ЯцолаТехред М,Дидык Корректор М. Максимишинец Заказ 2420 Тираж 563 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул, Гагарина,101 узла сортировки соединены с входамивторой группы второго коммутатора,входы второй группы узла сортировкисоединены с входами третьей и четвертой групп второго коммутатора и свходами четвертых групп коммутаторов(-1)-х блоков сортировки, вход начальной установки устройства соединен с входом начальной установки 1 Осчетчика, счетный вход которого соединен с тактовым входом устройства,а выходы разрядов соединены с входами блока памяти, 3-й выход которого соединен с управляющими входами первого и второго коммутаторов3-го блока сравнения, +1)-й выходблокапамяти соединен с управляющимвходом выходного коммутатора выход которого является выходом устройства.