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

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

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

В связи с этим в нашей стране и за рубежом ведутся интенсивные разработки по созданию новых перспективных средств ВТ, практическая реализация которых намечена на 2010;2015 годы [1−3].

Одним из главных направлений развития систем ВТ является разработка высокопроизводительных ЭВМ, сочетающих в комплексе современную элементную базу, развитое математическое обеспечение, достаточно большую емкость оперативной и внешней памяти с производительностью в сотни миллионов операций/с, что отмечается в многочисленных работах, например [4−8].

Это обусловлено тем, что среди различных научно-технических и планово-экономических задач, решаемых на ЭВМ, с каждым годом все больший удельный вес приобретают вычислительные задачи большого объема, многие из которых при этом должны решаться в режиме реального времени [8]. К таким задачам можно отнести аэродинамику, метеорологию, машинную графику, ядерную физику и физику плазмы, обработку изображений, задачи искусственного интеллекта, числового моделирования непрерывных полей, а также задачи финансового моделирования экономики [4, 9].

Характерными особенностями указанного класса задач является большой объем обрабатываемых данных, достигающий порядка 1011 бит информации. Такие задачи требуют выполнения огромного количества арифметических операций (АО), порядка 1014. Даже при использовании самых мощных на сегодняшний день ЭВМ решение задач подобного класса может затягиваться на многие дни, тогда как исследователю часто необходимо иметь в несравненно более короткие сроки. Для других задач, например, связанных с расчетом прогнозов погоды, решение должно быть получено не более чем через час, что принуждает разработчиков искать более эффективные пути построения вычислительных устройств (ВУ) высокой производительности, на несколько порядков выше по сравнению с производительностью существующих ЭВМ. Безусловно, в ВС, ориентированных на решение вычислительных задач большого объема, предъявляются самые высокие требования к производительности, объему оперативной и внешней памяти, точности вычислений, надежности и т. д., указанные в [9−30].

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

1 «Ч мом 300 миллионов слов, а сама ЭВМ должна обладать быстродействием не менее 10 ме-гафлоп/с.

Наиболее перспективным направлением создания высокопроизводительных ЭВМ считается разработка параллельных вычислителей. Параллельные ЭВМ широко применяются в различных сферах науки и техники, но чаще всего их используют для численного моделирования вычислительных задач большого объема. В таком применении параллельные вычислители способствуют получению новых знаний, позволяя пользователям путем моделирования справляться со сложнейшими проблемами, которые не могут быть решены на вычислительных устройствах (ВУ) с традиционной архитектуройизучить явления, труднодоступные для экспериментального исследованияподтверждать правильность тех или иных теоретических выводов [31−42]. Именно эти обстоятельства определяют значительный интерес к теории построения параллельных ЭВМ.

Однако, наряду со значительными успехами, достигнутыми в теории архитектуры параллельных вычислителей, традиционно функционирующих в двоичной системе счисления (СС), еще недостаточно исследованы возможности, связанные с оптимизацией способов кодирования потоков числовых данных (ПЧД). Это служит дополнительным резервом роста производительности ЭВМ. Так, представляется целесообразным использование в параллельных ЭВМ не только двоичной системы счисления, главный недостаток которой наличие «длинных» межразрядных переносов, влияющих на быстродействие выполнения арифметических операций, а некоторого комплекса систем счисления, включающего как позиционные, так и непозиционные системы счисления. Это способствует значительному сокращению времени реализации арифметических операций над ПЧД за счет их выполнения в наиболее рациональной системе счисления.

Проблема использования СОК в процессе преобразования данных является не новой. Впервые она была поставлена в пятидесятые годы прошлого века, и были предприняты попытки по практической реализации данной идеи в рамках пробкта «Алмаз», при создании ЭВМ Т-340А и К-340А и суперЭВМ 5Э53. Однако, после двадцати лет исследований все работы были практически приостановлены, по-видимому, ввиду недостаточно развитой элементной базы того времени. В настоящее время существующая элементная база позволяет не только реализовать проекты того времени, связанные с СОК, но и значительно усовершенствовать многие идеив частности, применительно к проблемам безопасности и безошибочности вычислений. Поэтому теоретические исследования и практические работы в данной области в последние годы активизировались.

Большой вклад в развитие теоретических и практических вопросов, связанных с СОК, внесли отечественные исследователи и ученые Акушский И. Я., Юдицкий Д. И., Коляда А. А, Исмаилов Ш.-М.А., Червяков Н. И, и др, среди зарубежных можно выделить работы М.А. Soderstand, D.D.Miller, G.A. Jullien, M. A Jenkins, В J. Leon и др.

С другой стороны, представляется целесообразной разработка арифметических узлов ЭВМ, ориентированных на реализацию «-арной операции суммирования, часто встречающейся при выполнении широкого спектра арифметических выражений. Степень значимости указанной операции отмечена в работах, например, И. В. Прангишвили, Я. И. Фета, Б. Н. Малиновского, В. Муртафа [43−48]. Отсутствие в настоящее время таких узлов приводит к необходимости организации попарной обработки ПЧД, что существенно снижает производительность параллельных ЭВМ.

