1,721,057 research outputs found
The complexity of deterministic PRAM simulation on distributed memory machines
No full textIn this paper we present lower and upper bounds for the deterministic simulation of a Parallel Random Access Machine (PRAM) withn processors andm variables on a Distributed Memory Machine (DMM) withp ≤n processors. The bounds are expressed as a function of the redundancyr of the scheme (i.e., the number of copies used to represent each PRAM variable in the DMM), and become tight for anym polynomial in n and r=Θ(1)
Optimal Many-to-One Routing on the Mesh with Constant Queues
No full textWe present randomized and deterministic algorithms for many-to-one
packet routing on an n-node two-dimensional mesh under the
store-and-forward model. We consider the general
instance of many-to-one routing where each node is the source (resp.,
destination) of l (resp., k) packets, for arbitrary values of
l and k. All our algorithms run in optimal O(\sqrt{lkn})
time and use queues of only constant size at each node to store
packets in transit. The randomized algorithms, however, are simpler to
implement. Our result closes a gap in the literature, where
time-optimal algorithms using constant-size queues were known only for
the special cases l=1 and l=k
Efficient Incremental Mining of Top-K Frequent Closed Itemsets
No full textIn this work we study the mining of top- frequent closed itemsets, a
recently proposed variant of the classical problem of mining frequent
closed itemsets where the support threshold is chosen as the maximum
value sufficient to guarantee that the itemsets returned in output be
at least . We discuss the effectiveness of parameter in
controlling the output size and develop an efficient algorithm
for mining top- frequent closed itemsets in order of decreasing
support, which exhibits consistently better performance than the best
previously known one, attaining substantial improvements in some
cases. A distinctive feature of our algorithm is that it allows the
user to dynamically raise the value with no need to restart the
computation from scratch
Tight bounds on deterministic PRAM emulations with constant redundancy
No full textIn this paper we present lower and upper bounds for the deterministic emulation of a Parallel Random Access Machine (PRAM) with n processors and m variables on a Distributed Memory Machine (DMM) with n processors. The bounds are expressed as a function of the redundancy r of the scheme (i.e., the number of copies used to represent each PRAM variable in the DMM), and become tight for any m polynomial in n and r=Θ(1)
A new scheme for the deterministic simulation of PRAMs in VLSI
No full textA deterministic scheme for the simulation of (n, m)-PRAM computation is devised. Each PRAM step is simulated on a bounded degree network consisting of a mesh-of-trees (MT) of siden. The memory is subdivided inn modules, each local to a PRAM processor. The roots of the MT contain these processors and the memory modules, while the otherO(n 2) nodes have the mere capabilities of packet switchers and one-bit comparators. The simulation algorithm makes a crucial use of pipelining on the MT, and attains a time complexity ofO(log2 n/log logn). The best previous time bound wasO(log2 n) on a different interconnection network withn processors. While the previous simulation schemes use an intermediate MPC model, which is in turn simulated on a bounded degree network, our method performs the simulation directly with a simple algorithm
Implementing Shared Memory on Clustered Machines (Extended Abstract)
No full textWe present a general deterministic scheme to implement a shared memory abstraction on any distributed-memory machine which exhibits a clustered structure. More specifically, we develop a memory distribution strategy and an access protocol for the Decomposable BSP (D-BSP), a generic machine model whose bandwidth/latency parameters can be instantiated to closely reflect the characteristics of machines that admit a hierarchical decomposition into independent clusters. Our scheme achieves provably optimal slowdown for those machines where delays due to latency dominate over those due to bandwidth limitations. For machines where this is not the case, the slowdown is a mere logarithmic factor away from the natural bandwidth-based lower bound. An important feature of the scheme is that it can be made fully constructive for small memory sizes, while for larger sizes it relies solely on nonconstructive graphs of weak expansion
On the Expansion and Diameter of Bluetooth-Like Topologies
No full textThe routing capabilities of an interconnection network are strictly related to its bandwidth and latency characteristics, which are in turn quantifiable through the graph-theoretic concepts of expansion and diameter. This paper studies expansion and diameter of a family of subgraphs of the random geometric graph, which closely model the topology induced by the device discovery phase of Bluetooth-based ad hoc networks. The main feature modeled by any such graph, denoted as BT(r(n),c(n)), is the small number c(n) of links that each of the n devices (vertices) may establish with those located within its communication range r(n). First, tight bounds are proved on the expansion of BT(r(n),c(n)) for the whole set of functions r(n) and c(n) for which connectivity has been established in previous works. Then, by leveraging on the expansion result, nearly-tight upper and lower bounds on the diameter of BT(r(n),c(n)) are derived. In particular, we show asymptotically tight bounds on the diameter when the communication range is near the minimum needed for connectivity, the typical scenario considered in practical applications
A probabilistic simulation of prams on a bounded degree network
No full textA simulation scheme for (n, m)-PRAM computation is devised, based on an interconnection network organized in the form of a mash-of-trees (MT) of side n. The m memory cells are subdivided in n modules, each local to one of the n PRAM processors. The MT roots contain these processors and the memory modules, while the other MT nodes have the mere functions of packet switchers. Time complexity is probabilistically analyzed. It is shown that, as n goes to infinity, the slow-down for each step of PRAM computation is O(log n) with probability tending to 1 and that, as either n or k go to infinity, the simulation time for k consecutive steps is O(k log n) with probability tending to 1. Area requirements are finally studied according to the VLSI grid mode
Deterministic Routing of h-relations on the Multibutterfly
No full textIn this paper we devise an optimal deterministic algorithm for routing h-relations on-line on an N-input/output multibutterfly. The algorithm, which is obtained by generalizing the circuit-switching techniques of [3], routes any h-relation with messages of X bits, in O \Gamma h(X + log N ) \Delta steps in the bit model, and in O \Gamma hdX= log Ne + log N \Delta communication steps in the word model. Unlike other recently developed algorithms, our algorithm does not need extra levels of expanders, hence minimizes the layout area. Moreover, the network topology does not depend on h. 1. Introduction A communication network can be regarded as a graph whose nodes represent input/output ports or internal switches, and whose edges represent direct links between pairs of nodes. A routing problem for such a network is defined as a set of point-to-point messages to be delivered from the inputs to the outputs. A solution to a routing problem requires selecting a path in the network for e..
- …
