V Международная студенческая научная конференция Студенческий научный форум - 2013

 

Постановка вопроса. Ставится задача выполнить перенос на случай информационного поиска метода вертикальной групповой арифметической обработки, изложенного в работе «Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. I. Групповые арифметические операции // Кибернетика и системный анализ, Киев, 1998, 1998, № 3. – C.123 – 151; II. Приложение к бинарным арифметическим операциям // там же, Киев, 1998, № 6. – С. 146 –162; III. Приложение к бинарным арифметическим операциям // там же, Киев, 1999, № 1. – С. 152 – 165». Конкретно будут рассмотрены задачи параллельной сортировки, слияния, параллельного поиска по маске, как в строковом, так и в числовом массиве. Попутно будет решаться задача синтеза параллельного алгоритма, объединяющего параллельное слияние и параллельную сортировку.

I. Сортировка подсчётом. Идея исходного алгоритма заключается в следующем. Количество элементов, меньших текущего, определяют его позицию (индекс) в выходном массиве. Для сортируемых элементов составляется матрица сравнений, по которой затем получаются номера элементов в отсортированной последовательности [1]. Элемент этой матрицы определяется как результат сравнения: = Правило вставки входного элемента в выходной массив определяется следующим образом. Входной элемент с номером получает номер в отсортированном массиве по правилу: в -м столбце подсчитывается количество нулей и плюсов сверху до диагонали включительно и складывается с количеством только плюсов ниже диагонали в этом же столбце. Суммарное количество составит значение выходного номера .

Пример 1. Пусть требуется отсортировать по неубыванию числовую последовательность . Запишем матрицу сравнения сортируемых чисел:

Как только что отмечалось, номер элемента в отсортированной последовательности () определяется подсчетом количества нулей и плюсов до главной диагонали и только плюсов после главной диагонали в столбце, где расположен рассматриваемый элемент. В результате: ; ; ; ; .

Отсортированная последовательность примет вид: .

Замечание 1. Данная разновидность сортировки устойчива (сохраняет порядок равных элементов), устанавливает взаимно однозначное соответствие между элементами массива входных и выходных индексов [2]. Наиболее существенно для дальнейшего, что массив выходных индексов формируется по ходу сортировки: ; при этом порядок следования выходных индексов совпадает с порядком следования элементов отсортированного массива .

II. Поиск на основе сортировки подсчётом. Пусть требуется найти в числовой последовательности заданное число . Заданная числовая последовательность преобразуется в новую последовательность вида: . Поиск заданного числа в числовом массиве сводится к поиску нуля в массиве , образованном из абсолютных величин разностей между элементами данного массива и искомым числом [2].

Пример 2. Найти в числовой последовательности число .

Для нахождения заданного числа на вход сортировки подается преобразование входной последовательности вида:

,

или, .

Матрица сравнений для сортировки последнего массива примет вид:

; ; ; ;

.

Наименьший элемент отсортированного массива имеет номер первый: . Согласно замечанию 1 при , процедура укажет наряду с первым номером элемент массива , который содержит значение входного индекса . Это значение указывает положение на входе наименьшего элемента отсортированного массива , или, . Именно отсюда , и такой же входной номер имеет искомый элемент: , или, . Описанный способ поиска целого числа применим и к поиску чисел любого типа.

По той же программе найдется, например, число в массиве , аналогично, найдется в массиве .

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

Пример 3. Требуется найти число с точностью до в последовательности чисел . Согласно предложенной схеме

; ; ; ; .

Проверяя условие ,находим .

Предложенный поиск может осуществляться также по символам, строкам, словам и т.д. в массиве слов соответственного типа.

Для поиска слов, например, строкового типа массиву элементов строкового типа сопоставляется числовой массив, который формируется из абсолютных величин разностей ASCII-кода символа: .

Здесь – входной массив строковых элементов, – текущий номер позиции в этом массиве после его сортировки, – символ, заданный в маске поиска, – входной номер элемента массива , – элемент сопоставляемого числового массива . В сопоставленном числовом массиве выполняется поиск нулевых элементов.

Пример 4. Требуется найти в слове “Informatika” букву «m».

По таблице ASCII-кодов присваиваем номера побуквенно каждому символу. Получаем: . С помощью матрицы сравнения ищем номер буквы () в последовательности:

. Сортировке подлежит массив

или,

Матрица сравнений примет вид:

