Спросить
Войти

ЛОКАЛЬНО-ПАРАЛЛЕЛЬНАЯ СОРТИРОВКА МАЛЫХ НАБОРОВ ДАННЫХ

Автор: Али Мохамад

2. Михаль О.Ф. Моделирование распределенных информационно-управляющих систем средствами локально-параллельных

алгоритмов обработки нечеткой информации / / Проблемы бионики. Всеукраинский межведомственный научно-технический сборник. Харьков: ХНУРЭ. 2001. Вып. 54. С. 28-34.

3. Михаль О.Ф., Руденко О.Г. Принципы организации систем нечеткого регулирования на однородных локально-параллельных алгоритмах // Управляющие системы и машины. 2001. № 3. С. 3-10.
4. Люггер Д.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем М.: Изд. дом «Вильямс», 2005.

- 864 с.

-□ □Процедуру сортування проаналiзовано на KOM6i-наторному piem для 4-елементних послидовностей. Подано алгоpитмiчне забезпечення локально-пара-лельного сортування. В ходi моделювання мовою Python з&ясовано, що локально-паралельний алгоритм максимально эфективний щодо сортування виборок в межах pозpядностi процесора

Ключовi слова: локальна паралельтсть, сортування даних

Процедура сортировки проанализирована на комбинаторном уровне на примере 4-элементных числовых последовательностей. Описана работа алгоритма локально-параллельной сортировки. Моделированием на языке Python показано, что алгоритм эффективен применительно к малым выборкам

сортировка данных

The Procedures of the sorting is analysed on combinatorial level for 4-element sequences. Algorithmic provision of local-parallel sorting is presented. In the course of modeling in language Python is revealled that local-parallel algorithm is greatly efficient with reference to sorting the samples within processor register size

ЛОКАЛЬНО-ПАРАЛЛЕЛЬНАЯ СОРТИРОВКА МАЛЫХ НАБОРОВ ДАННЫХ

Мохамад Али

Аспирант*

О.Ф. М ихал ь

Доктор технических наук, доцент, профессор*

*Кафедра Электронно-вычислительных

машин

Харьковский национальный университет радиоэлектроники пр. Ленина, 14, г. Харьков, 61166 Контактный тел. (057) 40-93-54 Е-mail: fuzzy16@pisem.net

1. Введение

Сортировка данных - классическая задача, сочетающая в себе прозрачность общей концепции и многовариантность решений. Алгоритмы сортировки подробно изучены для вычислительных систем (ВС) последовательного действия. Параллельные ВС до недавнего времени были исключительно многопроцессорными и разрабатывались для специальных приложений. Задачи параллельной сортировки рассматривалась в них преимущественно в контексте общих принципов распараллеливания алгоритмов. С распространением многоядерных процессоров и сетевых вычислительных структур [1]: приобрела актуальность сортировка ограниченных малых наборов данных [2, 3]. Эта задача эффективно решается с использованием, локально-параллельных (ЛП) алгоритмов обработки информации [4, 5].

В настоящей работе развиваются рассмотренные ранее [1-3] принципы сортировки на ЛП алгоритмах, проводится детальное сравнение с последовательными алгоритмическими процедурами и формулируются направления использования выявленных закономерностей в прикладных задачах.

2. Основные определения

Будем рассматривать набор данных А - множество, состоящее из элементов: А: {а1,а2,а3,...,а!,...,ап}, где а1 еА; 1 е(1,2,...,п) , - объект произвольной природы: число, фрагмент текста, запись в БД и др. Элементы множества А могут быть самими объектами набора данных, либо указателями на них, позволяющими взаимно-однозначно соотносить а1 еА и соответствующий объект. Термин «ограниченный» предполагает конечное число п элементов, неизменное в

процессе сортировки; термин «малый» - количество элементов при котором не требуется использование видов (типов) памяти, существенно замедляющих информационный обмен в процессе выполнения сортировки.

Отношение порядка (наличие упорядоченности) на множестве А предполагает указание для некоторых элементов а^ еА; 1,] е(1,2,3,...,п) ; 1 ф одного из следующих соотношений: а! а], а! >■ а]. Символы « » и « >■ » есть отношения следования: «предшествует» и «следует за». В частности они могут интерпретироваться как арифметические соотношения между числами - бинарные отношения «меньше» (<) и «больше» (>). Множество А является упорядоченным, если отношение порядка определено для любых а1,а] еА. Множество А является частично упорядоченным, если отношение порядка определено для некоторых пар а^ еА.

