Расширение диапазона данных для вертикальной потоковой обработки применительно к сортировке со слиянием и параллельному поиску тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Иванова, Анна Сергеевна

• Иванова, Анна Сергеевна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Иванова, Анна Сергеевна

СОДЕРЖАНИЕ

Введение

Глава 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. Выводы

3

Глава 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. Выводы

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

144

Введение диссертации (часть автореферата) на тему «Расширение диапазона данных для вертикальной потоковой обработки применительно к сортировке со слиянием и параллельному поиску»

ВВЕДЕНИЕ

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

Диапазон представления информации в памяти компьютера. Числа в памяти компьютеров представляются в двух форматах - для кодирования целых и действительных чисел - с фиксированной и плавающей точкой соответственно. Способы обработки и границы диапазона в данном формате сохраняют неизменность в течение нескольких десятилетий [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], которые отличаются тем, что в качестве источника входных образов используют запоминающие устройства с очередной выборкой (ЗУОВ) -запоминающие устройства с естественным последовательным обращением к разрядам каждого слова. Их преимуществом является большая емкость при низкой удельной стоимости.

Рис.3. Структурная схема динамического параллельного процессора где ЗУОВ - запоминающие устройства с очередной выборкой, ЗУМС -запоминающие устройства межэлементных сигналов, ВАЛУ - вертикальные арифметические запоминающие устройства [23, 24].

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

организация параллельной обработки информации [25]. Для организации параллельной обработки выделяют способы:

1) совмещение во времени разных этапов разных задач;

2) одновременное решение разных задач или частей одной задачи;

3) конвейерная обработка информации [25, 26].

Конвейерная обработка информации включает в себя:

- разбиение вычислений на последовательность одинаковых по времени этапов;

- реализацию каждого из этапов аппаратно в виде ступени конвейера;

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

Эффективность конвейера увеличивается при увеличении количества

задач на его входе. Примером конвейерных операционных устройств

являются матричные умножители [27].

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

<2з &2

х Ьт, Ь? Ь1 Ьп + аф0 а2Ь0 афо аф0 + аф\ а2Ь\ аф\ аф\

+ аф2 а2Ъ2 аф2 афг

+ афъ а2Ьъ афз афъ

с7 с6 с5 с4 с3 с2 с\ со

По косвенной схеме умножения на устройстве с одним сумматором и набором регистров для реализации этого умножения необходимо в общем случае выполнить четыре шага, на каждом их которых выполняется умножение А на очередной разряд Ь,, сложение АхЬ, с текущей суммой частичных произведений и сдвиг новой полученной суммы на 1 разряд вправо. Таким образом, время на выполнение этого умножения можно приближенно оценить как: Т = +4х/ш +/лА), где - задержка на 1

логическом вентиле (при умножении А на 6,), 4 х - задержка на сложение при использовании сумматора с последовательным переносом, /1т - задержка одноразрядного полного двоичного сумматора, которую можно принять равной , tih -задержка на 1 сдвиг, которую также можно приравнять

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

Системные средства

Средства

управления

систе- програм- коман-

мой мой дами

Локальная память

управляющ РОН РЮ с плавающ запятой

14 / \ \ / / \

71

Средства обработки

с фикс запятой с плав запятой деся-тичн строк

Управление каналами ввода / вывода

приоритеты

буферы данных

Средства управления памятью

буф память управл доступом защита памяти

1 'Г

Рис. 3. Схема умножителя Брауна

Каждая линейка сумматоров представляет собой, сумматор с сохранением переноса (ССП), используемый в разных арифметических устройствах [29].

Рис. 4. Схема умножителя.

Пунктиром обведен параллельный сумматор, который может быть реализован, как показано на рисунке, то есть как сумматор с последовательным переносом, или, - по схеме с ускорением переноса. Время умножения на подобном умножителе: Тумн =/+(« + т -2)х/5т, где п -

разрядность множимого, т - разрядность множителя.

В формуле не присутствуют затраты на сдвиги, так как они задаются жестко путем соединений линеек сумматоров, кроме того, считается, что все частичные произведения формируются за одно логическое умножение. Таким образом, быстродействие умножителя по сравнению с обычной схемой примерно в три раза выше. Кроме того, умножитель может работать в режиме конвейера. В данном случае число его ступеней равно шести [27]. Пиковая производительность конвейера при полной загрузке - 1 результат за 2г& то есть, в 20 раз выше, чем в обычной схеме. Такой выигрыш

