автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Расширение диапазона данных для вертикальной потоковой обработки применительно к сортировке со слиянием и параллельному поиску

На правах рукописи

Иванова Анна Сергеевна

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

СЛИЯНИЕМ И ПАРАЛЛЕЛЬНОМУ ПОИСКУ

Специальность:

05.13.17- Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

5 ДЕК 2013

Таганрог — 2013

005542784

Работа выполнена в ФГБОУ ВПО «Таганрогский государственный педагогический институт имени А.П. Чехова»

Научный руководитель: доктор технических наук, профессор

Ромм Яков Евсеевич

Официальные оппоненты: Турулин Игорь Ильич,

доктор технических наук, профессор, ФГАОУ ВПО «ЮФУ», кафедра информационных измерительных технологий и систем

Гречишников Анатолий Иванович,

кандидат технических наук, старший научный сотрудник, директор Таганрогского филиала НИИ Системотехники

Ведущая организация: ФГНУ НИИ «СПЕЦВУЗАВТОМАТИКА»

(г. Ростов-на-Дону).

Защита состоится «27» декабря 2013 г. в 14.20 на заседании диссертационного совета Д 212.208.21 Южного федерального университета по адресу: г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федеральной университета по адресу: 344000, г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан «23» ноября 2013 г.

Ученый секретарь диссертационного совета Д 212.208.21

доктор технических наук, профессор Ґ І Боженюк А.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Методы вертикальной обработки отличаются возможностью выполнения одновременно группы операций над вертикальным срезом полноразрядных данных. На этой основе с целью ускорения они применяются для нечисловой обработки данных. Известны также успешные реализации метода для потоковой числовой обработки. В работе' оба эти применения соединяются воедино с видоизменением, при котором исключаются операции вычисления переноса. В результате оказывается возможной вертикальная обработка с максимальным поразрядным параллелизмом, позволяющим достигать существенного ускорения метода во всех рассматриваемых применениях. Для числовой обработки этот подход позволяет расширить диапазон данных, что актуально для повышения точности приближенных методов вычислений. Для обработки строковых элементов это влечет возможность поразрядно-параллельного сравнения слов с оценкой времени, которая не зависит от длины слова. В развитие метода дается его приложение к схемам сортировки и слияния, где достигается максимальный параллелизм собственно алгоритмов сортировки и слияния в сочетании с максимальным поразрядным параллелизмом базовых операций сравнения. Исследуемые возможности интерпретируются как средства ускорения информационного поиска за счет минимизации временной сложности базовых алгоритмов поиска. Попутно исследуются актуальные проблемы поиска, связанные с идентификацией вхождения слов и сокращения списка выдачи.

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

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

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

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

2. Разработать видоизменение метода вертикального поразрядно-параллельного умножения и-разрядных двоичных чисел, исключающее вычисление переноса, с ускорением умножения до o(logn), при этом рост числового диапазона произведения должен быть не выше чем в известных

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

- 3. Найти видоизменение алгоритма параллельной сортировки подсчетом и синтезировать параллельный алгоритм одновременного слияния и сортировки на основе вертикального поразрядно-параллельного сравнения с целью максимально параллельного выполнения информационного поиска как числовой, так и нечисловой информации.

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

5. На основе вертикальной схемы алгебраического суммирования синтезировать алгоритмы упорядочения числовых и строковых элементов, включающие максимально параллельную сортировку с одновременным слиянием, с целью выполнения операций поиска с единичной оценкой временной сложности упорядочения, формально не зависящей от числа упорядочиваемых элементов И ДЛИНЫ СЛОВ;

6. Разработать модель параллельного вычислителя, программно реализующего предложенный метод вертикально.! обработки; выполнить программные реализации алгоритмов сортировки с одновременным слиянием, программные и численные эксперименты, подтверждающие достоверность искомых результатов.

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

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

Научная новизна результатов диссертационной работы заключается в следующем:

1. Выполнены оценки роста числового диапазона, предложено видоизменение и структура данных для метода поразрядно-параллельного вертикального суммирования потока натуральных двоичных чисел; модифицированный метод отличается от известных инвариантностью обработки слагаемых относительно номера разряда, не требует вычисления переноса, что позволяет исключить потерю значащих цифр, расширить числовой диапазон и концептуально организовать архитектуру параллельного вычислителя, в которой суммирование реализуется с минимальной временной сложностью (С. 49 — 63).

2. Предложено видоизменение метода вертикального поразрядно-параллельного умножения и-разрядных двоичных чисел, отличающееся исключением вычисления переноса и ускорением умножения до О(1оя л) при сохранении двухрядной промежуточной суммы, при этом рост числового диапазона произведения не выше чем в известных методах, что позволяет организовать архитектуру параллельного вычислителя, в которой умножение реализуется без отбрасывания значащих цифр младших разрядов с сохранением логарифмической оценки времени (С. 80-91, 100 - 103).

3. Разработано видоизменение алгоритма параллельной сортировки подсчетом и синтезирован параллельный алгоритм одновременного слияния и сортировки на основе вертикального поразрядно-параллельного сравнения с целью информационного поиска, которые отличаются от известных структурой алгоритмов, максимальным параллелизмом сравнений и применимостью к поиску как числовой, так и нечисловой информации (С. 111 - 119).

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

5. В качестве базовых операций поиска синтезированы алгоритмы упорядочения числовых и строковых элементов, включающие максимально параллельную сортировку с одновременным слиянием, с применением вертикальной схемы алгебраического суммирования двоичных кодов данных, которые отличаются от известных единичной оценкой временной сложности упорядочения, формально не зависящей от числа упорядочиваемых элементов и от числа входящих в них символов; даны оценки количества параллельных компараторов, при которых имеет место данная временная оценка (С. 116 - 133).

