Article

Article title PARALLEL-CONVEYOR ORDERING ARRAY OF UNLIMITED LENGTH
Authors Ya.E. Romm., I.I. Stakhovskaya
Section SECTION II. ALGORITHMS AND SOFTWARE
Month, Year 04, 2014 @en
Index UDC 681.3.06: 681.323 (519.6)
DOI
Abstract Presented parallel-conveyor algorithms merger with unlimited array that is built on the basis of the comparison matrix. Multipath synthesized by comparison matrix maximum parallel and performed with the unit time complexity. Parallel sorting on this basis performed duration logMN consecutive comparisons, where M – number of paths merger, N – consecution length. With the application of multipath synthesized fusion algorithm parallel-conveyor sorting an array of unlimited length. Conveyor unit in each cycle duration takes a new unlimited array Mxn of items, or a new part of the same unlimited length of the input array. Time loading has unit length of conveyor, output in the same clock cycle continuation to an ordered array of unlimited length adding Mxn new elements while the same order as a whole of the output array. Are given estimates for the time complexity, amount of processing elements, amount of conveyor seg-ments. Conveyor segments for an unlimited increase in the output array form a consecutive of processors, amount on i -th step load for a total of  Σl=0iRl=(2i+1-1)M2n2.

Download PDF

Keywords Parallel-conveyor algorithm; an array of unlimited length; parallel sorting; multipath mer- ger; matrix comparisons; time complexity.
References 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.