The mesh of buses (MBUS) is a parallel computation model which consists of n x n processors, II row buses and n column buses but no local connections between two neighboring processors. As for deterministic (permutati...
详细信息
The mesh of buses (MBUS) is a parallel computation model which consists of n x n processors, II row buses and n column buses but no local connections between two neighboring processors. As for deterministic (permutation) routing on MBUSs, the known 1.5n upper bound appears to be hard to improve. Also, the information theoretic lower bound for any type of MBUS routing is 1.0n. In this paper, we present two randomized algorithms for MBUS routing. One of them runs in 1.4375n + o(n) steps with high probability. The other runs 1.25n + o(n) steps also with high probability but needs more local computation. (C) 2001 Elsevier Science B.V. All rights reserved.
The mesh of buses (MBUS) is a parallel computation model which consists of n x n processors, II row buses and n column buses but no local connections between two neighboring processors. As for deterministic (permutati...
详细信息
ISBN:
(纸本)3540648240
The mesh of buses (MBUS) is a parallel computation model which consists of n x n processors, II row buses and n column buses but no local connections between two neighboring processors. As for deterministic (permutation) routing on MBUSs, the known 1.5n upper bound appears to be hard to improve. Also, the information theoretic lower bound for any type of MBUS routing is 1.0n. In this paper, we present two randomized algorithms for MBUS routing. One of them runs in 1.4375n + o(n) steps with high probability. The other runs 1.25n + o(n) steps also with high probability but needs more local computation. (C) 2001 Elsevier Science B.V. All rights reserved.
Popular algorithms for feature matching and model extraction fall into two broad categories: generate-and-test and Hough transform variations. However, both methods suffer from problems in practical implementations. G...
详细信息
Popular algorithms for feature matching and model extraction fall into two broad categories: generate-and-test and Hough transform variations. However, both methods suffer from problems in practical implementations. Generate-and-test methods are sensitive to noise in the data. They often fail when the generated model fit is poor due to error in the data used to generate the model position. Hough transform variations are less sensitive to noise, but implementations for complex problems suffer from large time and space requirements and from the detection of false positives. This paper describes a general method for solving problems where a model is extracted from, or fit to, data that draws benefits from both generate-and-test methods and those based on the Hough transform, yielding a method superior to both. An important component of the method is the subdivision of the problem into many subproblems. This allows efficient generate-and-test techniques to be used, including the use of randomization to limit the number of subproblems that must be examined. Each subproblem is solved using pose space analysis techniques similar to the Hough transform, which lowers the sensitivity of the method to noise. This strategy is easy to implement and results in practical algorithms that are efficient and robust. We describe case studies of the application of this method to object recognition, geometric primitive extraction, robust regression, and motion segmentation.
This paper presents a simple atomic model of message-passing multicomputers. Within one synchronous time step each processor can receive one atomic message, perform local computation, and send one message. When severa...
详细信息
This paper presents a simple atomic model of message-passing multicomputers. Within one synchronous time step each processor can receive one atomic message, perform local computation, and send one message. When several messages are destined to the same processor, then one is transmitted and the rest are blocked. Blocked messages cannot be retrieved by their sending processors;each processor must wait for its blocked message to clear before sending more messages into the network. Depending on the traffic pattern, messages can remain blocked for arbitrarily long periods. The model is conservative when compared with existing message-passing systems. Nonetheless, we prove linear message throughput when destinations are chosen at random;this rigorously justifies an instance of folklore. Based on this result we also prove linear speedup for backtrack and branch- and-bound searches using simple randomized algorithms.
In the Internet, a group of replicated servers is commonly used in order to improve the scalability of network service. Anycast service is a new network service that can improve network load distribution and simplify ...
详细信息
In the Internet, a group of replicated servers is commonly used in order to improve the scalability of network service. Anycast service is a new network service that can improve network load distribution and simplify certain applications. In this paper, the authors described a simple anycast service model in the Internet without significant affecting the routing and protocol processing infrastructure that was already in place, and proposed an anycast QoS routing algorithm for this model. The algorithm used randomized method to balance network load and improve its performance. Several new techniques are proposed in the algorithm, first, theminimum hops for each node are used in the algorithm, which are used as metric for computing the probability of possible out links. The metric is pre computed for each node in the network, which can simplify the network complexity and provide the routing process with useful information. Second, randomness is used at the link level and depends dynamically on the routing configuration. This provides great flexibility for the routing process, prevents the routing process from overusing certain fixed routing paths, and adequately balances the delay of the routing path. the authors assess the quality of QoS algorithm in terms of the acceptance ratio on anycast QoS requests, and the simulation results on a variety of network topologies and on various parameters show that the algorithm has good performances and can balance network load effectively.
This paper shows that many robust control problems can be formulated as constrained optimization problems and can be tackled by using randomized algorithms. Two different approaches in searching reliable solutions to ...
详细信息
This paper shows that many robust control problems can be formulated as constrained optimization problems and can be tackled by using randomized algorithms. Two different approaches in searching reliable solutions to robustness analysis problems under constraints are proposed, and the minimum computational efforts for achieving certain reliability and accuracy are investigated and bounds for sample size are derived. Moreover, the existing order statistics distribution theory is extended to the general case in which the distribution of population is not assumed to be continuous and the order statistics is associated with certain constraints.
An automobile consists of a large number of component parts that must be assembled. Even if all parts precisely fit together, it is not clear whether they can be assembled or not. The process of finding a suitable ass...
详细信息
ISBN:
(纸本)3540673547
An automobile consists of a large number of component parts that must be assembled. Even if all parts precisely fit together, it is not clear whether they can be assembled or not. The process of finding a suitable assembly sequence, which can be performed in reality, is called assembly planning. We present our probabilistic motion planner RAMONA developed in cooperation with Audi AG, Germany, which is used within a digital mock-up project for checking the feasibility of assembly sequences. The heart of RAMONA is a probabilistic complete motion planner, together with an efficient local path planner. We describe the basic concepts of our algorithm and investigate some details of the local planner.
The quality of network services is directly affected by QoS routing algorithms,and QoS routing algorithms rely heavily on network state information specifying the resource availability at network nodes and *** practic...
详细信息
ISBN:
(纸本)0780363949
The quality of network services is directly affected by QoS routing algorithms,and QoS routing algorithms rely heavily on network state information specifying the resource availability at network nodes and *** practice,the network state information is not always accurate because it does not update in time. This paper proposes a randomized QoS routing algorithm on networks with inaccurate link-state information,and develops a simulation environment. Our algorithm reduces computational cost and protocol *** tests demonstrate that our algorithm performs very well in practice.
In this paper we study the problem of finding the k largest elements of n distinct real numbers. We give a pure combinatorial argument to prove that n + (k - 1)log n + O(1) queries are necessary for any deterministic ...
详细信息
In this paper we study the problem of finding the k largest elements of n distinct real numbers. We give a pure combinatorial argument to prove that n + (k - 1)log n + O(1) queries are necessary for any deterministic algorithm using parity tests only. We also present a randomized algorithm with error probability O(1/n(c)) using only O(log(2) n + k log n) parity tests, where c > 1 is any fixed constant. (C) 2000 Elsevier Science B.V. All rights reserved.
We present two randomized algorithms, one for message passing and the other for shared memory, that, with probability 1, schedule multiparty interactions in a strongly fair manner. Both algorithms improve upon a previ...
详细信息
We present two randomized algorithms, one for message passing and the other for shared memory, that, with probability 1, schedule multiparty interactions in a strongly fair manner. Both algorithms improve upon a previous result by Joung and Smolka (proposed in a shared-memory model, along with a straightforward conversion to the message-passing paradigm) in the following aspects: first, processes' speeds as well as communication delays need not be bounded by any predetermined constant. Secondly, our algorithms are completely decentralized, and the shared-memory solution makes use of only single-writer variables. Finally, both algorithms are symmetric in the sense that all processes execute the same code, and no unique identifier is used to distinguish processes. (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论