Performance analysis for parallel solutions to generic search problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Performance analysis for parallel solutions to generic search problems

Full text

Pdf (894 KB)

Source

Symposium on Applied Computing archive
Proceedings of the 1997 ACM symposium on Applied computing table of contents

San Jose, California, United States

Pages: 422 - 430

Year of Publication: 1997

ISBN:0-89791-850-9

Authors

Wei-Ming Lin	Division of Engineering, The University of Texas at San Antonio, San Antonio, TX
Wei Xie	Division of Engineering, The University of Texas at San Antonio, San Antonio, TX
Bo Yang	Division of Engineering, The University of Texas at San Antonio, San Antonio, TX

Sponsors

SIGCUE: ACM Special Interest Group on Computer Uses In Education
SIGADA: ACM Special Interest Group on Ada Programming Language
SIGAPP: ACM Special Interest Group on Applied Computing
SIGBIO: ACM Special Interest Group on Biomedical Computing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 9, Citation Count: 0

Additional Information:

references index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/331697.332327 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Vikram S. Adve , Mary K. Vernon, The influence of random delays on parallel execution times, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.61-73, May 10-14, 1993, Santa Clara, California, United States
	2	V. D. Agrawal , S. T. Chakradhar, Performance Analysis of Synchronized Iterative Algorithms on Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.3 n.6, p.739-746, November 1992 [doi>10.1109/71.180628]
	3	B. C. Arnold, N. Balakrishnan and H. N. N agaraja, A First Course in Order Statistics, 1992.
	4	Wesley W. Chu , Chi-Man Sit , Kin K. Leung, Task Response Time for Real-Time Distributed Systems with Resource Contentions, IEEE Transactions on Software Engineering, v.17 n.10, p.1076-1092, October 1991 [doi>10.1109/32.99195]
	5	M. J. Clement , M. J. Quinn, Analytical performance prediction on multicomputers, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.886-894, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169856]
	6	H. A. David, Order Statistics. New York: Wiley, 1981.
	7	M. Dubois and F. A. Briggs, "Performance of Synchronized Iterative Processes in Multiprocessor ~Yo Stems,'' IEEE Trans. on Software Engineering, 1. SE-8, No. 4, July 1982.
	8	J. Gaschnig, "A General Backtrack Algorithm that Eliminates Most Redundant Tests," Proc. of the International Conf. on Artificial Intelligence, 1977.
	9	Arjan J. C. van Gemund, Performance prediction of parallel processing systems: the PAMELA methodology, Proceedings of the 7th international conference on Supercomputing, p.318-327, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.166002]
	10	B. Gendron, T. G. Crainic, "Parallel Branch & Bound on Quadputers", Proc. of 11th European Congress on Operational Research~ Aachen 1991, pp51-52.
	11	R. M. Haralick and G. L. Elliot, "Increasing Tree Search Efficiency for Constraint Satisfaction Problems,'' Artificial Intelligence 1~, 1980.
	12	V. K. Janakiram , D. P. Agrawal , R. Mehrotra, A Randomized Parallel Backtracking Algorithm, IEEE Transactions on Computers, v.37 n.12, p.1665-1676, December 1988 [doi>10.1109/12.9745]
	13	Alex Kapelinkov , Richard R. Muntz , Miloš D. Ercegovac, A modeling methodology for the analysis of concurrent systems and computations, Journal of Parallel and Distributed Computing, v.6 n.3, p.568-597, June 1989 [doi>10.1016/0743-7315(89)90007-5]
	14	D. Knuth, "Estimating the Efficiency of Backtracking Programs," Mathematics of Computation, 29, 1975.
	15	R. E. Korf, Optimal path-finding algorithms*, Search in Artificial Intelligence, Springer-Verlag, London, 1988
	16	Clyde P. Kruskal , Alan Weiss, Allocating independent subtasks on parallel processors, IEEE Transactions on Software Engineering, v.11 n.10, p.1001-1016, Oct. 1985 [doi>10.1109/TSE.1985.231547]
	17	Vipin Kumar , V. Nageshwara Rao, Scalable parallel formulations of depth-first search, Parallel algorithms for machine intelligence and vision, Springer-Verlag New York, Inc., New York, NY, 1990
	18	E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, The 7kaveling Salesman Problem, A Guided Tour of Combinatorial Optimization, Jhon Wiley & Sons, 1985.
	19	W.-M. Lin and B. Yang, "Load Balancing Technique for Parallel Search with Statistical Model," 1995 International Phoenix Conference on Computers and Communications.
	20	Guo-Jie Li , Benjamin W. Wah, Coping with anomalies in parallel branch-and-bound algorithms, IEEE Transactions on Computers, v.35 n.6, p.568-573, June 1986
	21	V. W. Mak , S. F. Lundstrom, Predicting Performance of Parallel Computations, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.257-270, July 1990 [doi>10.1109/71.80155]
	22	D. C. Marinescu and J. R. Rice, "Synchronization and Load Imbalance Effects in Distributed Memory Mult-processor Systems", Concurrency: Practice and Experience, Vol. 3, pp593-625, Dec. 1991.
	23	S. Madala , J. B. Sinclair, Performance of Synchronous Parallel Algorithms with Regular Structures, IEEE Transactions on Parallel and Distributed Systems, v.2 n.1, p.105-116, January 1991 [doi>10.1109/71.80193]
	24	K.S. Naterajan and V. Sarkar, "Processor Scheduling Algorithms for Constraint Satisfaction Search problems, Proc. 1988 International Conference on Parallel Processing, 1988.
	25	Randolph Nelson , Don Towsley , Asser N. Tantawi, Performance Analysis of Parallel Processing Systems, IEEE Transactions on Software Engineering, v.14 n.4, p.532-540, April 1988 [doi>10.1109/32.4676]
	26	Randolph Nelson, A performance evaluation of a general parallel processing model, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.13-26, April 1990, Univ. of Colorado, Boulder, Colorado, United States
	27	Manfred Padberg , Giovanni Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review, v.33 n.1, p.60-100, March 1991 [doi>10.1137/1033004]
	28	A. Papoulis, Probability, Random Variables, and Stochastic Processes, MaGraw-Hill, 1984.
	29	J. Quinn, Analysis and Implementation of Branch-and-Bound Algorithms on a Hypercube Multicomputer, IEEE Transactions on Computers, v.39 n.3, p.384-387, March 1990 [doi>10.1109/12.48868]
	30	V. N. Rao , V. Kumar, On the Efficiency of Parallel Backtracking, IEEE Transactions on Parallel and Distributed Systems, v.4 n.4, p.427-437, April 1993 [doi>10.1109/71.219757]
	31	G. Reinelt, "TSPLIB - A Traveling Salesman Problem Library", ORSA Journal on Computing, March, 1991, pp376-384.
	32	J. T. Robinson, "Some Analysis Techniques for Asynchronous Multiprocessor Algorithms," {EEE Trans. on Software Engineering, Vol. SE-5, Jan. 1979.
	33	A. Rosenfeld, R. A. Hummel, and S. W. Zucker, "Scene Labeling by Relaxation Operations," IEEE Trans. on $yst., Man, Cyber., Vol. SMC-6, pp. 420- 433, June 1976.
	34	V. Sarkar, Determining average program execution times and their variance, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.298-312, June 19-23, 1989, Portland, Oregon, United States
	35	S. Som , R. R. Mielke , J. W. Stoughton, Prediction of Performance and Processor Requirements in Real-Time Data Flow Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.11, p.1205-1216, November 1993 [doi>10.1109/71.250100]
	36	Athar B. Tayyab , Jon G. Kuhl, Stochastic performance models of parallel task systems (extended abstract), Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.284-285, May 16-20, 1994, Nashville, Tennessee, United States
	37	Stefan Tschöke , Reinhard Lüling , Burkhard Monien, Solving the traveling salesman problem with a distributed branch-and-bound algorithm on a 1024 processor network, Proceedings of the 9th International Symposium on Parallel Processing, p.182-189, April 25-28, 1995
	38	T. Volgenant and R. Jonker, "A Branch and Bound Algorithm for the Symmetric Traveling Salesman Problem Based on the 1-Tree Relaxation", European Journal on Operational Research, Sept., 1982, pp83-89.
	39	T. Volgenant and R. jonker, "N onoptunal Edges for the Symmetric Traveling Salesman Problem", Operations Research, Vol. 32, No. 4, pp65-74, April, 1984.
	40	L. F. Wilson and M. J. Gonzalez, "Synchronization and Communication in Algorithmic Structures", Proc. of the 6th IEEE Syrup. on Paral. and Distri. Processing, pp196-203, 1994.