Рассмотренные подходы могут быть использованы совместно для построения высокопроизводительных ЭВМ, функционирующих в комплексе систем счисления и содержащих арифметические узлы, выполняющие операцию параллельного суммирования чисел, с использованием разрядно-параллельных способов обработки ПЧД. Очевидно, что такая организация структуры ЭВМ требует преобразования числовой информации из одной системы счисления в другую, а следовательно, необходима разработка быстродействующих алгоритмов его выполнения [49−54].

Также следует отметить, что проблему повышения производительности необходимо решать в тесной взаимосвязи с задачей обеспечения точности вычислений [31,55−62]. Требования к высокой точности ВУ приобретает особую значимость при решении класса так называемых плохообусловленных задач и алгоритмов, где не допускается накопление ошибок округления [14, 63]. Значение этих ошибок уменьшается аппаратно путем удлинения разрядной сетки сумматоров, что влечет за собой увеличение аппаратурных затрат и не приводит к полному устранению указанных ошибок. Это требует поиска алгоритмических способов, связанных с применением новых нетрадиционных методов и систем счисления для представления и обработки чисел.

Этого можно достигнуть прежде всего средствами специального кодирования, наиболее широкий интерес из которых представляет система счисления в остаточных классах (ССОК). Ей присущи высокие скорость вычислений и точность их результатов, обусловленные, соответственно, отсутствием межразрядного переноса между цифрами числа и отсутствием операции округления результатов [6, 56, 64, 65].

Многие алгоритмы методов вычислений в непозиционных СС разработаны в рамках теории чисел [10, 66−73]. Однако, нерешенной осталась проблема оперативного фиксирования выхода результата за пределы диапазона применяемой ССОК и определения количественной меры возникшего переполнения, позволяющей его разрешения и восстановление истинной величины результата и ведущей к существенному снижению аппаратно-временных затрат, поскольку до сих пор традиционным путем избегания переполнения являлось увеличение числа или величин модулей ССОК с непосредственным увеличением аппаратурных и временных затрат.

Повышение быстродействия вычислительных устройств наряду с использованием прогрессивных интегральных технологий и скоростных табличных методов вычислений идет в направлении временного и пространственного распараллеливания алгоритмов и структур этих устройств, связанного с увеличением аппаратурных затрат [65, 74−82].

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

До сих пор разрядно-параллельные вычисления и вычисления в ССОК развивались независимо друг от друга. Представляет практический, в определенной степени научный интерес, задача объединить достоинства обоих направлений развития структур ЭВМ. Этим объясняется необходимость исследования принципов построения разрядно-параллельных процессоров безошибочной обработки вещественных чисел непозиционных СС, обладающих высокой производительностью прежде всего за счет автоматической коррекции результатов вычислений, а также достаточно высоким уровнем надежности и защищенности данных [85 — 90].

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

Традиционная, координатная форма представления комплексных чисел посредством выделения в них действительной и мнимой частей, использовавшаяся, например, в цифровой фильтрации с помощью комплекснозначного преобразования Мерсена, не дает ожидаемого повышения эффективности комплексных вычислений. Прорыв в области двоичных комплекснозначных параллельных вычислений в первые был осуществлен в [91, 92], в которых в практику указанных вычислений была введена бескоординатная форма представления комплексных чисел в системе с основанием (-1+1) [93, 94], а также благодаря изящной гауссовой идее изоморфизма между комплексными вычетами по комплексному модулю и его вещественными вычетами. Несмотря на то, что основы разряднопараллельных вычислений и структур рассмотрены в работах, но практически в них не рассматривались вопросы обработки комплексных чисел, представленных в системе с основанием (-1+1) и в СОК с комплексными основаниями. Не рассматривались также вопросы структурной организации соответствующих арифметических процессоров.

Следует отметить также, что до настоящего времени в литературе не исследованы вопросы организации разрядно-параллельных арифметических устройств (АУ) с точки зрения выбора оптимального комплекса систем счисления, разработки и исследования алгоритмов и структур параллельного суммирования и других арифметических операций на их основе, прямых и обратных преобразований ПЧД, с использованием базового ядра, а также принципы комплексирования процессорных элементов (ПЭ), являющихся основой построения высокопроизводительных ВУ [95−102].

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

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

Объектом исследованияявляются устройства преобразования данных в комплексе систем счисления.

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

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

Поставленная цель достигается решением следующих задач:

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

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

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

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

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

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

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

К основным результатам, представляющим новизну исследования, можно отнести следующие:

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы и вопросы их практического использования докладывались и обсуждались: на II международной научно-практической конференции «Молодежь и наука: реальность и будущее» (Невинномысск, 2009), на III Всероссийской конференции по актуальным проблемам внедрения и развития сектора 1 Т — технологий «Современные информационные технологии в проектировании, управлении и экономике» (Махачкала, 2008,), на IV Всероссийской конференции по актуальным проблемам внедрения и развития сектора 1Ттехнологий (Махачкала, 2009), на V региональной научно-технической конференции (Махачкала, ДНЦ РАН, 2009) .

Публикации. По результатам диссертационной работы опубликовано 12 работ, в том числе 9 статей, из них две статьи в научных изданиях, рекомендованных. Без соавторов опубликовано 4 работы.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников и четырех приложений. Работа изложена на 117 страницах, содержит 34 рисунка, 5 таблиц, список литературы, состоящий из 136 наименований и 4 приложений.

Выводы по главе 4

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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