Адреса вставок: ; ;

; ;

; ;

; ;

; ;

.

Аналогично примеру 2, находим, что наименьший элемент имеет номер . Это значение указывает положение на входе наименьшего элемента отсортированного массива такой же номер имеет искомый элемент входного массива . Обратное преобразование переводит найденный номер в искомый символ , который равен .

III. Сортировка подсчетом в алгоритмическом объединении со слиянием. Пусть имеются две последовательности чисел, и , одна из которых, , уже упорядочена, – не упорядочена, например,

; .

Требуется упорядочить все элементы одновременно двух последовательностей. Иными словами, требуется выполнить слияние еще неупорядоченного массива с уже упорядоченным массивом .

С помощью матриц сравнения принцип объединения алгоритма сортировки с алгоритмом слияния определяется следующим образом.

К квадратной матрице сравнений для сортировки подсчетом неупорядоченного массива присоединяется ее прямоугольное продолжение по вертикали для сравнения с элементами упорядоченного массива .

Единый подсчет определяется по двум правилам с дополнительным правилом приоритета равных элементов.

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

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

3. Правило приоритета: равные элементы входных массивов на выходе сохраняют взаимный порядок; если равны элементы массивов и , впереди на выходе располагается элемент массива .

Для рассматриваемого примера получается следующее.

Пример 5. В результате сортировки подсчетом первой последовательности получим:

К отсортированной последовательности присоединяем вторую, , элементы которой упорядочены по неубыванию между собой, – с продолжением данной (для сортировки подсчетом) матрицы сравнений по вертикали, так что в результате образуется прямоугольная матрица сравнений:

После подсчета по двум правилам с учетом приоритета получим номера элементов в окончательно упорядоченном едином массиве . В соответствии с номерами получится: .

Тем самым определено объединение сортировки со слиянием, иными словами, сконструирован алгоритм слияния неупорядоченного массива с упорядоченным. Объединение сортировки со слиянием осуществляется на основе матрицы сравнения для сортировки подсчетом и ее модификации в прямоугольную матрицу сравнений для объединения сортировки со слиянием.

Пример 6. Пусть ,. Требуется объединить эти массивы в один упорядоченный массив . Программа (Delphi), реализующая предложенный алгоритм дана в [6]. Без вывода входных и выходных индексов получится: Результат работы программы, где индексы массива сдвинуты на длину массива :

Окончательно упорядоченный массив с соответственным перемещением входных индексов:

Замечание 2. Чтобы поменять местами приоритеты равных элементов массивов и , достаточно изменить правила вставки элементов неупорядоченного и упорядоченного массива. Именно, изменение формулируется следующим образом.

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

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

3. Правило приоритета: равные элементы входных массивов на выходе сохраняют взаимный порядок; если равны элементы массивов и , впереди на выходе располагается элемент массива .

В справедливости данного видоизменения правил легко убедиться на матрицах сравнений примера 5. В дальнейшем предполагается показать реализуемость предложенных приемов с помощью метода вертикальной обработки.

Непосредственно ниже подсчитывается временная сложность сортировки со слиянием на модели неветвящихся параллельных программ. Именно, временная сложность (кратко – время) выполнения алгоритма определяется как количество последовательных шагов его выполнения и обозначается , где – количество процессорных элементов (ПЭ), или, для краткости, процессоров. При этом обмен и время его выполнения не учитывается – в целом данная модель абстрагируется от конкретной архитектуры параллельной вычислительной системы.

IV. Временная сложность параллельной и последовательной сортировки подсчетом в объединении с параллельным и последовательным слиянием. При параллельной обработке все клетки матрицы сравнения могут заполняться одновременно, сравнения в них взаимно независимы. Если количество процессоров будет равняться числу клеток матрицы сравнения, то общая временная сложность сортировки будет измеряться величиной порядка 1, точнее, – . Можно уменьшить число процессоров, если учесть нулевых элементов диагонали квадратной матрицы сравнений для сортировки подсчетом и ее антисимметричность относительно этой диагонали. Тогда получится:

. (1)

Если процесс сортировки выполняется последовательно, то общее время ее выполнения будет складываться из времени обработки квадратной матрицы сравнения и времени обработки присоединенной матрицы с продолжением данной по вертикали: .

V. Применение вертикального суммирования для сортировки подсчетом, алгоритмически совмещенной со слиянием.

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

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

