W. Yang et al. / Future Generation Computer Systems 83 (2018) 250–268 253
Table 1
Main notations used in the paper.
Symbol Description Symbol Description
H Hypergraph (n
j
, v
i
) A pin
V Vertex set Π A partition
N Hyperedge set ω(v
i
) Weight of vertex v
i
K Total number of partitions ω(n
i
) Weight of hyperedge n
i
v
i
A vertex in the vertex set N
i
A subset of hyperedge set
n
i
A hyperedge in the hyperedge set W (N
i
) Weight of a hyperedge subset
Vertices(n
i
) Vertex set connected by net n
i
c(v
i
) Cost value of vertex v
i
Nets(v
i
) Hyperedge set connects vertex v
i
Λ(v
i
) Cardinality of partitions
σ
p
(v
i
) Number of nets connecting where v
i
locates
vertex v
i
in part p C(H, Π) Cutsize of hypergraph H
g
xy
(n
i
) Move gain if n
i
was to be moved under partition Π
from part N
x
to part N
y
State(n
i
) The part that n
i
locates
connects a subset of vertices. The set of nets that connect vertex v
i
is represented by Nets(v
i
). The vertices set connected by net n
j
is
denoted as Vertices(n
j
). A (n
j
, v
i
) tuple denotes a pin of n
j
where
v
i
∈ Vertices(n
j
). The nets n
i
and n
j
are said to be neighbors if
they have at least one common pin, i.e., Vertices(n
i
) ∩ Vertices(n
j
)
= ∅. The vertices v
i
and v
j
are neighbors of each other if they
are connected by at least one common net, i.e., Nets(v
i
) ∩ Nets(v
j
)
= ∅. The degree of a net n
j
is equivalent to the number of ver-
tices it connects,
Vertices(n
j
)
. The total number of pins |P| =
n
j
∈N
Vertices(n
j
)
denotes the size of a given hypergraph H.
A vertex weight value ω(v
i
) is related to each vertex v
i
, and a
hyperedge weight value ω(n
j
) is the total weight of the connected
vertices of net n
j
, i.e. ω(n
j
) =
v
i
∈Vertices(n
j
)
ω(v
i
).
Π =
{
N
1
, . . . , N
K
}
is a K -way hyperedge partition of H =
(
V, N
)
if each part N
K
is a nonempty subset of N , the parts are pair
wise disjoint, and the union of K parts is equivalent to N . The set
of vertices located in partition N
k
is represented by Vertices(N
k
),
and the set of nets that located in partition N
k
is denoted as
Nets(N
k
). The weight W(N
k
) of a part N
k
is the total weights of
the hyperedges in that partition, i.e., W (N
k
) =
nj∈N
k
w(n
j
). A
partition Π is regarded as balanced if each part N
k
∈ Π satisfies
the balance constraint:
W (N
k
) ≤ (1 + ϵ)W
avg
for k = 1, . . . , K , (1)
where W
avg
= W (N )/K and ϵ is the predetermined maximum
imbalance ratio.
In a partition Π, a vertex is said to be located in a part if it
is connected by at least one hyperedge in that part. The locality
set Λ(v
i
) of vertex v
i
is defined as the set of parts where v
i
is
located. The cardinality of locality set Λ(v
i
) of vertex v
i
is denoted
by λ(v
i
) =
|
Λ(v
i
)
|
, or λ
i
for short. This is equivalent to the number
of required copies for vertices v
i
. A vertex is cut or replicated if it
locates in more than one part (λ(v
i
) > 1), and uncut or single if it
locates in only one part (λ(v
i
) = 1). The set of vertices in cut state
within a partition Π is denoted as V
R
. Since the replicated vertices
are the channels through which the partitions communicate, the
communication cost is mainly related with these vertices. A cost
value c(v
i
) is related to every vertex v
i
, and the cost function for a
vertex set is denoted by c(V ) =
v
i
∈V
c
(
v
i
)
. We define two cutsize
metrics to measure the cost of a partition Π of hypergraph H. The
cutsize can take the form of (2) or (3).
C(H, Π ) =
v
i
∈V
R
c(v
i
) (2)
C(H, Π ) =
v
i
∈V
R
(λ(v
i
) − 1)c(v
i
). (3)
We define the cost definitions in (2) and (3) to be the cut-
vertex metric and the replica metric, respectively. Cutsize under
the cut-vertex metric calculates the total number of vertices which
are replicated, thus in cut state. For example, assuming that every
vertex weight value is assigned a unit value, the cutsize under cut-
vertex metric of Fig. 1 is 3, since the vertices v
2
, v
6
and v
7
are cut.
While cutsize under the replica metric counts the total number of
slave copies, a.k.a replicas. This represents the difference between
the number of total copies of vertices (that have been replicated)
and the number of vertices in cut state. For example, assuming
that every vertex weight value is assigned a unit value, the cutsize
under replica metric of Fig. 1 is 5, since the number of replicas of
vertices v
2
, v
6
and v
7
are 3, 1 and 1, respectively.
Now, we formulate the optimization problem as follows: Find
the optimal partitioning Π
⋆
such that:
Π
⋆
= arg min
Π
C(H, Π )
s.t. W (N
k
) ≤ (1 + ϵ)W
avg
for k = 1, . . . , K .
(4)
In other words, given a hypergraph H =
(
V, N
)
, balanced K -
way hyperedge partitioning can be defined as finding a K -way
partition Π =
{
N
1
, . . . , N
K
}
that aiming at minimizing the cutsize
(2) or (3) as the primary objective and maintaining the balance
constraint (1) as the secondary objective.
4. Proposed HEPart
In this section, we will present our proposed heuristic central-
ized hyperedge partitioning algorithm, namely HEPart.
4.1. Definition
In a K-way hyperedge partitioning Π =
{
N
1
, . . . , N
K
}
, a net
only belongs to one part, and a vertex can belong to more than
one part, if it is cut, and then replicated. An instance of a replicated
vertex is termed as replica. No more than one instance of a vertex
can belong to the same part. A vertex connects a set of nets, and the
number of nets connecting vertex v
i
in part p is denoted as σ
p
(v
i
).
According to the definitions, |Nets(v
i
)| = σ
1
(v
i
) + σ
2
(v
i
) + · · · +
σ
k
(v
i
).
We use the cut-state of a vertex to describe whether that vertex
is cut or not. A vertex v
i
in a K-way hyperedge partitioning is said
to be cut or exterior or replicated if there are two or more parts with
at least one hyperedge connecting this vertex, i.e. σ
p
(v
i
) > 0 and
σ
q
(v
i
) > 0 (1 ≤ p ≤ K , 1 ≤ q ≤ K , p = q). A vertex v
i
is said
to be uncut or interior to part N
p
if only part N
p
owns at least one
hyperedge connecting this vertex, i.e. σ
p
(v
i
) > 0 and σ
q
(v
i
) = 0
(1 ≤ p ≤ K , 1 ≤ q ≤ K , p = q).
HEPart attempts to improve the cutsize of a given K -way
partition in an iterative way, by manipulating the move operations
performed on the nets. Every net owns a move gain when it is
moved from one part to another part. The move gain is defined as
follows.
The move gain g
pq
(n
j
) of a net n
j
refers to the reduction in the
cutsize if n
j
was to be moved from part N
p
to part N
q
(1 ≤ p ≤
K , 1 ≤ q ≤ K , p = q). Regarding the cut-vertex cutsize metric, the
剩余18页未读，继续阅读
weixin_38722588
- 粉丝: 6
- 资源: 839
我的内容管理
展开
最新资源
- AirKiss技术详解：无线传递信息与智能家居连接
- Hibernate主键生成策略详解
- 操作系统实验：位示图法管理磁盘空闲空间
- JSON详解：数据交换的主流格式
- Win7安装Ubuntu双系统详细指南
- FPGA内部结构与工作原理探索
- 信用评分模型解析：WOE、IV与ROC
- 使用LVS+Keepalived构建高可用负载均衡集群
- 微信小程序驱动餐饮与服装业创新转型：便捷管理与低成本优势
- 机器学习入门指南：从基础到进阶
- 解决Win7 IIS配置错误500.22与0x80070032
- SQL-DFS：优化HDFS小文件存储的解决方案
- Hadoop、Hbase、Spark环境部署与主机配置详解
- Kisso：加密会话Cookie实现的单点登录SSO
- OpenCV读取与拼接多幅图像教程
- QT实战：轻松生成与解析JSON数据
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
