Microsoft Word - tpel.doc


Mathematical Problems of Computer Science 35, 14--18, 2011. 

14 
 

 
 
 

Implementation of a Search Parallelization Method on High 
Performance Computing Structures 

Grigor H. Geoletsyan and Hrant G. Geoletsyan 

Institute for Informatics and Automation Problems of NAS RA 
Russian-Armenian (Slavonic) University 

 
Abstract 

We describe the implementation of modified initialization and load balancing 
methods during parallelization of search algorithms for solution of optimization 
problems on high performance computing structures. 

Most optimization problems in discrete mathematics related to applications in 
new research areas are NP-hard. Parallelization of search algorithms using static and 
dynamic load-balancing (distribution of computational resources) and their 
implementation on high performance computing structures, in particular, on 
computer clusters is an essential tool for obtaining effective solutions to such 
problems. 

 
 

 
References 

[1] Г. Геолецян, “Эвристический алгоритм решения задачи ограниченного вершинного покрытия 
двудольного графа”, Доклады НАН РА, т. 107, н. 1, стр. 44–48, 2007. 
[2] Г. Геолецян, Г. Геолецян, “Инициализация параллельного поиска”, Годичная научная 
конференция РАУ, 2007. Сборник научных статей, Ереван, стр. 115-121, 2008. 
[3] Г. Геолецян , Г. Геолецян, “Инструментальные средства реализации методов параллельного 
поиска”  Вестник РАУ. Ереван. 1, сс. 32-40, 2008. 
[4] I. Kim, Y. Zorian, G. Komoriya et al., “Built in self repair for embedded high density SRAM”,  
Proc. Int. Test Conference, pp. 1112–1119, 1998. 
[5] H. Fernau, R. Niedermeier, “An efficient exact algorithm for constraint bipartite vertex cover”, J. 
Algorithms, vol. 38, no. 2, pp. 374–410, 2001. 
[6] A. Grama, V. Kumar, “State of the art in parallel search techniques for discrete optimization 
problems”, IEEE Trans. Knowl. Data Eng., vol. 11, no. 1, pp. 28–35, 1999. 
[7] S.-Y. Kuo, W. K. Fuchs, “Efficient spare allocation in reconfigurable arrays”,   DAC, pp. 385–390, 
1986.    
[8] M. G. Lagoudakis, “An IDA* Algorithm for optimal spare allocation”,  SAC, pp. 486–488, 1999. 
[9] N. R. Mahapatra, S. Dutt, “Random seeking: A general, efficient, and informed randomized scheme 
for dynamic load balancing”,  Int. J. Found. Comput. Sci., vol. 11, no. 2, pp. 231–246, 2000. 
[10] F. Yu, C-H. Tsai, Y-W.Hang, H-Y. Lin, D. T. Lee, S-Y. Kuo, “Efficient еxact spare allocation via 
boolean satisfiability”, Proceedings of the 20th IEEE International Symposium on Defect and Fault 
Tolerance in VLSI Systems (DFT’05), Oct., Monterey, California, 9p, 2005. 



G.  Geoletsyan, H. Geoletsyan 
 

15 

 

гï³ñÏÙ³Ý ½áõգ³Ñ»é³óÙ³Ý Ù»Ãá¹Ç Çñ³Ï³Ý³óáõÙÁ µ³ñÓñ 
³ñï³¹ñÕáճϳÝáõÃÛ³Ùµ ѳßíáÕ³Ï³Ý Ï³éáõóí³ÍùÝ»ñáõÙ 
 

¶.  ¶»áÉ»óÛ³Ý ¨ Ð.  ¶»áÉ»óÛ³Ý 

 

²Ù÷á÷áõÙ 

 

Üϳñ³գñí³Í ¿ ѳٳϳñգí³Í ѳï³ñÏÙ³Ý ³ÉգáñÇÃÙÝ»ñÇ ½áõգ³Ñ»é³óÙ³Ý ëϽµÝ³µ»ñÙ³Ý  
¨ µ³É³Ýë³íáñÙ³Ý Ùá¹ÇýÇϳóí³Í Ù»Ãá¹Ç Çñ³Ï³Ý³óáõÙÁ µ³ñÓñ ³ñï³¹ñáճϳÝáõÃÛ³Ùµ 
ѳßíáÕ³Ï³Ý Ï³éáõóí³ÍùÝ»ñÇ íñ³ ûåïÇٳɳóÙ³Ý ËݹÇñÝ»ñÇ ÉáõÍÙ³Ý Å³Ù³Ý³Ï: