Parallel processing Puzzle N2-1 on cluster architectures performance analysis

被引：0
作者：
Sanz, Victoria
de Giusti, Armando
Chichizola, Franco
Naiouf, Marcelo
De Giusti, Laura
机构：
来源：
PROCEEDINGS OF THE ITI 2008 30TH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY INTERFACES | 2008年
关键词：
parallel algorithms; distributed processing; speedup; superlinearity; efficiency scalability;
D O I：
10.1109/ITI.2008.4588527
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
An analysis of a parallel solution of N-2-1 Puzzle using clusters, is presented. This problem is interesting due to its complexity and related applications, particularly in the field of robotics. A variation of classic heuristics for forecasting the work to be done in order to reach a solution is analyzed, and it is shown that its use significantly improves the time of sequential algorithm A*. Then, a parallel solution on a distributed architecture is presented and speedup is analyzed based on the number of processors, efficiency, and the possible superlinearity when scaling the problem.
引用
收藏
页码：879 / 884
页数：6
相关论文
共 25 条
[1]   A CASE FOR NOW (NETWORKS OF WORKSTATIONS) [J].
ANDERSON, TE ;
CULLER, DE ;
PATTERSON, DA .
IEEE MICRO, 1995, 15 (01) :54-64
[2]  
[Anonymous], 1999, HIGH PERFORMANCE CLU
[3]   Load balancing for heterogeneous clusters of PCs [J].
Bohn, CA ;
Lamont, GB .
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2002, 18 (03) :389-400
[4]   TERMINATION DETECTION FOR DIFFUSING COMPUTATIONS [J].
DIJKSTRA, EW ;
SCHOLTEN, CS .
INFORMATION PROCESSING LETTERS, 1980, 11 (01) :1-4
[5]  
Fitch R, 2005, IEEE INT CONF ROBOT, P117
[6]   State of the art in parallel search techniques for discrete optimization problems [J].
Grama, A ;
Kumar, V .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 1999, 11 (01) :28-35
[7]  
Grama Ananth, 2003, Introduction to Parallel Computing
[8]   CRITICIZING SOLUTIONS TO RELAXED MODELS YIELDS POWERFUL ADMISSIBLE HEURISTICS [J].
HANSSON, O ;
MAYER, A ;
YUNG, M .
INFORMATION SCIENCES, 1992, 63 (03) :207-227
[9]  
Helmbold D. P., 1990, IEEE Transactions on Parallel and Distributed Systems, V1, P250, DOI 10.1109/71.80148
[10]  
Hwang K., 1993, Advanced Computer Architecture: Parallelism. Scalability
123