Методи обчислення сплайнів орієнтовані на реалізацію засобами однорідних обчислювальних середовищ

Abstract

Dissertation is devoted to elaboration of methods for parallel calculation of functions, approximated by polynomial and rational uniform chebeshov’s splines oriented on implementation by means of homogeneous computational medium. The properties of approximation are investigated, and the computational algorithms for presentation of a single function, and also a number of functions with common set of nodes, by piecewise approximation (splines) with division of segment on unequal parts with identical error on each of them are designed. The decreasing of memory capacity for storage of approximation parameters is achieved by equalization of values of maximum error on each of subinterval. The algorithm of automated adjusting of homogeneous computational medium for parallel calculation of arithmetic and conditional expressions is carried out. The algorithm for synthesis of matrix spline-calculators on the basis of homogeneous computational medium for fast evaluation of functions, approximated by splines, with usage of parallel calculations is carried out. Диссертационная работа посвящена вопросам разработки методов параллельного вычисления функций, приближенных полиномиальными и рациональными равномерными чебышевскими сплайнами, ориентированных на реализацию средствами однородных вычислительных сред (ОВС). Установлены свойства приближения и разработаны вычислительные алгоритмы для представления одной функции, а также набора функций, сплайнами с автоматическим выбором границ участков по критерию выравнивания погрешностей на каждом из них, что уменьшает общую погрешность при фиксированном количестве параметров приближения или уменьшает количество параметров при одинаковой точности. Метод может использоваться для сжатия информации в процессе ее обработки и хранения, что существенно уменьшает объем используемой памяти. Предложен метод определения границ звеньев при приближении непрерывных функций полиномиальными и рациональными сплайнами. Это дало возможность на основе сравнения погрешностей разных типов сплайнов выбирать те, которые дают минимальные погрешности при неизменном количестве параметров, или при одинаковой точности приближения получить меньшее количество параметров. Разработаны алгоритмы и программные средства автоматизированной настройки ОВС на параллельное вычисление арифметических и условных выражений. При этом особенность реализации параллельных алгоритмов состоит в том, что в предложенном подходе распараллеливание осуществляется как в пределах одного выражения, так и для разных выражений. Предложен алгоритм синтеза средствами ОВС матричных сплайн-вычислителей для параллельного вычисления функций путем их представления сплайнами с неравным делением отрезка приближения, что дало возможность повысить быстродействие вычислений. Преимущество предложенного подхода к построению параллельных вычислителей состоит в том, что распараллеливание осуществляется, как между звеньями сплайна, так и в пределах одного звена. Дисертаційна робота присвячена питанням розробки методів паралельного обчислення функцій, наближених поліноміальними і раціональними рівномірними чебишовськими сплайнами, орієнтованих на реалізацію засобами однорідних обчислювальних середовищ. Встановлено властивості наближення та розроблено обчислювальні алгоритми для представлення однієї функції, а також набору функцій з спільною множиною вузлів, кусковими наближеннями ‑ сплайнами з розбиттям відрізка наближення на нерівні частини з однаковою похибкою на кожній з них. Зменшення об’єму пам’яті для зберігання параметрів наближення досягається за рахунок вирівнювання величин максимальних похибок на кожному з підінтервалів. Розроблено алгоритми і програмні засоби автоматизованого налаштування ООС на паралельне обчислення арифметичних і умовних виразів. Особливість реалізації паралельних алгоритмів полягає в тому, що в запропонованому підході розпаралелювання здійснюється як в межах одного виразу, так і для різних виразів. Запропоновано алгоритм синтезу засобами ООС матричних сплай-обчислювачів для швидкого обчислення функцій, представлених сплайнами! з нерівним поділом проміжку наближення з використанням паралельних обчислень. Перевага запропонованого підходу до побудови паралельних обчислювачів полягає в тому, що розпаралелювання здійснюється, як між ланками сплайну, так і в межах однієї ланки.