Supernode partitioning

ABSTRACT

Supercompilers must reschedule computations defined by nested DO-loops in order to make an efficient use of supercomputer features (vector units, multiple elementary processors, cache memory, etc…). Many rescheduling techniques like loop interchange, loop strip-mining or rectangular partitioning have been described to speedup program execution. We present here a class of partitionings that encompasses previous techniques and provides enough flexibility to adapt code to multiprocessors with two levels of parallelism and two levels of memory.

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	J.R. Allen and K. Kennedy, "PFC:: a Program to C(mvert Fortran to a Parallel Form," in Supercomputers, Design and Application, ed. K. Hwang (1982). COMPSAC, Tutorial
	2	John R. Allen , Ken Kennedy, Automatic loop interchange, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.233-246, June 17-22, 1984, Montreal, Canada
	3	C. Ancourt, "Utilisation de syst~mes lin~aires sur Z pour la paralI~lisation de programmes," ENSMP-CAI-87-E87, Ecole des Mines de Paris, Fontainebleau (France) (1987).
	4	Patrick Cousot , Nicolas Halbwachs, Automatic discovery of linear restraints among variables of a program, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.84-96, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512770]
	5	Ronald Gary Cytron, Compile-time scheduling and optimization for asynchronous machines (multiprocessor, compiler, parallel processing), 1984
	6	J. Davies, C. Huson, T. Macke, M. Wolfe, and B. Leasure, "The KAP/S-I: An Advznced Sourceto-Source Vectorizer-for the S-1 Mark IIa Supercomputer," lnt'l Conference on Parallel Processing, pp.833-835 (Aug. 1986).
	7	V. Dornic, "M~ithodes de partitionnement des r6seaux systoliques appliqudes ~ la triangularisation de matrice," Rapport de DEA, IRISA, Rennes (Juin 1987).
	8	R.J. Duffin, "On Fourier's Analysis of Linear Inequality Systems," Mathematical Programming Study 1, North-Holland (1974).
	9	D. Gannon, "Restructuring Nested Loops on the Alliant Cedar Cluster: A Case Study of Gaussian Elimination of Banded Matrices," CSRD document no. 543, University of llinois at Urbana Champaign (Feb. 1986).
	10	R. Cottlieb, K. Kimball, T. Jaskiewicz, and R. Swift, "A New Way To Speed Up a Supercompater," Electronics 58(30), pp.56-58 (July 1985).
	11	F. Irigoin and R. Triolet, "Supernodes and Alliant FX/8 Minisupercomputer," ENSMP-CAI-86-081, Ecole des Mines de Paris, Fontainebleau (France) (Aug. 1986).
	12	F. Irigoin and R. Triolet, "Computing Dependence Direction Vectors and Dependence Cones With Linear Systems," ENSMP-CAI-87-E94, Eicole des Mines de Paris, Fontainebleau (France) (,987).
	13	F. Irigoin, "Partitionnement des boucles imbriqudes : une technique d'optimisation pour les programmes scientifiques," Th~se de Doctorat d'Universit~, University! PARIS-VI, PARIS (1987).
	14	W. Jalby and U. Meier, "Optimizing Matrix Operation on a Parallel Multiprocessor with a Hierarchical Memory System," 1986 Int't Conference on Parallel Processing, pp.429-432 (Aug. 1986).
	15	Richard M. Karp , Raymond E. Miller , Shmuel Winograd, The Organization of Computations for Uniform Recurrence Equations, Journal of the ACM (JACM), v.14 n.3, p.563-590, July 1967 [doi>10.1145/321406.321418]
	16	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]
	17	Robert Henry Kuhn, Optimization and interconnection complexity for: parallel processors, single-stage networks, and decision trees, 1980
	18	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]
	19	A. Lichnewsky and F. Thoma,sset, "Techniques de Base sur l'Exploitation Automatique du Paralt~lisme dons tes Programmes," Calcul Parall~le h usage scientifique (Oct. 1985).
	20	Dan I Moldovan , Jose A. B Fortes, Partitioning and mapping algorithms into fixed size systolic arrays, IEEE Transactions on Computers, v.35 n.1, p.1-12, Jan. 1986 [doi>10.1109/TC.1986.1676652]
	21	C. Mongenet, "Une m~thode de conception d'algorithmes systoliques. R~sultats thdoriques et rdaIisation.," Th~se de Doctorat, INPL, Nancy (t985).
	22	J K Peir, Program partitioning and synchronization on multiprocessor systems, University of Illinois, Department of Computer Science, Urbana, IL, 1986
	23	J.-K. Peir and R. Cytron, "Minimum Distance: A Method for Partitioning Recurrences for Multiprocessors," 1987 Int'l Conference on Parallel Processing, pp.217-225 (Aug. 1987).
	24	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	25	Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.176-185, June 25-27, 1986, Palo Alto, California, United States
	26	Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
	27	M. J. Wolfe, "Advanced Loop interchanging," Int'l Conference on Parallel Processing, pp.536- 543 (Aug. lg86).