Содержание к диссертации
Введение
Глава 1. Модель безошибочных вычислений какнаправление развития высокопроизводительных эвм 12
1.1. Классы задач, определяющие необходимость перехода к безошибочным вычислениям 12
1.2. Модель безошибочных вычислений на основе системы остаточных классов '. 14
1.3. Анализ перспективных направлений в области построения вычислительных структур и методов совершенствования их основных характеристик ..- 41
1.4. Цели и задачи диссертационного исследования 55
1.5. Выводы 56
Глава 2. Разработка базовых алгоритмов, обеспечивающих выполнение безошибочных вычислений 57
2.1. Алгоритмы целочисленной обработки в системе остаточных классов 57
2.1.1. Преобразование целых чисел из позиционной системы счисления в систему остаточных классов 57
2.1.2. Преобразование целых чисел из системы остаточных классов в позиционную систему счисления 61
2.1.3. Целочисленная арифметика в системе остаточных классов 64
2.2. Алгоритмы обработки чисел с фиксированной запятой в системе остаточных классов 72
2.2.1.Преобразование чисел с фиксированной запятой в одномодульную систему остаточных классов 72
2.2.2. Преобразование чисел одномодульной системы остаточных классов в числа с фиксированной запятой в позиционной системе счисления 74
2.2.3. Преобразование чисел с фиксированной запятой в многомодульную систему остаточных классов 77
2.2.4. Преобразование чисел многомодульной системы остаточных классов в числа с фиксированной запятой в позиционной системе счисления 80
2.2.5. Арифметика чисел с фиксированной запятой в многомодульной системе остаточных классов 82
2.3. Выводы 84
Глава 3. Структурная организация узлов процессора для обработки чисел по схеме безошибочных вычислений 85
3.1. Структурная организация устройств целочисленной арифметики в системе остаточных классов. 85
3.2. Принципы структурной организации основных узлов процессора, обеспечивающих безошибочную обработку чисел с фиксированной запятой 96
3.3. Выводы 110
Глава 4. Экспериментальная реализация и оценкаэффективности алгоритмов безошибочных вычислений и структурных схем устройств ... 111
4.1. Сравнительные оценки временных и аппаратурных затрат разработанных структурных схем с известными 111
4.2. Разработка программного модуля безошибочной обработки чисел в одномодульной системе остаточных классов 113
4.3. Разработка программного модуля безошибочной обработки чисел в многомодульной системе остаточных классов с использованием параллельной мультикомпьютерной сети "КУРС-2000 116
4.4. Применение разработанных алгоритмов для безошибочного решения системы линейных уравнений методом Гаусса 126
4.5. Оценки аппаратной и программной реализации алгоритмов безошибочных вычислений в системе остаточных классов...135
4.6. Опытное применение программы безошибочных вычислений для оптимизации суточных режимов каскада Сулакских ГЭС 136
4.7. Выводы 138
Заключение 139
Список литературы . 141
Приложения 154
- Анализ перспективных направлений в области построения вычислительных структур и методов совершенствования их основных характеристик
- Алгоритмы обработки чисел с фиксированной запятой в системе остаточных классов
- Принципы структурной организации основных узлов процессора, обеспечивающих безошибочную обработку чисел с фиксированной запятой
- Разработка программного модуля безошибочной обработки чисел в многомодульной системе остаточных классов с использованием параллельной мультикомпьютерной сети "КУРС-2000
Введение к работе
Одним из новых направлений развития средств вычислительной техники является разработка высокопроизводительных вычислительных устройств, сочетающих в себе современную элементную базу, развитое математическое обеспечение, достаточную емкость памяти и т.д [ 37 ].
Это обусловлено, в первую .очередь, необходимостью решения широкого спектра задач в реальном режиме времени, понятия которых приводятся в [ 53]. Такие задачи возникают, например, в аэродинамике [ 32 ], климатологии, машинной графике , ядерной физике , физике плазмы, энергетике [15].
В то же время следует отметить, что существующие высокопроизводительные ЭВМ удовлетворяют пользователей сегодня, но уже в ближайшие годы могут не соответствовать требуемым параметрам из-за постепенного роста сложности решаемых задач. [ 15, 70 ].
Однако, наряду со значительными успехами в истории архитектуры высокопроизводительных ЭВМ, традиционно функционирующих в двоичной системе счисления, еще недостаточно исследованы возможности, связанные с оптимизацией способов кодирования потоков числовых данных, с точки зрения повышения производительности [ 4 ].
Также следует отметить, что проблему повышения производительности ЭВМ необходимо решать в тесной взаимосвязи с задачей обеспечения заданной точности вычислений. Требование к высокой точности ЭВМ приобретает особую значимость при решении класса плохообусловленных задач , где не допускается накопление ошибок округления [16]. К таким задачам относятся, например, решение систем линейных уравнений с определителем близким к нулю, обращение матриц Гильберта и др. [44,83].
Значение ошибок округления можно уменьшить путем удлинения разрядной сетки сумматоров, что безусловно влечет за собой увеличение аппаратурных затрат и не приводит к полному устранению погрешности вычислений. Указанный факт требует поиска алгоритмических способов,
6 связанных с применением новых нетрадиционных методов и систем счисления для представления и обработки чисел [ 3 ].
В [21] показывается, что это можно достичь, прежде всего, средствами специального кодирования, наиболее широкий интерес из которых представляет собой система остаточных классах (СОК). Ей присущи высокая скорость вычислений и точность результатов [1,2, 3].
В то же время практическая применимость СОК сдерживается рядом проблем, связанных со сложностью сравнения чисел, введения знака, преобразования в позиционную систему счисления [ 3 ].
Многочисленные работы в области непозиционных систем" и математического аппарата теории чисел позволили выделить новое научное направление - теорию безошибочных вычислений [ 21, 101-104 ].
Существенный вклад в развитие теории внесли работы Р. Грегори, Е. Кришнамурти , О. Ватануки, А. Фромента, посвященные безошибочным вычислениям в системе остаточных классов и с использованием кодов Гензеля [21,66,105, 119,122,123,139, 140 ].
Известны также работы, посвященные исследованиям знакоразрядной системы счисления и диадических рациональных чисел, называемых также «псевдо-цифрами» для безошибочных вычислений с плавающей запятой [138].
В работах Д. Вуллинина, А.Нильсона, П. Корнерупа, Р.Хэкмана развиваются алгоритмы безошибочных вычислений над числами с плавающей запятой [112,123,118,119].
Преимуществами системы остаточных классов для безошибочных вычислений являются высокое быстродействие в многомодульной системе и отсутствие межразрядного переноса между цифрами.
Объединение достоинств системы остаточных классов для безошибочных вычислений, табличной арифметики и разрядно-параллельных принципов обработки информации получило свое развитие в работе [ 4 ].
В работе [ 4 ] описывался метод оперативного выхода результата за пределы диапазона системы остаточных классов и определения количественной меры возникшего переполнения, позволяющей восстановить истинную величину результата, рассматривались алгоритмы безошибочных вычислений с числами формата плавающей запятой на основе рангов.
Однако, данный метод обладает существенными ограничениями применимости, поскольку не позволяет определить факт псевдопереполнения в одномодульной и многомодульной системах остаточных классов для рациональных чисел, а безошибочные вычисления с использованием рангов приводят к стремительному росту разрядности операндов и возникновению ошибки переполнения.
Следует отметить, что основными проблемами безошибочных вычислений, сдерживающими их применение на практике, являются невысокое быстродействие, отсутствие метода выбора модулей системы остаточных классов, рост разрядности операндов [112].
Решение указанных проблем позволит использовать методы безошибочных вычислений во многих задачах науки и техники.
Актуальность работы подкрепляется такими практическими приложениями, как управление сложными техническими системами, цифровая обработка сигналов и др.
ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ заключается в исследовании модели безошибочных вычислений в системе остаточных классов и ее усовершенствованию в направлении создания высокопроизводительных ЭВМ.
ПРЕДМЕТОМ ИССЛЕДОВАНИЯ является модель безошибочных вычислений в системе остаточных классов и её алгоритмическая, аппаратная и программная реализация.
МЕТОДЫ ИССЛЕДОВАНИЯ опираются на положения теории чисел, алгебры логики, линейной алгебры, компьютерных систем
8 программирования для последовательных и параллельных ЭВМ, теорию алгоритмов и организации вычислительных процессов, теорию автоматов.
НАУЧНАЯ НОВИЗНА данного диссертационного исследования заключается в разработке модели безошибочных вычислений с рациональными числами в СОК, отличающейся от ранее известной введением индексов, антииндексов, расширением диапазона представления искомых результатов, а также получением верхней оценки модуля СОК, для частных задач.
На защиту выносятся следующие результаты:
Алгоритмические принципы прямых и обратных преобразований чисел из позиционной системы счисления в СОК, включающие преобразование чисел, представленных в формате с фиксированной запятой.
Ускоренный алгоритм деления в многомодульной СОК на основе таблиц индексов и антииндексов.
Способ получения верхней оценки модуля СОК, обеспечивающий гарантированное получение результата безошибочных вычислений в зависимости от общего числа арифметических операций.
Метод организации безошибочных вычислений с расширением диапазона представления искомых результатов в классе дробей Фарея порядка N с модулем р в СОК, определяемого исходя из следующего неравенства:
N < Р -\ , ВМЄСТО Л, 5 ІР-l .
Принципы структурной реализации разработанной модели безошибочных вычислений с использованием разрядно-параллельной схемы обработки числовых данных.
Результаты экспериментального исследования модели безошибочных вычислений в многомодульной СОК с использованием параллельной мультикомпьютерной сети «КУРС-2000», разработанной на кафедре ВМСиС МЭИ (ТУ).
Сравнительные оценки быстродействия аппаратной и программной реализации алгоритмов безошибочных вычислений в СОК.
ПРАКТИЧЕСКАЯ ЦЕННОСТЬ
Разработана программа безошибочного решения системы линейных уравнений в одномодульной системе остаточных классов (свидетельство гос. регистрации №2003610764 в реестре, программ для ЭВМ). Программа безошибочного решения системы линейных уравнений в одномодульной СОК нашла применение в ОАО «Дагэнерго» и включена в состав комплекса программ "Расчет суточных режимов Сулакского каскада ГЭС",, что подтверждено соответствующим актом о внедрении.
Экспериментальное исследование, проведенное в ОАО «Дагэнерго» показало, что использование разработанной программы- безошибочных вычислений позволило уточнить прогностическую оценку уровня воды в нижнем бьефе Чирюртовской ГЭС более чем на 2% по сравнению с используемой на практике программы «Расчет добегания расхода воды».
Результаты диссертационного исследования также используются в учебном процессе Дагестанского государственного технического университета по специальностям 22.01 и 22.04, имеется акт о внедрении.
АПРОБАЦИЯ РАБОТЫ. Основные результаты работы докладывались и обсуждались на :
Республиканской научно-технической конференции «Информационные и телекоммуникационные системы: интегрированные корпоративные сети» («Дагинформ-2001» г. Махачкала, 2001 г.)
Всероссийской научной конференции с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» ( г.Таганрог, 2002 г.)
Всероссийской научно-технической конференции «Новые информационные технологии» ( г. Москва, 2003 г.)
Международной научной конференции «Информационные технологии в науке, образовании, телекоммуникации, бизнесе» ( Украина, Крым, Ялта-Гурзуф, 2003 г.)
Международной научной конференции «Информационные средства и технологии» ( г. Москва, 2003 г.)
Международной' научной конференции. Parallel Computational Fluid Dynamics ( г. Москва, 2003 г.)
ПУБЛИКАЦИИ. По материалам диссертационной работы опубликовано 11 трудов, в том числе 5. статьи, 6 тезисов докладов. Получено . свидетельство о регистрации программы и поданы 3 заявки на предполагаемые изобретения в области вычислительной техники.
СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ . Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы и приложения. Она изложена на 140 сраницах основного машинописного текста, содержит 42 рисунка, 18 таблиц, включает библиографию из 143 наименований. Общий объем диссертации составляет 264 страниц.
В ПЕРВОЙ ГЛАВЕ проводится анализ класса задач, требующих для своей реализации ЭВМ с повышенной точностью вычислений. Тем самым показывается целесообразность использования для их решения методов безошибочных вычислений.
Описываются основные операции и особенности представления чисел в системе остаточных классов. Предлагаются, способ получения верхней оценки модуля системы остаточных классов, гарантирующий получение искомого результата безошибочных вычислений и метод организации безошибочных вычислений с расширением диапазона представления искомых результатов в классе дробей Фарея. Приводятся теоретические основы алгоритмов деления в одномодульной и многомодульной СОК.
Рассматриваются способы повышения производительности
вычислительных устройств, принципы построения таких устройств с целью их применения при разработке структурных схем быстродействующих устройств безошибочных вычислений в системе остаточных классов. Приводятся основные цели и задачи диссертационного исследования, обосновывается необходимость аппаратной реализации алгоритмов,
обеспечивающих выполнение безошибочных вычислений в системе остаточных классов.
ВТОРАЯ ГЛАВА посвящена разработке быстродействующих алгоритмов, безошибочных вычислений. К ним относятся следующие алгоритмы: прямых и обратных преобразований целых чисел из позиционной системы счисления в систему остаточных классов, нахождения обратного' элемента в многомодульной СОК, реализации, арифметических операций с рациональными числами в одномодульной и многомодульной системах остаточных классов на основе дробей Фарея, преобразования чисел с фиксированной запятой в дроби Фарея.
В ТРЕТЬЕЙ ГЛАВЕ на основе разработанных алгоритмов, предлагается структурная организация основных узлов процессора, обеспечивающих безошибочную обработку чисел, с фиксированной запятой. Приводятся оценки временных и аппаратурных затрат разработанных структурных схем.
В ЧЕТВЕРТОЙ ГЛАВЕ проводится экспериментальное исследование модели безошибочных вычислений на основе параллельной мультикомпьютерной Сети «КУРС-2000», разработанной на кафедре ВМСиС МЭИ (ТУ). Приводятся оценки быстродействия аппаратной и программной реализации алгоритмов безошибочных вычислений в системе остаточных классов. Описываются результаты применения разработанной программы безошибочных вычислений в ОАО «Дагэнерго».
Анализ перспективных направлений в области построения вычислительных структур и методов совершенствования их основных характеристик
В ответ на постоянно растущие требования к ЭВМ, способным быстрее и надежнее решать все более сложные задачи, разработка их успешно осуществляется в нескольких различных, но взаимосвязанных направлениях [66,86, 87,88] - это повышение быстродействия элементов, усовершенствование программного обеспечения, развитие логической структуры, архитектуры машин [19,20]. .
Ограничением первого направления является то, что заранее известен теоретический предел увеличения производительности вычислений, обусловленный конечной скоростью передачи информации между элементами [31].
Усовершенствование программного обеспечения, с одной стороны, направлено на ускорение подготовки задач (автоматизация программирования, применение проблемно-ориентированных языков) и, с другой стороны, должно способствовать наиболее полному использованию возможностей, открываемых быстродействующей элементной базой (ЭБ) и новыми архитектурами ЭВМ (операционные системы, языки параллельного программирования) [35, 87].
Наиболее перспективным направлением увеличения производительности ЭВМ является дальнейшее развитие их архитектуры, связанное, главным образом, с использованием различных форм параллелизма в их работе [7,9,20,71-73,117]. В работе [71] рассмотрен ряд способов повышения производительности вычислительных устройств (ВУ) с точки зрения их архитектуры и указывается, что в реальных вычислительных системах (ВС), как правило, используется не один какой-либо способ увеличения производительности, а их различные комбинации.
Среди базовых способов повышения быстродействия ВУ наиболее важными можно считать:
- освобождение устройств обработки данных от выполнения вспомогательных операций;
- повышение "квалификации" или "интеллектуальности" процессоров путем аппаратурной реализации многих функций математического обеспечения;
- потоковое управление вычислительным процессом; Практически не исследованными остались вопросы разработки разрядно-параллельных алгоритмов и структур в непозиционных системах счисления (НСС).
Проанализируем существующие вычислительные средства, ориентированные на обработку массивов данных по PC.
Массовую обработку числовых или векторных данных по PC называют еще в [77]. последовательным преобразованием состояний запоминающих элементов решающего поля ассоциативных параллельных процессоров (АПП). В нем функции хранения аргументов и их обработка совмещены в пространстве и во времени, а в программе работы предусмотрены только векторные операции [48,79]. К решающему полю подключена память, в которой хранится полная таблица сложения двух одноразрядных двоичных аргументов. Время вычисления значения функции не зависит от размера векторов-аргументов. Выполнение операций, например, сложения, начинается с.младших разрядов (остальные маскированы) и состоит из m циклов, где m - разрядность аргументов. Каждый цикл состоит из 8-ми (по числу строк сложения таблицы) микроопераций поиска соответствующей в решающем поле АПП двоичных цифр результата и переноса и 8-ми микроопераций записи их на место одного из операндов. В итоге время сложения оценивается величиной t ел. = 2п+2 -т, п - арность функции.
Рассмотренная структура АПП, реализующая таблично-алгоритмический метод обработки числовых данных, обладает следующими недостатками:
1. Функциональные возможности ограничены векторными операциями, хотя в большинстве реальных программ гораздо чаще встречаются участки, требующие вычислений над скалярными величинами;
2. Экспоненциальная зависимость размеров полной таблицы сложения от арности арифметической функции и времени вычисления ее значения. Другой метод обработки числовых данных связан с отходом от принципа пространственно-временного совмещения функций обработки, и хранения векторов-аргументов посредством применения идеи "трубопровода данных", к одному концу которого подключено устройство параллельной их обработки. Трубопровод реализуется в динамической памяти с очередным доступом типа "первый на входе - первый на выходе". Функция параллельной обработки пары векторов реализуется аппаратно. Схема вычисления та же, по таблице значений функции одноразрядных двоичных аргументов. Такие АПП в [132] называют динамическими.
Недостаток, связанный с ограниченностью функциональных возможностей, устраняют посредством включения в состав АПП арифметических устройств классического типа. Структуры АПП, сочетающие принципы векторной (вертикальной) и скалярной (горизонтальной) обработки данных, называют в [132] ортогональными. Однако в приведенных типах АПП экспоненциальная зависимость времени вычислений от арности функций сохраняется. Следует отметить также, что в них не рассматривались вопросы групповой обработки скалярных величин.
Алгоритмы обработки чисел с фиксированной запятой в системе остаточных классов
Современные ВМ оперируют лишь с конечными дробями и используют два способа представления чисел: с фиксированной и с плавающей запятой. В данной работе рассматриваются методы безошибочных вычислений с целыми и рациональными числами. Не всегда результат выполнения арифметической операции над конечными дробями является конечной дробью, например, при делении [16,93,94,99]. Появление ошибок округления неизбежно в любой ВМ. Величина этих ошибок зависит от конкретной реализации операции округления и от принятой формы представления чисел.
За счет различных технических решений можно в какой-то мере влиять на ошибки округления. Однако есть принципиальные ограничения, связанные с их величиной [16]. Эти ограничения нельзя преодолеть никакими техническими средствами, если оставаться в рамках ПСС.
Рассмотрим задачу преобразования числа с фиксированной запятой в СОК. Пусть на изображение каждой дроби на ВМ отводится т разрядов , а на изображение разрядов, стоящих слева от запятой, отводится г разрядов, где г О. Такой способ представления чисел называется представлением с фиксированной запятой. С помощью этого способа можно точно запомнить любую из конечных дробей, имеющих не более г ненулевых разрядов слева от запятой и не более т - г ненулевых разрядов справа от запятой . Все эти дроби лежат в диапазоне [16]:- рг х рг, где
В отображении конечного результата безошибочных вычислений из СОК в ПСС возможны два варианта: а) ответ представляет собой число с фиксированной запятой; б) ответ является несократимой дробью Фарея. Алгоритм преобразования, в первую. очередь вычисляет дробь Фарея, которая определяет число с фиксированной запятой с любой степенью точности. Очевидно, что из представления б) легко получается а).
Известны алгоритмы перебора, которые служат для отображения конечного результата [4,37]. В этих алгоритмах число операций линейно зависит от значения модуля или исходного числа СОК. Такие алгоритмы могут применяться для малых, значений модуля. Одним из простых, имеющим логарифмическую сложность является расширенный алгоритм Евклида со следующей начальной матрицей [ 21 ]: т О" к .1 где m - модуль СОК, к - число СОК. В этом алгоритме генерируется последовательность чисел a,, b, , где " (2.2.2.1) bi = bi-i - It bi-\ Если а, N и Ь, N , то отношение а,/ 6,является дробью Фарея [21]. На рис 2.2.2.1. изображены две зависимости: первая ( сверху) - число итераций расширенного алгоритма Евклида от исходного числа и вторая -число итераций расширенного алгоритма Евклида, необходимых для нахождения дроби Фарея, от исходного числа. Среднее . число итераций г расширенного алгоритма Евклида определяется следующим образом: г « 16.017 - lri(P -1) + 7.14 , " . где Р - модуль СОК. Откуда следует, . что среднее число итераций алгоритма v для определения дроби Фарея определяется следующим неравенством: 0 v т
Принципы структурной организации основных узлов процессора, обеспечивающих безошибочную обработку чисел с фиксированной запятой
Принципы структурной организации основных узлов процессора, обеспечивающих безошибочную обработку чисел с фиксированной запятой. . Структурная схема разрядно-параллельного устройства преобразования чисел с фиксированной запятой в одномодульную СОК. На основе алгоритма 2.2.1 разработана структурная схема разрядно-параллельного устройства преобразования чисел с фиксированной запятой в одномодульную СОК, представленная нарис 3.2.1.
Устройство состоит из следующих блоков: Per 1 - регистр, служащий для хранения исходного числа; Per 2 - регистр, служащий для хранения количества цифр в исходном числе, расположенных справа от запятой; Per 3 -регистр, служащий для хранения результата преобразования; УМ - разрядно-параллельный умножитель; УУ - устройство управления; ПСС= СОК - преобразователь чисел из позиционной системы счисления в систему остаточных классов; ПЗУ 1 - постоянное запоминающее устройство, служащее для хранения обратных чисел: 10, 102,..., 10т ( т - количество разрядов исходного числа). Принцип работы устройства заключается в следующем. В регистры Per 1, Per 2 записываются исходное число а умноженное на корректирующий множитель 10т"г и количество цифр дробной части числа А соответственно.
По приходу первого импульса с устройства управления на адресные входы ПЗУ 1 поступает код с выходов регистра Per 1. По второму импульсу с устройства управления содержимое регистра Per 2 и код с выходов ПЗУ 1 поступают на соответствующие входы разрядно-параллельного умножителя УМ. По истечению трех тактов на выходе устройства ПСС= СОК формируется результат преобразования.
Временные затраты устройства с учетом преобразования чисел из ПСС в СОК составляют 6 тактов..
Объем хранимой информации постоянного запоминающего устройства равен - г log 2 max( р}) \ j = 1,:.., п условных бит. Аппаратурные затраты на реализацию рассмотренной структурной схемы можно определить как: . V = , + ... + 5, где Vi - затраты памяти постоянного запоминающего устройства ; V2 -затраты аппаратуры на реализацию разрядно-параллельного умножителя; Уз - затраты аппаратуры на реализацию преобразователя из позиционной системы счисления в систему остаточных классов ; V4 -затраты регистровой памяти; У5 - затраты аппаратуры на реализацию устройства управления. Структурная схема устройства преобразования числа одномодульной СОК в число с фиксированной запятой в ПСС. Устройство состоит из следующих блоков: Per 1 - регистр, служащие для хранения результатов преобразования, представленного в формате с фиксированной запятой; Per 2 - регистр, служащий для хранения количества цифр дробной части результата преобразования; Per N - регистр порядка дроби Фарея; УУ - устройство управления; СМР 1,2 - компараторы; Блоки aj, bj - для вычисления арифметических выражений вида (2.2.2.1). Принцип работы устройства заключается в следующем. В блоки a/, bj записываются исходные данные: Р - модуль СОК, А -число, представленное в СОК по модулю Р и числа «О», «1». По приходу первого импульса с УУ код с выходов блоков a;, bj поступает на соответствующие входы компараторов СМР 1 и СМР 2. Одновременно на входы компараторов СМР 1 и СМР 2 поступают значения порядка дроби Фарея N. На разрешающие входы регистров Per 1, Per 2 поступают биты сравнения "меньше" компараторов СМР 1 и СМР 2 соответственно. Если значения a;, bj меньше порядка дроби Фарея, то работа устройства прекращается, и значения aj, bj поступают на соответствующие входы регистров Perl и Рег2. В противном случае, по приходу импульса с устройства управления блоками alt bt вычисляются новые значения ai+ь bj+i . Далее работа устройства продолжается до тех пор, пока не будет выполнено условие: as N и bj N. Временные затраты преобразователя в условных тактах определяются формулой: где п - максимальное количество итераций, необходимых для нахождения дроби Фарея. Аппаратурные затраты на реализацию рассмотренной структурной схемы можно определить как: V = Vt + ..." + V5, где Vi - затраты аппаратуры на реализацию блоков а;и bj Уг- затраты аппаратуры на реализацию устройства управления; V3- затраты аппаратуры на реализацию двух компараторов и лог.элем. И; Уд- затраты регистровой памяти.
Разработка программного модуля безошибочной обработки чисел в многомодульной системе остаточных классов с использованием параллельной мультикомпьютерной сети "КУРС-2000
После завершения выполнения этого участка в программе проводятся вычисления традиционным способом.
Наибольшие временные затраты .библиотеки связаны с процедурой деления в СОК. Для повышения скорости в алгоритмах используются таблицы индексов и антииндексов. В программном модуле для этого выполняются следующие операции: - выделение необходимого объема памяти ОЗУ для хранения таблиц; - обращение к таблицам при выполнении операции деления; - обращение к таблицам и при операции умножения, если произведение сомножителей меньше модуля СОК. мультикомпьютерной сети "КУРС-2000". Одним из существенных факторов , влияющих на быстродействие безошибочных вычислений является разрядность слагаемых. Обработка чисел в одномодульной СОК неизбежно приводит к увеличению разрядности результатов, что усложняет их представление и обработку в ВМ. В многомодульной СОК благодаря параллельным вычислениям по нескольким основаниям существенно снижаются порядки слагаемых. . Для.. исследования безошибочных методов в многомодульной СОК использовалась параллельная мультикомпьютерная сеть «КУРС-2000», разработанная на кафедре ВМСиС МЭИ (ТУ). Параллельная сеть КУРС-2000 представляет собой параллельную мультикомпьютерную сеть (ПМК-сеть) с программируемой, динамически изменяемой структурой обменов. Программное обеспечение сети КУРС позволяет организовать выполнение параллельной программы на множестве персональных компьютеров, соединенных локальной сетью, и тем самым объединить их вычислительные ресурсы для решения общей задачи. Персональные компьютеры, включенные в сеть КУРС, играют роль вычислителей, выполняя отдельные части общей параллельной программы и ведя обмены между собой в соответствии с потактным описанием программы. Взаимодействие вычислителей ведется в модели передачи сообщений. В текущей реализации вычисления могут быть организованы в рамках одного сегмента локальной сети на персональных компьютерах, работающих под управлением ОС Windows.
КУРС-2000 работает поверх локальной сети, но при этом, в отличие от локальной сети, обеспечивает не только информационное взаимодействие пользователей (режим сети), но и глубокую синхронизацию выделенных персональных компьютеров на решение задач повышенной сложности (режим параллельной обработки данных). Программируемый жезл, используемый в системе КУРС, превращает сеть в детерминированную при том, что используемая локальная сеть является недетерминированной (со случайным доступом к каналу). Это обстоятельство является очень важным при реализации ряда параллельных алгоритмов с интенсивными обменами между вычислителями. На каждом из вычислителей выполняется прикладная программа, использующая вызовы специального программного обеспечения системы КУРС и посредством этих вызовов обменивающаяся данными по сети с другими вычислителями: Программы всех вычислителей согласованны и образуют единую параллельную программу. Специальное ПО системы КУРС реализует: инициализацию параллельной сети, в том числе автоматическое нахождение персональных компьютеров ее составляющих, обмен данными между вычислителями во время работы программы, обнаружение ошибок и сигнализацию о них, контроль за ходом выполнения, а также мониторинг работы.параллельной программы.
Основным архитектурным элементом сети КУРС является использование жезла. "Программируемый жезл" - это информационная структура, способная циркулировать в параллельной сети наравне с данными. Наличие жезла у некоторого вычислителя дает ему право (но не обязывает) на передачу информации.
Основные особенности реализации сети КУРС-2000 следующие:
Для организации сетевого взаимодействия используется интерфейс сокетов. При этом для обмена данными между вычислителями используется потоковый протокол TCP, а в ходе инициализации, для мониторинга и при широкоэещательных передачах протокол UDP, допускающий широковещательную передачу данных внутри одного сегмента локальной сети. Именно поэтому нахождение всех вычислителей в одном сегменте локальной сети является обязательным условием.
Реализована автоматическая инициализация сети, для которой достаточно запустить все вычислители и нет необходимости настраивать вручную какие бы то ни было адреса других вычислителей. Вычислители самостоятельно находят друг друга путем передачи широковещательных сообщений.
С момента старта инициализации и до завершения работы параллельной программы на каждом задействованном компьютере открывается управляющее окно ПМК-сети. Оно позволяет настраивать некоторые параметры работы ПМК-сети, контролировать ход выполнения программы вычислителя и вручную прерывать работу всей сети в случае необходимости. Основными характеристиками сети являются латентность (задержка от момента передачи данных, одним вычислителем до момента получения их другим вычислителем) и скорость передачи данных. Для сети КУРС-2000 они могут отличаться в каждой конкретной используемой . локальной сети, но порядок этих величин таков: - латентность - единицы мс, типичное значение порядка 2 мс; - скорость передачи - чуть меньше, теоретической скорость передачи используемой локальной сети, например для сети 10 Mbit Ethernet -порядка 1 Мбайта/сек. . В библиотеке используются следующие функции сети, представленные в .таблице 4.3.1. Функции возвращают ненулевое значение в случае успешного . выполнения и нулевое в случае ошибки. Рассмотрим используемые функции ПМК-сети. int PmkInitNet(int CID,int CompN.int TID=0,bool Token=false, int Flags=0); . int PmkInitNetAuto(int pGetCID,int pGetCompN,int TID=0,int Flags=0);