Имеется в виду следующее. Пусть дана строковая запись с большим количеством символов. Если каждый символ представить его целочисленным компьютерным номером в двоичной форме, а для каждого такого символа отвести соответственно фиксированное число двоичных разрядов, то вся запись будет иметь вид полноразрядного двоичного числа. Двоичные разряды этого числа можно интерпретировать с учетом веса коэффициентов двоичного полинома справа налево, как в обычной позиционной системе счисления. В данной интерпретации операция сравнения в лексикографическом порядке двух строковых записей сводится к операции алгебраического сложения их числовой формы с определением знака сравнения. Преимущество вертикального суммирования при этом заключается в поразрядном параллелизме [5] рассматриваемого выполнения операции сравнения: при максимальном поразрядном параллелизме одно сравнение независимо от числа разрядов занимает время одной бинарной операции над двоичными коэффициентами одного веса – , или,

, (2)

независимо от , где – число разрядов двоичного представления записи.

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

На основании изложенного и с учетом оценок (1), (2) имеет место

Теорема 1. Алгоритм сортировки, совмещенной со слиянием, при использовании матриц сравнения, вертикального алгебраического сложения для выполнения сравнений, а также вертикального суммирования одноразрядных чисел (2), в максимально параллельной форме выполняется с временной сложностью

, (3)

где – число двоичных разрядов в представлении одной записи, – число сортируемых, – число упорядоченных для слияния записей.

Оценка (3) показывает принципиальную достижимость единичного порядка временной сложности выполнения рассматриваемой сортировки со слиянием независимо от количества и длины записей.

Замечание 3. Формально теорема распространяется на записи переменной (фактически неограниченной) длины, если применять метод поразрядно-параллельного вертикального суммирования данных с неограниченной длиной слова (разрядной сетки).

VI. Применение вертикального алгебраического сложения для выполнения сравнений записей, сортировки подсчетом и слияния. Выполнение сортировки подсчетом путем вертикального суммирования по столбцам матрицы позволяет синхронно и взаимно независимо – параллельно – по всем столбцам осуществлять поиск элементов по матрице сравнения. Входной индекс наименьшего из элементов этой матрицы укажет адрес искомого элемента.

Данный способ [6] позволяет, не выполняя окончательных вычислений, определять знак результата вертикального суммирования пары полноразрядных чисел только по старшим разрядам пары чисел в двухрядном коде алгебраической суммы.

Пример 7. Пусть требуется сравнить два числа и определить, какое из них больше – по знаку результата алгебраического сложения. Составим разность , которая согласно предложенному способу представляется в виде: , где второе слагаемое инвертировано, и от результата вертикального сложения потребуется вычесть при .

Вертикальное суммирование рассматриваемой пары чисел влечет:

От двухрядной суммы надлежит вычесть . Имеем:

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

В данном примере это именно так, в чем легко убедиться непосредственно:

где .

Соответственно, в данном случае уменьшаемое больше вычитаемого.

Неполное правило определения знака разности двух положительных чисел. В силу неравенства рассматриваемая закономерность обобщается на любой двухрядный код алгебраической суммы как результата вертикального суммирования пары -разрядных чисел: наличие хоть одной единицы в разряде двухрядного кода суммы с весом (с инверсией разрядов вычитаемого и до окончательного вычитания числа ) означает, что алгебраическая сумма имеет положительное значение. То же означает наличие вертикальной пары единиц в разряде двухрядного кода той же суммы с весом вследствие образования переноса в разряд с весом .

Напротив, наличие только нулей в разрядах веса рассматриваемой алгебраической суммы (вычитание пары положительных чисел с инверсией разрядов вычитаемого и до окончательного вычитания числа ) при вертикальном суммировании -разрядных чисел в сочетании с хотя бы одной вертикальной парой веса , в которой нет единиц (отсутствие потенциального переноса в -й разряд), будет означать, в силу того же неравенства, отрицательное значение алгебраической суммы.

Соответственно в первом случае уменьшаемое больше, во втором – меньше вычитаемого.

Полное правилоопределения знака разности двух положительных чисел дано в [6] и основано на использовании знакоразрядного кода [7].

Рассмотрим пример сравнения двух слов.

Пример 8. Требуется сравнить слова "byte" и "bit".