6. Разработана модель параллельного вычислителя, программно реализующая предложенный метод вертикальной обработки, даны программные реализации алгоритмов сортировки с одновременным слиянием, выполнены программные и численные эксперименты, подтверждающие достоверность теоретических результатов (С. 64 - 67, 92 - 98, 114).

Основные положения, выносимые на защиту:

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

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

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

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

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

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

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

Внедрение и использование результатов работы. Полученные в работе результаты использованы:

1. В ОАО НКБ ВС приняты к использованию: аналитические оценки роста числового диапазона, видоизменение и структура данных для метода поразрядно-

параллельного вертикального суммирования потока натуральных двоичных чисел; параллельный алгоритм одновременного слияния и сортировки на основе вертикального поразрядно-параллельного сравнения применительно к поиску как числовой, так и нечисловой информации; аналог дополнительного кода для потоковой вертикальной обработки и метод сравнения слов на основе вертикального алгебраического суммирования двоичных кодов с единичной

оценкой времени бинарного сравнения для произвольного числа символов слов.

2. В работах по гранту РФФИ «Компьютерные методы численной оптимизации на основе сортировки с приложением к анализу устойчивости, разностно-полиномиальному решению дифференциальных уравнений, распознаванию изображений и цифровой обработке сигналов» на 2012-2013 г.г. (номер проекта 12-07-00143-а) использован параллельный алгоритм сортировки подсчетом, совмещенной с одновременным слиянием по матрицам сравнений с применением знакоразрядной кодировки результатов сравнения и аналога дополнительного кода с целью максимально параллельного выполнения операции сравнения для ускорения информационного поиска как числовой, так и нечисловой информации.

3. В учебном процессе кафедры информатики ФГБОУ ВПО «11 МИГ имени А.П. Чехова» материалы диссертации использованы в курсах «Программирование», «Алгоритмы параллельных и последовательных сортировок», «Информатика и программирование» и «Архитектура вычислительных систем».

Апробация работы. Основные результаты работы были представлены на

Всероссийской научной школе «Микроэлектронные информационно-управляющие системы и комплексы» (Южно-Российский государственный технический университет (Новочеркасский политехнический институт) (ЮРГТУ (НПИ)), 2011 г.); Всероссийской научной школе для молодежи «Итоги и перспективы развития Российско-Германского сотрудничества в области мехатроники» (ЮРГТУ (НПИ)), 2011 г.); Всероссийской научно-технической конференции с международным участием "Компьютерные и информационные технологии в науке, инженерии и управлении" «КомТех-2012» (ТТИ ЮФУ, Таганрог, 2012 г.); VIII Международной Петрозаводской конференции «Вероятностные методы в дискретной математике», XIII Всероссийском симпозиуме по прикладной и промышленной математике (весенняя сессия) (Петрозаводск, 2012 г.); «Студенческом научном форуме» V Международной студенческой электронной научной конференции ' (Электронная научная конференция, 2013 г.).

Публикации. По материалам работы опубликовано 12 печатных работ общим объемом около 10 печатных листов, в том числе 3 статьи в рецензируемых журналах из перечня рекомендуемых ВАК РФ.

Структура и объём работы. Диссертационная работа состоит из введения, трех глав основного раздела, заключения, списка литературы. Основное содержание работы изложено на 158 страницах, включая список литературы из 122 наименований и приложения, включающего акты об использовании материалов диссертации.

СОДЕРЖАНИЕ РАБОТЫ

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

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

^16=П1и1001 + 1000+ПП + р]01+0001 + 0]{Юн-0011 + рН1+(Х)00+1001+0111 + 1011 + 0000+1001 + 1000 А1 л2 л3 ' Т4

Шаг к-1:

S,™

i 1 1 1 1-1 1 0 0 1- 1 0 0 н 1 1 0 1*

?- а 9- 0.

а -V "V

1 '(V 0* 'и

s<»=w

I») 0) (I) ¿1=2

Шаг к= Z

Hill

S, В'

■о;

01

РЪ

S®

S,ra

PC'" PC С) PC»1 L,= 2

Шаг к=Ъ:

ol

з;

к

:э

i

2

S3)

>С<°> | РС<"

PC (1)1

"¿3=2

Ша к- 01 г 4: о°| 1 0 0. 1 1 0. 1 0 1 1 0 1 1, 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0

1 0 1

't f

uj UJ '1. "<х -tv

SM

ГС С PC»

Вертикальные стрелки указывают диагональную запись суммы вертикального среза, при которой исключено попадание двух двоичных коэффициентов в один разряд ячейки суммы. Сумма не вычисляется, а сохраняется в виде промежуточного набора слагаемых (${''),/ = 1,2,...). Доказано, что число слагаемых в нем ограничено константой при неограниченном продолжении обработки: sup if' slog;(//+i)+2 , где н - число слагаемых группы

на шаге вертикального суммирования (в примере jv = 4), при этом вычисление переноса исключено на всех шагах суммирования. Метод модифицируется со

сжатием Л,1'1 до двух слагаемых, с видоизменением распространяется на бинарное сложение полноразрядных слагаемых, при этом во всех модификациях исключается вычисление переноса. Разрядные срезы обрабатываются синхронно и взаимно независимо (СВН-параплельно) на параллельно работающих процессорных элементах (ПЭ). Рост числового диапазона данного способа оценивается следующим образом. После накопления промежуточных

слагаемых в результате шага вертикального суммирования в старших

разрядах выполняется / + 1-й шаг поразрядно-параллельного вертикального сложения, в результате к накопленному набору старших разрядов присоединяются <[1ое1б] + 1 промежуточных слагаемых, где я = 51ф , которые

сохраняются без обработки, диапазон по диагонали возрастет не более чем на 1Юёг5] старших разрядов:

