Пристрій для паралельного зовнішнього сортування даних

Реферат: UA 97237 U UA 97237 U 5 10 15 20 25 30 35 40 45 50 Корисна модель належить до обчислювальної техніки і може застосовуватись в системах управління базами даних та інших комп'ютерних системах, що потребують сортування великих обсягів даних. Відомий пристрій та спосіб для паралельного сортування злиттям [патент США US 2005/0144167 А1 МПК G06F7/00, Jun. 30, 2005], який містить блок для злиття символьних рядків, блок для поділу даних на два рядки, блок сортування, блок адміністрування системою, блок зберігання даних і блок керування, вихід якого зв'язаний з входом блока адміністрування системою, який за допомогою шини керування зв'язаний з блоком для злиття символьних рядків, блоком для поділу даних на два рядки і блоком сортування, причому блок зберігання даних за допомогою шини даних зв'язаний з блоком сортування, блоком для поділу даних на два рядки і блоком для злиття символьних рядків. Недоліком цього пристрою є великі апаратні витрати і великі витрати часу, обумовлені можливістю лише попарного злиття відсортованих символьних рядків на останньому етапі сортування. Найбільш близьким по технічній суті до запропонованого є пристрій для сортування [Патент США US 5727200, МПК G06F17/30, Маr. 10, 1998], що містить генератор початкової множини даних, блока розподілу даних, набір р блоків часткового сортування і блок порівняння та вибору входів, p входів якого з'єднані відповідно з виходами p блоків сортування, входи яких з'єднані відповідно з p виходами блока розподілу даних, вхід якого з'єднаний з виходом генератора початкової множини даних. У відомому пристрої сортування даних складається з трьох етапів: етапу розподілу даних, етапу часткового сортування (сортування векторів) і етапу повного сортування (злиття даних). У відомому пристрої суміщаються перші два етапи, за винятком сортування останнього вектора. Етап повного сортування розпочинається лише після повного завершення сортування першого вектора. Основним недоліком такого пристрою є необхідність зберігання відсортованих векторів даних, що вимагає додаткових витрат обладнання та додаткового часу. В основу корисної моделі поставлена задача створення пристрою для паралельного зовнішнього сортування даних, в якому за рахунок введення нових блоків та зв'язків, паралельного виконання етапів часткового та повного сортування, а також відсутності в потребі зберігання відсортованих векторів даних, досягається можливість прискорення операції зовнішнього сортування та розширення функціональних можливостей пристрою. Поставлена задача вирішується за рахунок того, що у пристрій для паралельного зовнішнього сортування даних, який складається із p блоків часткового сортування, блока розподілу даних, p виходів якого з'єднані з входами p блоків часткового сортування, введені блок пам'яті вхідних даних, блок пошуку мінімального елемента, блок пошуку максимального елемента, блок пам'яті вихідних даних, блок керування, виходи якого з'єднані з входами керування блока розподілу даних, p блоків початкового сортування, блока пам'яті вихідних даних і блока пам'яті вхідних даних, інформаційний вхід якого з'єднаний з інформаційним входом пристрою, а вихід з'єднаний з інформаційним входом блока розподілу даних, p виходів якого з'єднані, відповідно, з інформаційними входами p блоків сортування, виходи мінімуму і виходи максимуму яких з'єднані відповідно, з входами блока пошуку мінімального елемента і блока пошуку максимального елемента, виходи яких з'єднані відповідно з першим інформаційним входом і другим інформаційним входом блока пам'яті вихідних даних, інформаційний вихід якого під'єднаний до інформаційного виходу пристрою, вхід керування якого з'єднаний з входом початкового установлення блока керування. На фіг. 1 представлена функціональна схема пристрою; на фіг. 2 - функціональна схема і-го блока часткового сортування; на фіг. 3 - функціональна схема блока пошуку мінімального елемента; на фіг. 4 - функціональна схема блока пошуку максимального елемента. Пристрій для паралельного зовнішнього сортування даних (фіг. 1) містить блок 1 пам'яті вхідних даних, блок 2 розподілу даних, p блоків 31,,3p часткового сортування, блок 4 пошуку мінімального елемента, блок 5 пошуку максимального елемента, блок 6 пам'яті вихідних даних і блок 7 керування, виходи якого з'єднані з входами керування блока 2 розподілу даних, p блоків 31,,3p часткового сортування, блока 6 пам'яті вихідних даних і блока 1 пам'яті вхідних даних, 55 інформаційний вхід якого з'єднаний з входом 8 пристрою, а вихід з'єднаний з інформаційним входом блока 2 розподілу даних, p виходів якого з'єднані, відповідно, з інформаційними входами p блоків 31,,3p початкового сортування, виходи мінімуму і виходи максимуму яких з'єднані відповідно, з входами блока 4 пошуку мінімального елемента і входами блока 5 пошуку 1 UA 97237 U 5 максимального елемента, виходи яких з'єднані відповідно з першим інформаційним входом і другим інформаційним входом блока пам'яті вихідних даних, інформаційний вихід якого під'єднаний до інформаційного виходу 9 пристрою, вхід 10 керування якого з'єднаний з входом початкового установлення блока 7 керування. Блок 3i i  1  p часткового сортування даних (фіг. 2) містить інформаційний вхід 11i , вхід 12i керування, вихід 13 i мінімуму і вихід 14 i максимуму. Блок 4 пошуку мінімального елемента (фіг. 3) містить 2  log 2 p  1 вузлів 15 вибору мінімального з двох елементів, які утворюють log 2 p -рівневе бінарне дерево, у якому вузол 15, 10 15 20 25 що відповідає кінцевій вершині дерева, має входи 16 j1 і 16 j  j  2  p  , а вихід вузла 15, що відповідає кореневій вершині дерева, з'єднаний з виходом 17 блока. Блок 5 пошуку максимального елемента (фіг. 3) містить 2log2 p  1 вузлів 18 визначення   максимального з двох елементів, які утворюють log 2 p -рівневе бінарне дерево, у якому вузол 18, що відповідає кінцевій вершині дерева, має входи 19 j1 і 19 j  j  2  p  , а вихід вузла 18, що відповідає кореневій вершині дерева, з'єднаний з виходом 20 блока. Пристрій працює таким чином. В блок 1 пам'яті вхідних даних по входу 8 надходить невідсортована послідовність S із n чисел. У пристрої реалізовано спосіб для зовнішнього сортування даних, який складається з трьох етапів: - етапу розподілу даних, - етапу часткового сортування (сортування векторів), - етапу повного сортування(злиття даних). На етапі розподілу даних початкова послідовність S за допомогою блока 2 розподілу даних поділяється на p векторів із m елементів n  p  m . На наступному етапі p векторів одночасно надходять на p блоків 31,,3p часткового сортування. В блоці 3i часткового сортування протягом m ітерацій відбувається сортування вектора i методом простого 2 вибору i  1  p . В кінці першої ітерації визначається мінімальний елемент e вектора i , min який поміщається на початок вектора i і визначається максимальний елемент e вектора max i , який поміщається в кінець вектора i . Мінімальні елементи векторів  i ,,  p утворюють 30 35 40 45 вектор мінімальних елементів  min , а максимальні елементи  i ,,  p утворюють вектор максимальних елементів  max . На наступних ітераціях визначають чергові мінімальні і максимальні елементи кожного вектора серед невідсортованих елементів цих векторів. Після завершення етапу часткового сортування в початкових позиціях блоків 31,,3p знаходяться мінімальні елементи, а в кінцевих позиціях цих блоків - максимальні елементи відповідних векторів. Етап повного сортування полягає у формуванні відсортованої послідовності S через злиття відсортованих векторів i . Для цього використовується метод вибору мінімальних і максимальних елементів за допомогою бінарних дерев. Спочатку перший вектор  min мінімальних елементів з перших позицій блоків 31,,3p надходить на p входів блока 4 пошуку мінімального елемента. Одночасно перший вектор  max максимальних елементів з останніх позицій блоків 31,,3p надходить на p входів блока 5 пошуку максимального елемента. Протягом однієї ітерації в блоці 4 пошуку мінімального елемента визначається мінімальний елемент першого вектора  min , тобто мінімальний елемент початкової послідовності S , і записується за першою адресою блока 6 пам'яті вихідних даних. Протягом цієї ітерації в блоці 5 пошуку максимального елемента визначається максимальний елемент першого вектора  max , тобто максимальний елемент початкової послідовності S , і записується за останньою адресою блока 6 пам'яті вихідних даних. Таким чином, в блоці 6 пам'яті вихідних даних починає формуватися відсортована послідовність S sort . 2 UA 97237 U 5 На j-й ітерації етапу повного сортування із j-го вектора  min мінімальних елементів за допомогою блока 4 пошуку мінімального елемента визначається мінімальний елемент, який записується за j-ю адресою блока 6 пам'яті вихідних даних, тобто переміщається в j-у позицію послідовності S sort . Одночасно із j-го вектора  max максимальних елементів за допомогою блока 5 пошуку максимального елемента визначається максимальний елемент, який записується за n  j  1 -ю адресою блока 6 пам'яті вихідних даних, тобто переміщається в n  Ssort  j  1   . 2  Елементи, які поміщаються у відсортовану послідовність S sort , вилучаються із блоків 31,,3p , а на їх місце надходять із відповідних векторів i наступні по зростанню та спаданню елементи. Через n ітерацій буде завершено етап повного сортування і в блоці 6 пам'яті вихідних 2 даних буде сформована повністю відсортована послідовність S sort . Якщо тривалість часу ітерацій на етапах часткового і повного сортування буде однакова, тоді ці етапи можна частково сумістити і виконувати паралельно. Можливість суміщення в часі двох етапів сортування основана на тому, що після кожної ітерації етапу часткового сортування векторів підготовляються початкові дані для проведення однієї ітерації етапу повного сортування. Відразу після закінчення першої ітерації етапу часткового сортування будуть визначені перші вектори  min і  max , тому можна розпочинати етап повного сортування. Тоді загальна кількість ітерацій для сформування відсортованої послідовності S sort становитиме n  j  1 -у позицію послідовності 10 15 20 n .   1 2  Блок 4 пошуку мінімального елемента працює таким чином. На p входів 161,,16 p блока 4 надходить вектор  min мінімальних елементів. Для визначення найменшого серед елементів вектора  min використовується спосіб log 2 p  25  рівневого бінарного дерева. Бінарне дерево реалізоване за допомогою 2log2 p  1 вузлів 15 визначення мінімального з двох елементів. На виході вузлів 15 першого рівня формується мінімальні елементи серед пар сусідніх вхідних елементів, які надходять з входів 161,,16 p блока. На виході вузлів 15 (j+1)-го рівня формується мінімальні елементи серед пар сусідніх вхідних елементів, які отримані з вузлів 15 j-го рівня  j  1  log 2 p  . На виході 17 блока 4 буде 30 сформований мінімальний елемент серед всіх елементів вектора  min . Блок 5 пошуку максимального елемента працює таким чином. На р входів 191,,19 p блока 5 надходить вектор  max максимальних елементів. Для визначення найбільшого серед елементів вектора  min використовується спосіб  35 log 2 p  log 2 p рівневого бінарного дерева. Бінарне дерево реалізоване за допомогою 2  1 вузлів 18 визначення максимального з двох елементів. На виході вузлів 18 першого рівня формується максимальні елементи серед пар сусідніх вхідних елементів, які надходять з входів 191,,19 p блока. На виході вузлів 18 (j+1)-го рівня формується максимальні елементи серед пар сусідніх вхідних елементів, які отримані з вузлів 18 j-го рівня  j  1  log 2 p  . На виході 20 блока 5 буде 40 45 сформований максимальний елемент серед всіх елементів вектора  max . Блоки 4 і 5 працюють одночасно. Таким чином, у відомому пристрої відбувається суміщення у часі етапів часткового та повного сортування, за винятком першої ітерації. Загальний час T1 сортування n елементів даних у запропонованому пристрої складає: T1  pt роз  t ітер  t1 , пов де t роз - тривалість розподілу n елементів даних по p векторах; t ітер - тривалість однієї ітерації сортування; t1 - тривалість етапу повного сортування. пов Загальний час T2 сортування n елементів даних у відомому пристрої складає: 3 UA 97237 U 2 T2  pt роз  t сорт  t пов , де t сорт - тривалість етапу сортування останнього вектора даних; 5 10 2 t пов - тривалість етапу повного сортування. Тривалість однієї ітерації сортування менша за час сортування одного вектора даних: t ітер  t сорт . Завдяки одночасному пошуку мінімальних та максимальних елементів вдвічі зменшується тривалість етапу повного сортування: 1 2 t1  t пов . пов 2 Крім того, не потрібно зберігати відсортовані вектори даних, що дає додаткову економію часу та обладнання. Таким чином: T1  T2 . ФОРМУЛА КОРИСНОЇ МОДЕЛІ 15 20 25 1. Пристрій для паралельного зовнішнього сортування даних, який складається із p блоків часткового сортування, блока розподілу даних, p виходів якого з'єднані з входами p блоків часткового сортування, який відрізняється тим, що в нього введені блок пам'яті вхідних даних, блок пошуку мінімального елемента, блок пошуку максимального елемента, блок пам'яті вихідних даних, блок керування, виходи якого з'єднані з входами керування блока розподілу даних, p блоків початкового сортування, блока пам'яті вихідних даних і блока пам'яті вхідних даних, інформаційний вхід якого з'єднаний з інформаційним входом пристрою, а вихід з'єднаний з інформаційним входом блока розподілу даних, р виходів якого з'єднані, відповідно, з інформаційними входами р блоків сортування, виходи мінімуму і виходи максимуму яких з'єднані, відповідно, з входами блока пошуку мінімального елемента і блока пошуку максимального елемента, виходи яких з'єднані, відповідно, з першим інформаційним входом і другим інформаційним входом блока пам'яті вихідних даних, інформаційний вихід якого під'єднаний до інформаційного виходу пристрою, вхід керування якого з'єднаний з входом початкового установлення блока керування. 2. Пристрій за п. 1, який відрізняється тим, що блок пошуку мінімального елемента містить 2 log 2 p 2 30 log 2 p   1 вузлів вибору мінімального з двох елементів, які утворюють log 2 p -piвневе бінарне дерево, у якому вузол, що відповідає кінцевій вершині дерева, має входи  j  1 і j-й  j  2  p  , а вихід вузла, що відповідає кореневій вершині дерева, з'єднаний з виходом блока. 3. Пристрій за п. 1, який відрізняється тим, що блок пошуку максимального елемента містить 35   1 вузлів вибору максимального з двох елементів, які утворюють бінарне дерево, у якому вузол, що відповідає кінцевій вершині дерева, має log 2 p -piвневе входи  j  1 і j-й  j  2  p  , а вихід вузла, що відповідає кореневій вершині дерева, з'єднаний з виходом блока. 4 UA 97237 U 5 UA 97237 U Комп’ютерна верстка А. Крулевський Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 6