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

• Автор: Иванова, Анна Сергеевна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Таганрог
• Количество страниц: 162 с. : ил.

СОДЕРЖАНИЕ
Введение
Глава 1. Оценка роста числового диапазона при потоковой вертикальной обработке целочисленных двоичных кодов с фиксированной точкой
1.1. Предварительное описание метода вертикальной обработки
1.2. Теоремы об ограниченности промежуточного числа слагаемых
1.3. Последовательное по разрядам многовходовое вертикальное суммирование с одновременным запоминанием группы двоичных коэффициентов
1.4. Оценка роста числового диапазона в методе вертикальной обработки
1.4.1. Расположение промежуточных слагаемых по секциям после нескольких шагов вертикальной обработки
1.4.2. Предварительная оценка сверху роста числового диапазона при вертикальной обработке
1.4.3. Улучшенная оценка роста числового диапазона
1.5. Метод ограничения роста числового диапазона при вертикальной обработке
1.5.1. Сжатие промежуточного набора слагаемых до двух полноразрядных чисел
1.5.2. Схема ограничения роста числового диапазона слагаемых
1.5.3. Алгоритм выполнения вертикальной обработки
1.6. Компьютерное моделирование схемы ограничения роста диапазона двоичных слагаемых в процессе вертикальной обработки
1.6.1. Программная реализация метода
1.6.2. Результат компьютерного моделирования
1.7. Временная сложность параллельной реализации схемы ограничения роста диапазона двоичных слагаемых
1.8. Выводы

Гпава 2. Оценка роста числового диапазона при выполнении потокового вертикального умножения
2.1. Описание способа вертикального умножения без распространения переноса
2.2. Оценка роста числового диапазона промежуточных слагаемых при вертикальном умножении
2.3. Организация архитектуры параллельной вычислительной системы для ограничения роста числового диапазона при выполнении вертикального умножения
2.4. Компьютерное моделирование метода ограничения роста числового диапазона двоичных сомножителей в процессе вертикальной обработки
2.4.1. Компьютерное моделирование схемы ограничения роста диапазона двоичных слагаемых в процессе вертикальной обработки
2.4.2. Результаты компьютерного моделирования
2.5. Сравнение поразрядно-параллельного метода вертикальной потоковой обработки без вычисления переноса с известными методами
2.6. Выводы
Глава 3. Модификации параллельной сортировки, слияния и организация параллельного поиска на основе алгебраического целочисленного вертикального сложения
3.1. Сортировка подсчётом
3.2. Поиск на основе сортировки подсчётом
3.3. Алгоритмическое объединение параллельной сортировки подсчетом со слиянием
3.4. Временная сложность параллельной и последовательной сортировки подсчетом в объединении с параллельным и последовательным слиянием
3.5. Применение вертикального суммирования для выполнения сортировки подсчетом, алгоритмически совмещенной со слиянием
3.6. Вертикальное алгебраическое сложение двоичных чисел в знакоразрядном коде для сравнения при упорядочении слов и чисел
3.7. Вертикальное выполнение групповых арифметических и алгебраических операций над двоичными числами с построением аналога дополнительного кода
3.7.1. Аналог дополнительного кода для потока групповых алгебраических операций
3.7.2. Поразрядно-параллельное сравнение полноразрядных двоичных чисел без вычисления переноса
3.8. Использование вертикального алгебраического сложения двоичных чисел для максимально параллельного сравнения слов произвольной длины
3.9. Применение вертикального алгебраического сложения двоичных чисел для максимально параллельного сравнения при локализации экстремумов функций на основе сортировки
3.10. Выводы
Заключение
Литература.

ГЛАВА 1. ОЦЕНКА РОСТА ЧИСЛОВОГО ДИАПАЗОНА ПРИ ПОТОКОВОЙ ВЕРТИКАЛЬНОЙ ОБРАБОТКЕ ЦЕЛОЧИСЛЕННЫХ ДВОИЧНЫХ КОДОВ С ФИКСИРОВАННОЙ ТОЧКОЙ
Постановка вопроса. В главе ставится задача получить оценку роста числового диапазона метода потоковой вертикальной обработки, специфика которого состоит в поразрядном параллелизме на основе исключения операций вычисления переноса. Непосредственно метод изложен в [20, 38, 72], но при этом асимптотика роста числового диапазона аналитически не была исследована и искомая оценка роста в исходном описании отсутствует. С~ целью' провести требуемое исследование необходимо представить' предварительное описание метода вертикальной обработки. Вначале исследуется рост диапазона при потоковом сложении [73]. Затем в главе будет показано, что начиная с некоторого шага, рост диапазона не превосходит роста при обычном бинарном сложении с вычислением переноса. Конечной целью является показать, что метод позволяет исключить отбрасывание значащих цифр мантиссы числа, то есть увеличить точность операций сложения потока слагаемых. Помимо аналитических оценок в главе выполняется компьютерное моделирование метода с целью аргументации излагаемых положений и выкладок. Будут предложены варианты архитектуры параллельного вычислителя на базе полученных оценок. В дальнейшем (гл. 2, 3) метод, оценки и архитектура
распространяются на операции общего вида и прилагаются к выполнению сортировок, слияния и поиска.
1.1. Предварительное описание метода вертикальной обработки.
Предварительное описание метода вертикальной обработки заимствуется без изменений из [20, 38].
Пусть на входе метода все числа представлены (п +1) -разрядными двоичными полиномами вида:
(1.1)