Пристрій сортування даних

Пристрій сортування даних, що містить запам'ятовуючий пристрій, адресний вхід якого підключений до інформаційного виходу лічильника адреси, вхід якого є інформаційним входом пристрою, вихід і вхід підключені ВІДПОВІДНО до входу і виходу лічильника даних, що також підключений до входу компаратора, вихід лічильника адреси Винахід відноситься до обчислювальної техніки і може бути використаний при побудові проблемно-орієнтованих обчислювальних пристроїв цифрової обробки сигналів Відомий пристрій для сортування чисел (А А Мельник, А с СРСР №1123030, кл G06F7/06, опубл 30 12 1992р у Бюлетні №48), що містить блоки оперативної і постійної пам'яті, блок порівняння, мультиплексори, регістри, лічильники, тригер, елемент "ИСКЛЮЧАЮЩЕЕ ИЛИ", елемент "ИЛИ" і елемент "И" Спіль ними ознаками відомого пристрою і запропонованого є оперативний запам'ятовуючий пристрій, лічильник, блок порівняння і регістр Однак технічна задача підвищення швидкодії не може бути вирішена тільки пристроєм для сортування чисел тому, що блоки оперативної пам'яті адресуються за допомогою, послідовно включених блоків постійної пам'яті, що збільшує такт роботи пристрою на час вибірки даних із блоків постійної пам'яті Найбільш близьким до запропонованого є пристрій сортування даних (Опанасенко В Н , Сахарин В Г Структурная организация устройств сортировки в елементном базисе ПЛИС // Засоби комп'ютерної техніки з віртуальними функціями і підключений також до інформаційних входів блока ключів, виходи яких є інформаційними виходами пристрою, виходи з першого по четвертий блока керування підключені ВІДПОВІДНО ДО керуючого входу лічильника адреси, запам'ятовуючого пристрою, лічильника даних і блока ключів, а перший і другий входи підключені ВІДПОВІДНО до входу синхросигналів пристрою і до керуючого виходу компаратора, який відрізняється тим, що в нього додатково введені дешифратор адреси й індексний регістр, причому вхід дешифратора з'єднаний з виходом лічильника адреси і входами запам'ятовуючого пристрою і блока ключів, вихід дешифратора через індексний регістр з'єднаний із входом блока керування, п'ятий вихід якого з'єднаний із входом індексного регістра нові інформаційні технології Київ, 2002 - С 45-51), що містить лічильник адреса 1, запам'ятовуючий пристрій 2, лічильник даних 3, компаратор 4, ключі 5 і блок керування 6 (фіг 1) Адресний вхід запам'ятовуючого пристрою підключений до інформаційних входів ключів і до інформаційного виходу лічильника адреса, вхід якого є інформаційним входом пристрою, вихід підключений до входу лічильника даних, вхід підключений до входу компаратора і виходу лічильника даних, виходи, ключів 5 є інформаційними виходами пристрою, виходи з першого по четвертий блоку керування підключені ВІДПОВІДНО до керуючого входу лічильника адреса, запам'ятовуючого пристрою, лічильника даних і ключів, а перший і другий входи підключені ВІДПОВІДНО до входу синхросигналів пристрою і до керуючого виходу компаратора Спільними ознаками прототипу і запропонованого пристрою сортування даних є запам'ятовуючий пристрій, адресний вхід якого підключений до інформаційного виходу лічильника адреса, вхід якого є інформаційним входом пристрою, вихід і вхід підключені ВІДПОВІДНО до входу і виходу лічильника даних, що також підключений до входу компаратора, вихід лічильника адреса (О 1 ю 59716 тування Процес сортування містить у собі дві стадії стадію запису даних, що сортуються, у запам'ятовуючий пристрій і стадію зчитування відсортованих даних із запам'ятовуючого пристрою На першій стадії ПОСЛІДОВНІСТЬ даних, що сортуються, через лічильник адреса надходить на адресні входи запам'ятовуючого пристрою та у ВІДПОВІДНИЙ розряд індексного регістра через дешифратор адреса записується одиниця Зчитані з ЗП дані записуються в лічильник даних, модифікуються на "+1" і записуються назад у ЗП по тому ж самому адресу Далі цей процес повторюється для всіх даних, що надходять на вхід і сортуються На другій стадії сортування звертання до ЗП виробляється, починаючи з молодшого адреса При цьому, звернення буде вироблятися тільки до В основу винаходу поставлена задача створитих комірок ЗП, до яких було звернення на першій ти такий пристрій сортування даних, у якому ввестадії за рахунок установленої на першій стадії дення нових блоків дешифратора адреса й сортування одиниці у відповідному розряді індексного регістра дозволило б виключити непроіндексного регістра Одночасно дані з виходу дуктивні звертання до комірок пам'яті залічильника адреса через ключі передаються на пам'ятовуючого пристрою й аналіз їхнього вмісту інформаційний вихід пристрою Далі до лічильника на другій стадії сортування, при відсутності зверадреса додається одиниця, виробляється зсув тання до них на першій стадії, і збільшити швидіндексного регістра і, у залежності від значення кодію процесу сортування даних його молодшого розряду, виконується чергове Поставлена задача вирішується тим, що зчитування ЗП чи додавання одиниці до пристрій сортування даних містить лічильник адлічильника адреса Процес сортування реса, запам'ятовуючий пристрій, лічильник даних, закінчується по досягненні значення вмісту компаратор, ключі, блок керування, дешифратор лічильника адреса, рівного значенню старшого адреса й індексний регістр, адресний вхід заадреса ЗП пам'ятовуючого пристрою підключений до інформаційних входів ключів, входу дешифратора Число, що міститься в комірці заадреса і до інформаційного виходу лічильника пам'ятовуючого пристрою, визначає КІЛЬКІСТЬ КОДІВ, адреса, вхід якого є інформаційним входом прищо відповідають адресу цієї комірки, у масиві, що строю, вихід підключений до входу лічильника дасортується Формування керуючих сигналів виробних, вхід підключений до виходу лічильника даних ляється блоком керування і входу компаратора, виходи ключів є На фіг 1 наведена блок-схема прототипу інформаційними виходами пристрою, вихід деНа фіг 2 наведена граф-схема алгоритму рошифратора адреса підключений до боти пристрою сортування даних інформаційного входу індексного регістра, вихід На фіг 3 наведена блок-схема пристрою сорякого підключений до третього входу блоку керутування даних вання, п'ятий вихід якого підключений до керуючоПристрій містить лічильник адреса 1, заго входу індексного регістра, а виходи з першого пам'ятовуючий пристрій 2, лічильник даних 3, компо четвертий підключені ВІДПОВІДНО до керуючого паратор 4, ключі 5, блок керування 6, дешифратор входу лічильника адреса, запам'ятовуючого приадреса 7 та індексний регістр 8 строю, лічильника даних і ключів, а перший і друАдресний вхід запам'ятовуючого пристрою 2 гий входи підключені ВІДПОВІДНО до входу синхропідключений до інформаційних входів ключів 5, сигналів пристрою і до керуючого виходу входу дешифратора адреса 7 і до інформаційного компаратора виходу лічильника адреса 1, вхід якого є інформаційним входом пристрою, вихід ВІДМІННИМИ ознаками запропонованого припідключений до входу лічильника даних 3, вхід строю є те, що в його склад додатково введені підключений до виходу лічильника даних 3 і входу дешифратор адреса й індексний регістр, причому компаратора 4, виходи ключів 5 є інформаційними вхід дешифратора з'єднаний з виходом лічильника виходами пристрою, вихід дешифратора адреса 7 адреса і входами запам'ятовуючого пристрою і підключений до інформаційного входу індексного блоку ключів, вихід дешифратора через індексний регістра 8, вихід якого підключений до третього регістр з'єднаний з входом блоку керування, п'ятий входу блоку керування 6, п'ятий вихід якого вихід якого з'єднаний з входом індексного регістра підключений до керуючого входу індексного Введення цих ознак дозволило виключити нерегістра 8, а виходи з першого по четвертий продуктивні витрати часу, викликані послідовним підключені ВІДПОВІДНО до керуючого входу звертанням до всіх комірок запам'ятовуючого прилічильника адреса 1, запам'ятовуючого пристрою строю й аналізом їхнього вмісту (на другій стадії 2, лічильника даних 3 і ключів 5, а перший і другий сортування), включаючи і ті комірки, до яких не входи підключені ВІДПОВІДНО до входу синхросигбуло звертання на першій стадії сортування, за налів пристрою і до керуючого виходу компараторахунок чого підвищилась швидкодія процесу сорпідключений також до інформаційних входів блоку ключів, виходи яких є інформаційними виходами пристрою, виходи з першого по четвертий блоку керування підключені ВІДПОВІДНО ДО керуючого входу лічильника адреса, запам'ятовуючого пристрою, лічильника даних і блоку ключів, а перший і другий входи підключені ВІДПОВІДНО до входу синхросигналів пристрою і до керуючого виходу компаратора Однак технічна задача підвищення швидкодії не може бути вирішена тільки прототипом через непродуктивні витрати часу, викликані послідовним звертанням до всіх комірок запам'ятовуючого пристрою й аналізом їхнього вмісту на другій стадії сортування Цей недолік усувається тим, що в запропонованому пристрої виключаються звертання до тих комірок запам'ятовуючого пристрою, до яких не було звертання на першій стадії сортування 59716 pa 4 Пристрій працює в такий спосіб На першій стадії ПОСЛІДОВНІСТЬ даних, що сортуються, надходячи через лічильник адреса 1 на адресні входи запам'ятовуючого пристрою 2 дешифрується одночасно дешифратором адреса 7 Далі по кожному обраному адресу, що відповідає коду, який сортується, здійснюється зчитування слова із запам'ятовуючого пристрою 2 у лічильник даних 3, до зчитаного числа додається одиниця і модифіковане число по тому ж самому адресу записується в запам'ятовуючий пристрій 2 У циклі "зчитування числа із запам'ятовуючого пристрою 2, збільшення числа на одиницю, запис числа в запам'ятовуючий пристрій 2" в обраний дешифратором адреса 7 розряд індексного регістра 8 записується одиниця При багаторазовому звертанні по тому ж самому адресу одиниця, що знаходиться у відповідному розряді індексного регістра 8, підтверджується розряді індексного регістра 8 виробляється зчитування з відповідної комірки пам'яті і число, що зчитується, переписується в лічильник даних 3 Одночасно формується сигнал дозволу передачі даних і ВІДПОВІДНИЙ код масиву, що сортується, передається через ключі 5 з лічильника адреса 1 у приймач даних Далі з лічильника даних З віднімається одиниця і перевіряється його вміст Якщо лічильник даних 3 містить не нуль, то процес повторюється до очищення лічильника На виходах лічильника адреса 1 у цьому випадку будуть формуватися коди з відсортованої ПОСЛІДОВНОСТІ СТІЛЬКИ разів, скільки їх містилося в масиві, що сортується При очищенні лічильника даних 3 до лічильника адреса 1 додається одиниця, виробляється зсув даних індексного регістра 8 і в залежності від значення молодшого розряду індексного регістра 8 виконується зчитування запам'ятовуючого пристрою 2 чи додавання одиниці до лічильника адреса 1 На другій стадії сортування при послідовному переборі адреса запам'ятовуючого пристрою 2 здійснюється зсув даних індексного регістра 8 убік молодших розрядів і передача значення молодшого розряду індексного регістра 8 у блок керування 6 (молодший розряд індексного регістра 8 відповідає нульовій комірці запам'ятовуючого пристрою 2) При наявності одиниці в молодшому Усі блоки запропонованого пристрою можуть бути реалізовані на кристалі ПЛІС типу FPGA, наприклад фірми ХІІІПХ (США) Запропонований пристрій сортування даних, як випливає з опису, може бути реалізований промисловим способом, оскільки його складові вузли і блоки побудовані на основі елементної бази широкого застосування ІГ.1 59716 Комп'ютерна верстка Н Лисенко Підписано до друку 06 10 2003 Тираж39 прим Міністерство освіти і науки України Державний департамент інтелектуальної власності, Львівська площа, 8, м Київ, МСП, 04655, Україна ТОВ "Міжнародний науковий комітет", вул Артема, 77, м Київ, 04050, Україна