Parallel asynchronous algorithms for discrete data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel asynchronous algorithms for discrete data

Full text

Pdf (1.40 MB)

Source

Journal of the ACM (JACM) archive
Volume 37 , Issue 3 (July 1990) table of contents

Pages: 588 - 606

Year of Publication: 1990

ISSN:0004-5411

Authors

Aydin Üresin	Univ. of Southern California, Los Angeles
Michel Dubois	Univ. of Southern California, Los Angeles

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 42, Citation Count: 7

Additional Information:

abstract references cited by index terms collaborative colleagues

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/79147.79162 What is a DOI?

ABSTRACT

Many problems in the area of symbolic computing can be solved by iterative algorithms. Implementations of these algorithms on multiprocessors can be synchronous or asynchronous. Asynchronous implementations are potentially more efficient because synchronization is a major source of performance degradation in most multiprocessor systems. In this paper, sufficient conditions for the convergence of asynchronous iterations to desired solutions are given. The main sufficient condition is shown to be also necessary for the case of finite data domains. The results are applied to prove the convergence of three asynchronous algorithms for the all-pairs shortest path problem, the consistent labeling problem, and a neural net model.

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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Gérard M. Baudet, Asynchronous Iterative Methods for Multiprocessors, Journal of the ACM (JACM), v.25 n.2, p.226-244, April 1978 [doi>10.1145/322063.322067]
	3	BERTSEKAS, D.P. Distributed dynamic programming. IEEE Trans. Automatic Control 27 (1982), 610-616.
	4	BERTSEKAS, O.P. Distributed asynchronous computation of fixed points. Math. Prog. 27 (1983), 107-120.
	5	CHAZAN, D., AND MIRANKER, W. Chaotic relaxation. Linear Algebra and its Applications 2 (1969), 199-222.
	6	HARALICK, R. M., AND SHAPIRO, L.G. The consistent labeling problem: Part I. IEEE Trans. Pattern Anal. and Mach. Int. I, 2 (Apr. 1979), 173-184.
	7	Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
	8	KUNG, H. T. Synchronized and asynchronous parallel algorithms for multiprocessors. In Algorithms and Complexity: New Directions and Recent Results. J. F. Traub, ed. Academic Press, Orlando, Fla., 1976.
	9	LIPPMANN, R.P. Introduction to computing with neural nets. IEEE Acoustics, Speech, and Signal Processing Magazine (Apr. 1987), 4-22.
	10	Boris Lubachevsky , Debasis Mitra, A chaotic asynchronous algorithm for computing the fixed point of a nonnegative matrix of unit spectral radius, Journal of the ACM (JACM), v.33 n.1, p.130-150, Jan. 1986 [doi>10.1145/4904.4801]
	11	J. C. Miellou, Asynchronous iterations and order intervals, Proceedings of the international workshop on Parallel algorithms & architectures, p.85-96, November 1986, Luminy, France
	12	ROBERT, F. Discrete Iterations. Springer-Verlag, Berlin, 1986.
	13	ROSENFELD, A., HUMMEL, R. A., AND ZUCKER, S.W. Scene labeling by relaxation operations. IEEE Trans. Systems, Man, and Cybernetics 6, 6 (June 1976), 420-433.
	14	P. Spiteri, Parallel asynchronous algorithms for solving boundary value problems, Proceedings of the international workshop on Parallel algorithms & architectures, p.73-84, November 1986, Luminy, France
	15	TSITSIKLIS, J. N.On the stability of asynchronous iterative processes. Math. Syst. Theory 20 (1987), 137-153.
	16	TSITSIKLIS, J. N., AND BERTSEKAS, D. P. Distributed asynchronous optimal routing in data networks. IEEE Trans. on Automatic Control 31 (1986), 325-332.
	17	TSITSIKLIS, J. N., BERTSEKAS, D. P., AND ATHANS, M. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Trans. on Automatic Control 31 (1986), 803-812.
	18	A Uresin , M Dubois, Generalized asynchronous iterations, Proc. of the conference on algorithms and hardware for parallel processing on CONPAR 86, p.272-278, November 1986, Aachen, Germany
	19	I~JRESIN, A., AND DUBOIS, M. Sufficient conditions for the convergence of asynchronous iterations. Parallel Computing I0 (1989), 83-92.

CITED BY 7

	Hans-Christian Hege , Hinnerk Stüben, Vectorization and parallelization of irregular problems via graph coloring, Proceedings of the 5th international conference on Supercomputing, p.47-56, June 17-21, 1991, Cologne, West Germany
	Hyunyoung Lee , Jennifer L. Welch, Specification, implementation and application of randomized regular registers (brief announcement), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.338, July 16-19, 2000, Portland, Oregon, United States
	Stephen A. Edwards , Edward A. Lee, The semantics and execution of a synchronous block-diagram language, Science of Computer Programming, v.48 n.1, p.21-42, July 2003
	Bertrand Ducourthial , Sébastien Tixeuil, Self-stabilization with path algebra, Theoretical Computer Science, v.293 n.1, p.219-236, 3 February 2003
	Hyunyoung Lee , Jennifer L. Welch, Randomized registers and iterative algorithms, Distributed Computing, v.17 n.3, p.209-221, March 2005
	Chi-kin Chau, Policy-based routing with non-strict preferences, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
	Steven Y. Ko , Indranil Gupta , Yookyung Jo, A new class of nature-inspired algorithms for self-adaptive peer-to-peer computing, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.3 n.3, p.1-34, August 2008