14860014
Self-scheduling on distributed-memory machines
The authors present a general approach of self-scheduling a non-uniform parallel loop on a distributed-memory machine. The approach has two phases: a static scheduling phase and a dynamic scheduling phase. In addition to reduce scheduling overhead, using the static scheduling phase allows the data needed by the statically scheduled iterations to be prefetched. The dynamic scheduling phase balances the workload. Data distribution methods for self-scheduling are also the focus of this paper. The authors classify the data distribution methods into four categories and present partial duplication, a method that allows the problem size to grow linearly in the number of processors. The experiments conducted on a 64-node NCUBE show that as much as 79% improvement is achieved over static scheduling on the generation of a false-color image.
28349358
Data Parallel Program Design
We have shown how graphical languages such as CODE/ROPE and PPSE can be used to design SIMD or data parallel programs. The advantages of this approach are machine independence, design clarity, automated program analysis, and accelerated software development. The disadvantages are that many problems remain in this approach such as how to reduce design clutter, how to automate optimal processor mapping, and how to perform messagepassing optimization. More work is needed before this approach can be used in the design of large-scale applications, but we believe the approach is promising. The main contribution is to show how the simple ideas of stencils, stream generators, and replicators can be used effectively to extend the classical dataflow design paradigm into the data parallel design paradigm. While more work is needed, these three ideas lead to greater expressiveness of design. The PPSE toolset currently does much of the mapping, scheduling, and automatic code generation described in this paper. However, PPSE does not currently handle data parallel programming. Work is progressing toward a full implementation of these ideas. Even so, PPSE has been invaluable for performing a variety of what-if analyses on parallel programs. Insights have been gained with this approach that would not be possible with a purely textual representation of the parallel program.
9690577
Automatic Camera Calibration and Scene Reconstruction with Scale-Invariant Features
The goal of our research is to robustly reconstruct general 3D scenes from 2D images, with application to automatic model generation in computer graphics and virtual reality. In this paper we aim at producing relatively dense and well-distributed 3D points which can subsequently be used to reconstruct the scene structure. We present novel camera calibration and scene reconstruction using scale-invariant feature points. A generic high-dimensional vector matching scheme is proposed to enhance the efficiency and reduce the computational cost while finding feature correspondences. A framework for structure and motion is also presented that better exploits the advantages of scale-invariant features. In this approach we solve the “phantom points” problem and this greatly reduces the possibility of error propagation. The whole process requires no information other than the input images. The results illustrate that our system is capable of producing accurate scene structure and realistic 3D models within a few minutes.
15096079
Lock-free scheduling of logical processes in parallel simulation
With fixed lookahead information in a simulation model, the overhead of asynchronous conservative parallel simulation lies in the mechanism used for propagating time updates in order for logical processes to safely advance their local simulation clocks. Studies have shown that a good scheduling algorithm should preferentially schedule processes containing events on the critical path. This paper introduces a lock-free algorithm for scheduling logical processes in conservative parallel discrete-event simulation on shared-memory multiprocessor machines. The algorithm uses fetch and add operations that help avoid inefficiencies associated with using locks. The lock-free algorithm is robust. Experiments show that, compared with the scheduling algorithm using locks, the lock-free algorithm exhibits better performance when the number of logical processes assigned to each processor is small or when the workload becomes significant. In models with large number of logical processes, our algorithm shows only modest increase in execution time due to the overhead in the algorithm for extra bookkeeping.
15698160
Performance prediction of a parallel simulator
There are at least three major obstacles thwarting widespread adoption of parallel discrete-event simulation: lack of need; lack of tools; and lack of predictability in behavior and performance. The plain truth is that most simulation studies can be adequately done on ordinary serial computers. Parallel simulation tools are products of research efforts, and simply do not stand up to the demands of modern software engineering. The results of 20 years of research in parallel simulation reveal it to be a highly complex endeavour, with performance results very much dependent on implementation details and model characteristics. The Scalable Simulation Framework (SSF) is an effort to address some these concerns. It addresses lack of need in two ways; it provides a modeling API that is attractive both for serial and parallel simulation, with parallel execution requiring no change to the model, and it targets large-scale telecommunication system modeling, an application area that requires the computational capabilities of parallelism. We address the concern over unpredictable behavior. We show how we measured the internal overheads of the Dartmouth implementation of the SSF API (DaSSF), and how those measurements can be used to predict the performance of a given model, using given features of the simulator, without having to run, or even build, the model.
12033351
mTreebone: A Hybrid Tree/Mesh Overlay for Application-Layer Live Video Multicast
Application-layer overlay networks have recently emerged as a promising solution for live media multicast on the Internet. A tree is probably the most natural structure for a multicast overlay, but is vulnerable in the presence of dynamic end-hosts. Data-driven approaches form a mesh out of overlay nodes to exchange data, which greatly enhances the resilience. It however suffers from an efficiency-latency tradeoff, given that the data have to be pulled from mesh neighbors with periodical notifications. In this paper, we suggest a novel hybrid tree/mesh design that leverages both overlays. The key idea is to identify a set of stable nodes to construct a tree-based backbone, called treebone, with most of the data being pushed over this backbone. These stable nodes, together with others, are further organized through an auxiliary mesh overlay, which facilitates the treebone to accommodate node dynamics and fully exploit the available bandwidth between overlay nodes. This hybrid design, referred to as mTreebone, is braced by our real trace studies, which show strong evidence that the performance of an overlay closely depends on a small set of backbone nodes. It however poses a series of unique and critical design challenges, in particular, the identification of stable nodes and seamless data delivery using both push and pull methods. In this paper, we present optimized solutions to these problems, which reconcile the two overlays under a coherent framework with controlled overhead. We evaluate mTreebone through both simulations and PlanetLab experiments. The results demonstrate the superior efficiency and robustness of this hybrid solution.
5682640
A dual-space approach to tracking and sensor management in wireless sensor networks
Wireless ad hoc sensor networks have the advantage of spanning a large geographical region and being able to collaboratively detect and track non-local spatio-temporal events. This paper presents a dual-space approach to event tracking and sensor resource management in sensor networks. The dual-space transformation maps a non-local phenomenon, e.g., the edge of a half-plane shadow, to a single point in the dual space, and maps locations of distributed sensor nodes to a set of lines that partitions the dual space. The detection problem becomes finding and tracking the cell that contains the point in the arrangement defined by these lines. This mechanism can be effectively used for power management of the sensor network - nodes that will not be immediately visited by an event can be turned off to save energy required for sensing, processing, and communication. The approach has been successfully demonstrated on a laboratory testbed built using the UC Berkeley motes sensors. An implemented application of detecting and tracking light shadow edges moving over a sensor field is described.