350 руб
Журнал «Системы высокой доступности» №1 за 2015 г.
Статья в номере:
Параллельная реализация решения оптимизационных задач средствами баз данных
Ключевые слова: оптимизационные алгоритмы облачные системы и вычисления параллельные вычисления базы данных
Авторы:
В.И. Мунерман - к.т.н., доцент, кафедра информатики, Смоленский государственный университет. E-mail: vimoon@gmail.com Т.А. Самойлова - к.т.н., доцент, кафедра информатики, Смоленский государственный университет. E-mail: tatsam@hotbox.ru
Аннотация:
Рассмотрен один из способов решения широкого класса оптимизационных задач, общее название которых «задачи о кратчайшем пути», исходными данными для которых служат нагруженные графы. Предложено использовать алгоритм, основанный на вычислении транзитивного замыкания матрицы весов графа, который легко распараллеливается. Показано, что большинство достоинств этого алгоритма теряются в том случае, когда эта матрица разреженная. Выбрано представление разреженных матриц, позволяющее хранить и обрабатывать их в реляционных базах данных. Приведена реализация алгоритма решения задачи о кратчайшем пути средствами языка Tranzact-SQL. Выполнена возможность параллельной реализации этого алгоритма на основе принципа симметричного горизонтального распределения данных. Отмечено, что эвристический оптимизационный алгоритм распределения данных может быть также реализован средствами баз данных. Сделан вывод о возможности использования баз данных для эффективного решения оптимизационных задач. Ключевые слова:
Страницы: 18-22
Список источников

 

  1. Fletcher P., Hoyle H., Patty C.W. Foundations of Discrete Mathematics. Boston: PWS-KENTPub. Co. 1991. 781 p.
  2. Lidl R., Pilz G. Applied abstract algebra, 2nd edition. Undergraduate Texts in Mathematics. Springer. 1998. 488 p.
  3. Gross J.L., Yellen J. Handbook of Graph Theory, Discrete Mathematics and Its Applications. CRCPress. 2004. 779 p.
  4. Aho A., Ullman J.D., Hopcroft J.E. Data Structures and Algorithms. AddisonWesley. 1983.
  5. Agarwal R.C., Gustavson F.G., Zubair M. A High-Performance Matrix-Multiplication Algorithm on a Distributed-Memory Parallel Computer Using Overlapped Communication // IBM Journal of Research and Development. 1994. № 38(6). P. 673−681.
  6. Gupta H., Sadayappan P. Communication Efficient Matrix-Multiplication on Hypercubes. Technical Report // Stanford InfoLab. Publication Note: Sixth Annual ACM Symposium on Parallel Algorithms and Architectures. 1994. (SPAA 1994). ExtendedversioninParallelComputing. 1996. № 22. P. 75−99.
  7. Pissanetzky Sergio Sparse Matrix Technology. AcademicPress. 1984. 321 p.
  8. Munerman V.I. The Object-Oriented Model of Mass Data Processing // Highly available systems. 2011. V. 7. № 4. P. 72−74.
  9. Munerman V.I. A multidimesional matrix model of mass data processing // Highly available systems. 2012. V. 8. № 1. P. 19−22.
  10. Levin N.A., Munerman V.I. Models of big data processing in massively parallel systems // Highly available systems. 2013. V. 9. № 2. P. 36−39.
  11. Munerman V.I. Implementation of big data processing on symmetric multiprocessing systems // Highly available systems. 2013. V. 9. № 3. P. 35−43.
  12. Munerman V.I. The experience of massive data processing in the cloud using Windows Azure (as an example) // Highly available systems. 2014. V. 10. № 2. P. 3−8.