论文标题
卵石和I/O下限的DAG访问方法
The DAG Visit approach for Pebbling and I/O Lower Bounds
论文作者
论文摘要
我们介绍了定向的无环dag $ g =（v，e）$的$ r $ - 访问的概念，这是符合给定规则$ r $的dag的顶点的序列。规则$ r $为每个顶点$ v \在v $中指定一个$ r $ $ $ $的（即时）的（直接）前任的集合：在访问$ v $之前，至少必须访问其启用套件之一。特殊情况是$ r^{（top）} $ - 规则（或拓扑规则），唯一的启用集是所有前任的集合，$ r^{（sin）} $ - rule（或，singleton规则），为此，启用集是包含一个准确的单元。 DAG $ G $，$ b_ {r} \ left（g \右）$的$ r $ - 限制复杂性是最小整数$ b $，因此在每个阶段都有一个$ r $ b $，在每个阶段，对于最多$ b $，尚未访问过的$ b $。通过对已知结果的重新重新制定，可以表明，dag $ g $的边界复杂性是反向dag的卵子数量的下限，$ g^r $。可以根据$ r^{（sin）} $ - 边界复杂性来施放几个已知的卵石下限。 I/O下限的访问分区技术，该技术概括了Hong和Kung在其经典论文“ I/O复杂性：Red-Blue Pebble Game”中引入的$ S $分区I/O技术。访问分区的方法可为某些DAG产生紧密的I/O边界，而这些DAG的$ S $分区技术只能产生$ω（1）$下限。
We introduce the notion of an $r$-visit of a Directed Acyclic Graph DAG $G=(V,E)$, a sequence of the vertices of the DAG complying with a given rule $r$. A rule $r$ specifies for each vertex $v\in V$ a family of $r$-enabling sets of (immediate) predecessors: before visiting $v$, 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 $r$-boundary complexity of a DAG $G$, $b_{r}\left(G\right)$, is the minimum integer $b$ such that there is an $r$-visit where, at each stage, for at most $b$ 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 $G$ is a lower bound to the pebbling number of the reverse DAG, $G^R$. Several known pebbling lower bounds can be cast in terms of the $r^{(sin)}$-boundary complexity. A visit partition technique for I/O lower bounds, which generalizes the $S$-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.
