Статья

Название статьи ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЕ УПОРЯДОЧЕНИЕ НЕОГРАНИЧЕННОГО МАССИВА
Автор Я.Е. Ромм, И.И. Стаховская
Рубрика РАЗДЕЛ II. АЛГОРИТМИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
Месяц, год 04, 2014
Индекс УДК 681.3.06: 681.323 (519.6)
DOI
Аннотация Представлены параллельно-конвейерные алгоритмы слияния с неограниченным массивом, которые построены на основе матриц сравнения. Многопутевое слияние по матрицам сравнения максимально параллельно и выполняется с единичной временной сложностью. Параллельная сортировка на этой основе выполняется с длительностью logM N последовательных сравнений, где M – число путей слияния, N – длина последовательности. С применением многопутевого слияния синтезирован алгоритм параллельно-конвейерной сортировки массива неограниченной длины. Конвейер в каждом такте единичной длительности принимает на вход новый неупорядоченный массив из Mxn элементов или новую часть такой же длины неограниченного входного массива. Время загрузки конвейера имеет единичную длительность, на выходе в такте той же длительности к упорядоченному массиву неограниченной длины добавляются новые Mxn элементов с сохранением порядка всего выходного массива в целом. Даны оценки временной сложности, числа процессорных элементов, количества сегментов конвейера. Сегменты конвейера для неограниченного возрастания выходного массива образуют последовательность процессоров, количество которых на i -м шаге загрузки в сумме составит Σl=0iRl=(2i+1-1)M2n2.

Скачать в PDF

Ключевые слова Параллельно-конвейерные алгоритмы; массив неограниченной длины; параллельная сортировка; многопутевое слияние; матрица сравнения; временная сложность.
Библиографический список c1. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. I // Кибернетика и системный анализ. – 1994. – № 5. – С. 3-23.
2. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. – 1995. – № 4. – С. 13-37.
3. Ромм Л.Я. Целочисленная идентификация плоских изображений с учетом множества внутриконтурных точек на основе экстремальных признаков и алгоритмов сортировки: Автореф. дис. … канд. техн. наук. – Таганрог: ЮФУ. – 2013. – 21 с.
4. Царев Р.Ю. Структуры и алгоритмы обработки данных. – Красноярск: Сиб. федер. ун-т, 2013. – 160 с.
5. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки: Дис. … д-ра техн. наук. – Таганрог: ТРТУ. – 1998. – 546 с.
6. Ромм Я.Е. Стаховская И.И. Параллельно-конвейерное упорядочение массива неограниченной длины. – Таганрог. гоc. пед. ин-т., 2013. – 27 с.
7. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989. – 360 с.
8. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. I // Кибернетика и системный анализ. – 2007. – № 1. – С. 165-183.
9. Гречко В.О., Фальфушинский В.В. Параллельно-конвейерные схемы алгоритмов сортировки // Труды Международной конференции «Высокопродуктивные вычисления» HPC-UA’2011. – С. 145-149.
10. Легалов А.И. Методы сортировки, полученные из анализа максимально параллельной программы // Распределенные и кластерные вычисления. Избранные материалы Третьей школы семинара. – Красноярск: Институт вычислительного моделирования СО РАН, 2004. – С. 119-134.
11. Мирошниченко С.Ю., Титов В.С. Параллельно-конвейерное устройство для векторизации аэрокосмических изображений земной поверхности // Приборостроение. – 2009. – № 2. – С. 45-52.

Comments are closed.