достигается за счет дополнительных аппаратных затрат, которые выше, чем в первом случае примерно в 4-5 раз [27].

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

- распараллеливание вычислений (одновременное вычисление всех

ль,);

- конвейеризация вычислений (цикл умножения разворачивается в

последовательность ступеней, межразрядные переносы сохраняются и передаются на следующую ступень);

- аппаратная реализация и специализация вычислений позволяет

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

Основной элемент матричного умножителя - сумматор с сохранением переноса (ССП) [27]. Его используют для ускорения сложения N чисел. На рис 5. показан сумматор, выполняющий сложение трех чисел на базе ССП. Полный сумматор позволяет складывать 3 одноразрядных числа. В качестве третьего слагаемого выступает перенос, поступающий с предыдущего сумматора, или со схемы передачи переноса. Но если в качестве третьего слагаемого использовать соответствующий разряд третьего «-разрядного числа и не передавать перенос в следующий одноразрядный сумматор, то на выходе сумматора сформируется сумма в данном разряде и перенос [27].

На выходе линейки таких сумматоров формируются два числа -собственно сумма разрядов трех п -разрядных слагаемых и сумма переносов при сложении этих слагаемых. Сумма этих двух чисел и представляет собой значение суммы трех слагаемых: 3 = Х + У + г = Я ху. + Сху: [27].

Линейка полных сумматоров, обведенная на рис.5 пунктиром -сумматор с сохранением переноса (ССП). Данная схема имеет три входа и два выхода (имеются в виду п - разрядные входы и выходы) - обозначается ССПМ [27].

Рис. 5. Сумматор на базе ССП

Если подать два полученных числа на обычный параллельный сумматор, то на выходе мы получим сумму трех чисел. Если использовать не один ССП32, а дерево таких сумматоров, как показано на рис. 6 (ССП8_2), то выполняется сложение восьми чисел, и так далее - для N чисел мы используем схему ССПЫ_2. Фактически имеем схему, похожую на пирамидальную, но с одной общей схемой передачи и ускорения переноса [27, 28].

Б

Рис 6. Сумматор на базе ССП для сложения восьми чисел

Ускорение схемы на базе ССП по сравнению с пирамидальным включением сумматоров зависит от времени задержки параллельного сумматора со схемой ускоренного переноса (СУП):

'сум N

Куск = ----- , где гсум - время задержки параллельного

1сум 1оёз/2 м

сумматора с СУП, - задержка полного одноразрядного сумматора [27].

Рис. 7. Сумматор на базе ССП для сложения чисел

При этом для большинства СУП ускорение схемы с ССП по сравнению с пирамидальной возрастает при увеличении разрядности слагаемых, так как соответственно растет (сум, а /зс не меняется.

На базе быстродействующего сумматора на N чисел, можно построить матричный умножитель Уоллеса [30]. В таком устройстве умножение выполняется в два этапа - на первом формируются все частичные произведения вида АхЫх2' , на втором - полученные N частичных произведений складываются на сумматоре с ССПМ.2, как показано на рис. 7 на примере умножения на восьми разрядный множитель. В умножителе Брауна быстродействие выше по причине использования большего количества ССП , что дает возможность распараллелить процесс сложения частичных произведений [29].

Конвейерные операционные устройства (ОУ) могут являться составной частью ОУ процедурного типа, или - блочных ОУ для аппаратного ускорения выполнения операций [29].

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

Таким образом, особенностью векторно-конвейерных машин является:

1. Поддержка векторных и матричных операций в системе команд.

2. Ускорение обработки векторов за счет конвейеризации выборки и собственно обработки в конвейерных исполнительных устройствах.

3. Наличие векторных регистров.

4. Развитые механизмы адресации и выборки/записи в память.

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

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

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

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

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

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

ПЭ1+1 ПЭ; ПЭз ПЭ2 ПЭ1

.. 1 1 г 1 1 г

Рис. 8. Архитектура МВС для потоковой вертикальной обработки в формате с

фиксированной точкой

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

Соединение параллельных вычислений и вертикальная обработка (архитектуры системы СТАРАН). Выделяют следующие подходы к построению архитектуры параллельных программ [1, 33]:

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

• распараллеливание по данным. Весь исходный массив данных разбивается на подмножества и фрагменты распределяются между процессорами системы. Одни и те же операции выполняются одновременно над несколькими элементами массива данных [34]. Наиболее известной из параллельных моделей программирования является 81МЕ). Недостаток

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

