基于超完美图着色的存储分配算法

为了提高性能,一些应用需要在编译时对主存进行针对性的管理.提出了基于超完美图的主存分配方法,其基本思想是通过生命周期分割将一般的相干图转换为超完美图,从而可以使用已有的线性时间的区间着色算法完成主存的分配.分别基于自底向上的积极生命周期分割策略和自顶向下的被动生命周期分割策略,实现了两个分配算法.初步评测表明,我们的分配算法是有效的编译时管理主存手段.     

SRF Coloring: Stream Register File Allocation via Graph Coloring

Stream Register File (SRF) is a large on-chip memory of the stream processor and its efficient management is essential for good performance. Current stream programming languages expose the management of SRF to the programmer, incurring heavy burden on the programmer and bringing difficulties to inheriting the legacy codes. SF95 is the language developed for FT64 which is the first 64-bit stream processor designed for scientific applications. SF95 conceals SRF from the programmer and leaves the management...     

多目标优化的图的邻点可区别均匀V-全染色算法

图的邻点可区别均匀V-全染色（AVDEVTC）是指在满足邻点可区别V-全染色的基础上,还要保证每种颜色的使用次数相差不超过1,把完成AVDEVTC所用的最少颜色称为图的邻点可区别均匀V-全色数（AVDEVTCN）。针对图的AVDEVTC问题,提出了一种基于多目标优化的染色算法。设计了一个总目标函数和四个子目标函数,在染色矩阵上通过每个点的颜色集合的迭代交换操作,使得每个子目标函数都达到最优,进而满足总目标函数的要求,完成染色。经过理论分析和实验对比表明,8个顶点以内的所有简单连通图都存在AVDEVTC,且图的AVDEVTCN介于最大度加1与最大度加2之间。实验结果表明,该染色算法能够在较短的时间内正确地计算出1000个顶点以内的图的AVDEVTCN。     

A graph coloring heuristic using partial solutions and a reactive tabu scheme

Most of the recent heuristics for the graph coloring problem start from an infeasible k-coloring (adjacent vertices may have the same color) and try to make the solution feasible through a sequence of color exchanges. In contrast, our approach (called FOO-PARTIALCOL), which is based on tabu search, considers feasible but partial solutions and tries to increase the size of the current partial solution. A solution consists of k disjoint stable sets (and, therefore, is a feasible, partial k-coloring) and a set of uncolored vertices. We introduce a reactive tabu tenure which substantially enhances the performance of both our heuristic as well as the classical tabu algorithm (called TABUCOL) proposed by Hertz and de Werra [Using tabu search techniques for graph coloring, Computing 1987;39:345–51]. We will report numerical results on different benchmark graphs and we will observe that FOO-PARTIALCOL, though very simple, outperforms TABUCOL on some instances, provides very competitive results on a set of benchmark graphs which are known to be difficult, and outperforms the best-known methods on the graph flat300_28_0. For this graph, FOO-PARTIALCOL finds an optimal coloring with 28 colors. The best coloring achieved to date uses 31 colors. Algorithms very close to TABUCOL are still used as intensification procedures in the best coloring methods, which are evolutionary heuristics. FOO-PARTIALCOL could then be a powerful alternative. In conclusion FOO-PARTIALCOL is one of the most efficient simple local search coloring methods yet available.     

VColor*: a practical approach for coloring large graphs

Graph coloring has a wide range of real world applications, such as in the operations research, communication network, computational biology and compiler optimization fields. In our recent work [1], we propose a divide-andconquer approach for graph coloring, called VColor. Such an approach has three generic subroutines. (i) Graph partition subroutine: VColor partitions a graph G into a vertex cut partition (VP), which comprises a vertex cut component (VCC) and small non-overlapping connected components (CCs). (ii) Component coloring subroutine: VColor colors the VCC and the CCs by efficient algorithms. (iii) Color combination subroutine: VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs (CCBs). VColor has revealed some major bottlenecks of efficiency in these subroutines. Therefore, in this paper, we propose VColor*, an approach which addresses these efficiency bottlenecks without using more colors both theoretically and experimentally. The technical novelties of this paper are the following. (i) We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm. (ii) For sparse CCs, we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case, while preserving the approximation ratio. (iii) We propose a distributed graph coloring algorithm. Our extensive experimental evaluation on real-world graphs confirms the efficiency of VColor*. In particular, VColor* is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets, respectively. VColor* also significantly outperforms the state-ofthe- art graph coloring methods.     

Linear time self-stabilizing colorings

We propose two new self-stabilizing distributed algorithms for proper Δ+1 (Δ is the maximum degree of a node in the graph) colorings of arbitrary system graphs. Both algorithms are capable of working with multiple type of daemons (schedulers) as is the most recent algorithm by Gradinariu and Tixeuil [OPODIS'2000, 2000, pp. 55-70]. The first algorithm converges in O(m) moves while the second converges in at most n moves (n is the number of nodes and m is the number of edges in the graph) as opposed to the O(Δ×n) moves required by the algorithm by Gradinariu and Tixeuil [OPODIS'2000, 2000, pp. 55-70]. The second improvement is that neither of the proposed algorithms requires each node to have knowledge of Δ, as is required by Gradinariu and Tixeuil [OPODIS'2000, 2000, pp. 55-70]. Further, the coloring produced by our first algorithm provides an interesting type of coloring, called a Grundy Coloring [Jensen and Toft, Graph Coloring Problems, 1995].     

Coloring inductive graphs on-line

In this paper we consider the problem of on-line graph coloring. In an instance of on-line graph coloring, the nodes are presented one at a time. As each node is presented, its edges to previously presented nodes are also given. Each node must be assigned a color, different from the colors of its neighbors, before the next node is given. LetA(G) be the number of colors used by algorithmA on a graphG and letx(G) be the chromatic number ofG. The performance ratio of an on-line graph coloring algorithm for a class of graphsC is max_{G C(A(G)/(G))}. We consider the class ofd-inductive graphs. A graphG isd-inductive if the nodes ofG can be numbered so that each node has at mostd edges to higher-numbered nodes. In particular, planar graphs are 5-inductive, and chordal graphs arex(G)-inductive. First Fit is the algorithm that assigns each node the lowest-numbered color possible. We show that ifG isd-inductive, then First Fit usesO(d logn) colors onG. This yields an upper bound ofo(logn) on the performance ratio of First Fit on chordal and planar graphs. First Fit does as well as any on-line algorithm ford-inductive graphs: we show that, for anyd and any on-line graph coloring algorithmA, there is ad-inductive graph that forcesA to use (d logn) colors to colorG. We also examine on-line graph coloring with lookahead. An algorithm is on-line with lookaheadl, if it must color nodei after examining only the firstl+i nodes. We show that, forl/logn, the lower bound ofd logn colors still holds.This research was supported by an IBM Graduate Fellowship.     

Solving the Register Allocation Problem for Embedded Systems Using a Hybrid Evolutionary Algorithm

Embedded systems are unique in the challenges they present to application programmers, such as power and memory space constraints. These characteristics make it imperative to design customized compiler passes. One of the important factors that shape runtime performance of a given embedded code is the register allocation phase of compilation. It is crucial to provide aggressive and sophisticated register allocators for embedded devices, where the excessive compilation time can be tolerated due to high demand on code quality. Failing to do a good job on allocating variables to registers (i.e., determining the set of variables to be stored in the limited number of registers) can have serious power, performance, and code size consequences. This paper explores the possibility of employing a hybrid evolutionary algorithm for register allocation problem in embedded systems. The proposed solution combines genetic algorithms with a local search technique. The algorithm exploits a novel, highly specialized crossover operator that takes into account domain-specific information. The results from our implementation based on synthetic benchmarks and routines that are extracted from well-known benchmark suites clearly show that the proposed approach is very successful in allocating registers to variables. In addition, our experimental evaluation also indicates that it outperforms a state-of-the-art register allocation heuristic based on graph coloring for most of the cases experimented.     

Acyclic coloring of graphs of maximum degree five: Nine colors are enough

An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic number of G is the least number of colors necessary to acyclically color G. In this paper, we show that any graph of maximum degree 5 has acyclic chromatic number at most 9, and we give a linear time algorithm that achieves this bound.     

Coloring large graphs based on independent set extraction

This paper presents an effective approach (EXTRACOL) to coloring large graphs. The proposed approach uses a preprocessing method to extract large independent sets from the graph and a memetic algorithm to color the residual graph. Each preprocessing application identifies, with a dedicated tabu search algorithm, a number of pairwise disjoint independent sets of a given size in order to maximize the vertices removed from the graph. We evaluate EXTRACOL on the 11 largest graphs (with 1000 to 4000 vertices) of the DIMACS challenge benchmarks and show improved results for four very difficult graphs (DSJC1000.9, C2000.5, C2000.9, C4000.5). The behavior of the proposed algorithm is also analyzed.     

Elimination of parallel copies using code motion on data dependence graphs

Register allocation regained much interest in recent years due to the development of decoupled strategies that split the problem into separate phases: spilling, register assignment, and copy elimination.Traditional approaches to copy elimination during register allocation are based on interference graphs and register coalescing. Variables are represented as nodes in a graph, which are coalesced, if they can be assigned the same register. However, decoupled approaches strive to avoid interference graphs and thus often resort to local recoloring.A common assumption of existing coalescing and recoloring approaches is that the original ordering of the instructions in the program is not changed. This work presents an extension of a local recoloring technique called Parallel Copy Motion. We perform code motion on data dependence graphs in order to eliminate useless copies and reorder instructions, while at the same time a valid register assignment is preserved. Our results show that even after traditional register allocation with coalescing our technique is able to eliminate an additional 3% (up to 9%) of the remaining copies and reduce the weighted costs of register copies by up to 25% for the SPECINT 2000 benchmarks. In comparison to Parallel Copy Motion, our technique removes 11% (up to 20%) more copies and up to 39% more of the copy costs.     

A note on 2-facial coloring of plane graphs

An l-facial coloring of a plane graph is a vertex coloring such that any two different vertices joined by a facial walk of length at most l receive distinct colors. It is known that every plane graph admits a 2-facial coloring using 8 colors [D. Král, T. Madaras, R. Škrekovski, Cyclic, diagonal and facial coloring, European J. Combin. 3-4 (26) (2005) 473-490]. We improve this bound for plane graphs with large girth and prove that if G is a plane graph with girth g?14 (resp. 10, 8) then G admits a 2-facial coloring using 5 colors (resp. 6, 7). Moreover, we give exact bounds for outerplanar graphs and K₄-minor free graphs.     

Algorithmic Aspects of Acyclic Edge Colorings

Abstract. A proper coloring of the edges of a graph G is called acyclic if there is no two-colored cycle in G . The acyclic edge chromatic number of G , denoted by a'(G) , is the least number of colors in an acyclic edge coloring of G . For certain graphs G , a'(G)\geq Δ(G)+2 where Δ(G) is the maximum degree in G . It is known that a'(G)≤ Δ + 2 for almost all Δ -regular graphs, including all Δ -regular graphs whose girth is at least cΔ log Δ . We prove that determining the acyclic edge chromatic number of an arbitrary graph is an NP-complete problem. For graphs G with sufficiently large girth in terms of Δ(G) , we present deterministic polynomial-time algorithms that color the edges of G acyclically using at most Δ(G)+2 colors.     

Register allocation via coloring

Register allocation may be viewed as a graph coloring problem. Each node in the graph stands for a computed quantity that resides in a machine register, and two nodes are connected by an edge if the quantities interfere with each other, that is, if they are simultaneously live at some point in the object program. This approach, though mentioned in the literature, was never implemented before. Preliminary results of an experimental implementation in a PL/I optimizing compiler suggest that global register allocation approaching that of hand-coded assembly language may be attainable.     

A Coloring Problem With Restrictions of Adjacent Colors

The coloring problem is a well-known problem of graphs. This paper considers a new coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, called coloring problem with restrictions of adjacent colors . The restriction of adjacent colors can be represented by a graph H called a restriction graph , i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices of the edge cannot be used for adjacent vertices. This paper shows some properties of the new coloring problem. It also presents a necessary and sufficient condition such that a restriction graph H cannot be replaced with a more simple graph, when H is a cactus with no 3-cycle.     

A self-stabilizing algorithm for coloring planar graphs

Summary This paper describes an algorithm for coloring the nodes of a planar graph with no more than six colors using a self-stabilizing approach. The first part illustrates the coloring algorithm on a directed acyclic version of the given planar graph. The second part describes a selfstabilizing algorithm for generating the directed acyclic version of the planar graph, and combines the two algorithms into one. Sukumar Ghosh received his Ph.D. degree in Computer Science from Calcutta University in 1971. From 1969 to 1984, he taught at Jadavpur University, Calcutta. During 1976–77, he was a Fellow of the Alexander von Humboldt Foundation at the University of Dortmund, Germany. Since 1984, he is with the Department of Computer Science of the University of Iowa. His current research interests are in the areas of Distributed Systems, Petri Nets and Self-Stabilizating Systems. Mehmet Hakan Karaata received the Sc. B. degree in Computer Science and Engineering from Hacettepe University in Turkey in 1987, and the M.S. degree in Computer Science from the University of Iowa in 1990. He is currently studying towards his Ph.D. at the same university. His research interests are in the areas of Distributed Systems, Self-Stabilizing Systems and Database Systems.This research was supported in part by the National Science Foundation under grant CCR-9109078, and the Old Gold Summer Fellowship of the University of Iowa. An abstract of this paper was presented at the 29th Allerton Conference on Control, Communication & Computing in October 1991.     

随机图的点可区别V-全染色算法

图[G]的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求所有顶点的色集合也不相同,所用的最少颜色数称为图[G]的点可区别V-全色数。根据点可区别V-全染色的约束规则,设计了一种启发式的点可区别V-全染色算法,该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果,对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明,该算法有很好的执行效率并可以得到给定图的点可区别V-全色数,并且算法的时间复杂度不超过[O(n3)]。     

An effective heuristic algorithm for sum coloring of graphs

Given an undirected graph G=(V,E), the minimum sum coloring problem (MSCP) is to find a legal vertex coloring of G, using colors represented by natural numbers (1,2,…) such that the total sum of the colors assigned to the vertices is minimized. In this paper, we present EXSCOL, a heuristic algorithm based on independent set extraction for this NP-hard problem. EXSCOL identifies iteratively collections of disjoint independent sets of equal size and assign to each independent set the smallest available color. For the purpose of computing large independent sets, EXSCOL employs a tabu search based heuristic. Experimental evaluations on a collection of 52 DIMACS and COLOR2 benchmark graphs show that the proposed approach achieves highly competitive results. For more than half of the graphs used in the literature, our approach improves the current best known upper bounds.     

On the complexity of some colorful problems parameterized by treewidth

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph.

1.

The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C_v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C_v, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W[1]-hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W[1]-hard, parameterized by treewidth.

2.

An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W[1], parameterized by the treewidth plus the number of colors. We also show that a list-based variation, List Equitable Coloring is W[1]-hard for forests, parameterized by the number of colors on the lists.

3.

The list chromatic numberχ_l(G) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list L_v of colors, where each list has length at least r, there is a choice of one color from each vertex list L_v yielding a proper coloring of G. We show that the problem of determining whether χ_l(G)?r, the List Chromatic Number problem, is solvable in linear time on graphs of constant treewidth.

     

Graphs with maximum degree 6 are acyclically 11-colorable

An acyclic k-coloring of a graph G is a proper vertex coloring of G, which uses at most k colors, such that the graph induced by the union of every two color classes is a forest. In this note, we prove that every graph with maximum degree six is acyclically 11-colorable, thus improving the main result of Yadav et al. (2009) [11].