Реализация параллельного алгоритма геометрического хеширования на основе пакета NumPy и пула процессов
Автор: Клячин Владимир Александрович
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Компьютерное моделирование
Статья в выпуске: 4 (29), 2015 года.
Бесплатный доступ
В статье рассматривается задача многомерного геометрического хеширования. Предлагается способ построения соответствующей хеш-матрицы параллельным алгоритмом. В работе построен алгоритм параллельного геометрического хеширования с использованием шаблона «пул процессов». Реализация алгоритма выполнена с применением языка программирования Python и пакета NumPy для манипулирования многомерными данными. В качестве основы для пула процессов предложено использовать класс ProcessPoolExecutor модуля concurrent.futures, который входит в дистрибутив интерпретатора Python начиная с версии 3.2. Все решения представлены в статье соответствующими UML-диаграммами классов. Найденное обобщенное программное решение может быть использовано для реализации параллельных алгоритмов и других задач, которые могут быть описаны в терминах схемы пула процессов.
Хеширование, пул процессов, пакет numpy, вычислительная геометрия, параллельный алгоритм
Короткий адрес: https://sciup.org/14968991
IDR: 14968991 | УДК: 514.142.2+514.174.6 | DOI: 10.15688/jvolsu1.2015.4.2
Parallel algorithm of geometrical hashing based on NumPy package and processes pool
The article considers the problem of multi-dimensional geometric hashing. The paper describes a mathematical model of geometric hashing and considers an example of its use in localization problems for the point. A method of constructing the corresponding hash matrix by parallel algorithm is considered. In this paper an algorithm of parallel geometric hashing using a development pattern «pool processes» is proposed. The implementation of the algorithm is executed using the Python programming language and NumPy package for manipulating multidimensional data. To implement the process pool it is proposed to use a class Process Pool Executor imported from module concurrent.futures, which is included in the distribution of the interpreter Python since version 3.2. All the solutions are presented in the paper by corresponding UML class diagrams. Designed GeomNash package includes classes Data, Result, GeomHash, Job. The results of the developed program presents the corresponding graphs. Also, the article presents the theoretical justification for the application process pool for the implementation of parallel algorithms. It is obtained condition pt2 > p - 1 t1 of the appropriateness of process pool. Here t 1 - the time of transmission unit of data between processes, and t 2 - the time of processing unit data by one processor.
Список литературы Реализация параллельного алгоритма геометрического хеширования на основе пакета NumPy и пула процессов
- Академия Microsoft: Параллельные вычисления и многопоточное программирование. Лекция 7: Пул потоков и библиотека параллельных задач. -Электрон. текстовые дан. -Режим доступа: http://www.intuit.ru/studies/courses/10554/1092/lecture/21509. -Загл. с экрана.
- Бабищевич, П.Н. Численные методы: Вычислительный практикум/П.Н. Бабищевич. -М.: ЛЕНАНД, 2015. -320 c.
- Гергель, В.П. Теория и практика параллельных вычислений/В.П. Гергель. -М.: Интернет-Университет Информационных технологий; БИНОМ. Лаборатория знаний, 2007. -423 c.
- Гриценко, Ю.Б. Решение проблемы обновления пространственных данных в среде Oracle Spatial/Ю.Б. Гриценко, В.Ю. Вишняков, С.С. Ощепков//Докл. ТУСУРа. Управление, вычислительная техника и информатика. -2008. -№ 2 (18). -C. 76-79.
- Клячин, В.А. Оптимизация построения расчетной сетки для решения задачи локального криовоздействия с использованием многомерного геометрического хеширования на основе пакета NumPy/В.А. Клячин//Изв. Сарат. ун-та. Новая серия. Серия Математика. Механика. Информатика. -2014. -Т. 14, № 3. -C. 355-362.
- Математический Python. -Электрон. текстовые дан. -Режим доступа: http://jenyay.net/Programming/PyMath. -Загл. с экрана.
- Никольский, Д.Н. Разработка программного обеспечения для численного решения задач эволюции границы раздела различных жидкостей в пористых средах сложной геологической структуры с использованием пакета NumPy/Д.Н. Никольский//Ученые записки Орловского государственного университета. Серия: Естественные, технические и медицинские науки. -2012. -№ 6-1. -C. 42-47.
- Олифант, Т. Многомерные итераторы NumPy/Т. Олифант//Идеальный код. -СПб.: Питер, 2011. -C. 341-358.
- Препарата, Ф. Вычислительная геометрия/Ф. Препарата, М. Шеймос. -М.: Наука, 1989. -478 c.
- Пул управляемых потоков. MSDN -Microsoft. -Электрон. текстовые дан. -Режим доступа: https://msdn.microsoft.com/ru-ru/library/0ka9477y(v=vs.110).aspx. -Загл. с экрана.
- Саммерфилд, М. Python на практике/М. Саммерфилд. -М.: ДМК Пресс, 2014. -338 c.
- Скворцов, А.В. Алгоритмы построения и анализа триангуляции/А.␣В. Скворцов, Н.С. Мирза. -Томск: Изд-во Том. ун-та, 2006. -168 c.
- Шикин, Е.В. Компьютерная графика. Полигональные модели/Е.В. Шикин, А.В. Боресков. -М.: ДИАЛОГ-МИФИ, 2001. -464 c.
- An Improved Method of Geometric Hashing Pattern Recognition/M. Ling, L. Yumin, J. Huiqin, W. Zhongyong, Z. Haofei//I. J. Modern Education and Computer Science. -2011. -Vol. 3. -P. 1-7.
- Mian, A.S. Three-dimensional model-based object recognition and segmentation in cluttered scenes/A.S. Mian, M. Bennamoun, R. Owens//IEEE Transactions on Pattern Analysis and Machine Intelligence. -2006. -Vol. 28. -P. 1584-1601.
- Thread pool pattern. -Electronic text data. -Mode of access: https://en.wikipedia.org/wiki/Thread_pool_pattern. -Title from screen.
- Wolfson, H.J. Geometric Hashing: An Overview/H.J. Wolfson, I. Rigoutsos//IEEE Computational Science and Engineering. -1997. -Vol. 4, № 4. -P. 10-21.