Ассоциативные вычислительные системы создаются для решения задач невычислительного характера, таких как распознавание и поиск. Например, реляционный ассоциативный процессор (RAP), являющийся вычислительной системой для поддержки баз данных [27, 36.]. Проектом вычислительной ассоциативной системы являются вычислительные машины "Staran", "Omen" [25]. Отличительной особенностью является наличие ассоциативной памяти - памяти с многомерным доступом, к которой можно обратиться как поразрядно, так и пословно, операционные процессорные элементы предусмотрены для каждого слова памяти; имеется уникальная схема перестановок для перегруппировки данных в памяти.

Основным элементом системы является многомерная ассоциативная матрица - ассоциативный модуль (AM) [36]. Для обработки информации в нем 256 процессорных элементов (яэ), которые последовательно обрабатывают слова. Все пэ работают по одной команде, передаваемой устройством управления в одно время. Таким образом, по одной команде обрабатываются одновременно все выбранные по определенным признакам из памяти слова [36].

Для выполнения параллельных арифметических и логических операций над словами в памяти схема перестановок позволяет сдвигать и перегруппировывать данные [36].

Разряд

255

§

а б

255

V////////////////////,

254

255

пэо

пэ1

ПЭ254

пэ255

Рис. 9. Процессорная обработка в системе 5'ТАЛАМ

В базовой конфигурации 8ТАЯАК содержится один АМ [37]. При этом число модулей может изменяться в системе от 1 до 32. То есть, при максимальном числе модулей в системе может подвергаться ассоциативной обработке 256 кбайт информации. Скорость поиска и обработки информации 256 процессорными элементами высока, и остальные элементы системы спроектированы так, чтобы поддерживать эту скорость [37].

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

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

Список литературы диссертационного исследования кандидат наук Иванова, Анна Сергеевна, 2013 год

СПИСОК ЛИТЕРАТУРЫ

1. Карцев М.А. Арифметика цифровых машин - М.: Наука, 1969. - 575 с.

2. Косякин A.A. Статистическая теория квантования по уровню // Автоматика и телемеханика. - 1961- № 6. - С.722-729.

3. Генри С. Уоррен, мл. Глава 15. Числа с плавающей точкой // Алгоритмические трюки для программистов. — М.: Вильяме, 2007. — 288 с.

4. Желнов Ю.А. Точностные характеристики управляющих вычислительных машин. - М.: Энергоатомиздат, 1983. - С.40-41.

5. Дьяконов В.П., Абраменкова И.В., Пеньков A.A. Новые информационные технологии. Новые информационные технологии: Учебное пособие. Часть 3. Основы математики и математическое моделирование. - Смоленск: СГПУ, 2003. - 192 с.

6. Токхейм Р. Основы цифровой электроники: Пер. с англ. - М.: Мир, 1988. -392 с.

7. Пономаренко В.И., Лапшева Е.Е. Информатика. Технические средства // Учебное пособие - Саратов: Научная книга, 2009. - 212 стр.

8. Мураховский В.И. Устройство компьютера - М.: Аст-пресс книга, 2003. - 640 с.

9. Каган Б.М. Электронные вычислительные машины и системы. М.: Энергоатомиздат. 1991. - 592 с.

10. Шауман A.M. Основы машинной арифметики. Л.: Изд-во Ленинградского университета. 1979.-321 с.

11. Гармаш А.Н. Основы информатики: Учебное пособие. - Таганрог: Изд-во ТРТУ, 2004.- 131 с.

12. Фрике К. Вводный курс цифровой электроники. - М: Техносфера, 2003. -432с.

13. Горнец H.H., Рощин А.Г., Соломенцев В.В.. Организация ЭВМ и систем: Учебное пособие для студ. высш. учебных заведений. — М.: Изд. центр «Академия», 2006. - 320 с.

14. Корнеев B.B. Вычислительные системы. - М.: Гелиос АРВ, 2004. - 512 с.

15. Келим Ю. М. Вычислительная техника. — М.: Изд. центр «Академия», 2005.-384 с.

16. Жуков К.Г. Справочное руководство пользователя Fixed-Point Blockset. http://matlab.exponenta.rU/fixedpoint/bookl/l.php.

17. Хамахер К., Врашевич Э., Заки С. Организация ЭВМ. 5-е изд./ - СПб.: Питер, Киев BHV, 2003. - 848 с.