1 1 1 i 1

1 0 0 0 1

1 0 1 1 0

1 i 1 0 1

1 о о 0 о

/ 1 0 0 0 0/

'п 1 i 1 /

А 0 1 0 i /

В продолжение процесса число промежуточных слагаемых ограничено и вместе с этим окажется ограниченным прирост числа старших разрядов промежуточных сумм. Алгоритм обработки прироста на шаге / влечет: siog2J,_, +2> гДе '=1.2,...

Учитывая ¿t -*г, получим:

s Slog W + 2 , j ¿log3 а +2 <1 log _ (log ^ jy + 2) + 2 ,.., s < log n (log, -(log, AT+2)+...+2)+2) .

' f ' '

Последнее неравенство, очевидно, эквивалентно

j Ü2+ log}+ log, (2 +... + log2 (2 + log ч N)...) .

ПОСКОЛЬКУ 2 + log2^áW ДЛЯ BCeX W 2:4 , ТО

í_ ¿ 2 + log 2 (2 + log з (2 +... + log ^ (2 + log 2 JV)...)).,

Отсюда I Si , где / = 1,2..... В силу индукции SI SJ(. Отсюда J S2 + los2N.

Поскольку суммирование N слагаемых приводит к приросту не более 2+iogi N

старших разрядов, то вертикальное СВН-параллельное суммирование приросших разрядов влечет в свою очередь прирост по отношению к ним не больший 2+log г (2+log г V) разрядов и т.д. По ицдукции доказывается

Теорема 1. Для произвольно фиксированного количества входных слагаемых N на шаге вертикального СВН-параллельного суммирования всегда найдется номер 7, такой, что для всех ¡г? количество старших разрядов, прирастающих на шаге /, не превысит единицы.

Таким образом, в асимптотике скорость распространения переноса не выше, чем при обычном бинарном сложении с распространением переноса.

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

слагаемых — о, 1.....п — те разряды сжатой двухрядной суммы, которые имеют вес

больше веса разряда с номером п, отсоединяются для подсуммирования в дальнейшем в отдельный новый массив. Такой массив формируется из отсоединенных двухрядных наборов слагаемых, пополняясь на каждом шаге вертикальной обработки текущего набора входных слагаемых, сжимаемого до двухрядной промежуточной суммы. Заполнение массива продолжается до накопления и + г строк, которые затем суммируется. При этом, аналогично предыдущему, происходит отсоединение старших разрядов в еще один новый двумерный массив, который после заполнения СВН-параллельно суммируется, его старшие разряды также отсоединяются в новый массив и т.д. Процесс заполнения массивов происходит по принципу счетчика, который замедляется с каждым новым массивом обрабатываемых отсоединенных старших разрядов.

Следующая архитектура (рис.1) параллельного вычислителя реализует данный метод с расширенным диапазоном данных:

Рис. 1. Архитектура параллельного вычислителя для вертикальной обработки с расширенным диапазоном данных

Вертикальные стрелки соответствуют способу вертикального сложения группы целочисленных двоичных слагаемых с сжатием до двухрядного кода на отдельном ПЭ. Горизонтальные стрелки соответствуют направлению передачи отсоединенных старших разрядов от этапа / к этапу /+1 и от соответственной

группы ПЭ,- к соседней группе ПЭ,+1, / = 1.2..... Выполнена оценка времени

суммирования для данной архитектуры вычислителя, которая показывает, что суммирование без отбрасывания значащих цифр и без округления может продолжаться достаточно долго в единицах времени, измеряемых сутками и более, при количестве ПЭ, меньшем десяти ДЛЯ и =127 .

Таким образом, в главе показано, что рост диапазона данных в рассматриваемом методе не выше, чем в традиционной арифметической обработке, при этом производительность метода характеризуется тем, что выполнение групп полноразрядных операций сводится к поразрядно-

и

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

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

Во второй главе с целью полноты исследования аспекта расширения диапазона данных при вертикальной обработке предложенный метод апробируется на умножении целых двоичных чисел. Выполнены оценки роста диапазона произведений применительно к поразрядно-параллельной обработке потока целых двоичных сомножителей без вычисления переноса, рассмотрен аналог архитектуры параллельного вычислителя с учетом специфики выполнения операций в данном случае. Поясним метод на примере потокового умножения ПОСЛеДОВаТеЛЬНОСТИ 4-раЗрЯДНЫХ ДВОИЧНЫХ ЧИСеЛ: а| =10П , аг =1101 , а! =1001 ,...

Шаг 1. Ла и :

0 1 1 0

і[°>

10 11 0 0 0 0 10 11 10 11 Г 1111111 1 [0001000 ]'

школьная схема

невычисляемый набор промежуточных слагаемых

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

Шаг 2 :

= і{0)х 1001+4^x1001.

1111111 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1111111

0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0

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

переносится на шаг к, к = и г.....В общем случае промежуточный набор всегда

состоит из ограниченного количества двоичных слагаемых. При вычислении произведения по этому алгоритму для сколь угодно большого количества сомножителей м и произвольно зафиксированного числа их разрядов л+1 количество sf*) слагаемых к -го промежуточного набора ограничено константой, не зависящей от а и м, но зависящей от л

snpSf^Slog л + log-log (2n + 2)+-2 . (1)

ta '

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

Вводится обозначение правой части неравенства (1) — и

рассматриваются sîxfn+i) слагаемых входного набора, в них выделены те старшие разряды, которые соответствуют сдвигу сомножителя на л разрядов влево на каждом шаге формирования набора «школьных» схем умножения. В главе доказана

Лемма 1. В рассматриваемых ограничениях з кй = const такое, что прирост р числа разрядов, отсчитываемый от старшего разряда промежуточных слагаемых на входе к -го шага умножения, удовлетворяет неравенству:

