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

Реферат: UA 93797 U UA 93797 U 5 10 15 Корисна модель належить до операцій сортування даних і може бути використана в системах управління базами даних, в інформаційно-вимірювальних та інших системах, пов'язаних з обробкою великих обсягів даних. Відомі способи зовнішнього сортування даних: прямого злиття, багатофазного злиття, каскадного злиття [Д. Э. Кнут Искусство программирования для ЭВМ, т. 3, Сортировка и поиск. Пер. с англ. - М.: Мир, 1978. - С. 174]. Недоліками цих способів є велика кількість операцій запису і зчитування для зовнішніх носіїв даних, наявність спеціальних умов для ефективного виконання задачі сортування. Найбільш близьким за технічною суттю до запропонованого є спосіб паралельного злиття/сортування за допомогою паралельних процесорів [патент США US 2005/0144167 А1 М. кл., G06F 7/00, Jun. 30, 2005], який складається із етапу проміжного сортування і етапу повного сортування, на етапі проміжного сортування невідсортований рядок S із n чисел поділяється на p векторів із m чисел кожний, які сортуються паралельно, на етапі повного сортування відсортовані вектори методом злиття формують відсортований рядок чисел більшої довжини одночасно в порядку зростання значень чисел і в порядку спадання значень чисел, етап повного сортування розпочинається: закінчення етапу проміжного сортування і триває log2 p ітерацій, на і -й ітерації із p відсортованих векторів методом попарного злиття кожних двох сусідніх рядків (двох сусідніх векторів на першій ітерації) із 25 30 35 2 i 1 чисел формується чисел з використанням 2i 1 паралельних процесів (i  1  log 2 p) . Недоліками цього способу є великі витрати часу внаслідок великої кількості операцій запису і зчитування для зовнішніх носіїв даних та послідовного використання двох процедур сортування: процедури сортування частин рядків і багатокрокової процедури злиття частин рядка в один відсортований рядок. В основу корисної моделі поставлена задача створення способу для паралельного зовнішнього сортування даних, згідно якого зменшується кількість операцій запису та зчитування даних на зовнішній носій даних та суміщаються в часі процеси сортування частин рядків (векторів) і злиття відсортованих векторів в один відсортований рядок, в результаті чого зменшуються загальні витрати часу на виконання зовнішнього сортування даних. Поставлена задача вирішується тим, що в способі для паралельного зовнішнього сортування даних, який складається із етапу проміжного сортування і етапу повного сортування, на етапі проміжного сортування невідсортований рядок S із n чисел поділяється на p векторів із m чисел кожний, які сортуються паралельно, на етапі повного сортування відсортовані вектори методом злиття формують відсортований рядок чисел більшої довжини одночасно в порядку зростання значень чисел і в порядку спадання значень чисел, причому на етапі проміжного сортування p векторів протягом m 2 ітерацій сортуються з використанням 2p паралельних процесів методом вибору за допомогою бінарного дерева, на одній ітерації етапу відсортований рядок із у 20 p p 2i h проміжного сортування процес Z i сортує вектор vi в порядку зростання і одночасно з ним процес Z ls сортує вектор vi в порядку спадання і визначаються відповідні мінімальні і i максимальні значення вектора i (i  1  p) , після закінчення першої ітерації етапу проміжного 40 сортування розпочинається етап повного сортування, на якому протягом n 2 ітерацій з ls використанням паралельних процесів Z h end та Z end методом вибору за допомогою бінарного дерева формується відсортований рядок Ssort із заданих n чисел, на k-й ітерації етапу повного сортування із чергових мінімальних значень чисел всіх векторів з використанням першого 45 h процесу Z end визначається найменше число, яке переміщається в k - у позицію рядка Ssort і одночасно із чергових максимальних значень чисел всіх векторів з використанням процесу Z ls end 50 визначається найбільше число, яке переміщається в (n  k  1)  y позицію рядка n S sort (k  1  ) , після вибору мінімального (максимального) числа із відповідного вектора на 2 його місце переміщається чергове в порядку зростання (спадання) число цього вектора, тривалість ітерації тієї частини етапу повного сортування, яка суміщається із етапом проміжного сортування, повинна бути такою ж, як і тривалість ітерації етапу проміжного сортування. 1 UA 93797 U 5 Спосіб здійснюється наступним чином. Задано невідсортований рядок із n чисел S  {s1, s2,..., sn } , з якого необхідно сформувати рядок чисел Ssort з відсортованими в порядку зростання числами. Рядок S поділяється на p векторів 1,  2 ,...,  p , кожний з яких містить по m чисел. Спосіб сортування складається з двох етапів: - етапу проміжного сортування; - етапу повного сортування. Етап проміжного сортування полягає у формуванні p відсортованих векторів за допомогою h 2p паралельних процесів, створених відповідно у 2p процесорах. Процес Z сортує вектор i в i 10 порядку зростання і одночасно з ним процес сортує вектор i в порядку спадання (i  1  p) . Для сортування векторів використовується метод сортування вибором за допомогою бінарного min дерева. Для вектора i формується дерево Dmax та дерево D (i  1  p) . Числа вектора i Z ls l i i 15 утворюють кінцеві вершини обох дерев. Протягом першої ітерації визначаються мінімальне і максимальне числа кожного вектора. На першому кроці першої ітерації сортування вектора i порівнюються сусідні числа і ' '' визначаються з них мінімальне число ei (у дереві Dmin ) і максимальне число e i (у дереві i Dmax ). На j-му рівні обох дерев порівнюються відповідні пари чисел, знайдених на (j-1)-му рівні i ' ( j  1  log 2 m) . В кінці першої ітерації в корні дерева Dmin формується мінімальне число e min i max вектора i , яке поміщається на початок вектора i , а в корні дерева Di формується 20 25 '' максимальне число emax вектора i , яке поміщається в кінець вектора i (Фіг. 1). На наступних ітераціях визначають чергові мінімальні і максимальні числа кожного вектора серед невідсортованих чисел цих векторів. Через m 2 ітерацій буде завершено сортування всіх векторів. Після завершення етапу проміжного сортування в початкових позиціях всіх векторів знаходяться мінімальні числа, а в кінцевих позиціях - максимальні числа відповідних векторів. Кількість кроків для виконання етапу проміжного сортування складає не більше, ніж N1 кроків: N1  m log 2 m 2 Етап повного сортування полягає у сортуванні масиву M через злиття відсортованих векторів i . Для виконання цього етапу використовується метод сортування вибором за 30 допомогою бінарних дерев Dmax і Dmin та паралельних процесів Z h і Z ls . Початкові позиції end end end end векторів i утворюють вектор мінімальних значень  min , а кінцеві позиції векторів i утворюють вектор максимальних значень max . Числа вектора  min утворюють кінцеві вершини дерева Dmin , а числа вектора max утворюють кінцеві вершини дерева Dmax . end end min 35 В кінці першої ітерації другого етапу сортування в корні дерева D end за допомогою процесу h Z end формується найменше число вектора  min , яке поміщається на початок рядка Ssort , а в max ls корні дерева Dend за допомогло процесу Z end формується найбільше число вектора max , яке поміщається в кінець рядка Ssort . На k-й ітерації етапу повного сортування із вектора мінімальних значень  min з використанням першого процесу Z h end визначається найменше число, яке переміщається в k-у позицію рядка Ssort і одночасно із вектора максимальних 40 значень max з використанням Z ls end процесу визначається найбільше число, яке n переміщається в (n  k  1)  y позицію рядка S sort (k  1  ) . 2 Числа, які поміщаються у відсортований рядок Ssort , вилучаються із векторів  min та max , а на їх місце поступають із відповідних векторів i наступні по зростанню та спаданню числа. 2 UA 93797 U 5 10 15 20 Через n 2 ітерацій буде завершено формування відсортованого масиву Msort . Кількість кроків для виконання етапу повного сортування складає не більше, ніж N2 кроків: n N2  log 2 p 2 . Для скорочення загального часу сортування етап проміжного та етап повного сортування можна частково сумістити і виконувати паралельно. Можливість суміщення в часі двох етапів сортування основана на тому, що після кожної ітерації етапу проміжного сортування векторів підготовляються початкові дані для проведення однієї ітерації етапу повного сортування. Відразу після закінчення першої ітерації етапу проміжного сортування можна розпочинати етап m повного сортування. Етап проміжного сортування триває перші t1  ітерацій, етап повного 2 n сортування триває з другої по t 2 ітерацію ( t 2  2  1) (Фіг.2). Протягом того періоду часу, коли обидва етапи сортування взаємно суміщаються, тривалість ітерацій на цих етапах повинна бути однаковою і визначатися тривалістю тієї ітерації, що вимагає більше часу. Порівняльна оцінка витрат часу на проведення сортування запропонованим та відомим способами. Протягом однієї ітерації першого етапу сортування для кожного процесу відбувається m операцій зчитування елементів вектора з оперативної пам'яті, log2 m операцій сортування процесором та дві операції запису результату в оперативну пам'ять (обмін позиціями для мінімального або максимального чисел), отже загальна тривалість ітерації складає 1 Ts,it  m  RAM  log2 m  proc  2RAM , де RAM - час доступу до оперативної пам'яті, proc - час роботи процесора. Загальна тривалість першого етапу сортування запропонованим способом складає m T1  T1,it . s 25 30 35 2 Тривалість перших етапів запропонованого і відомого способів приблизно однакові. Протягом однієї ітерації другого етапу сортування запропонованим способом для кожного процесу відбувається m операцій зчитування елементів векторів з оперативної пам'яті, log 2 p операцій сортування процесором та одна операція запису результату на зовнішній носій даних (наприклад, магнітний диск), отже загальна тривалість ітерації складає 2 Ts ,it  m  RAM  log2 m  proc  disk . disk - час доступу до зовнішнього носія даних. де Загальна тривалість другого етапу сортування запропонованим способом складає n 2 2 Ts   Ts ,it . 2 Протягом однієї ітерації другого етапу сортування відомим способом під час злиття на зовнішньому носії даних двох рядків із k чисел в один рядок із 2k чисел відбувається k операцій зчитування із зовнішнього носія даних, 2k операцій запису на зовнішній носій даних, а також k операцій порівняння за допомогою процесора (k  2m, 4m,...) , отже загальна тривалість ітерації складає 2 Tk ,it  40 s 1 (2n   disk  2  proc ) . 2 Загальна тривалість другого етапу сортування відомим способом складає 2 Tk  1 n n (2n  log 2 p  1)  disk   disk   log 2 p  proc . 2 2 2 При виконанні процедури зовнішнього сортування на сучасних комп'ютерах основні витрати (  disk  RAM,  disk  proc ) часу припадають на звертання до зовнішніх носіїв даних . Тому можна вважати, що 45 2 Ts  n 1 n 2   disk , Tk  (2n  log 2 p  1)   disk    disk . 2 2 2 3 UA 93797 U Таким чином, в  разів зменшуються витрати часу на зовнішнє сортування запропонованим і відомим способами за рахунок зменшення кількості операцій звертання до зовнішніх носіїв даних: T2   k  2(log 2 p  1)  1 . 2 Ts 5 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 10 Спосіб для паралельного зовнішнього сортування даних, який складається із етапу проміжного сортування і етапу повного сортування, на етапі проміжного сортування невідсортований рядок S із n чисел поділяється на p векторів із m чисел кожний, які сортуються паралельно, на етапі повного сортування відсортовані вектори методом злиття формують відсортований рядок чисел більшої довжини одночасно в порядку зростання значень чисел і в порядку спадання значень чисел, який відрізняється тим, що на етапі проміжного сортування p векторів протягом m 2 ітерацій сортуються з використанням 2p паралельних процесів методом вибору за допомогою 15 бінарного дерева, на одній ітерації етапу проміжного сортування процес Z h сортує вектор i в i порядку зростання і одночасно з ним процес Z ls сортує вектор i - в порядку спадання і i визначаються відповідні мінімальні і максимальні значення вектора i ( 1  p) , після закінчення першої ітерації етапу проміжного сортування розпочинається етап повного сортування, на ls якому протягом n 2 ітерацій з використанням паралельних процесів Z h end та Z end методом 20 25 вибору за допомогою бінарного дерева формується відсортований рядок Ssort із заданих n чисел, на k -й ітерації етапу повного сортування із чергових мінімальних значень чисел всіх векторів з використанням першого процесу Z h визначається найменше число, яке end переміщається в k -у позицію рядка Ssort і одночасно із чергових максимальних значень чисел всіх векторів з використанням процесу, визначається найбільше число, яке переміщається в n (n  k  1)  y позицію рядка S sort (k  1  ) , після вибору мінімального (максимального) числа із 2 відповідного вектора на його місце переміщається чергове в порядку зростання (спадання) число цього вектора, тривалість ітерації тієї частини етапу повного сортування, яка суміщається із етапом проміжного сортування, повинна бути такою ж, як і тривалість ітерації етапу проміжного сортування. 30 4 UA 93797 U Комп’ютерна верстка С. Чулій Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5