Approaches to realization Yen’s algorithm for systems with the shared memory

S.D. Pogorilyy, M.I. Tribrat, U.V. Boyko, D.V. Afanasyev

Abstract


Construct a regular scheme of algorithm Yen using the apparatus of systems algorithmic algebras, proposed approaches to parallel implementation of the algorithm Yen for SMP- architecture. Executed formalization the method of forming patterns by parallel schemes using the mathematical apparatus of modified systems algorithmic algebras. The parallel Yen’s algorithm is realized, experimental data are resulted.

Prombles in programming 2011; 2: 12-22


References


Brander A.W., Sinclair M.C. A comparative study of k-shortest path algorithms// In Proc. of 11th UK Performance Engineering Workshop. – 1995.

O’Mahony M.J, Sinclair M.C., Mikac B. Ultra-high capacity optical transmission network. European research project COST 239 // Information, Telecommunications, Autonata. – 1993. – 12. – P 33–45.

Кристофидес Н. Теория графов. – М.: Мир, 1978. – 432 с.

Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П. и др. Многоуровневое структурное проектирование программ. Теоретические основы, интсрументарий. – М.: Финансы и статистика, 1989. – 342 с.

Martins E., Pascoal M. A new imple-mentation of Yen’s ranking loopless paths algorithm. – 2000. – 13 c.

Кормен Т., Лейзерсон Х., Чарльз И., Штайн Л. Алгоритмы: построение и анализ, 2-е издание : Пер. с англ. – М.: «Вильямс», 2005. – 1296 с.

Погорілий С.Д., Бойко Ю.В., Білоус Р.В. Формування та аналіз паралельних схем алгоритму Дейкстри // Математичні машини і системи. – 2008. – № 4. – C. 62 – 72.

Ефимов С.С. Обзор методов распараллеливания алгоритмов решения некоторых задач вычислительной дискретной математики // Математические структуры и моделирование. – М.: Мир, 2007. – № 17. – C. 72–93.

POSIX Threads Programming [ Електронний ресурс ] / Blaise Barney, Lawrence Livermore National Laboratory – Режим доступу https://computing.llnl.gov/tutorials/pthreads/

The OpenMP API specification for parallel programming [Електронний ресурс] – Режим доступу http://openmp.org/

Марьяновский В.А., Погорелый С.Д.,

Бойко Ю.В, и др. Программное обеспечение UAClaster // Управляющиесистемы и машины. – 2009. – № 5. – С. 76–80.


Refbacks

  • There are currently no refbacks.