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

Аннотация

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