Параллельная сортировка слиянием - RU2016151387A

1. Способ (1100) сортировки для сортировки входных данных, распределенных по сегментам (401, 402, 403, 404) локальной памяти множества соединенных между собой узлов (701, 702) обработки данных, содержащий этапы, на которых:

сортируют (1101) распределенные входные данные, локально по узлу (701, 702) обработки данных, посредством развертывания первых процессов на узлах (701, 702) обработки данных для создания множества сортированных списков в сегментах (401, 402, 403, 404) локальной памяти узлов (701, 702) обработки данных;

создают (1102) последовательность диапазонных блоков (703, 704, 713, 714) в сегментах локальной памяти узлов (701, 702) обработки данных, при этом каждый диапазонный блок выполнен с возможностью хранения значений данных, находящихся в пределах его диапазона;

копируют (1103) указанное множество сортированных списков в указанную последовательность диапазонных блоков (703, 704, 713, 714) посредством развертывания вторых процессов на узлах (701, 702) обработки данных, при этом каждый диапазонный блок (703, 704, 713, 714) принимает те элементы сортированных списков, значения которых находятся в пределах его диапазона;

сортируют (1104) элементы диапазонных блоков (703, 704, 713, 714), локально по узлу (701, 702) обработки данных, с использованием вторых процессов для создания сортированных элементов в диапазонных блоках (703, 704, 713, 714); и

считывают (1105) сортированные элементы из последовательности диапазонных блоков (703, 704, 713, 714) последовательно в отношении их диапазона для получения сортированных входных данных.

2. Способ (1100) сортировки по п. 1, в котором сегменты (401, 402, 403, 404) локальной памяти множества соединенных между собой узлов (701, 702) обработки данных структурированы в качестве асимметричной памяти.

3. Способ (1100) сортировки по п. 1, в котором количество первых процессов является равным количеству сегментов (401, 402, 403, 404) локальной памяти.

4. Способ (1100) сортировки по любому из пп. 1-3, в котором процессы выполнены с возможностью создания непересекающихся сортированных списков.

5. Способ (1100) сортировки по п. 1, в котором сортировка распределенных входных данных, локальная по узлу (701, 702) обработки данных, основана на одной процедуре из: последовательной процедуры сортировки и параллельной процедуры сортировки.

6. Способ (1100) сортировки по п. 1, в котором количество вторых процессов равно количеству диапазонных блоков (703, 704, 713, 714).

7. Способ (1100) сортировки по п. 1, в котором каждый диапазонный блок (703, 704, 713, 714) имеет отличный от других диапазон.

8. Способ (1100) сортировки по п. 1, в котором каждый диапазонный блок (703, 704, 713, 714) выполнен с возможностью приема множества сортированных списков, при этом количество сортированных списков в соответствии с количеством первых процессов.

9. Способ (1100) сортировки по п. 1, в котором второй процесс из числа вторых процессов, исполняемых на одном узле (701, 702) обработки данных, копируя множество сортированных списков в последовательность (703, 704, 713, 714) диапазонных блоков, осуществляет чтение последовательно из локальной памяти указанного одного узла (701) обработки данных и из локальной памяти других узлов (702) обработки данных.

10. Способ (1100) сортировки по п. 9, в котором второй процесс, исполняемый на указанном одном узле (701) обработки данных, посредством копирования множества сортированных списков в последовательность диапазонных блоков (703, 704, 713, 714), осуществляет запись только в локальную память указанного одного узла (701) обработки данных.

11. Способ (1100) сортировки по п. 1, в котором последовательное считывание сортированных элементов из последовательности диапазонных блоков (703, 704, 713, 714) выполняется с использованием аппаратной упреждающей выборки.

12. Способ (1100) сортировки по п. 1, в котором вторые процессы, для сравнения значений сортированных списков с диапазонами диапазонных блоков (703, 704, 713, 714) и для копирования множества сортированных списков в последовательность диапазонных блоков (703, 704, 713, 714), используют векторизованную обработку данных, в частности, векторизованную обработку данных, исполняемую на аппаратных блоках архитектуры с одним потоком команд и множественными потоками данных.

13. Способ (1100) сортировки по п. 1, в котором множество узлов (701, 702) обработки данных соединены между собой посредством межгнездовых соединений; а

локальная память одного узла (701) обработки данных является, для другого узла (702) обработки данных, удаленной памятью.

14. Система 100 обработки данных, содержащая:

множество соединенных между собой узлов (101, 103) обработки данных, каждый из которых содержит локальную память (107, 117) и блок (109, 119) обработки данных, при этом входные данные распределены по локальной памяти (107, 117) узлов (101, 103) обработки данных, а блоки (109, 119) обработки данных выполнены с возможностью:

сортировки (1001) распределенных входных данных, локально по узлу (701, 702) обработки данных, посредством развертывания первых процессов на узлах (701, 702) обработки данных для создания множества сортированных списков в сегментах (401, 402, 403, 404) локальной памяти узлов (701, 702) обработки данных;

создания (1102) последовательности диапазонных блоков (703, 704, 713, 714) в сегментах локальной памяти узлов (701, 702) обработки данных, при этом каждый диапазонный блок выполнен с возможностью хранения значения данных, находящиеся в пределах его диапазона;

копирования (1103) указанного множества сортированных списков в указанную последовательность диапазонных блоков (703, 704, 713, 714) посредством развертывания вторых процессов на узлах (701, 702) обработки данных, при этом каждый диапазонный блок (703, 704, 713, 714) принимает те элементы сортированных списков, значения которых находятся в пределах его диапазона;

сортировки (1104) элементов диапазонных блоков (703, 704, 713, 714), локально по узлу обработки данных, с использованием вторых процессов для создания сортированных элементов в диапазонных блоках (703, 704, 713, 714); и

считывают (1105) сортированные элементы из последовательности диапазонных блоков (703, 704, 713, 714) последовательно в отношении их диапазона для получения сортированных входных данных.

15. Компьютерный программный продукт, содержащий машиночитаемый носитель информации, хранящий на себе программный код для использования компьютером, причем программный код выполнен с возможностью сортировки входных данных, распределенных по сегментам локальной памяти множества соединенных между собой узлов обработки данных, и содержит:

команды для локальной сортировки (1101) распределенных входных данных по узлу (701, 702) обработки данных, посредством развертывания первых процессов на узлах (701, 702) обработки данных для создания множества сортированных списков в сегментах (401, 402, 403, 404) локальной памяти узлов (701, 702) обработки данных;

команды для создания (1101) последовательности диапазонных блоков (703, 704, 713, 714) в сегментах локальной памяти узлов обработки данных, при этом каждый диапазонный блок выполнен с возможностью хранения значений данных, находящихся в пределах его диапазона;

команды для копирования (1103) этого множества сортированных списков в эту последовательность диапазонных блоков (703, 704, 713, 714) посредством развертывания вторых процессов на узлах (701, 702) обработки данных, при этом каждый диапазонный блок (703, 704, 713, 714) принимает те элементы сортированных списков, значения которых находятся в пределах его диапазона;

команды для локальной сортировки (1104) элементов диапазонных блоков (703, 704, 713, 714), по узлу (701, 702) обработки данных, с использованием вторых процессов для создания сортированных элементов в диапазонных блоках (703, 704, 713, 714); и

команды для считывания (1105) сортированных элементов из последовательности диапазонных блоков (703, 704, 713, 714), последовательного в отношении их диапазона, для получения сортированных входных данных.