18. Богданов А. В., Корхов В. В., Мареев В. В., Станкова Е. Н. Архитектуры и топологии многопроцессорных вычислительных систем - М. : ИНТУИТ.РУ, 2004. - 176 с.

19. Грис Д. Наука программирования - Пер. с англ. - М.: Мир, 1984. -416с.

20. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. I. Групповые арифметические операции // Кибернетика и системный анализ, Киев, 1998, № 3. - С. 123 - 151.

21. Тютюнов Д.Н. Продукционная алгоритмическая схема и устройство сумматора массива чисел в знакоразрядной системе счисления. - Курск: КГТУ, 2006, автореферат диссертации на соискание ученой степени кандидата технических наук. - 167 с.

22. Городняя J1.B. Парадигмы программирования. М: Интернет-университет информационных технологий, http://www.intuit.ru, 2007.

23. Фет Я.И. Параллельные процессоры для управляющих систем. М.:Энергоиздат.,1981. - 160 с.

24. Воеводин Вл.В., Капитонова А.П. Методы описания и классификации вычислительных систем. // Изд-во МГУ, 1994. - 79 с.

25. Ларионов A.M., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети. - Ленинград: «Энергоатомиздат», 1987. -С.34 - 35.

26. Ramachandran Dr. S. Digital VLSI Systems Design A Design Manual for Implementation of Projects on FPGAs and ASICs Using Verilog, 2007. Springer. 709 pp.

27. Ремонтов А.П., Писарев А.П. Вычислительные машины и системы: Учеб. пособие // Пенза, 2006 - 96 с.

28. Орлов С. А., Цилькер Б. Я. Организация ЭВМ и систем: Учебник для ВУЗов (изд:2) - Питер, 2004 - 654 с.

29. Духнич Е.И., Андреев А.Е. Организация вычислительных машин и систем: Учебное пособие. - ВолгГТУ, Волгоград, 2003 - 80 с.

30. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах - М.: Радио и связь, 1990 - 304 с.

31. Уэйкерли Дк. Ф. Проектирование цифровых устройств. Т.1. - М.: Постмаркет, 2002 - 544 с.

32. Тарануха В.М. Многоуровневая m-матричная вычислительная структура вертикальной арифметики. Патент РФ № 2246128.

33. Шпаковский Г.И. Организация параллельных ЭВМ и суперскалярных процессоров: Учеб. пособие. - Мн.: Белгосуниверситет, 1996 - 296 с.

34. Дорошенко А.Е. Математические модели и методы организации высокопроизводительных параллельных вычислений // Киев: Наукова думка, 2000. - 176 с.

35. Running Code at a Teraflop: Overview of GPU Architecture, SIGGRAPH 2009: Beyond Programmable Shading, Kayvon Fatahalian, Stanford University.

36. Смирнов А.Д. Архитектура вычислительных систем: Учеб.пособие для вузов. М.: Наука. Гл. ред. физ.мат. лит., 1990. - 320 с.

37. Goodyear Aerospace Corporation (1972), STARAN S APPLE-Programming Manual GER-15637, Akron, Ohio: Goodyear Aerospace Corporation.

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

39. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

40. Сегалович И.В. Как работают поисковые системы // Мир Internet. — 2002. -№ 10.-С. 23-25.

41. Гречихин A.A. История, теория и методика информационного поиска, hi-edu.ru/e-books/xbook020/01/index.html.

42. Yiannis John, Zobel Justin. Compression techniques for fast external sorting. The VLDB Journal (2007) 16(2): 269-291.

43. Akl, S.G. Parallel Sorting Algorithms. Academic Press, Inc., London (1990).

44. Cormen Т.Н., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. 2nd Edition The MIT Press, 2001.

45. Кнут Д. Искусство программирования для ЭВМ. Т.З. Сортировка и поиск. - М. : Мир, 2001. - 844 с.

46. Ромм Я.Е., В.В. Виноградский. Преобразование сортировки Хоара в параллельную форму на основе матриц сравнений. // Проблемы программирования. Киев, 2008. № 2-3. - С. 332 - 340 с.

47. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. -2-е изд., испр. -сПб:. Невский Диалект, 2001г.-352 с.

48. Кузнецов С.Д. Методы сортировки и поиска ИСП РАН, Центр Информационных Технологий Электронный ресурс - Режим доступа: http:// www.citforum.ru/pro gramming/theory/sorting/sorting2. shtml

49. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. II // Кибернетика и системный анализ. 1995. - № 4. - С. 13-37.

50. Седжвик Р. Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск/Алгоритмы на графах. - Киев: ДиаСофт, 2003 - 1136 с.

51. Dumi A.l. Computers & Automation, 5, 12 (December 1956), P. 6-9.

52. Peterson U.U. IBM J.Research & Development, 1 (1957), P. 130-146.

53. But E.D. Information and Control, 1 (1958), P. 159-164.

54. Duglas A.C. Comp.J., 2 (1959), P. 1-9.

55. Ajverson K.E. A Programming Language (New York: Wiley, (1962)), P. 133158.

56. Buhholxc B. IBM Systems J., 2 (1963), P. 86-111.

57. http://pmkinfo.tversu.ru/dis/inform2/S.pdf.

58. Sedgewick, Robert, Algorithms in С++, (Addison-Wesley, 1992).

59. Robertson, S.E. and Sparck Jones, K. Relevance weighting of search terms, Journal of the American Society for Information Science, 27, 1976, 129-146; (reprinted in Willett 1988).

60. Горбатов B.A. Фундаментальные основы дискретной математики. Информационная математика. - М.: Высш. шк., 2000. - 544 с.

61. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов - М.: Мир, 1979.

62. Лукашевич Н.В. Тезаурусы в задачах информационного поиска. - М.: Изд-во Московского университета, 2011. - 512 с.

63. Агеев М.С., Кураленок И.Е. 2004. Официальные метрики РОМИП 2004 // Российский семинар по Оценке Методов Информационного Поиска.

64. Адамович И.М., Заикин М.Ю., Земсков Д.В., Пешков А.И. Поиск информации в WEB. Сравнительная оценка поисковых машин // Системы и средства информации. 2003, № 13. - С. 84 - 105.

65. Korfhage, Robert R. (1997). Information Storage and Retrieval. Wiley, pp. 368 pp.

66. Frakes, William B. (1992). Information Retrieval Data Structures & Algorithms. Prentice-Hall, Inc. ISBN 0-13-463837-9

67. Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. — 1998 r.

68. Капустин B.A. Основы поиска информации в Интернете. Методическое пособие. - СПб.: Институт «Открытое общество». Санкт-Петербургское отделение, 1998. — 13 с.

69. Manning С., Raghavan Р., Schütze Н. Introduction to Information Retrieval. — Cambridge University Press, 2008. — ISBN 0-521-86571-9.

70. Baeza-Yates R., Ribeiro-Neto В. Modern Information Retrieval. — Addison-Wesley, 1999. — ISBN 0-201-39829-X.

71. Татарников О. Новые технологии поиска в Интернет // Компьютер Пресс. 2005. № 10.-С. 14-17.

72. http://www.seonews.ru/

73. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. III. Приложение к бинарным арифметическим операциям // Кибернетика и системный анализ, Киев, 1999, № 1. - С. 152165.

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

75. Храпченко В.М. Об одном способе преобразования многорядного кода в однорядный // ДАН СССР, 1963. - т. 148. - № 2. - С. 296 - 299.

76. Dadda L. Some schemes for parallel multipliers. - Alta Freg. - May. - 1965. -p. 349-356.

77. Храпченко В.М. Методы ускорения арифметических операций, основанные на преобразовании многорядного кода // Вопросы радиоэлектроники. - Сер. УП ЭВТ. 1965. - вып. 8 - С. 121 - 144.

78. Храпченко В.М. Об асимптотической оценке времени сложения параллельного сумматора // Проблемы кибернетики. - М.: Наука, 1967. -Вып. 19.-С. 107- 123.

79. Дрозд A.B., Паулин О.Н., Дрозд Ю.В. Выполнение операции вертикального сложения в арифметических устройствах / Тр. Одес. политехи, ун-та. - Одесса, 1997. - Вып. 2(4). - С. 30 - 32.

80. Карцев М.А., Брик В.А. Вычислительные системы и синхронная арифметика. - М.: Радио и связь, 1981. - 358 с.

81. A.C. 798830 (СССР). Устройство для подсчета количества единиц в двоичном числе / Сорокин C.B., Морозов Г.М. Опубл. в БИ. - 1981. - № 3.

82. Swartzlander Е.Е. Parallel Counters // IEEE Transactions of computers. -1973. -v.c. 22, № 11.-p. 1021-1024.

