arvind@utcsri.UUCP (Arvind Gupta) (02/10/87)
From: ihnp4!wucs1!wuccrc!jst@rsch.wisc.edu (Jon Turner) Subject: anyone heard of this problem? I have a student who is interested in register allocation on machines with multiple register types. As with most register allocation problems it can be formalized as a pebble game or a graph layout problem. The graph layout formulation of the particular version we're interested in goes like this. Given a directed tree T=(V,E) in which each internal node has two incoming edges and each node but the root has one outgoing edge, a subset B of E, (called the black edges, the others are white) and integers b and w. Is there a function f from V to the positive integers such that 1. f(u) < f(v) implies there is no path from v to u in T 2. for all i, |H(i)| <= b where H(i) = { (x,y) | (x,y) is in B and f(x) <= i < f(y) } 3. for all i, |J(i)| <= w where J(i) = { (x,y) | (x,y) is in E-B and f(x) <= i < f(y) } Restating, we want to know if there is a monotone layout of T such that the number of black edges crossing any point is at most b, and the number of white edges is at most w. If you replace T with a dag, the problem is NP-complete. This follows trivially from the NP-completeness of register allocation on dags with just one register type. The problem can be solved in polyomial time for trees with one register type, but the complexity of the version given here (trees with two register types) appears to be open. I would appreciate hearing from anyone who knows of any results for this problem. Thanks in advance. Jon Turner Washington University in St. Louis 314-889-6193 UUCP: jst@wucs.UUCP or ..!{ihnp4,seismo}!wucs!jst ARPANET: wucs!jst@seismo.ARPA CSNET: wucs!jst%seismo.ARPA@csnet-relay or wucs!jst.uucp%bbncv.ARPA@csnet-relay