Article

The meeting graph: a new model for loop cyclic register allocation

Authors:

Christine Eisenbeis,

Sylvain Lelait,

Bruno MarmolAuthors Info & Claims

PACT '95: Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques

Pages 264 - 267

Published: 27 June 1995 Publication History

Abstract

No abstract available.

References

[1]

A. Apostolico, M. J. Atallah, and S. E. Hambrusch. New clique and independent set algorithms for circle graphs. Discrete Applied Mathematics, 36:1--24, 1992.

Digital Library

Google Scholar

[2]

G. J. Chaitin. Register allocation and spilling via graph coloring. In ACM Sigplan'82 Symposium on Compiler Construction, volume 17 of Sigplan Notices, pages 98--105, June 1982.

Digital Library

Google Scholar

[3]

B. Dupont de Dinechin. An introduction to simplex scheduling. In PACT' 94, Montreal, Quebec, August 1994.

Digital Library

Google Scholar

[4]

C. Eisenbeis, W. Jalby, and A. Lichnewsky. Compiler techniques for optimizing memory and register usage on the Cray-2. International Journal on High Speed Computing; 2(2), June 1990.

Google Scholar

[5]

C. Eisenbeis, S. Lelait, and B. Marmol. The meeting graph: a new framework for loop register allocation. Rapport de recherche, INRIA, 1995.

Digital Library

Google Scholar

[6]

M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou. The complexity of coloring circular arcs and chords. SIAM J. Alg. Disc. Meth., 1(2):216--227, June 1980.

Digital Library

Google Scholar

[7]

M. C. Golumbic and R. Shamir. Complexity and algorithms for reasoning about time: a graph-theoretic approach. Technical Report DIMACS-TR-91-54, Rutgers University, 1991.

Google Scholar

[8]

L. J. Hendren, G. R. Gao, E. R. Altman, and C. Mukerji. A register allocation framework based on hierarchical cyclic interval graphs. In Compiler Construction'92, October 1992.

Digital Library

Google Scholar

[9]

Richard A. Huff. Lifetime-sensitive modulo scheduling. In SIGPLAN-PLDI'93, June 1993.

Digital Library

Google Scholar

[10]

M. S. Lam. Software Pipelining: An Effective scheduling Technique for VLIW Machines. In SIGPLAN-PLDI'88, Atlanta, June 1988.

Digital Library

Google Scholar

[11]

E. L. Lawler. Optimal Cycles in Doubly Weighted Directed Linear Graphs. In Theory of Graphs - International Symposium, Rome, 1966.

Google Scholar

[12]

Q. Ning and G. R. Gao. A novel framework of register allocation for software pipelining. In POPL'93, 1993.

Digital Library

Google Scholar

[13]

B. R. Rau, M. Lee, P. P. Tirumalai, and M. S. Schlansker. Register allocation for software pipelined loops. In SIGPLAN-PLDI'92, July 1992.

Digital Library

Google Scholar

[14]

J. Wang, A. Krall, M. A. Ertl, and C. Eisenbeis. Registers Requirement for Exposing Loops' Maximal Instruction Level Parallelism. In MICRO 27, San Jose, California, 1994.

Google Scholar

Cited By

View all

Su XLiao XXue JReddi VSmith ATang L(2017)Automatic generation of fast BLAS3-GEMM: a portable compiler approachProceedings of the 2017 International Symposium on Code Generation and Optimization10.5555/3049832.3049846(122-133)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3049832.3049846
Chen LMitra T(2014)Graph Minor Approach for Application Mapping on CGRAsACM Transactions on Reconfigurable Technology and Systems10.1145/26552427:3(1-25)Online publication date: 3-Sep-2014
https://dl.acm.org/doi/10.1145/2655242
Barik RZhao JSarkar V(2013)A decoupled non-SSA global register allocation using bipartite liveness graphsACM Transactions on Architecture and Code Optimization10.1145/254410110:4(1-24)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1145/2544101
Show More Cited By

Index Terms

The meeting graph: a new model for loop cyclic register allocation
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Small Edge Sets Meeting all Triangles of a Graph

It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2t edges that shares an edge with each triangle of G. In this paper, we prove this ...
Meeting facilitation: process versus content interventions

