О РАСПАРАЛЛЕЛИВАНИИ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ НА ПМК-СЕТИ «КУРС-2000»

 

 

Дзегелёнок И.И., Оцоков Ш.А.  

 

 

( г. Москва, Московский энергетический институт (ТУ), Россия )

 

 

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

Исследование непозиционных систем счисления ( системы остаточных классов, конечно-разрядных р-адических кодов,  знакоразрядной системы ) позволили выделить новое научное направление – безошибочные вычисления.

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

Безошибочные вычисления в системе остаточных классов основаны на представлении чисел в виде остатков их деления на заданные простые числа - модули системы и выполнении целочисленных арифметических операций над ними. Окончательный результат вычислений в системе остаточных классов преобразуется в позиционную систему счисления (ПСС)  и представляется в виде пары чисел - числителя и знаменателя несократимой дроби Фарея [1].

Преимуществом безошибочных вычислений в системе остаточных классов является возможность параллельной обработки чисел по нескольким модулям. Это обеспечивает  значительное увеличение быстродействия по сравнению с последовательной обработкой [ 3 ].

Эффективность многомодульных безошибочных вычислений  исследовалась при решении систем линейных уравнений с использованием созданного на кафедре ВМСиС МЭИ (ТУ) макета  «КУРС-2000». 

«КУРС-2000» представляет собой параллельную мультикомпьютерную сеть (ПМК-сеть) с программируемой, динамически изменяемой структурой обменов. Программное обеспечение сети «КУРС-2000» позволяет организовать выполнение параллельной программы на множестве персональных компьютеров - вычислителей,  соединенных локальной сетью и таким образом, объединить их вычислительные ресурсы для решения общей задачи.

Основным архитектурным элементом сети «КУРС-2000» является использование жезла. "Программируемый жезл" – это информационная структура, способная циркулировать в параллельной сети наравне с данными. Наличие жезла у некоторого вычислителя дает ему право (но не обязывает) на передачу информации.

Организация безошибочных вычислений в многомодульной системе  остаточных классов (СОК) на множестве персональных компьютерах с использованием ПМК-сети «КУРС-2000»  приведена на рис 1.

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

Измерение времени безошибочного решения систем линейных алгебраических уравнений (СЛАУ)  методом Гаусса с использованием разработанной программы проводилось при помощи ПМК-сети «КУРС 2000» на компьютерах Pentium III – 600МГц, ОС Windows2000 в сети FastEthernet.  Временные затраты решения СЛАУ различных порядков в одномодульной, двухмодульной,  четырехмодульной и восьмимодульной СОК представлены в табл. 1.

В ходе эксперимента изменялось число уравнений и коэффициенты. Неизвестные генерировались случайным образом в диапазоне от 1 до 10. На основе этого вычислялась правая часть системы, причем в одномодульной и многомодульной СОК (с числом модулей 2, 4, 8). Порядки модулей составляли 10¹¹ для одномодульной СОК и 10⁶, 10³ ,10² соотвественно для многомодульной СОК.

 

Таблица 1.

Время решения СЛАУ в различных системах счисления.

 

Из таблицы 1 следует, что наибольшим быстродействием обладала программа, находившее безошибочное решение в  восьмимодульной СОК и разница между временем решения СЛАУ в одномодульной СОК и двухмодульной СОК намного больше чем  между 4-х и 8-ми модульной СОК. Это объясняется тем, что в одномодульной СОК над числами в силу их большой разрядности  арифметические операции выполнялись программными процедурами языка программирования, в отличие от многомодульной, в которой использовались стандартные арифметические операции над числами меньшей разрядности.

Эффект реализации модели безошибочных вычислений на ПК Pentium в ОС Windows 2000 уже виден для одномодульной СОК. Так, традиционная схема вычислений с плавающей запятой не позволяет найти точное решение, если оно представляет десятичную дробь с периодом, превосходящим 9 разрядов.

Если же перейти к использованию целочисленной арифметики по схеме приведения правильных дробей, то и здесь нет гарантии получения точного решения, если его числитель и знаменатель превосходит значение 215×10⁷ в стандартном формате LongInt. Еще больший эффект достигается при реализации многомодульной СОК на базе ПМК-сети, поскольку интенсивность информационных обменов между ПК, каждый из которых «отвечает» за свой модуль, невелика.  Прежде всего расширяется диапазон представления точных решений и, более того, существенно сокращается время вычислений с увеличением мерности решаемых задач.

Рис. 1.  Организация безошибочных вычислений в многомодульной системе остаточных классов на основе ПМК-сети « КУРС2000 ».

 

ЛИТЕРАТУРА.

1.     Грегори Р, Кришнамурти Е. Безошибочные вычисления. Методы и приложения.М.:Мир,1988. –207 с.

2.     Воеводин В.В. Вычислительные основы линейной алгебры. -  М.: «Наука», 1977. -303 с.

3.      Акушский Н.Я, Юдицкий Д.И. Машинная арифметика в остаточных классах,  М. «Сов. радио », 1968. – 439 с.