This paper presents an algorithm to process a multi-way join with load O(n/p(2/(alpha phi))) under the mpc model, where n is the number of tuples in the input relations, alpha the maximum arity of those relations, p t...
详细信息
ISBN:
(纸本)9781450383813
This paper presents an algorithm to process a multi-way join with load O(n/p(2/(alpha phi))) under the mpc model, where n is the number of tuples in the input relations, alpha the maximum arity of those relations, p the number of machines, and phi a newly introduced parameter called the generalized vertex packing number. The algorithm owes to two new findings. The first is a two-attribute skew free technique to partition the join result for parallel computation. The second is an isolated cartesian product theorem, which provides fresh graph-theoretic insights on joins with alpha >= 3 and generalizes an existing theorem on alpha = 2.
Massively parallel join algorithms have received much attention in recent years, while most prior work has focused on worst-optimal algorithms. However, the worst-case optimality of these join algorithms relies on har...
详细信息
ISBN:
(纸本)9781450362276
Massively parallel join algorithms have received much attention in recent years, while most prior work has focused on worst-optimal algorithms. However, the worst-case optimality of these join algorithms relies on hard instances having very large output sizes, which rarely appear in practice. A stronger notion of optimality is output-optimal, which requires an algorithm to be optimal within the class of all instances sharing the same input and output size. An even stronger optimality is instance-optimal, i.e., the algorithm is optimal on every single instance, but this may not always be achievable. In the traditional RAM model of computation, the classical Yannakakis algorithm is instance-optimal on any acyclic join. But in the massively parallel computation (mpc) model, the situation becomes much more complicated. We first show that for the class of r-hierarchical joins, instance-optimality can still be achieved in the mpc model. Then, we give a new mpc algorithm for an arbitrary acyclic join with load O(IN/p + root ***/p ), where IN, OUT are the input and output sizes of the join, and p is the number of servers in the mpc model. This improves the mpc version of the Yannakakis algorithm by anO(root OUT/IN) factor. Furthermore, we show that this is output-optimal when OUT = O(p center dot IN), for every acyclic but non-r-hierarchical join. Finally, we give the first output-sensitive lower bound for the triangle join in the mpc model, showing that it is inherently more difficult than acyclic joins.
Model Predictive Control (mpc) has been used in a wide range of application areas including chemical engineering, food processing, automotive engineering, aerospace, and metallurgy. An important limitation on the appl...
详细信息
ISBN:
(纸本)9781424453634
Model Predictive Control (mpc) has been used in a wide range of application areas including chemical engineering, food processing, automotive engineering, aerospace, and metallurgy. An important limitation on the application of mpc is the difficulty in completing the necessary computations within the sampling interval. Recent trends in computing hardware towards greatly increased parallelism offer a solution to this problem. This paper describes modeling and analysis tools to facilitate implementing the mpc algorithms on parallel computers, thereby greatly reducing the time needed to complete the calculations. The use of these tools is illustrated by an application to a class of mpc problems.
暂无评论