83. Ромм Я.Е. Вертикальная организация поразрядно-параллельных вычислений в ЭВМ. II / ТРТИ - Таганрог, 1990. - 57 с. ДЕП в ВИНИТИ 16.07.90, №3970-В 90.

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

85. Пат. 5210711 (США). Very fast variable input multi-bit addder / Rossmer David, Capitant Patrice.-Опубл. 11.5.93.

86. Пат. 2023288 (Россия). Комбинационный сумматор структурных кодов / Ткаченко A.B., Харламов Д.В. Опубл. 15.11.94.

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

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

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

90. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. М: Мир, 1978.

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

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

93. Базарова С. Б-М., Чемерисюк A.C., Тулохонов Э.А., Гомбоев Е.Ш., Варфоломеев A.B.: Выполнение арифметических операций в АЛУ для чисел с фиксированной запятой. Часть I // Практическое пособие -ВСГТУ. - Улан-Удэ, 2006. - 77 с.

94. Савельев А.Я. Основы информатики. М.: Изд-во МГТУ им Н.Э. Баумана, 2001.-328 с.

95. Постников А.И., Вейсов Е.А. Теория автоматов и машинная арифметика. Учебное пособие. - М.: ИПЦ КГТУ, 2006.

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

97. Сергеев И.С. О глубине схем для многократного сложения и умножения чисел. — В сборнике: Материалы VI молодежной научной школы по

дискретной математике и ее приложениям (Москва, 16-21 апреля 2007 г.), Изд-во ИПМ РАН Москва, том 2, тезисы, С. 40-45.

98. Гашков С. Б., Гринчук М. И., Сергеев И. С. О построении схем сумматоров малой глубины // Дискрет, анализ и исслед. операций. Сер. 1. — 2007.— Т. 14, № 1. —С. 27-44.

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

100. Гашков С.Б., Сергеев И. С. Сложность вычислений в конечных полях // Фундамент, и прикл. матем., 17:4 (2012), С.95-131.

101. Карацуба Е. А. Быстрые алгоритмы и метод БВЕ, 2008.

102. Furer М. Faster integer multiplication // Proc. 39th ACM STOC 2007 Conf. — P. 57—66.

103. Поспелов А. Д. Сложность умножения в ассоциативных алгебрах Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. - Московский государственный университет им. М. В. Ломоносова, 2008. - 18 с.

104. Bernstein D. J. Multidigit Multiplication for Mathematicians. - 2004. - http:// cr.yp.to/papers.html#m3.

105. Von zur Gathen J., Gerhard J. Modern Computer Algebra.—Cambridge: Cambridge Univ. Press, 1999.

106. Gaudry P., Kruppa A., Zimmermann P. A GMP-based implementation of Schon-hage—Strassen's large integer multiplication algorithm // ISSAC'07. Waterloo, Ontario, Canada, 2007.

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

108. Ромм Я.Е., Иванова А.С. Известия ЮФУ. Технические науки. Тематический выпуск «Компьютерные и информационные технологии в науке, инженерии и управлении». - № 5 (130), 2012. - С. 144 - 151.

109. Кормен, Томас X., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. Сортировка за линейное время // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е издание. — М.: Вильяме, 2005. — С. 224-226.

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

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

112. Иванова А.С., Ромм Я.Е., Вертикальный метод арифметической обработки, сортировки и поиска. - V Международная студенческая электронная научная конференция «Студенческий научный форум» 15 февраля - 31 марта 2013.

ПЗ.Зубчук В. И. и др. Справочник по цифровой схемотехнике. — К.: Тэхника, 1990. — 448 с.

114. Ромм Я.Е., Белоконова С.С. Детерминированный поиск объектов различных типов на основе сортировки. Монография. - Изд-во ТГПИ, Таганрог, 2011. - 227 с.

115.Таненбаум Э. Архитектура компьютера, 5-е изд - СПб.:Питер, 2007. -844 с.-С. 739 —741.

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

УТВЕРЖДАЮ

Генеральный директор, шавйьгй^^нструктор

С

[тенберг

АКТ

об использовании результатов диссертационной работы Ивановой A.C.

в ОАО НКБ ВС

Настоящий акт составлен в том, что в ОАО НКБ ВС приняты к использованию следующие результаты диссертационной работы Ивановой A.C. «Расширение диапазона данных для вертикальной потоковой обработки применительно к сортировке со слиянием и параллельному поиску», представленной на соискание ученой степени кандидата технических наук.

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

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

76).

