When the communication channels are subject to interruptions such as jamming, the coordination of the real time motions of distributed autonomous vehicles becomes a challenging problem, that differs significantly with...
详细信息
ISBN:
(纸本)354067442X
When the communication channels are subject to interruptions such as jamming, the coordination of the real time motions of distributed autonomous vehicles becomes a challenging problem, that differs significantly with fault tolerance communication problems such as reliable broadcast. In this paper, we investigate the issues on the maintenance of the coordination in spite of arbitrarily long interruptions to the communication.
Using a directed acyclic graph (dag) model of algorithms, we solve a problem related to precedence-constrained multiprocessor schedules for array computations: Given a sequence of dags and linear schedules parametrize...
详细信息
ISBN:
(纸本)0818684038
Using a directed acyclic graph (dag) model of algorithms, we solve a problem related to precedence-constrained multiprocessor schedules for array computations: Given a sequence of dags and linear schedules parametrized by n, compute a lower bound on the number of processors required by the schedule as a function of n. In our formulation, the number of tasks that are scheduled for execution during any fired time step is the number of non-negative integer solutions d(n) to a set of parametric linear Diophantine equations.: We illustrate an algorithm based on generating functions far constructing a formula for these numbers d(n). The algorithm has been implemented as a Mathematica program. An example run and the symbolic formula for processor lower bounds automatically produced by the algorithm for Gaussian Elimination is presented.
Experiments are a fundamental part of science. They are needed when the system under evaluation is too complex to be analytically described and they serve to empirically validate hypotheses. This work presents the exp...
详细信息
ISBN:
(纸本)9781479941162
Experiments are a fundamental part of science. They are needed when the system under evaluation is too complex to be analytically described and they serve to empirically validate hypotheses. This work presents the experimentation framework ExCovery for dependability analysis of distributed processes. It provides concepts that cover the description, execution, measurement and storage of experiments. These concepts foster transparency and repeatability of experiments for further sharing and comparison. ExCovery has been tried and refined in a manifold of dependability related experiments during the last two years. A case study is provided to describe service discovery (SD) as experiment process (EP). A working prototype for IP networks runs on the distributed Embedded System (DES) wireless testbed at the Freie Universitat Berlin.
Computing the configuration space obstacles is an important problem in spatial planning for robotics applications. In this paper, we present parallel algorithm for computing the configuration space obstacles by using ...
详细信息
Computing the configuration space obstacles is an important problem in spatial planning for robotics applications. In this paper, we present parallel algorithm for computing the configuration space obstacles by using hypercube multiprocessors. The digitized images of the obstacles and the robot are stored in an N × N image plane. An algorithm for handling robots whose shapes are arbitrary convex polygons was presented. Our algorithms take O(logN) time and O(1) space which is asymptotically optimal for hypercube computers.
This paper deals with the parallel implementation of reconstruction algorithms for functional imaging on a network of workstations (NOW). Algorithms which provide the best image quality are not used in clinical routin...
详细信息
ISBN:
(纸本)0818684038
This paper deals with the parallel implementation of reconstruction algorithms for functional imaging on a network of workstations (NOW). Algorithms which provide the best image quality are not used in clinical routine, because they have a runtime of up to 60 hours with real clinical data sets of several hundred megabytes. After giving an overview of currently used image reconstruction algorithms, we describe a general parallel implementation of these algorithms with almost linear speedup and high efficiency which cuts down the runtime to a feasible limit The high load which is caused by the parallel application conflicts with the predominantly interactive usage of clinical workstations, therefore we address load balancing with an application oriented, adaptive mechanism in order to preserve the ownership of workstations. Furthermore we explain how the integration of MATLAB and IDL based applications with a conventional distributed queuing system coes, can be achieved and why this significantly improves usage in clinical routine.
The inter-processor communication time is a major bottleneck for the distributed memory systems (DMSs) and can be reduced by having an efficient task partitioning and scheduling strategy. This paper deals with the sch...
详细信息
The inter-processor communication time is a major bottleneck for the distributed memory systems (DMSs) and can be reduced by having an efficient task partitioning and scheduling strategy. This paper deals with the scheduling issues and presents an algorithm to schedule tasks onto DMSs. The complexity of this algorithm is O(V2), where V is the number of nodes of the directed acyclic graph (DAG). This algorithm has been applied to some practical DAGs and the results obtained using this algorithm are very promising.
This paper presents a methodology to predict the execution time of massively parallel applications before any significant implementation actions are taken. This methodology captures the problem decomposition into task...
详细信息
ISBN:
(纸本)081864222X
This paper presents a methodology to predict the execution time of massively parallel applications before any significant implementation actions are taken. This methodology captures the problem decomposition into tasks and their precedence relationship, along with the computational and communication demands placed by the application on the underlying architecture. An example shows how the methodology may be used to study the effects of various data placement strategies, problem size, and number of processors for an LU factorization algorithm. The model predictions were validated with published experimental results on a Touchstone Delta machine.
Indexing multidimensional data is inherently complex leading to slow query processing. This behavior becomes more pronounced with the increase in database size and/or number of dimensions. In this paper, we address th...
详细信息
Indexing multidimensional data is inherently complex leading to slow query processing. This behavior becomes more pronounced with the increase in database size and/or number of dimensions. In this paper, we address this issue by processing an index structure in parallel. First, we study different ways of partitioning an index structure. We then propose efficient algorithms for processing each query in parallel on the index structure. Using these strategies, we parallelized two multidimensional index structures - R* and LIB and evaluated the performance gains for the Gazetteer and the Catalog data of the Alexandria Digital Library on the Meiko CS-2.
The proceedings contains 125 papers from the 12th International parallelprocessingsymposium and 9th symposium on parallel and distributedprocessing. Topics discussed include: broadcast on d-dimensional all-port and...
详细信息
The proceedings contains 125 papers from the 12th International parallelprocessingsymposium and 9th symposium on parallel and distributedprocessing. Topics discussed include: broadcast on d-dimensional all-port and wormhole-routed torus;time-step optimal broadcast;hiding communication latency;non-deterministic communication over synchronous channels;coarse-grain broadcast communication model;all-to-some personalized communication;distributed memory multiprocessors;sparse algorithms;processor-in-memory arrays;block-cyclic distribution;global communication optimization;compiler and runtime library approaches;parallel MATLAB compiler;and multi-port hypercubes message-passing parallel programs.
In this paper we use competitive analysis to study preemptive multiprocessor allocation policies for parallel jobs whose execution time is not known to the scheduler at the time of scheduling. The objective is to mini...
详细信息
In this paper we use competitive analysis to study preemptive multiprocessor allocation policies for parallel jobs whose execution time is not known to the scheduler at the time of scheduling. The objective is to minimize the makespan (i.e., the completion time of the last job to finish executing). We characterize a parallel job, Ji, by two parameters: its execution time, li, and its parallelism, Pi, which may vary over time. The preemption and reallocation of processors can take place at any time. We devise a preemptive policy which achieves the best possible competitive ratio and then derive upper and lower bounds for scheduling N parallel jobs on P processors.
暂无评论