This article examines the impacts of two types of meeting facilitation that occur in traditional and GSS environments: process and content facilitation. Based on existing facilitation, leadership, and GSS research, and structuration theory, we ...
Using the meeting graph framework to minimise kernel loop unrolling for scheduled loops
LCPC'09: Proceedings of the 22nd international conference on Languages and Compilers for Parallel Computing

This paper improves our previous research effort [1] by providing an efficient method for kernel loop unrolling minimisation in the case of already scheduled loops, where circular lifetime intervals are known. When loops are software pipelined, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PACT '95: Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques

June 1995

324 pages

ISBN:0897917456

Chairmen:
Lubomir Bic
Univ. of California, Irvine
,
Paraskevas Evripidou
Univ. of Cyprus
,
Wim Böhm
Colorado State Univ.
,
Jean-Luc Gaudiot
Univ. of Southern California

Publisher

IFIP Working Group on Algol

United Kingdom

Publication History

Published: 27 June 1995

Check for updates

Qualifiers

Article

Conference

PACT95

Sponsor:

SIGARCH

PACT95: International Conference on Parallel Architectures and Compilation Techniques

June 27 - 29, 1995

Limassol, Cyprus

Acceptance Rates

Overall Acceptance Rate 121 of 471 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Su XLiao XXue JReddi VSmith ATang L(2017)Automatic generation of fast BLAS3-GEMM: a portable compiler approachProceedings of the 2017 International Symposium on Code Generation and Optimization10.5555/3049832.3049846(122-133)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3049832.3049846
Chen LMitra T(2014)Graph Minor Approach for Application Mapping on CGRAsACM Transactions on Reconfigurable Technology and Systems10.1145/26552427:3(1-25)Online publication date: 3-Sep-2014
https://dl.acm.org/doi/10.1145/2655242
Barik RZhao JSarkar V(2013)A decoupled non-SSA global register allocation using bipartite liveness graphsACM Transactions on Architecture and Code Optimization10.1145/254410110:4(1-24)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1145/2544101
Touati SBrault FDeschinkel KDupont de Dinechin B(2011)Efficient Spilling Reduction for Software Pipelined Loops in Presence of Multiple Register Types in Embedded VLIW ProcessorsACM Transactions on Embedded Computing Systems (TECS)10.1145/2043662.204367110:4(1-25)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1145/2043662.2043671
Nash NLelait SGregg D(2009)Efficiently implementing maximum independent set algorithms on circle graphsJournal of Experimental Algorithmics (JEA)10.1145/1412228.145526513(1.9-1.34)Online publication date: 23-Feb-2009
https://dl.acm.org/doi/10.1145/1412228.1455265
Bachir MGregg DTouati S(2009)Using the meeting graph framework to minimise kernel loop unrolling for scheduled loopsProceedings of the 22nd international conference on Languages and Compilers for Parallel Computing10.1007/978-3-642-13374-9_19(278-292)Online publication date: 8-Oct-2009
https://dl.acm.org/doi/10.1007/978-3-642-13374-9_19
Bachir MTouati SCohen A(2008)Post-pass periodic register allocation to minimise loop unrolling degreeACM SIGPLAN Notices10.1145/1379023.137567743:7(141-150)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1379023.1375677
Bachir MTouati SCohen AFlautner KRegehr J(2008)Post-pass periodic register allocation to minimise loop unrolling degreeProceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems10.1145/1375657.1375677(141-150)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1375657.1375677
De La Luz VKandemir M(2004)Array Regrouping and Its Use in Compiling Data-Intensive Embedded ApplicationsIEEE Transactions on Computers10.1109/TC.2004.125578753:1(1-19)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1109/TC.2004.1255787
Llosa JValero MAyguadé EMelvin SBeaty S(1996)Heuristics for register-constrained software pipeliningProceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture10.5555/243846.243892(250-261)Online publication date: 2-Dec-1996
https://dl.acm.org/doi/10.5555/243846.243892

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Small Edge Sets Meeting all Triangles of a Graph

Meeting facilitation: process versus content interventions

Using the meeting graph framework to minimise kernel loop unrolling for scheduled loops