вычислителя, в которой умножение реализуется без отбрасывания значащих цифр младших разрядов с сохранением логарифмической оценки времени (Глава 2. - С. 81 -92, 101 - 104).

3. Параллельный алгоритм одновременного слияния и сортировки на основе вертикального поразрядно-параллельного сравнения, которые отличаются максимальным параллелизмом сравнений и -применимостью к поиску" как числовой, так и нечисловой информации (Глава 3. - С. 112-117).

4. Аналог дополнительного кода для потоковой вертикальной обработки, и-метод сравнения слов на основе вертикального алгебраического суммирования двоичных кодов с единичной оценкой времени бинарного сравнения, не зависящей от числа символов слов (Глава 3. - С. 134 - 140).

Указанные результаты используются в ОАО НКБ ВС для повышения эффективности обработки потоков видеоданных при разработке функций обработки изображений, реализуемых в ПЛИС.

Технический директор, к.т.н.

Бачило С. А.

Заведующий отделом, к.т.н.

Боровков И.К.

«УТВЕРЖДАЮ»

Ректор ФГБОУВПО «ТГГШ имени А П Чехова» .х5*** 'aV>>i(9Krop филологических наук, ^ профессор И В Голу^ева~<

I »л, " /I 2013 г

\"< .о-\ « ,, АКТ ;

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

Настоящий акт составлен в том, что при выполнении работ по гранту РФФИ «Компьютерные методы численной оптимизации на основе сортировки с приложением к анализу устойчивости, разностно-полиномиальному решению дифференциальных уравнений, распознаванию изображений и цифровой обработке сигналов» использованы следующие материалы диссертационной работы Ивановой A.C. «Расширение диапазона данных для вертикальной потоковой обработки применительно к сортировке со слиянием и параллельному поиску», представленной на соискание ученой степени кандидата технических наук.

1. Изложенный в главе 3 максимально параллельный алгоритм и программа одновременного слияния и сортировки по матрице сравнений (стр. 112-117).

2. Метод вертикального выполнения параллельной сортировки подсчетом и сортировки со слиянием по матрицам сравнений с применением знакоразрядной кодировки результатов сравнения и аналога дополнительного кода с целью максимально параллельного выполнения операции сравнения для ускорения информационного поиска как числовой, так и нечисловой информации (стр. 128-141).

Доктор технических наук, профессор Н.И. Витиска

УТВЕРЖДАЮ

É*»ЦgpвьIЙ проректор -

Г^Эщоувпо

РЦИим^иАЖ-Чехова» т^г^Ж^С А. Дядченко t'J/jM^ 2013 г.

работрЙвановой А.С в учебном процессе^й":аг!-'«'5<! кафедры информатики ФГБОУ ВПО «ТГПИ имени А.П. Чехова»

Настоящий акт составлен в том, что в учебном процессе кафедры информатики ФГБОУ ВПО «ТГПИ имени А.П. Чехова» используются следующие материалы диссертационной работы Ивановой А С. «Расширение диапазона данных для вертикальной потоковой обработки применительно к сортировке со слиянием и параллельному поиску», представленной на соискание ученой степени кандидата технических наук.

1. Описанный в первой главе диссертации метод и модификация метода поразрядно-параллельного вертикального суммирования групп натуральных двоичных чисея (стр. 56 - 64), а также программный эксперимент поразрядно-параллельного вертикального суммирования групп натуральных двоичных чисел ограничения роста диапазона двоичных слагаемых в процессе их вертикального суммирования (стр 65 - 69) используются в качестве учебного материала в лекционных курсах и при проведении лабораторных работ по дисциплинам «Программирование», «Информатика и программирование» и «Архитектура вычислительных систем», а также в качестве тематики курсовых и выпускных квалификационных работ факультета информатики и управления.

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

3. Описанные в третьей главе параллельный алгоритм одновременного слияния и сортировки на основе вертикального поразрядно-параллельного сравнения (стр. 112 -117) и аналог дополнительного кода (стр. 129 - 133) используются в курсах «Алгоритмы последовательных и параллельных сортировок», «Информатика и программирование», а также в курсах по выбору в качестве учебного материала и в качестве тематики курсовых и выпускных квалификационных работ факультета информатики и управления.

Декан факультета информатики и управления

доктор педагогических наук, доцент ____И.А. Стеценко

' ) /