The DAG Visit approach for Pebbling and IO Lower Bounds

2025-05-02 0 0 902.8KB 31 页 10玖币

侵权投诉

The DAG Visit approach for Pebbling

and I/O Lower Bounds

Gianfranco Bilardi !

University of Padova, Department of Information Engineering, Italy

Lorenzo De Stefani1!

Department of Computer Science, Brown University, United States of America

Abstract

We introduce the notion of an

-visit of a Directed Acyclic Graph DAG

(V, E)

, a sequence of

the vertices of the DAG complying with a given rule

. A rule

speciﬁes for each vertex

v∈V

family of

-enabling sets of (immediate) predecessors: before visiting

, at least one of its enabling

sets must have been visited. Special cases are the

r(top)

-rule (or, topological rule), for which the

only enabling set is the set of all predecessors and the

r(sin)

-rule (or, singleton rule), for which the

enabling sets are the singletons containing exactly one predecessor. The

-boundary complexity of a

DAG

br(G)

, is the minimum integer

such that there is an

-visit where, at each stage, for at

most

of the vertices yet to be visited an enabling set has already been visited. By a reformulation

of known results, it is shown that the boundary complexity of a DAG

is a lower bound to the

pebbling number of the reverse DAG,

. Several known pebbling lower bounds can be cast in

terms of the r(sin)-boundary complexity. The main contributions of this paper are as follows:

An existentially tight

O√doutn

upper bound to the

r(sin)

-boundary complexity of any DAG

of nvertices and out-degree dout.

An existentially tight

OÄdout

log2dout log2nä

upper bound to the

r(top)

-boundary complexity of any

DAG. (There are DAGs for which

r(top)

provides a tight pebbling lower bound, whereas

r(sin)

does not.)

A visit partition technique for I/O lower bounds, which generalizes the

-partition I/O technique

introduced by Hong and Kung in their classic paper “I/O complexity: The Red-Blue pebble

game”. The visit partition approach yields tight I/O bounds for some DAGs for which the

S-partition technique can only yield an Ω (1) lower bound.

2012 ACM Subject Classiﬁcation Theory of computation →Design and analysis of algorithms

Keywords and phrases Pebbling, Directed Acyclic Graph, Pebbling number, I/O complexity

Funding

Gianfranco Bilardi: This work was supported in part by the Italian National Center for

HPC, Big Data, and Quantum Computing; by MIUR, the Italian Ministry of Education, University

and Research, under PRIN Project n. 20174LF3T8 AHeAD (Eﬃcient Algorithms for HArnessing

Networked Data); and by the University of Padova, under Project CPGA

(Parallel and Hierarchical

Computing: Architectures, Algorithms, and Applications).

1Corresponding author

arXiv:2210.01897v1 [cs.DS] 4 Oct 2022

2 The DAG Visit approach for Pebbling and I/O Lower Bound

1 Introduction

Avisit of a Directed Acyclic Graph (DAG) is a sequence of all its vertices. We consider

diﬀerent types of visits, where a type is speciﬁed by a visit rule

, a prescription that a

vertex

can be visited only after all the vertices in one of a given family of enabling sets of

predecessors of

have been visited. One example is the singleton visit rule,

r(sin)

, where

each vertex is enabled by each singleton containing one of its predecessors. Breadth First

Search (BFS) and Depth First Search (DFS) visits are special cases of

r(sin)

-visits. Another

example is the topological visit rule,

r(top)

, where a vertex

is enabled only by the set of all

its predecessors. The

r(top)

-visits are exactly the topological orderings of the DAG. Many

other rules are possible; for example, the enabling sets of a vertex could be those with a

majority of its predecessors.

In this work, we investigate the

-boundary complexity of DAGs. The boundary com-

plexity of

(

), is the minimum integer

such that there exists an

-visit where, at

each stage, for at most

of the vertices yet to be visited an enabling set has already been

visited. By a reformulation of the results of Bilardi, Pietracaprina, and D’Alberto [

], in

terms of the familiar concept of visit, we show that the boundary complexity of a DAG

a lower bound to the pebbling number

(

)of its reverse DAG, i.e.,

(

)

≥br

(

). The

pebbling number of a DAG provides a measure of the space required by a computation with

data dependences described by that DAG, in the pebble game framework, introduced by

Friedman [

], Paterson and Hewitt [

], Hopcroft, Paul and Valiant [

]. While a pebbling

game resembles a visit where each vertex can be visited multiple times, the relation between

