5564142
Provable algorithms for parallel generalized sweep scheduling
Abstract We present provably efficient parallel algorithms for sweep scheduling, which is a commonly used technique in radiation transport problems, and involves inverting an operator by iteratively sweeping across a mesh from multiple directions. Each sweep involves solving the operator locally at each cell. However, each direction induces a partial order in which this computation can proceed. On a distributed computing system, the goal is to schedule the computation, so that the length of the schedule is minimized. Due to efficiency and coupling considerations, we have an additional constraint, namely, a mesh cell must be processed on the same processor along each direction. Problems similar in nature to sweep scheduling arise in several other applications, and here we formulate a combinatorial generalization of this problem that captures the sweep scheduling constraints,and call it the generalized sweep scheduling problem. Several heuristics have been proposed for this problem; see [S. Pautz, An algorithm for parallel S n sweeps on unstructured meshes, Nucl. Sci. Eng. 140 (2002) 111–136; S. Plimpton, B. Hendrickson, S. Burns, W. McLendon, Parallel algorithms for radiation transport on unstructured grids, Super Comput. (2001)] and the references therein; but none of these have provable worst case performance guarantees. Here we present a simple, almost linear time randomized algorithm for the generalized sweep scheduling problem that (provably) gives a schedule of length at most O ( log 2 n ) times the optimal schedule for instances with n cells, when the communication cost is not considered, and a slight variant, which coupled with a much more careful analysis, gives a schedule of (expected) length O ( log m log log log m ) times the optimal schedule for m processors. These are the first such provable guarantees for this problem. The algorithm can be extended with an additional multiplicative factor in the case when we have inter-processor communication latency, in the models of Rayward-Smith [UET scheduling with inter-processor communication delays, Discrete Appl. Math. 18 (1) (1987) 55–71] and Hwang et al. [Scheduling precedence graphs in systems with inter-processor communication times, SIAM J. Comput. 18(2) (1989) 244–257]. Our algorithms are extremely simple, and use no geometric information about the mesh; therefore, these techniques are likely to be applicable in more general settings. We also design a priority based list schedule using these ideas, with the same theoretical guarantee, but much better performance in practice; combining this algorithm with a simple block decomposition also lowers the overall communication cost significantly. Finally, we perform a detailed experimental analysis of our algorithm. Our results indicate that the algorithm compares favorably with the length of the schedule produced by other natural and efficient parallel algorithms proposed in the literature [S. Pautz, An Algorithm for parallel S n sweeps on unstructured meshes, Nucl. Sci. Eng. 140 (2002) 111–136; S. Plimpton, B. Hendrickson, S. Burns, W. McLendon, Parallel algorithms for radiation transport on unstructured grids, Super Comput. (2001)].
47278894
Equilibria in Topology Control Games for Ad Hoc Networks
We study topology control problems in ad hoc networks where network nodes get to choose their power levels in order to ensure desired connectivity properties. Unlike most other work on this topic, we assume that the network nodes are owned by different entities, whose only goal is to maximize their own utility that they get out of the network without considering the overall performance of the network. Game theory is the appropriate tool to study such selfish nodes: we define several topology control games in which the nodes need to choose power levels in order to connect to other nodes in the network to reach their communication partners while at the same time minimizing their costs. We study Nash equilibria and show that—among the games we define—these can only be guaranteed to exist if each network node is required to be connected to all other nodes (we call this the Strong Connectivity Game). For a variation called Connectivity Game, where each node is only required to be connected (possibly via intermediate nodes) to a given set of nodes, we show that Nash equilibria do not necessarily exist. We further study how to find Nash equilibria with incentive-compatible algorithms and compare the cost of Nash equilibria to the cost of a social optimum, which is a radius assignment that minimizes the total cost in a network where nodes cooperate. We also study variations of the games; one where nodes not only have to be connected, but k-connected, and one that we call the Reachability Game, where nodes have to reach as many other nodes as possible, while keeping costs low. We extend our study of the Strong Connectivity Game and the Connectivity Game to wireless networks with directional antennas and wireline networks, where nodes need to choose neighbors to which they will pay a link. Our work is a first step towards game-theoretic analyses of topology control in wireless and wireline networks.
213611
Covering rectilinear polygons with axis-parallel rectangles
We give an O( log n) factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. This is the first polynomial time approximation algorithm for this problem with an o(log n) approximation factor. 1. Introduction. We consider the problem of covering rectilinear polygons with axis-parallel rectangles. Given a rectilinear polygon P with complexity n (complexity refers to the minimum of the number of vertical edges and the number of horizontal edges in the polygon), this problem requires determining the minimum number of axis-parallel rectangles whose union covers P. The polygon P may have holes in it. Applications. Cheng, Iyengar, and Kashyap (5) showed that this problem has applications to image compression. They claim that representing an image using a rectangle covering of its white pixels gives compression superior to that achieved by quadtrees. It also has applications to printing integrated circuits (9). Hardness. Much effort has gone into determining the computational complexity of this problem. In spite of this, the exact complexity of this problem has remained open for many years and continues to do so. Masek (19) showed that this problem is NP-complete. Later, Culberson and Reckhow (6) used a clever reduction from 3-SAT to show that this is the case even when P has no holes. The next natural question is whether the number of rectangles needed to cover P can be computed approximately. Berman and Dasgupta (2) showed that this problem is MaxSNP-Hard for polygons with holes, ruling out the possibility of a polynomial time approximation scheme. Approximation results. Note that the rectangle covering problem is a special case of the general set covering problem. Therefore, it admits an approximation algorithm with a performance guarantee of O(log n), using the greedy scheme due to Johnson (10) and Lovasz (16). This was the best approximation factor known for the rectangle covering problem until now. Further, it is known that the general set covering problem cannot be approximated any better, modulo constant terms, unless NP = P (17, 18). However, this proof of hardness assumes certain properties about the set system which do not hold for the rectangle covering problem. In this paper, we address the issue of whether the Ω(log n) approximation factor barrier can be broken in polynomial time for the rectangle covering problem. There seem to be only a few examples of nontrivial algorithms breaking this
39362526
Main memory database recovery algorithms and their performance
In main memory systems recovery becomes more complex mainly due to the volatility of main memory and the elimination of the separation of data storage (disk) and data processing locations (main memory). In a disk based database system, it is the disk copy that represents the stable database restored after a system failure; but in MDBSs, the main memory copy of the database must be recovered. The paper discusses the recovery issues in MDBSs and presents a somewhat detailed performance study of two recovery algorithms, one using a shadow approach and the other update-in-place.<<ETX>>
10015251
Repartitioning of Adaptive Meshes: Experiments with Multilevel Diffusion
For a large class of irregular grid applications, the structure of the mesh changes from one phase of the computation to the next. Eventually, as the graph evolves, the adapted mesh has to be repartitioned to ensure good load balance. If this new graph is partitioned from scratch, it will lead to an excessive migration of data among processors. In this paper, we present a new scheme for computing repartitionings of adaptively refined meshes. This scheme performs diffusion of vertices in a multilevel framework and minimizes vertex movement without significantly compromising the edge-cut.
38254367
Parallel formulations of decision-tree classification algorithms
Classification decision tree algorithms are used extensively for data mining in many domains such as retail target marketing, fraud detection, etc. Highly parallel algorithms for constructing classification decision trees are desirable for dealing with large data sets in reasonable amount of time. Algorithms for building classification decision trees have a natural concurrency, but are difficult to parallelize due to the inherent dynamic nature of the computation. We present parallel formulations of classification decision tree learning algorithm based on induction. We describe two basic parallel formulations. One is based on Synchronous Tree Construction Approach and the other is based on Partitioned Tree Construction Approach. We discuss the advantages and disadvantages of using these methods and propose a hybrid method that employs the good features of these methods. Experimental results on an IBM SP-2 demonstrate excellent speedups and scalability.
6412662
Abstraction and control for groups of fully-actuated planar robots
This paper shows how a large number of robots can be coordinated by designing control laws on a small dimensional manifold, independent on the number and ordering of the robots. The small dimensional description of the team has a product structure of a Lie group, which captures the dependence of the ensemble on world frame, and a shape manifold, which is an intrinsic description of the team. We design decoupled controls for group and shape. The individual control laws which are mapped to the desired collective behavior can be realized by feedback depending only on the current state of the robot and the state on the small dimensional manifold, so that the robots have to broadcast their states and only have to listen to some coordinating agent with small bandwidth.