Pil VkZk0. (2)

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

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

Р ¿n + l V kzk . (3)

в g V '

Теорема 3. Начиная с некоторого шага с номером умножения,

выполняемого рассматриваемым способом, общий прирост pt числа разрядов по отношению ко всем предыдущим шагам будет удовлетворять неравенству:

к,

Р £ Е log, log^.log, St +kn+l Viai^. (4)

( = 1'-,-:-'

J

Лемма 2. При сжатии промежуточной суммы до двухрядного кода на нечетных шагах прирост старшего разряда оценивается из неравенства Р, s 1, к =\, 2...; на четных - из неравенства ? siogi log s . При этом з*, такое, что

l^Zk

для всех номеров к шага сжатия входного набора будет выполняться неравенство:

р si viaio. (5)

Следствие 1. Суммарный прирост р по всем i шагам сжатия текущего

входного набора (без учета отношения ко всем предыдущим шагам) на шаге с

четным номером составит: р £ £ (i +log log ...log s ). При нечетном номере шага

> w ^-ъ

сжатия текущего входного набора суммарный прирост составит:

Р £ i (1 + log log ...log S ) + l.

/=1 •—I-i-•

Перенести прием ограничения роста диапазона данных при потоковом сложении на случай умножения не представляется возможным. Однако возможно вести процесс без округления и отбрасывания значащих цифр на абстрактной архитектуре параллельного вычислителя, в котором все разрядные срезы суммируются СВН-параллельно на сопоставленных им ПЭ.

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

Метод выполнения сложения Временная и аппаратная сложность выполнения существующих методов

Сложение п -разрядных двоичных чисел с последовательным распространением переноса Т = о{п), число элементов устройства: (7л+1)

Бинарное сложение п -разрядных двоичных чисел на параллельном сумматоре log2я <7*<loglп + ^2Iogзл + 6, Т = ^ п + С) (ьтц ^ ^ ,

число элементов устройства о^2п^

Сумматор п -разрядных чисел, построенный методом В.М. Храпченко Г<1О8!И + ^21О82И + 6 , число элементов устройства:

Троичный метод Т < 1,262 л + 1]+1, число элементов устройства: о(н1овп)

Предложенный метод вертикальной обработки т =0(1), число компонентов устройства о(л)

Сравнительные оценки временной сложности бинарного умножения п -разрядных чисел и вертикальной обработки потока сомножителей располагаются в следующей таблице:

Метод умножения Временная и аппаратная сложность выполнения существующих методов

Традиционный метод умножения «в столбик» (школьная схема) r = o(«2), число элементов устройства: бл2 -8л +0(1)

Метод Карацубы или метод Devide and Conquer (разделяй и влавствуй) Г< o(log: п) 1463 1п<»3 ЧИСЛО элементов устройства: —*лш=а -52л + 5

Алгоритм Шёнхаге — Штрассена r<o(logn), л —количество двоичных цифр в произведении, число элементов устройства: о(л log п log л log л)