pebbling number and boundary complexity is rather subtle, as indicated by the fact that it

involves graph reversal. Several pebbling lower bounds arguments in the literature (examples

are mentioned in Section 3) can indeed be recast in terms of the

r(sin)

-boundary complexity,

thus achieving some uniﬁcation in the derivation of these results. In this context, it is natural

to explore the potential of the visit approach to yield signiﬁcant pebbling lower bounds for

arbitrary DAGs.

Main contributions:

We begin our study with the singleton rule and show that, for any

DAG

with

nodes and out-degree at most

dout

br(sin)

(

)

≤

√doutn

. As a universal

bound, this result cannot be improved, as shown by matching existential lower bounds. With

respect to pebbling, there are DAGs such that

br(sin)

(

) = Ω(

(

)), for which the singleton

rule provides asymptotically tight pebbling lower bounds. But there are also DAGs with

very low

r(sin)

-boundary complexity, where the reverse DAG has high pebbling number. For

example, Paul, Tarjan, and Celoni [

] introduced a DAG, which we will denote as

PTC

, of

vertices and in-degree

din

(1), and proved that

(

PTC

) = Θ(

log n

). This DAG can be

easily modiﬁed to yield a DAG

PTC+

with

(

PTC+

) = Θ(

log n

)and

br(sin)

((

PTC+

)

) = 2,

thus exhibiting a large gap between boundary and pebbling complexity.

It is natural to wonder whether other visit rules can lead to better bounds, whereas

the singleton rule does not. We have then turned our attention to the topological rule

showing that for any DAG

with

nodes and out-degree at most

dout ≥

2the boundary

br(top)

(

) =

dout−1

log2dout log2n

. This bound is existentially tight. It indicates that the potential of

the topological rule for pebbling lower bounds is limited. However, the topological technique

is not subsumed by the singleton one, as we exhibit DAGs for which topological visits yield

a tight pebbling lower bound, whereas singleton visits yield a trivial lower bound.

For an arbitrary visit rule,

, we show that

(

)

≤

