ИНТЕРПОЛЯЦИЯ В УСЛОВИЯХ ОГРАНИЧЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ РЕСУРСОВ

​INTERPOLATION UNDER LIMITED COMPUTATIONAL RESOURCES

Lyudmila Gorbenko

student, Faculty of Computer Science and Engineering, Don State Technical University (DGTU),

Russia, Rostov-on-Don

Andrey Bondarenko

student, Faculty of Computer Science and Engineering, Don State Technical University (DGTU),

Russia, Rostov-on-Don

Vladimir Litvinov

scientific supervisor, Ph.D., Associate Professor, Faculty of Computer Science and Engineering, Don State Technical University (DGTU),

Russia, Rostov-on-Don

АННОТАЦИЯ

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

ABSTRACT

The article addresses the development of interpolation methods under limited computational resources. It examines factors affecting algorithm speed and accuracy, including computational architecture heterogeneity, memory constraints, and real-time processing requirements. The proposed approaches combine accuracy and efficiency on heterogeneous platforms. Implementation examples of bilinear and spline interpolation with performance evaluation on CPU and GPU are provided.

Ключевые слова: интерполяция, CUDA, билинейная интерполяция, сплайн, GPU, реальное время.

Keywords: interpolation, CUDA, bilinear interpolation, spline, GPU, real-time.

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

Во встраиваемых системах, мобильных устройствах и системах реального времени наблюдается жёсткое ограничение на объём оперативной памяти, частоту процессора и энергопотребление. Это исключает использование тяжелых полиномиальных моделей высокой степени и требует приближённых, но быстрых решений. Системы, использующие одновременно CPU и GPU, предъявляют особые требования к структуре алгоритмов: они должны быть векторизуемыми, легко распараллеливаемыми и минимально зависимыми от последовательной логики. Некоторые методы интерполяции, например, билинейная или бикубическая, успешно реализуются на GPU, тогда как методы на основе глобальных полиномов требуют сложной синхронизации и плохо масштабируются. Современные приложения — от медицинской диагностики до автономных транспортных систем — требуют не только точности, но и времени отклика в пределах миллисекунд. Это делает особенно актуальными методы, сочетающие предобученные аппроксимации, кэширование и адаптивную выборку.

Математическая модель оценки точности интерполяции в условиях ограниченных вычислительных ресурсов

 – время выполнения алгоритма интерполяции, с;

 – среднеквадратичная ошибка (RMSE) интерполяции, о.е.;

 – объём используемой оперативной памяти, Мб;

 – архитектурный коэффициент, отражающий уровень поддержки алгоритма данной платформой (например, CPU ускорение) [5]

 – весовые коэффициенты, отражающие приоритеты задач (например, скорость важнее точности и памяти: α = 0.5, β = 0.4, γ = 0.1)

Формула целевой функции (интерполяционного качества):

                                                               (1)

Формула (1) разработана авторами на основе анализа критериев эффективности интерполяционных алгоритмов в условиях ограниченных ресурсов. Аналогичные подходы к комбинированию метрик обсуждаются в работах по оптимизации вычислений [6] и GPU-ускорению. [7][8]

Условия:

 – ограничение по времени (например, для систем реального времени)

 – ограничение по допустимой памяти (например, 512 МБ)

 – допустимая ошибка

Допустим, у нас есть 2 алгоритма:

Таблица 1

2 алгоритма

Выбираем: , ,

Посчитаем :

• Билинейный:

• Сплайн:

Вывод: билинейный метод на GPU эффективнее по общей метрике Q.

Методы оптимизации

• Локальные методы (k-ближайших соседей, локальные сплайны) — минимизируют объем необходимых данных и хорошо подходят для потоковой обработки.
• Предобработка с квантованием и индексированием — уменьшает объем выборки, требуемой для интерполяции.
• Сжатые представления (compressed sensing) — восстанавливают сигнал из малой выборки без прямой интерполяции.
• Гибридные архитектуры (смешанные вычисления на CPU и GPU) — позволяют вынести ресурсоемкие этапы (например, генерацию весов) на GPU, а быстрые — оставить на CPU.

Примеры алгоритмов и сравнение производительности

1. Билинейная интерполяция (NumPy, CPU)

import numpy as np

from scipy.ndimage import zoom

import time

image = np.random.rand(1000, 1000)

start = time.time()

resized_cpu = zoom(image, (2, 2), order=1)  # order=1 — билинейная интерполяция

end = time.time()

print("CPU (biliinear):", end - start, "сек")

2. Кубический сплайн (SciPy, CPU)

start = time.time()

resized_cpu_spline = zoom(image, (2, 2), order=3)  # order=3 — кубический сплайн

end = time.time()

print("CPU (spline):", end - start, "сек")

3. Билинейная интерполяция с помощью OpenCV (CUDA)

import cv2 as cv

image_uint8 = (image * 255).astype(np.uint8)

gpu_mat = cv.cuda_GpuMat()

gpu_mat.upload(image_uint8)

start = time.time()

resized_gpu = cv.cuda.resize(gpu_mat, (2000, 2000), interpolation=cv.INTER_LINEAR)

resized_cpu = resized_gpu.download()

end = time.time()

print("GPU (bilinear):", end - start, "сек")

Рисунок 1. Сравнение производительности алгоритмов интерполяции

Сравнение: CPU-базированные сплайны обеспечивают высокую точность, но значительно медленнее. Билинейная интерполяция на GPU в разы быстрее при приемлемом качестве.

Заключение

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

Список литературы:

1. Burden R.L., Faires J.D. Numerical Analysis. 9th ed. — Brooks Cole, 2010.
2. Ghosh A., Gupta S., Roy S. Fast Interpolation Techniques for Real-Time Systems // Journal of Real-Time Image Processing. — 2020.
3. Micikevicius P. 3D Finite Difference Computation on GPUs using CUDA. — NVIDIA Developer Technology, 2009.
4. Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — Cambridge University Press, 2007.
5. NVIDIA Developer Blog. Optimizing Interpolation on CUDA. — 2023. [Электронный ресурс]. URL: https://developer.nvidia.com/blog/ (дата обращения: 10.06.2025).
6. Вычисление функций [Электронный ресурс] URL: http://www.machinelearning.ru/wiki/index.php?title=Вычисление_функций (дата обращения 09.06.2025)
7. Интерполяция [VMath]. — 2022. [Электронный ресурс]. URL: https://vmath.ru/vf5/interpolation (дата обращения: 11.06.2025)
8. Экстраполяция и интерполяция. Подводные камни расчетов — 2021. [Электронный ресурс]. URL: https://gk-adept.ru/pir_blog/proektnye_raboty/ekstr_interpol/ (Дата обращения: 10.06.2025)