Будем различать множество А , как совокупность элементов, и последовательность элементов множества, как выборку элементов множества с учётом порядка размещения. Для последовательности, включающей все элементы А , допустимо упорядочение по возрастанию а1 < а2 < а3 <... < а! <... < ап, либо по убыванию а1 > а2 > а3 >... > а! >... > ап. При этом для любой пары элементов справедливо а! < а] ( а! > а]), где 1,] е(1,2,3,...,п) , 1 < Если хотя бы для одной пары условие а! < а] ( а! > а]) не выполняется, последовательность является не упорядоченной по возрастанию (убыванию). Процесс упорядочения - переход от одной расстановки к другой иллюстрируется графом рис. 1 для множества из четырёх элементов.

2314

ТТЭТ

ащнзщкш:

&2341 к

X 3241 >

& 3214 У

У 2431 > а 3421;

,2413 К Л •*•

У 4213> Н 4231 &

&3142&к I ......

К 3412 V —14312 &

4123)^ ***********

X 4132 У

Рис. 1. Структуры частично упорядоченных множеств перестановок четырёхэлементной последовательности

Вводится мера разупорядоченности, как число перестановок соседних элементов, которое необходимо произвести чтобы прийти к упорядоченной последовательности элементов. Может быть показано, что множества, упорядоченные по возрастанию и убыванию максимально взаимно разупорядочены. Для данного множества число перестановок в парах соседствующих элементов является максимальным при переупорядочении множества из упорядоченности по возрастанию в упорядоченность по убыванию.

При рассмотрении цепочек перестановок необходимо исключить циклы, ограничившись только продуктивными перестановками. Графы рис. 1 а, б позволяют проследить различные варианты таких цепочек, поскольку охватывают все возможные варианты связей по перестановкам в парах соседствующих элементов. Так, для 4-элементной последовательности (рис. 1 б) одна из цепочек преобразования (1,2,3,4)^(4,3,2,1) имеет вид:

(1,2,3,4) ^ (2,1,3,4) ^ (2,1,4,3) ^ ^ (274,1,3) ^ (4,2,173) ^ (4,273,1) ^ (4,3,2,1)

Две соседние последовательности, разделённые знаком «^ », различаются перестановкой местами одной (обозначенной « 7 ») пары двух соседних элементов (цифр). Процедура сортировки - последовательная, поэтому соседствующие пары переставляются по одной. В результате, (1,2,3,4)^(4,3,2,1) реализуется за 6 шагов.

В отличие от последовательной процедуры сортировки, ЛП процедура поддерживает обмен местами сразу нескольких (всех имеющихся) пар соседствующих элементов последовательности. Вследствие этого число переходов « ^ » может быть существенно сокращено.

3. Локальная параллельность

Принцип ЛП обработки информации, может быть проиллюстрирован вычислительным примером. Имеется п выражений с = а! + Ь ; 1 = 1,2,...,п . Значения а! и Ь заданы, требуется найти с . В последовательном варианте задача разрешима за 4п шагов: загрузить а! , загрузить Ь , произвести суммирование, выгрузить результат с . Если а! , Ь и с положительные и имеют ограниченную разрядность, исходные данные могут быть конкатенированы: А = а1 © а2 ©... © а! ©... Ф ап ; В = Ь1 © Ь2 ©... © Ь ©... © Ьп .

Результат С = А + В так же может быть интерпретирован как конкатенация. При этом весь набор значений с может быть получен за 4 шага. п-крат-ный выигрыш достигнут без учёта «окаймляющих» операций конкатенации и деконкатенации. Если в реальном случае вычислительный блок сложный и включает последовательное применение нескольких операций без промежуточных конкатенаций-декон-катенаций, - выигрыш может быть значительным. Выигрыш растёт с ростом разрядности процессора и с сокращением размеров конкатенируемых сегментов. При этом снижается точность представления данных (система «загрубляется»), что в ряде конкретных приложений бывает допустимо.

Проиллюстрируем работу алгоритма ЛП сортировки. Имеется множество элементов А: {а1,а2,...,ап}, на котором определено отношение порядка а1 > а2 >... > ап. Из элементов множества А составлена разупорядо-ченная последовательность В:{Ьп,Ьп-1,...,Ь2,Ь1}; Ь = а]; 1,] е(1,2,3,...,п); 1 ф

Максимально разупорядоченный случай соответствует обратной упорядоченности: В: {ап,ап-1,...,а2,а1}. Требуется привести последовательность к правильной исходной упорядоченности: В ^ А .

Производим конкатенацию элементов Ь согласно их расположению в последовательности. В вербальном описании ЛП процедура сортировки включает 4 шага.

Шаг 1. Скопировать текущее В для последующего сравнения: В1 = В.

Шаг 2. Сравнить попарно нечётные элементы В с чётными, стоящими слева от них. В каждой сравниваемой паре больший из элементов поставить на нечётное место, а меньший - на чётное.

Шаг 3. Сравнить попарно чётные элементы В с нечётными, стоящими слева от них. В каждой сравниваемой паре больший из элементов поставить на чётное место, а меньший - на нечётное.

Шаг 4. Сравнить В и В1. Если В1 = В, ЛП процедура сортировки закончена. Результат содержится в В . Если В1 Ф В - перейти к Шагу.1.

Основные черты ЛП сортировки могут быть прослежены на примере.

циклов сортировки не меняется и результат - нижняя строка - одинаков. Пример соответствует графу рис. 1. ЛП алгоритм преобразования (1,2,3,4)^(4,3,2,1) в варианте, обозначенном (а), соответствует вершинам графа, выделенным жирным пунктиров; в варианте, обозначенном (б), - вершинам, выделенным мелким пунктиров. Сопоставление с графом рис. 1 показывает сокращение числа проходимых вершин, за счёт чего достигается выигрыш в производительности ЛП сортировки по сравнению с традиционной последовательной.

(а) (б)

1) (1,2,3,4) (1,2?3,4)
2) (2,14,3) (1,3,2,4)
3) (2,4,1,3) (3,14,2)
4) (4,2?3,1) (3,4,1,2)

(4,3,2,1) (4,3,2,1)

В столбце, обозначенном (а), представлены 4 последовательных цикла ЛП сортировки начиная со строки обменов «чётный-нечётный»; в столбце (б) -начиная со строки обменов «нечётный-чётный». При изменении порядка чередования обменов общее число

Выводы

Локально-параллельное представление информации обеспечивает повышенную эффективность работы программного обеспечения. Принципы локально-параллельной обработки применимы к задачам сортировки наборов данных. Процедуры сортировки рассмотрены на комбинаторном уровне для 4-элементных последовательностей. Разработано алгоритмическое обеспечение локально-параллельной сортировки. В ходе моделирования, проведенного на языке Python, выявлено, что локально-параллельный алгоритм максимально эффективен применительно к сортировке малых (в пределах разрядности процессора) выборок.

Литература

1. Мохамад Али, Михаль О.Ф. Перспективы реализации локально-параллельных вычислений на многоядерных процессорах //

Радиоэлектронные и компьютерные системы. - 2008. - № 6 (33). - с. 234-237.

2. Мохамад Али. Локально-параллельная сортировка данных с ограниченной разрядностью // Материалы международной научно-практической конференции студентов и аспирантов "Информационные технологии в экономике и образовании". - М.: Российский университет кооперации, 2008. - с. 48-52.
3. Мохамед Али, Михаль О.Ф. Локально-параллельная сортировка со встречной чередующейся упорядоченностью данных. Материалы 13-го международного молодёжного форума "Радиоэлектроника и молодёжь в XXI веке" Ч.2. - Харьков: ХНУРЭ, 2009, с. 209.
4. Михаль О.Ф. Локально-параллельные алгоритмы определения степени включения и степени равенства нечетких множеств //

"Проблемы бионики", Вып. 55, Харьков, 2001, с. 80-90.

5. Михаль О.Ф., Руденко О.Г. Принципы организации систем нечеткого регулирования на однородных локально-параллельных

алгоритмах // Управляющие системы и машины. 2001. № 3. с. 3-10.

ЛОКАЛЬНАЯ ПАРАЛЛЕЛЬНОСТЬ local parallelity СОРТИРОВКА ДАННЫХ data sorting
Другие работы в данной теме:
Контакты
Обратная связь
support@uchimsya.com
Учимся
Общая информация
Разделы
Тесты