Присвоим номера побуквенно каждому символу по таблице ASCII-кодов. Получим: "byte" – 98 121 116 101; "bit" – 98 105 116. Переведем посимвольно каждый десятичный номер в двоичный код. В результате имеем: "byte" – 1100010111100111101001100101; "bit" – 110001011010011110100.

Составим разность двух полученных двоичных чисел:

Переведем вычитаемое в инвертированный код, получим:

Выполним шаг поразрядно параллельного сложения полученных чисел:

Выполним вертикальные шаги [7] распространения переноса в знакоразрядном коде:

В результате получится:

Вертикальной черточкой отделен разряд веса , в который распространилась положительная единица переноса. Это означает положительный знак результата сравнения: уменьшаемое больше, следовательно, больше в лексикографическом смысле слово "byte" по отношению к слову "bit".

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

Очевидно, в способе сравнения ничего не изменится, если его применить непосредственно к вещественным числам в форме с фиксированной точкой.

При осуществлении поиска все сравнения выполняются максимально параллельно, поэтому с учетом максимального параллелизма предложенных сортировок и слияния из двух последних лемм вытекает

Заключение. Рассматриваемые способы позволяют выстраивать слова в лексикографическом порядке с использованием параллельных сортировок со слиянием по матрицам сравнений. При этом использование способа вертикального суммирования дает возможность вести одновременное сравнение сколь угодно длинных слов параллельно. Для каждого отдельного сравнения оценки временной сложности определяются согласно [6], там же определяется количество поразрядно параллельных компонентов, а также совокупное количество параллельных компонентов и временная сложность для всех сравнений. Таким образом, соединение параллельной сортировки и слияния с представленным способом знакоразрядного алгебраического сложения влечет возможность максимально параллельного поиска при наличии достаточного количества разрядных сумматоров битовых значений, что существенно отличает предложенный метод от известных схем поиска [9 – 11].

Список литературы

1. Ананий В. Левитин. Пространственно-временной компромисс: Сортировка подсчетом // Алгоритмы: введение в разработку и анализ. — М.: Вильямс, 2006. — С. 307 - 310.

2. Я.Е. Ромм, С.С. Белоконова Детерминированный поиск объектов различных типов на основе сортировки. – Таганрог: Изд-во ТГПИ. – 2001. – 228 с.

3. Ромм Я.Е., Иванова А.С. Потоковая вертикальная арифметическая обработка целочисленных двоичных кодов с фиксированной точкой / ТГПИ. – Таганрог, 2011. – 56 с. Деп. В ВИНИТИ 19.07.2011, № 350-В2011.

4. Ромм Я.Е., Иванова А.С. Вертикальная арифметическая обработка с расширением целочисленного диапазона/ в кн.: Микроэлектронные информационно-управляющие системы и комплексы. Сборник тезисов и статей Всероссийской научной школы. 5-7 сентября 2011 г. (г. Новочеркасск. – ЛИК. – 2011). – С. 12 – 15.

5. Ромм Я.Е., Иванова А.С. Метод расширения числового диапазона при вертикальной арифметической обработке / Известия ЮФУ. Технические науки. Тематический выпуск «Методы и средства адаптивного управления в энергетике». – № 2 (127), 2012. – С. 35 – 43.

6. Ромм Я.Е., Иванова А.С. Вертикальное групповое алгебраическое суммирование применительно к сортировке со слиянием и параллельному поиску / ТГПИ. – Таганрог, 2012. – 44 с. Деп. В ВИНИТИ 03.09.2012, № 362-В2012.

7. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. II. Приложение к бинарным арифметическим операциям // Кибернетика и системный анализ, Киев, 1998, № 6. – С. 146-162.

8. Уильям Столлингс Структурная организация и архитектура компьютерных систем. – М., 2002 г.–350с.

9. Веселая А.А. Вычисление нулей и экстремумов функций при вариации параметров на основе сортировки с приложением к моделированию устойчивости систем линейных дифференциальных уравнений. – Таганрог: ТРТУ, 2009, автореферат диссертации на соискание ученой степени канд. техн. наук. – 17 с.

10. Ромм Я.Е., Заика И.В. Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида // Кибернетика и системный анализ, Киев, 2011, № 2. – С. 165 – 180

11. Ромм Я.Е., Тюшнякова И.А. Программная идентификация нулей и особенностей функций на основе сортировки с приложением к цифровой фильтрации // Проблемы программирования. Киев, 2010. № 2-3. – С. 593 – 603.

 

Код для цитирования: Скопировать