(

dout −

+ 1, where

is the length

of the longest paths of

. This result is also existentially tight and is consistent with the

G. Bilardi and L. De Stefani 3

known pebbling upper bound,

(

)

≤

(

dout −

+ 1. It remains an open question whether

a tight boundary-complexity lower bound to the pebbling number can always be found by

tailoring the choice of

to the DAG, or there are DAGs for which the two metrics exhibit a

gap for any rule.

We also exploit visits to analyze the I/O complexity of a DAG

IO (M, G)

, pioneered by

Hong and Kung in [

]. This quantity is the minimum number of accesses to the second level

of a two-level memory, with the ﬁrst level (i.e.,, the cache) of size

, required to compute

Such computation can be modeled by a game with pebbles of two colors. Let

(

G, M

)be the

smallest integer

such that the vertices of

can be topologically partitioned into a sequence

subsets, each with a dominator set and minimum set no larger than

. (

is a dominator

if the vertices of

can be computed from those of

. The minimum set of

contains

those vertices of

with no successor in

.) Then,

IO (G, M)≥M

(

)

−

1) [

Dominators play a role in the red-blue game (where pebbles are initially placed on input

vertices which, if unpebbled, cannot be replebbled), but not in standard pebbling (where a

pebble can be placed on an input vertex at any time, hence a dominator of what is yet to be

computed needs not be currently in memory). Intuitively, each segment of a computation

must read a dominator set Dof the vertices being computed and at least |D| − Mof these

reads must be to the second level of the memory. It is also shown in [

] that the minimum

set, say

, of a segment of the computation must be present in memory at the end of such

segment, so that at least

|Y| − M

of its elements must have been written to the second

level of the memory. In the visit perspective, the minimum set emerges as the boundary of

topological visits, capturing a space requirement at various points of the computation. In

addition to providing some intuition on minimum sets, this insight suggests a generalization

of the partitioning technique to any type of visit. In fact, the universal upper bounds on visit

boundaries mentioned above do indicate that the singleton rule has the potential to yield

better lower bounds than the topological one. Following this insight, we have developed the

visit partition technique. For some DAGs for which

partitions can only lead to a trivial,

Ω(1), lower bound, visit partitions yield a much higher and tight lower bound.

Further related work:

Since the work of Hong and Kung [

], I/O complexity has attracted

considerable attention, thanks also to the increasing impact of the memory hierarchy on

the performance of all computing systems, from general purpose processors, to accelerators

such as GPUs, FPGAs, and Tensor engines. Their

-partition technique has been the

foundation to lower bounds for a number of important computational problems, such as the

Fast Fourier Transform [

], the deﬁnition-based matrix multiplication [

], sparse

matrix multiplication [

], Strassen’s matrix multiplication [

] (this work also introduces

the “G-ﬂow” technique, based on the Grigoriev ﬂow of functions [

], to lower bound the

size of dominator sets), and various integer multiplication algorithms [

]. Ballard et

al. [

] generalized the results on matrix multiplication of [

], by means of the approach

proposed by Irony, Toledo, and Tiskin in [

] based on the Loomis-Whitney geometric

theorem [

], which captures a trade-oﬀ between dominator size and minimum set size. The

same papers present tight I/O complexity bounds for various linear algebra algorithms for

LU/Cholesky/LDLT/QR factorization and eigenvalues and singular values computation.

After four decades from its introduction, the S-partition technique [

] is still the state of

the art for I/O lower bounds that do hold when recomputation (the repeated evaluation of the

same DAG vertex) is allowed. Savage [

] has proposed the S-span technique, as “ a slightly

weaker but simpler version of the Hong-Kung lower bound on I/O time”[

]. The S-covering

technique [

], which merges and extends aspects from both [

] and [

], is in principle

4 The DAG Visit approach for Pebbling and I/O Lower Bound

more general than the

-partition technique and leads to interesting resources-augmentation

considerations; however, we are not aware of its application to speciﬁc DAGs.

A number of I/O lower bound techniques have been proposed and applied to speciﬁc

DAG algorithms for executions without recomputations. These include the edge expansion

technique of [

], the path routing technique of [

], and the closed dichotomy width technique

of [

]. While the emphasis in this paper is on models with recomputation, Section 5.5 does

show how the visit partition technique specializes when recomputation is not allowed.

Automatic techniques to derive I/O lower bounds - with and without recomputation -

have been developed, in part with the goal of automatic performance evaluation and code

restructuring for improving temporal locality in programs by Elango et al. [

], Carpenter et

al. [12], Olivry et al. [24].

Paper organization:

The visit framework is formulated in Section 2. The relationship

between boundary complexity and pebbling number is discussed in Section 3. Section 4

presents universal upper bounds to the boundary complexity. Section 5 develops the visit

partition technique for I/O lower bounds. Conclusions are oﬀered in Section 6.

2 Visits of a DAG

ADirected Acyclic Graph (DAG)

(V, E)

consists of a ﬁnite set of vertices

and of a set

of directed edges

E⊆V×V

, which form no directed cycle. We say that edge

(u, v)∈E

is directed from

. We let

pre (v)

{u|

(

u, v

)

∈E}

denote the set of predecessors of

and

suc (v)

{u|

(

v, e

)

∈E}

denote the set of its successors. The maximum in-degree

(resp. out-degree) of

is deﬁned as

din

maxv∈V|pre (v)|

(resp.,

dout

maxv∈V|suc (v)|

Further, we denote as

des (v)

(resp.,

anc (v)

) of

’s descendants (resp., ancestors), that is, the

vertices that can be reached from (resp., can reach)

with a directed path. Given

V0⊆V

we say that G0= (V0, E ∩(V0×V0)) is the sub-DAG of Ginduced by V0.

Let

(v1, . . . , vi, . . . , vj, . . . , vk)

be a sequence of vertices with

|φ|

. Let

[

] =

for 1

≤i≤j≤k

, we denote as

(

i..j

] =

(vi+1, . . . , vj)

the inﬁx from the

-th element

excluded to the

-th included. If

j < i

(

i..j

]is the empty sequence. Depending on the

context, we sometimes interpret a sequence as the set of items appearing in the sequence.

Avisit of a DAG

(V, E)

is a sequence of all its vertices, without repetitions, complying

with a visit rule:

IDeﬁnition 1

(Visit rule)

Avisit rule for a DAG

(V, E)

is a function

V→

where

r(v)⊆

pre(v)

is a non-empty family of sets of predecessors of

called enablers of

The set of visit rules of Gis denoted as R(G).

Intuitively, a rule

r∈ R(G)

permits a vertex

to be visited only after at least one of its

enablers Q∈r(v)has been entirely visited.

IDeﬁnition 2

(

-sequence and

-visit)

Given a DAG

(V, E)

and a visit rule

r∈ R(G)

a sequence

of distinct vertices is an

-sequence of

if, for every 1

≤i≤ |ψ|

, the preﬁx

..i −

1] includes an enabler

Q∈r(ψ[i])

. The

-sequences with

|ψ|

are called

-visits

and their set is denoted as Ψr(G).

Clearly, any preﬁx of an

-sequence is an

-sequence. Of particular interest are the “

topological visit rule” deﬁned as

r(top)(v)

{pre (v)}

and the “singleton visit rule” deﬁned

as r(sin)(v) = {{u} | u∈pre (v)}if |pre (v)|>0and r(sin)(v) = {∅} otherwise.

A vertex

not contained in

, but enabled by some non-empty set

included in

, is

considered to be a “boundary” vertex.

G. Bilardi and L. De Stefani 5

IDeﬁnition 3

(Boundary of an

-sequence)

Given a DAG

(V, E)

r∈ R(G)

, and an

r-sequence ψof G, the r-boundary of ψis deﬁned as the set:

Br(ψ) = {v∈V\ψ| ∃Q6=∅s.t. Q ∈r(v)∧Q⊆ψ}.

Input vertices are never contained in the boundary of any sequence since their only enabler

is the empty set.

IDeﬁnition 4

(Boundary complexity)

The

-boundary complexity of an

-sequence

deﬁned as:

br(ψ) = max

i∈{1,...,|ψ|} |Br(ψ[1..i])|.

The

-boundary complexity of

is deﬁned as the minimum

-boundary complexity among

all r-visits of G:

br(G) = min

ψ∈Ψr(G)br(ψ).

By deﬁnition, for any

r∈ R(G)

, any

ψ∈

r(top)(G)

and, for any

= 1

, . . . , n

we have

Br(top)(ψ[1..i]) ⊆Br(ψ[1..i])

; thus,

br(top)(ψ)≤br(ψ)

. Similarly, if

∅ ∈ r

(

)only when

has no predecessors, then br(ψ)≤br(sin)(ψ), for any ψ∈Ψr(G).

3 Boundary complexity and pebbling number

In this section, we discuss an interesting relationship between the pebbling number of a

DAG

(V, E)

and the boundary complexity of its reverse DAG

(V, ER)

, where

ER={(u, v)|(v, u)∈E}, which can prove useful in deriving pebbling lower bounds.

ITheorem 5

(Pebbling lower bound)

Let

be the reverse of

(V, E)

. Then, for any

r∈ R(GR), the pebbling number of Gsatisﬁes:

p(G)≥br(GR) = min

ψ∈Ψr(GR)br(ψ).

Proof.

Consider a pebbling schedule

which uses

pebbles, and any visit rule

r∈ R(GR)

. The proof proceeds by constructing an

-visit

whose

-boundary

complexity is itself bounded from above by

. Let

denote the total number of steps of the

pebbling

. The construction of

proceeds iteratively starting from the end of the pebbling

schedule

to its beginning: Let

denote the vertex which is being pebbled at the

-th step

for 1

≤i≤T

, then the same vertex

is visited in

if and only if all the vertices

in at least one of the subsets in the enabling family

h(v)

have already been visited. By

construction, ψis indeed a valid r-visit of GR.

By the construction of the reverse DAG

, the set of the successors of any vertex

v∈V

corresponds to the set of predecessors of

. By the rules of the pebble game,

when considering a complete pebbling schedule for

, each vertex

v∈V

is pebbled in for the

ﬁrst time before any of its successors. As each enabler in

r(v)

is a subset of the predecessors

and, hence, a subset of the successors of

, each vertex will surely be visited

at the step corresponding to its ﬁrst pebbling in

unless it has already been visited.

This allows us to conclude that all vertices of GRare indeed visited by ψ.

Let

[

]denote the vertex being pebbled at the

-th step of the pebbling schedule, for

≤t≤T

. In order to prove that the statement holds, it must be shown that, ﬁxed an index

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

TheDAGVisitapproachforPebblingandI/OLowerBoundsGianfrancoBilardi!UniversityofPadova,DepartmentofInformationEngineering,ItalyLorenzoDeStefani1!DepartmentofComputerScience,BrownUniversity,UnitedStatesofAmericaAbstractWeintroducethenotionofanr-visitofaDirectedAcyclicGraphDAGG=(V;E),asequenceofthevertic...

展开>> 收起<<

The DAG Visit approach for Pebbling and IO Lower Bounds.pdf

共31页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

The DAG Visit approach for Pebbling and IO Lower Bounds

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: