Computational Intelligence - May 2014 - 59
equal to or larger than k, choose a node
to spill into memory and remove the
spilled node and all its edges from the
interference graph. After removing a
node, the degrees of all its previous
neighbors are lowered, so that they can
be moved into the stack. Repeat the
above steps in the simplify phase until
the graph is empty. In the select phase,
nodes are popped up from the stack and
are colored one by one until the stack is
empty. Another widely used heuristic
algorithm is the optimistic coloring
heuristic (OCH) presented by Briggs et
al. [15, 18]. The OCH is an improvement to Chaitin's algorithm, which can
successfully resolve some graphs that
Chaitin's algorithm cannot [19]. The key
improvement of the OCH is on the
timing of making spill decisions: the
OCH makes spill decisions later than
Chaitin's in the process. In the simplify
phase, when the degrees of all nodes are
greater than k, the OCH algorithm
does not spill the node, but treats it as a
spill candidate, which may get a color
(register) in the select phase.
EAs are stochastic global optimization
methods, which have been widely used
in multi-objective optimization (e.g.,
[20-24]), image processing (e.g., [25]),
combinatorial optimization (e.g., [26]),
numerical optimization (e.g., [27]), graph
coloring (e.g., [28]), and other applications (e.g., [29-33]). For more comprehensive discussions about various applications of EAs, please refer to Ref.[34].
Topcuoglu et al. proposed a hybrid evolutionary algorithm (HEA) for the register allocation problem, that includes a
specialized conflict-free partition crossover (CFPX) and an efficient local search
method [16]. The HEA outperformed all
the previous algorithms in performance.
Memetic algorithms (MAs) are a
family of meta-heuristics that emphasize
on hybridization of different algorithmic
approaches for a given problem [35-39].
Ong et al. have shown that hybridization is an important feature in memetic
computing [37]. Zhu et al. hybridized
wrapper and filter methods for feature
selection to form a novel memetic
framework, which was shown to be efficient in microarray and hyperspectral
imagery datasets [40]. Ruiz-Torrubiano
and Suárez hybridized EAs, quadratic
programming, and specially devised
pruning heuristics for the selection of
cardinality constrained optimal portfolios
[41]. Unlike traditional EAs, MAs are
intrinsically concerned with exploiting
all domain-specific information about
the problem under study [42, 43]. Chia
et al. designed a miner into a memetic
algorithm for mining information to
improve the optimization process [43].
When described as a node-weighted
graph, it is obvious that there are two
types of information for the resource
allocation problem: one is the conflict
(edge) information and the other is the
costs (weight) of nodes. CFPX makes
full use of the conflict information but
neglects the cost information of the
nodes. However, minimizing the total
cost of the spilled variables is the optimization objective of the register allocation problem. The first motivation of
this paper is to hybridize the two types
of information and to provide a costoriented cross operator (COPX), that
can decrease the total cost of a solution
by making full use of the cost information along with the conflict information
of the nodes. It is also noticed that there
are two types of techniques in decoding
a chromosome in previous algorithms:
the conflict-based technique and the
cost-based technique [16]. The second
motivation is to hybridize the two types
of techniques in the decoding scheme.
This paper aims at providing a costoriented memetic algorithm (COMA)
for the resource allocation problem.
Detailed description of the COMA is
provided in Section II. Comparative
experiments are performed in Section
III. Section IV is the conclusion of this
paper. For simplicity, some notations
are introduced here. In EAs (including
both the HEA and COMA), an individual (e.g., S p ) is a partition of all the
nodes in k subsets for the resource
allocation problem, where k is the
number of resources. The k subsets of
an individual are called resource classes
denoted as R i, i = 1, f, k. In short,
S p = {R 1, f, R k} . A number of individuals construct the population. Some
times, the words "resource" and "node"
may be replaced by "register" and
"variable" respectively in the context
for convenience to compare with algorithms for register allocation. The number of conflicts (interferences) of node
v j in its own resource class is denoted
as Conf ^v j h, which is different from
the degree of a node in the interference graph. The cost (weight) of node
v j is denoted as Cost ^v j h . Similarly, the
sum of costs of the nodes in a node set
S is denoted as Cost ^S h .
II. Description of the Coma
Let Fitness (R i) be the fitness of R i, the
sum of Fitness (R i) for i = 1, f, k is the
fitness of the individual S p . The fitness
of the individuals determines which of
the two parents should be replaced by
their offspring via evolution after the
local search phase (see Section II.B). In
the local search phase, the fitness of the
resource classes determines the target
resource class for moving a node into
(see Section II.C). Even at the end of
the algorithm, the fitness of the final
chromosome determines which nodes
in the individual should be spilled. A
decoding scheme transforms an individual (chromosome) to the corresponding
solution and gets the fitness value. As
mentioned above, the fitness of an individual is the sum of the fitness of the
resource classes. So the techniques to
calculate the fitness value of a resource
class have an important effect on the
performance of the algorithm.
In general, it is not all of the nodes
(variables) in a resource class R i that can
obtain (share) a resource due to conflicts;
part of them have to be moved into a
spill set (SS Ri) such that the rest of the
nodes in R i are conflict-free. Fitness (R i)
is the sum of costs of the nodes in
SS Ri: Fitness (R i) = Cost (SS Ri) . Obviously, for a given resource class R i, different criterions to move nodes into
SS Ri will result in different Fitness (R i) .
A better approach will result in smaller
value of Fitness (R i) . In [16], Fitness (R i)
is calculated by the following equation:
Fitness (R i) = min {Fitness C (R i),
Fitness S (R i)}, (1)
may 2014 | IEEE ComputatIonal IntEllIgEnCE magazInE
59
Table of Contents for the Digital Edition of Computational Intelligence - May 2014
Computational Intelligence - May 2014 - Cover1
Computational Intelligence - May 2014 - Cover2
Computational Intelligence - May 2014 - 1
Computational Intelligence - May 2014 - 2
Computational Intelligence - May 2014 - 3
Computational Intelligence - May 2014 - 4
Computational Intelligence - May 2014 - 5
Computational Intelligence - May 2014 - 6
Computational Intelligence - May 2014 - 7
Computational Intelligence - May 2014 - 8
Computational Intelligence - May 2014 - 9
Computational Intelligence - May 2014 - 10
Computational Intelligence - May 2014 - 11
Computational Intelligence - May 2014 - 12
Computational Intelligence - May 2014 - 13
Computational Intelligence - May 2014 - 14
Computational Intelligence - May 2014 - 15
Computational Intelligence - May 2014 - 16
Computational Intelligence - May 2014 - 17
Computational Intelligence - May 2014 - 18
Computational Intelligence - May 2014 - 19
Computational Intelligence - May 2014 - 20
Computational Intelligence - May 2014 - 21
Computational Intelligence - May 2014 - 22
Computational Intelligence - May 2014 - 23
Computational Intelligence - May 2014 - 24
Computational Intelligence - May 2014 - 25
Computational Intelligence - May 2014 - 26
Computational Intelligence - May 2014 - 27
Computational Intelligence - May 2014 - 28
Computational Intelligence - May 2014 - 29
Computational Intelligence - May 2014 - 30
Computational Intelligence - May 2014 - 31
Computational Intelligence - May 2014 - 32
Computational Intelligence - May 2014 - 33
Computational Intelligence - May 2014 - 34
Computational Intelligence - May 2014 - 35
Computational Intelligence - May 2014 - 36
Computational Intelligence - May 2014 - 37
Computational Intelligence - May 2014 - 38
Computational Intelligence - May 2014 - 39
Computational Intelligence - May 2014 - 40
Computational Intelligence - May 2014 - 41
Computational Intelligence - May 2014 - 42
Computational Intelligence - May 2014 - 43
Computational Intelligence - May 2014 - 44
Computational Intelligence - May 2014 - 45
Computational Intelligence - May 2014 - 46
Computational Intelligence - May 2014 - 47
Computational Intelligence - May 2014 - 48
Computational Intelligence - May 2014 - 49
Computational Intelligence - May 2014 - 50
Computational Intelligence - May 2014 - 51
Computational Intelligence - May 2014 - 52
Computational Intelligence - May 2014 - 53
Computational Intelligence - May 2014 - 54
Computational Intelligence - May 2014 - 55
Computational Intelligence - May 2014 - 56
Computational Intelligence - May 2014 - 57
Computational Intelligence - May 2014 - 58
Computational Intelligence - May 2014 - 59
Computational Intelligence - May 2014 - 60
Computational Intelligence - May 2014 - 61
Computational Intelligence - May 2014 - 62
Computational Intelligence - May 2014 - 63
Computational Intelligence - May 2014 - 64
Computational Intelligence - May 2014 - 65
Computational Intelligence - May 2014 - 66
Computational Intelligence - May 2014 - 67
Computational Intelligence - May 2014 - 68
Computational Intelligence - May 2014 - 69
Computational Intelligence - May 2014 - 70
Computational Intelligence - May 2014 - 71
Computational Intelligence - May 2014 - 72
Computational Intelligence - May 2014 - Cover3
Computational Intelligence - May 2014 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com