Введение к работе
з
Актуальность темы. Методы вертикальной обработки отличаются возможностью выполнения одновременно группы операций над вертикальным срезом полноразрядных данных. На этой основе с целью ускорения они применяются для нечисловой обработки данных. Известны также успешные реализации метода для потоковой числовой обработки. В работе оба эти применения соединяются воедино с видоизменением, при котором исключаются операции вычисления переноса. В результате оказывается возможной вертикальная обработка с максимальным поразрядным параллелизмом, позволяющим достигать существенного ускорения метода во всех рассматриваемых применениях. Для числовой обработки этот подход позволяет расширить диапазон данных, что актуально для повышения точности приближенных методов вычислений. Для обработки строковых элементов это влечет возможность поразрядно-параллельного сравнения слов с оценкой времени, которая не зависит от длины слова. В развитие метода дается его приложение к схемам сортировки и слияния, где достигается максимальный параллелизм собственно алгоритмов сортировки и слияния в сочетании с максимальным поразрядным параллелизмом базовых операций сравнения. Исследуемые возможности интерпретируются как средства ускорения информационного поиска за счет минимизации временной сложности базовых алгоритмов поиска. Попутно исследуются актуальные проблемы поиска, связанные с идентификацией вхождения слов и сокращения списка выдачи.
В диссертационной работе выполняется адаптированная к рассматриваемым возможностям модификация двоичных кодов для числовых и нечисловых данных, затронуты вопросы вертикальной обработки на параллельно работающих процессорных элементах с расширением диапазона данных и минимизацией временной сложности.
Целью диссертационной работы является выполнить аналитические оценки числового диапазона вертикальной обработки, модифицировать ее на этой основе для расширения диапазона данных потоковой числовой и нечисловой обработки и распространить метод на базовые операции сортировки и поиска в максимально параллельной форме с минимизацией временной сложности.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
-
Выполнить оценки роста числового диапазона для метода поразрядно-параллельного вертикального суммирования потока натуральных двоичных чисел, разработать для этого метода видоизменение и структуру данных, при которых расширяется числовой диапазон и исключается потеря значащих цифр суммы. На этой основе дать концепцию архитектуры параллельного вычислителя, в котором суммирование потока реализуется с минимальной временной сложностью.
-
Разработать видоизменение метода вертикального поразрядно-параллельного умножения и-разрядных двоичных чисел, исключающее вычисление переноса, с ускорением умножения до 0(log«), при этом рост
числового диапазона произведения должен быть не выше чем в известных методах. Найти концепцию архитектуры параллельного вычислителя, в котором умножение реализуется без отбрасывания значащих цифр младших разрядов и сохраняется логарифмическая оценка времени умножения.
-
Найти видоизменение алгоритма параллельной сортировки подсчетом и синтезировать параллельный алгоритм одновременного слияния и сортировки на основе вертикального поразрядно-параллельного сравнения с целью максимально параллельного выполнения информационного поиска как числовой, так и нечисловой информации.
-
Разработать метод сравнения строковых элементов на основе видоизменения поразрядно-параллельного вертикального суммирования с применением двоичной кодировки символов. Найти аналог дополнительного кода для вертикального потокового алгебраического сложения и применить его для сравнения строковых элементов и чисел, которое выполнялось бы с формальной единичной оценкой времени бинарного сравнения независимо от числа символов сравниваемых слов.
-
На основе вертикальной схемы алгебраического суммирования синтезировать алгоритмы упорядочения числовых и строковых элементов, включающие максимально параллельную сортировку с одновременным слиянием, с целью выполнения операций поиска с единичной оценкой временной сложности упорядочения, формально не зависящей от числа упорядочиваемых элементов и длины слов.
-
Разработать модель параллельного вычислителя, программно реализующего предложенный метод вертикальной обработки; выполнить программные реализации алгоритмов сортировки с одновременным слиянием, программные и численные эксперименты, подтверждающие достоверность искомых результатов.
Методы исследования включают элементы теории вычислительных систем, способы кодирования информации, асимптотические оценки диапазона данных вертикальной обработки, организацию структур данных, синтез и анализ параллельных алгоритмов поиска и сортировки, оценки временной сложности.
Достоверность результатов вытекает из корректного математического обоснования с помощью аналитических оценок погрешности приближений и временной сложности формализованных алгоритмов, подтверждается результатами моделирования, программного и численного эксперимента.
Научная новизна результатов диссертационной работы заключается в следующем:
1. Выполнены оценки роста числового диапазона, предложено видоизменение и структура данных для метода поразрядно-параллельного вертикального суммирования потока натуральных двоичных чисел; модифицированный метод отличается от известных инвариантностью обработки слагаемых относительно номера разряда, не требует вычисления переноса, что позволяет исключить потерю значащих цифр, расширить числовой диапазон и концептуально организовать архитектуру параллельного вычислителя, в которой суммирование реализуется с минимальной временной сложностью (С. 49 - 63).
-
Предложено видоизменение метода вертикального поразрядно-параллельного умножения и-разрядных двоичных чисел, отличающееся исключением вычисления переноса и ускорением умножения до 0(log«) при сохранении двухрядной промежуточной суммы, при этом рост числового диапазона произведения не выше чем в известных методах, что позволяет организовать архитектуру параллельного вычислителя, в которой умножение реализуется без отбрасывания значащих цифр младших разрядов с сохранением логарифмической оценки времени (С. 80-91, 100 - 103).
-
Разработано видоизменение алгоритма параллельной сортировки подсчетом и синтезирован параллельный алгоритм одновременного слияния и сортировки на основе вертикального поразрядно-параллельного сравнения с целью информационного поиска, которые отличаются от известных структурой алгоритмов, максимальным параллелизмом сравнений и применимостью к поиску как числовой, так и нечисловой информации (С. 111-119).
-
На основе видоизменения поразрядно-параллельного вертикального суммирования натуральных двоичных чисел предложен метод сравнения строковых элементов с использованием двоичной кодировки символов, который отличается вертикальной схемой алгебраического суммирования двоичных кодов слов, наличием аналога дополнительного кода, инвариантностью относительно коэффициентов кода и формальной единичной оценкой времени бинарного сравнения, не зависящей от числа символов слов (С. 133 - 140).
-
В качестве базовых операций поиска синтезированы алгоритмы упорядочения числовых и строковых элементов, включающие максимально параллельную сортировку с одновременным слиянием, с применением вертикальной схемы алгебраического суммирования двоичных кодов данных, которые отличаются от известных единичной оценкой временной сложности упорядочения, формально не зависящей от числа упорядочиваемых элементов и от числа входящих в них символов; даны оценки количества параллельных компараторов, при которых имеет место данная временная оценка (С. 116 - 133).
-
Разработана модель параллельного вычислителя, программно реализующая предложенный метод вертикальной обработки, даны программные реализации алгоритмов сортировки с одновременным слиянием, выполнены программные и численные эксперименты, подтверждающие достоверность теоретических результатов (С. 64 - 67, 92 - 98, 114).
Основные положения, выносимые на защиту:
-
Оценки роста числового диапазона, видоизменение метода и структуры данных поразрядно-параллельного вертикального суммирования потока натуральных двоичных чисел, которые на основе отсутствия вычисления переноса позволяют исключить потерю значащих цифр, расширить числовой диапазон и реализовать суммирование с минимальной временной сложностью.
-
Видоизменение метода вертикального умножения «-разрядных двоичных чисел с исключением вычисления переноса и ускорением бинарного умножения до o(iog«), на основе которых возможна реализация умножения без отбрасывания младших разрядов значащих цифр при сохранении логарифмической оценки времени.
-
Синтез параллельного алгоритма сортировки в соединении с одновременным слиянием на основе вертикального поразрядно-параллельного сравнения для информационного поиска с максимальным параллелизмом сравнений, применимых к поиску числовой и нечисловой информации.
-
Видоизменение поразрядно-параллельного вертикального суммирования натуральных двоичных чисел для сравнения строковых элементов с использованием двоичной кодировки символов и аналога дополнительного кода, на основе которых сравнение выполнимо инвариантно относительно коэффициентов кода с единичной оценкой времени, формально не зависящей от числа символов слов.
-
Синтез алгоритмов упорядочения числовых и строковых элементов с применением вертикальной схемы алгебраического суммирования двоичных кодов данных, на основе которых достигается единичная оценка временной сложности упорядочения, не зависящая от числа упорядочиваемых слов и входящих в них символов.
-
Модель численной реализации предложенной модификации вертикальной обработки, программные реализации алгоритмов сортировки с одновременным слиянием.
Практическая ценность диссертационного исследования заключается в прикладном характере предложенных методов и алгоритмов. Разработанное видоизменение метода вертикальной обработки может быть использовано для увеличения точности вьгаислительной обработки за счет исключения потери значащих цифр числа, для расширения числового диапазона и реализации суммирования с минимальной временной сложностью за счет поразрядно-параллельной потоковой обработки с исключением вычисления переноса. Разработанная схема поиска на основе модифицированного метода вертикальной обработки при сравнении чисел и слов, а также соединение сортировки подсчетом со слиянием на данной основе могут быть реализованы в максимально параллельной форме для ускорения, повышения точности и расширения функциональных возможностей поиска.
Внедрение и использование результатов работы. Полученные в работе результаты использованы:
1. В ОАО НКБ ВС приняты к использованию: аналитические оценки роста числового диапазона, видоизменение и структура данных для метода поразрядно-
параллельного вертикального суммирования потока натуральных двоичных чисел; параллельный алгоритм одновременного слияния и сортировки на основе вертикального поразрядно-параллельного сравнения применительно к поиску как числовой, так и нечисловой информации; аналог дополнительного кода для потоковой вертикальной обработки и метод сравнения слов на основе вертикального алгебраического суммирования двоичных кодов с единичной
оценкой времени бинарного сравнения для произвольного числа символов слов.
-
В работах по гранту РФФИ «Компьютерные методы численной оптимизации на основе сортировки с приложением к анализу устойчивости, разностно-полиномиальному решению дифференциальных уравнений, распознаванию изображений и цифровой обработке сигналов» на 2012-2013 г.г. (номер проекта 12-07-00143-а) использован параллельный алгоритм сортировки подсчетом, совмещенной с одновременным слиянием по матрицам сравнений с применением знакоразрядной кодировки результатов сравнения и аналога дополнительного кода с целью максимально параллельного выполнения операции сравнения для ускорения информационного поиска как числовой, так и нечисловой информации.
-
В учебном процессе кафедры информатики ФГБОУ ВПО «ТГПИ имени А.П. Чехова» материалы диссертации использованы в курсах «Программирование», «Алгоритмы параллельных и последовательных сортировок», «Информатика и программирование» и «Архитектура вычислительных систем».
Апробация работы. Основные результаты работы были представлены на
Всероссийской научной школе «Микроэлектронные информационно-управляющие системы и комплексы» (Южно-Российский государственный технический университет (Новочеркасский политехнический институт) (ЮРГТУ (НИИ)), 2011 г.); Всероссийской научной школе для молодежи «Итоги и перспективы развития Российско-Германского сотрудничества в области мехатроники» (ЮРГТУ (НИИ)), 2011 г.); Всероссийской научно-технической конференции с международным участием "Компьютерные и информационные технологии в науке, инженерии и управлении" «КомТех-2012» (ТТИ ЮФУ, Таганрог, 2012 г.); VIII Международной Петрозаводской конференции «Вероятностные методы в дискретной математике», XIII Всероссийском симпозиуме по прикладной и промышленной математике (весенняя сессия) (Петрозаводск, 2012 г.); «Студенческом научном форуме» V Международной студенческой электронной научной конференции (Электронная научная конференция, 2013 г.).
Публикации. По материалам работы опубликовано 12 печатных работ общим объемом около 10 печатных листов, в том числе 3 статьи в рецензируемых журналах из перечня рекомендуемых ВАК РФ.
Структура и объём работы. Диссертационная работа состоит из введения, трех глав основного раздела, заключения, списка литературы. Основное содержание работы изложено на 158 страницах, включая список литературы из 122 наименований и приложения, включающего акты об использовании материалов диссертации.