Алгоритм М. Фюрера где чрезвы« сверхлогари отношения число элеме где O(lo числа л айно ме фм 1 log...logn log" л нтов уст 5*п) — И] Г <0^1ognlog* л^, ,дленно растущая функция Dg" п определяется ИЗ = 1 -ройства: л 2°(|о8*"^, герированный логарифм

Предложенный метод вертикальной обработки Г=о(1о8л), число компонент устройства О^и2 lognj

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

сложении, — малая временная сложность достигается за счет отсутствия вычисления переносов.

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

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

число представленное в двоичном коде, где т — количество

инвертированных в обратный код слагаемых. Способ сохраняется для бинарного поразрядно-параллельного алгебраического сложения и в таком виде используется для сравнения строк. Пусть требуется найти алгебраическую сумму ПЯТИ ДВОИЧНЫХ чисел: Б = а, + (-аг) + а, + а, + (-я5) , ГДе ^ =10101 , =-01011 ,

а. =1пп , =00000, ^ »-поп . Отрицательные числа переводятся в обратный

код: а2 =10100, я1 =аошо . Инвертированные слагаемые наряду с положительными

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

10 10 1 10 10 0 + 11111 0 0 0 0 0 0 0 10 0 110 10 1 0 0 0 1 00100 0 10 10 0 0 0 10 0 1

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

0 10 10 0 0 +01001 10 0 110 0

Для окончательного результата из значения юопоо вычитается число тх(2"+1-1), где т~2 - количество инвертированных слагаемых, «+1 = 5— число разрядов входных данных справа налево с отсчетом от нуля. Отсюда

тх(2"+1-1) = 2х[25-1^ = 26-21. Вычитание ^-г1} из полученной суммы сводится к

поразрядно параллельному сложению с двоичным значением разряда веса 21 и вычитанием единицы из разряда веса 26 .Окончательно получим: я =ооошо. Сумма положительна - по знаку старшего ненулевого разряда.

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

дописывается "плюс" единица: ^ - -¡-[^ (2-1=1). Вслед за тем выполняется

еще один шаг вертикального суммирования, который всегда даст алгебраическую сумму в однорядном коде. Пусть, например, требуется сравнить по величине два числа 101011,1000001. Составляется разность 101011-1000001, вычитаемое инвертируется в обратный код: 101011+0111110, слагаемые выравниваются по младшему разряду. Вертикальное суммирование влечет:

10 10 11 + 0 111110 0 0 10 10 1 0 10 10 10

Выполняется тождественное преобразование промежуточной двухрядной суммы:

0 0 10 10 1

+

0 10 10 10 0 0-10-10-1

+

0 111111

Выполняется еще один - завершающий шаг вертикального суммирования:

0 0-10-10-1

+

0 111111 0 110 10 1-1 0 0 0 0 0 0 0

Сумма является однорядной и размещается в верхней разрядной сетке. Ввиду применения модифицированного дополнительного кода от однорядной суммы надлежит вычесть шх(2п+1-1) = 27-2° , где т = 1, и-б, - в соответствии с

инверсией одного (второго) слагаемого с весом старшего разряда 26 . Вычитание единицы из разряда с весом 27 и добавление единицы к разряду с весом 2° даст окончательную алгебраическую сумму в знакоразрядном коде: (-1)1101010. В скобках помещен знак разряда веса 27. В силу неравенств 2п + \ > 2« + 1_1= Н1 ..^щ г ±1±1±1...±1±1±1 наличие отрицательной единицы в старшем

л и

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

поэтому в данном случае уменьшаемое меньше вычитаемого: ююп < 1000001.

На этой же основе, с использованием алгебраического сложения двоичных чисел в знакоразрядном коде, можно осуществлять поразрядно-параллельное сравнение слов произвольной длины. Для этого каждый символ двух сравниваемых слов представляется в двоичном коде согласно его номеру в кодировочной таблице ASCII-кода. Двоичные номера символов слова в порядке следования (в европейских языках - слева направо) записываются в последовательности и интерпретируются как одно двоичное число в позиционной двоичнои системе. При сравнении двух слов сопоставленные им двоичные числа выравниваются по старшему разряду с целью определения лексикографического порядка. Первое из них интерпретируется как число со знаком "плюс" (уменьшаемое), второе - со знаком "минус" (вычитаемое). К сравниваемым числам-словам применяется операция алгебраического сложения в знакоразрядном коде. Знак суммы определяет результат сравнения: если старший ненулевой разряд суммы отрицателен, то первое слово меньше второго в лексикографическом смысле, если положителен, - то оно больше в том же смысле. Пусть сравниваются слова "byte" и "bit". По таблице ASCII-кодов: "byte" 98,121.116,101; "bit" - 98,105,116 . В порядке расположения в двоичном коде получится: "byte" - iioooioiiuooiiiioimnooioi; "bit" - lioooioimooimoim. Разность чисел с выравниванием веса старших разрядов: -

1 0 0 0 1 « 1 1 ' > » 0 1 I ] 1 о I О 0 I 1 о о i о 1 '■"OVIOllOtOOllllOlOO

Алгебраическая сумма с инверсией вычитаемого:

+' 1 0 0 0 1 0 ' ' ' I ° о 1 1 I , о I о и 1 1 о о 1 о 1 ao,l '0i00)01 10000101]

Шаг поразрядно-параллельного вертикального суммирования влечет:

>1111

..........'""OOtOOOOOOOOO

Знакоразрядное преобразование двухрядного кода примет вид:

1111111110 1111

111111110 0 10 1

0 0 ° 0 ° 0 » о ' ° о ° 0 О о о о о о о о о о о о о о , -' -1 -' » -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1-10 0-10 -1 ттт ' 1 1 1 1 1 1 1 1 11 ' > 1 1 1 1 1 1 1 1 1 . О О 1 о I

шаг поразрядно параллельного сложения по вертикали переводит сумму в однорядный код: 1

\ о • о о

1 1 1111

1 о

О о о о о " * " * ' 1

От полученной алгебраической суммы (в 'верхней "¿¡рядной сетке) надлежит вычесть «,х<2» + >-1) при -1,-27, приэтом единица младшего разряда вычитаемого имеет вес 27 относительно младшего разряда уменьшаемого (вследствие сдвига для выравнивания по старшему разряду двоичных кодов слов). Таким образом следует вычесть и^-г1) , т.е. вычитается единица го

разряда с весом 228 и добавляется единица к разряду с весом 27 , в результате сумма со знаком примет вид: оооооооооо 1000000000010-101-11-1.

Знак старшего ненулевого разряда «+», уменьшаемое больше, соответственно, в лексикографическом порядке слово "byte" больше слова "bit".

В главе доказана

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

Лемма не учитывает оценку времени выделения старшего ненулевого разряда.

В главе описан алгоритм совмещения сортировки подсчетом со слиянием в максимально-параллельной форме, который позволяет полностью упорядочивать элементы одновременно двух последовательностей: выполнять слияние еще неупорядоченного массива а (попутно сортируя его) с уже упорядоченным массивом ь. Процесс упорядочения выполняется при помощи матриц сравнения: к квадратной матрице сравнений для сортировки подсчетом неупорядоченного массива а присоединяется ее прямоугольное продолжение по вертикали для сравнения с элементами упорядоченного массива ь. Пусть имеются две последовательности чисел, «=(4,-1,2,0) и 6= (1,3,4,5,6), из которых ь упорядочена, а не упорядочена. Квадратная матрица сравнений и ее вертикальное продолжение имеют вид:

Л* 4 -1 2 0

(1) 4 0 -1 -1 -1

(2) -1 + 1 0 + 1 + 1

(3) 2 + 1 -1 0 -1

(4) 0 + 1 -1 + 1 0

w О) 01 (»

(1) 1 + 1 + 1 -1т (2+1)

(2) 3 + 1 -Ь -1р. (3+2)

(3) 4 От -1т -1(4) (**1)

(4) 5 -Ь -1«) («♦«>

(5) 6 -1т -Ь —1(3) -1«, («♦$)

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

элементов 1-го столбца 6 = по , - для 2-го столбца 1 =от , - для 3-го столбца 4 = мо, - для 4-го столбца 2 = ою . Подсчет по горизонтали влечет: для 1-го элемента массива ь з = он ;-для 2-го элемента 5-101;-для 3-го элемента 7=111;-для 4-го элемента з =2000; - для 5-го элемента 9=1001. В результате полностью упорядоченная последовательность примет вид: (-1,0,1,2,3,4,4,5,6). Все сравнения взаимно независимы, отсюда следует максимальный параллелизм представленного алгоритма. Если число пэ равно числу клеток объединенной матрицы сравнения, то временная сложность сортировки со слиянием составит г^2+пх^=г = о(1). Если учесть „ нулевых элементов диагонали квадратной матрицы и ее антисимметричность относительно этой диагонали, то количество

= т=о{1). В главе даны оценка временной сложности и

пэ снизится: т

„2

( (г VI

Мх л -л

-- + пхт

2

< и

программа последовательного варианта алгоритма. Параллельный вариант следующим образом совмещается с вертикальным потоковым алгебраическим сложением, изложенным в главе 1. Суммирование по столбцам матрицы можно выполнять СВН-параллельно как суммирование разрядных срезов, аналогично выполнимо суммирование по строкам, оба процесса совместимы во времени. Более существенно то, что собственно сами сравнения в этом алгоритме могут бьггь выполнены поразрядно параллельно, как описано выше для бинарного полноразрядного алгебраического сложения в знакоразрядном коде. Отсюда с учетом леммы 3 вытекает

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

= т бинарное ~ О(0 >

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

Описанный алгоритм устойчив (сохраняет порядок равных элементов) и устанавливает взаимно однозначное соответствие входных и выходных индексов. Поиск по маске на данной основе поясняет следующий пример. Пусть в последовательности чисел 1,7.3,4) требуется найти число ь=з и указать индекс его местонахождения. На вход сортировки подается преобразование входной последовательности (в, 1,7, з, 4) вида:

5=(|а.-4К-А|.....1«. -л)з = (|8-3|. |1-3].|7-3|.[3-3|.}4-3| =( 5.2. 4. 0.1

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

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

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

Г 2

(разрядов), умноженном на величину ЛГх " ~"+п:

где ы— число двоичных

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

Теорема не учитывает время выделения старшего ненулевого разряда на выходе сравнения. Этот аспект в главе предлагается разрешать на основе максимально параллельной сортировки знакоразрядных значений.

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

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

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

В частности, следующие результаты отличаются новизной:

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

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

3. Разработано видоизменение алгоритма параллельной сортировки подсчетом и синтезирован параллельный алгоритм одновременного слияния и сортировки на основе вертикального поразрядно-параллельного сравнения с целью информационного поиска, которые отличаются от известных структурой алгоритмов, максимальным параллелизмом сравнений и применимостью к поиску как числовой, так и нечисловой информации.

4. На основе видоизменения поразрядно-параллельного вертикального суммирования натуральных двоичных чисел предложен метод сравнения строковых

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК

1.РоммЯ.Е., Иванова A.C. Оценка числового диапазона целочисленного вертикального умножения // Известия ЮФУ. Технические науки. Тематический выпуск: «Компьютерные и информационные технологии в науке, инженерии и управлении». - 2012. -№ 5. - С. 143 - 151.

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

3.РоммЯ.Е., Иванова A.C. Вертикальные групповые арифметические операции над целочисленными данными без вычисления переноса. // «Фундаментальные исследования». - 2012. - №11 (4).- С. 960 - 964.

Публикации в других изданиях.

4. Ромм Я.Е., Иванова A.C. Оценка роста числового диапазона промежуточных слагаемых в методе вертикального группового суммирования без вычисления переноса / ТГПИ. - Таганрог, 2010. - 29 с. Деп. в ВИНИТИ 19.11.2010, № 644-В2010.

5.РоммЯ.Е., Иванова A.C. Вертикальная арифметическая обработка с расширением целочисленного диапазона // Всероссийская научная школа «Микроэлектронные информационно-управляющие системы и комплексы» Южно-Российский государственный технический университет (Новочеркасский политехнический институт) (ЮРГТУ (НПИ)). 5 -7 сентября 2011 г. - С.12 - 15.

6. Ромм Я.Е., Иванова A.C. Способ вертикального выполнения целочисленного умножения с оценкой роста числового диапазона // Итога и перспективы развития Российско-Германского сотрудничества в области мехатроники. Всероссийская научная школа для молодежи, г. Новочеркасск, 26-28 октября 2011 г.-С. 63-68.

7. Ромм ЯЕ„ Иванова A.C. Оценка роста числового диапазона и архитектура параллельного процессора для вертикального целочисленного умножения / ТГПИ. - Таганрог, 2011. - 16 с. Деп. в ВИНИТИ 22.11.2011, № 506-В2011.

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

9. Ромм Я.Е., Иванова A.C. Оценка числового диапазона, архитектура параллельного процессора и компьютерное моделирование вертикального умножения без вычисления переноса / ТГПИ. - Таганрог, 2012. - 28 с. Деп. в ВИНИТИ 14.02.2012, № 68-В2012.

10. Ромм Я.Е., Иванова A.C. Ограничение роста диапазона двоичных чисел при параллельном выполнении вертикального сложения. Обозрение прикладной и промышленной математики. - Т. 19. - Вып.2. - 2012. - С. 277 - 278 (VIII Международная Петрозаводская конференция «Вероятностные методы в дискретной математике», XIII Всероссийский симпозиум по прикладной и промышленной математике (весенняя сессия), г. Петрозаводск, 2-9 июня 2012 г.).

П.РоммЯ.Е., Иванова A.C. Вертикальное групповое алгебраическое суммирование применительно к сортировке со слиянием и параллельному поиску / ТГПИ. - Таганрог, 2012. - 44 q. Деп. в ВИНИТИ 03.09.2012, № 362-В2012. 12. Иванова A.C., Ромм Я.Е., Вертикальный метод арифметической обработки, сортировки и поиска. — V Международная студенческая электронная научная конференция «Студенческий научный форум» 15 февраля - 31 марта 2013 г. http:// www. scienceforum .ru/2013/27/384.

Личный вклад автора в работах, опубликованных в соавторстве: [1, 4, 7] -

оценки роста диапазона данных поразрядно-параллельного сложения двоичных чисел; [2, 5, 10] - модификация вертикальной обработки с целью исключения потери значащих цифр и расширения диапазона данных; [3, 6-9] — модификация вертикального умножения с исключением вычисления переноса и ускорением умножения до o(iogn); [11, 12] - синтез параллельного алгоритма одновременного слияния и сортировки; [11, 12] - метод сравнения строк в двоичной кодировке с использованием аналога дополнительного кода.

Соискатель

Иванова A.C.

Типогр. ИПК ЮФУ Заказ №£9<*тир.Я?0экз.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ

имени А.П. Чехова»

Правах рукописи

Иванова Анна Сергеевна

РАСШИРЕНИЕ ДИАПАЗОНА ДАННЫХ ДЛЯ ВЕРТИКАЛЬНОЙ ПОТОКОВОЙ ОБРАБОТКИ ПРИМЕНИТЕЛЬНО К СОРТИРОВКЕ СО СЛИЯНИЕМ И ПАРАЛЛЕЛЬНОМУ ПОИСКУ

Специальность:

05.13.17 - Теоретические основы информатики

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

доктор технических наук, профессор Ромм Я.Е.

Таганрог -2013

СОДЕРЖАНИЕ

Введение......................................................................................5

Глава 1. Оценка роста числового диапазона при потоковой вертикальной обработке целочисленных двоичных кодов с фиксированной точкой.........................................................................................35

1.1. Предварительное описание метода вертикальной обработки.........35

1.2. Теоремы об ограниченности промежуточного числа слагаемых.....41

1.3. Последовательное по разрядам много входовое вертикальное суммирование с одновременным запоминанием группы двоичных коэффициентов........................................................................45

1.4. Оценка роста числового диапазона в методе вертикальной обработки........................................................................................................49

1.4.1. Расположение промежуточных слагаемых по секциям после нескольких шагов вертикальной обработки.............................49

1.4.2. Предварительная оценка сверху роста числового диапазона при вертикальной обработке...............................................50

1.4.3. Улучшенная оценка роста числового диапазона........52

1.5. Метод ограничения роста числового диапазона при вертикальной обработке...............................................................................56

1.5.1. Сжатие промежуточного набора слагаемых до двух полноразрядных чисел.......................................................56

1.5.2. Схема ограничения роста числового диапазона слагаемых.............................................................................................57

1.5.3. Алгоритм выполнения вертикальной обработки................60

1.6. Компьютерное моделирование схемы ограничения роста диапазона двоичных слагаемых в процессе вертикальной обработки..................65

1.6.1. Программная реализация метода...................................65

1.6.2. Результат компьютерного моделирования.......................69

1.7. Временная сложность параллельной реализации схемы ограничения роста диапазона двоичных слагаемых..................*..........................73

1.8. Выводы

3 76

Глава 2. Оценка роста числового диапазона при выполнении потокового вертикального умножения................................................................78

2.1. Описание способа вертикального умножения без распространения переноса...............................................................................78

2.2. Оценка роста числового диапазона промежуточных слагаемых при вертикальном умножении...........................................................81

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

2.4. Компьютерное моделирование метода ограничения роста числового диапазона двоичных сомножителей в процессе вертикальной обработки...............................................................................92

2.4.1. Компьютерное моделирование схемы ограничения роста диапазона двоичных слагаемых в процессе вертикальной обработки.......................................................................92

2.4.2. Результаты компьютерного моделирования.....................99

2.5. Сравнение поразрядно-параллельного метода вертикальной потоковой обработки без вычисления переноса с известными методами..............................................................................101

2.6. Выводы..........................................................................104

Глава 3. Модификации параллельной сортировки, слияния и организация параллельного поиска на основе алгебраического целочисленного вертикального сложения........................................................................106

3.1. Сортировка подсчётом........................................................106

3.2. Поиск на основе сортировки подсчётом...................................108

3.3. Алгоритмическое объединение параллельной сортировки подсчетом со слиянием..........................................................................112

3.4. Временная сложность параллельной и последовательной сортировки подсчетом в объединении с параллельным и последовательным слиянием..............................................................................117

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

3.6. Вертикальное алгебраическое сложение двоичных чисел в знакоразрядном коде для сравнения при упорядочении слов и чисел....................................................................................120

3.7. Вертикальное выполнение групповых арифметических и алгебраических операций над двоичными числами с построением аналога дополнительного кода...................................................128

3.7.1. Аналог дополнительного кода для потока групповых алгебраических операций..................................................129

3.7.2. Поразрядно-параллельное сравнение полноразрядных двоичных чисел без вычисления переноса.............................133

3.8. Использование вертикального алгебраического сложения двоичных чисел для максимально параллельного сравнения слов произвольной длины..................................................................................134

3.9. Применение вертикального алгебраического сложения двоичных чисел для максимально параллельного сравнения при локализации экстремумов функций на основе сортировки.................................141

3.10. Выводы.........................................................................142

Заключение Литература.

144 148

ВВЕДЕНИЕ

Актуальность проблемы

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

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

г

двоичными дробями: (а)2 = азиа]а2 ...аг = > гДе (а)2~ Двоичная форма

;=1

представления числа а; а311,а1={0,1} - двоичные цифры, г- разрядность машинных чисел.

Знак числа обычно кодируется двоичной цифрой ат, находящейся слева от точки. При обработке информации все числа находятся в регистрах или ячейках памяти:

Условное положение точки

I

(Хзн а, а2 а,., а

1 1 Цифровые разряды двоичной дроби

Знаковый разряд

Рис.1. Машинное представление чисел с фиксированной точкой

Интервал возможных значений чисел с фиксированной точкой определяется соотношением -(1 -2~г)< а < 1 - 2~г.

В случае если точка фиксирована справа от младшего разряда, компьютер оперирует с целыми числами в диапазоне 0 < |я| < Т -1.

Разрядность сумматоров и ячеек памяти ограничена, поэтому все используемые при вычислениях числа должны быть округлены до г разрядов после запятой или для некоторых специальных способов вычислений - до значения кратного г [4].

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

только младшего разряда аг на значение Д. = {0,1} веса младшего разряда, однако такая замена может повлечь изменение предшествующих цифр числа с фиксированной точкой. Замена числа его приближенным значением меньшей разрядности может осуществляться по различным правилам, описанным, например, в [4].

Полная операция алгебраического сложения, выполняемая компьютером в качестве самостоятельного законченного арифметического действия в соответствии со специальной командой центрального управления, существенно сложнее той элементарной операции суммирования, которая осуществляется сумматором. Элементарное суммирование входит лишь частью в полную операцию сложения или вычитания [6-8].

По знаковому разряду в машинном представлении определяется знак числа: 0 означает, что число положительное; 1 - показывает отрицательное значение [9, 10].

Ниже число разрядов в соответствии с дальнейшими обозначениями определяется равенством г - п.

При сложении чисел с одинаковыми знаками возможно получение значения большего 2"+1, где п - разрядность слагаемых. При этом результат не укладывается в отведенных для него разрядах, такая ситуация называется переполнением разрядной сетки [11 - 13]. Одним из признаков переполнения является отличие знака суммы от знака слагаемых. Если переполнение не возникает, то значения знаковых разрядов совпадают [13].

Конечность диапазона числовых величин в данном формате часто является недостаточной для решения задач научных вычислений.

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

Существующие способы компьютерного алгебраического сложения (на момент рассуждения числа представлены как целочисленные). Для выполнения арифметических операций числа записываются в форме машинных кодов, которые позволяют свести операцию вычитания к операции сложения, автоматически получать знак суммы (разности), выявлять переполнение разрядной сетки [14, 15].

Двоичное представление положительных чисел в компьютере основано на выражении числа в виде суммы степеней двойки с коэффициентами, равными нулю или единице: А = ап2" + апЛ2пЛ + ... + а,2' + а02°, где а0, а],...,ап принимают одно из двух значений: 0 или 1. Неотрицательные целые числа представляются в прямом коде.

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

целыми числами. Вместо этого формата широкое распространение получили форматы представления чисел в обратном и дополнительном кодах [16, 17].

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

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

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

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

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

Способы расширения числового диапазона в формате с плавающей точкой. На случай потокового выполнения алгебраического суммирования в работе предлагается способ сложения чисел с разными знаками, который позволяет выполнять арифметические операции без применения дополнительного и обратного кодов в классической форме: текущее слагаемое, содержащее знак «-», инвертируется, при этом к содержимому счетчика инвертированных слагаемых добавляется единица. Это равносильно тому, что к отрицательному слагаемому прибавили число с положительной единицей и нулями во всех разрядах. Преимуществом данного способа [20] является то, что он позволяет, не выполняя окончательных вычислений, определять знак результата суммирования пары чисел, только по старшим разрядам пары чисел в двухрядном коде алгебраической суммы.

Информационно-логические основы построения вычислительных машин охватывают круг вопросов, связанных с формами и системами представления информации в компьютерах, а также с логико-математическим синтезом вычислительных схем и архитектурой электронных компонентов компьютера. Процесс выполнения любых арифметических и логических операций в арифметическом устройстве слагается из выполнения более простых элементарных операций. К числу последних относятся, например, сдвиг числа, обращение кода числа, передачи чисел и другие; наиболее сложной и, может быть, наиболее важной из элементарных операций является суммирование. Каждая из элементарных операций осуществляется, как правило, своей специальной схемой, например, схемой, известной как сумматор. Иногда, схемы для выполнения двух или нескольких элементарных операций могут частично состоять из общих для одной и для другой схемы элементов (особенно если эти операции не предполагается выполнять одновременно) [1]. Необходимо подчеркнуть, что классические схемы ориентированы на отдельные операции, поэтому возникают проблемы их адаптации к обработке потоков данных, в частности, числовых.

Рост требований к производительности и пропускной способности вычислительных систем, связанный с ростом объемов обрабатываемой информации, требует повышения эффективности использования вычислительных ресурсов [18].

Усовершенствование и развитие вычислительной техники напрямую зависят от скорости и точности выполнения арифметических операций в ЭВМ [21].

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

Вертикальная обработка. Близкой в качестве прототипа к теме и подходу излагаемого исследования является схема вертикальной обработки.

Операции сложения и умножения в целом занимают доминирующее место среди арифметических операций. Ускорение выполнения операции сложения позволит повысить скорость других арифметических операций.

Вопросам скоростной обработки числовой и символьной информации занимались такие отечественные и зарубежные ученые как Каляев A.B., Ачасова С.Н., Бойков В.Д., Смолов В.Б., Марков A.A., Бандман O.A., Kung N.T., Book R.V. [21].

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

данную схему вертикальной обработки. Предлагается, помимо того, для увеличения быстродействия использовать в элементах вертикального арифметического устройства последовательный двоичный сумматор [23] (рис.2).

1 1

А С В А

ЗУ АУ

Рис.2 Моделирование ассоциативной обработки в вертикальном параллельном

процессоре

Еще одним видом параллельных процессоров с вертикальной обработкой являются динамические параллельные процессоры [23, 24], которые отличаются тем, что в качестве источника входных образов используют запоминающие устройства с оче