Vectorization and parallelization of irregular problems via graph coloring

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Vectorization and parallelization of irregular problems via graph coloring

Full text

Pdf (1.03 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 5th international conference on Supercomputing table of contents

Cologne, West Germany

Pages: 47 - 56

Year of Publication: 1991

ISBN:0-89791-434-1

Authors

Hans-Christian Hege	Konrad-Zuse-Zentrum für Informationstechnik Berlin, Heilbronner Str. 10, D-1000 Berlin 31, F. R. G.
Hinnerk Stüben	Freie Universität Berlin, Institut für Theoretische Physik, Arnimallee 14, D-1000 Berlin 33, F. R. G.

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references 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/109025.109042 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	K.-Y. Wang, D. Cannon, "Applying AI Techniques to Program Optimization for Parallel Computers". In K. Hwang, D. DeGroot (eds.). Parallel Processing for Supercomputers and Artificial Intelligence, pp. 441-485, McGraw-Hill, New York, 1989.
	2	D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
	3	Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
	4	Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
	5	Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.162-175, June 25-27, 1986, Palo Alto, California, United States
	6	C. D. Polychronopoulos, "Loop Coalescing: A Compiler Transformation for Parallel Machines", Proc. of the 1987 Int. Conf. on Parallel Processing, St. Charles, IL, Sahni (ed.), Penn State Univ. Press, University Park, PA, pp. 235-242, Aug. 1957.
	7	C. D. Polychronopoulos, Compiler Optimizations for Enhancing Parallelism and Their Impact on Architecture Design, IEEE Transactions on Computers, v.37 n.8, p.991-1004, August 1988 [doi>10.1109/12.2249]
	8	J.-K. Peir , R. Cytron, Minimum Distance: A Method for Partitioning Recurrences for Multiprocessors, IEEE Transactions on Computers, v.38 n.8, p.1203-1211, August 1989 [doi>10.1109/12.30873]
	9	Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
	10	Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
	11	Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
	12	Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
	13	Constantine D. Polychronopoulos , Milind B. Girkar , Mohammad Reza Haghighat , Chia Ling Lee , Bruce Leung , Dale Schouten, Parafrase-2: an environment for parallelizing, partitioning, synchronizing, and scheduling programs on multiprocessors, International Journal of High Speed Computing, v.1 n.1, p.45-72, May 1989 [doi>10.1142/S0129053389000044]
	14	Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	15	Ian G. Angus , Geoffrey C. Fox , Jai Sam Kim , David W. Walker, Solving problems on concurrent processors: vol. 2, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
	16	Arvind , R S Nikhil, Executing a program on the MIT tagged-token dataflow architecture, Volume II: Parallel Languages on PARLE: Parallel Architectures and Languages Europe, p.1-29, March 1987, Eindhoven, The Netherlands
	17	G. Rote, "Path Problems in Graphs", in G. Tinhofer, E. Noltemeier, M. Syslo (eds.), Computational Graph Theory, Springer-Verlag, Computing Suppl. 7, Wien, 1990, pp. 155-198.
	18	D. Chazan, W. Miranker, "Chaotic Relaxation", Linear Algebra Appl. 2 (1969), pp. 199-222.
	19	Debasis Mitra, Asynchronous relaxations for the numerical solution of differential equations by parallel processors, SIAM Journal on Scientific and Statistical Computing, v.8 n.1, p.43-58, January 2, 1987 [doi>10.1137/0908012]
	20	Aydin Üresin , Michel Dubois, Parallel asynchronous algorithms for discrete data, Journal of the ACM (JACM), v.37 n.3, p.588-606, July 1990 [doi>10.1145/79147.79162]
	21	Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
	22	J. M. Ortega, R. V. Vogt, "Solution of Partial Differential Equations on Vector and Parallel Computers", SIAM Review 27, 2 (June 1985), pp. 149-240.
	23	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]
	24	M. GrStschel, L. Lov~sz and A. Schrijver, "Polynomial Algorithms for Perfect Graphs", Annals of Discrete Mathematics 21, (1984), pp. 325-356.
	25	Xin He, "Efficient Parallel and Sequential Algorithms for 4-coloring Perfect Planar Graphs", A1- gorithmica 5, (1990), pp. 545-559.
	26	B. Berger and J. Rompel, "A Better Performance Guarantee for Approximate Graph Coloring", A1- gorithmica 5, (1990), pp. 459-466.
	27	J. Zerovnik, "A Parallel Variant of a Heuristical Algorithm for Graph Coloring", Parallel Computing 13, (1990), pp. 95-100.
	28	D. de Werra, "Heuristics for Graph Coloring", Computing Suppl. 7, (1990), pp. 191-208.
	29	H. Stiiben, "Monte-Carlo Untersuchungen der topologischen Suszeptibilit/it im zweidimensionalen nichtlinearen O(3)-a-Modell", Thesis, Freie Universit~it Berlin, 1989.
	30	H. Stfiben, H.-C. Hege, A. Nakamura, "The Nonlinear O(3)-a-Model on Random Lattices with Different Topology", Phys. Lett. 244B, (1990), pp. 473- 478.
	31	H.-C. Hege, "Geometric der Zufallsgitter, ihre Realisierung und ihr Verhalten als physikalische Systeme am Beispiel des Z(2)-Spin-Modells", Thesis, Freie Universit//t Berlin, 1984.