Browsing by Subject "synchronization"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    An Efficient Algorithm for the Run-time Parallelization of DOACROSS Loops
    (1997) Chen, Ding-Kai; Torrellas, Josep; Yew, Pen-Chung
    While loop parallelization usually relies on compile-time analysis of data dependences, for some loops the data dependences cannot be detennined at compile time. An example is loops referencing arrays with subscripted subscripts. To parallelize these loops, it is necessary to use run-time analysis. In this paper, we present a new run-time algorithm to parallelize these loops. Our scheme handles any type of data dependence in the loop without requiring any special architectural support in the multiprocessor. Furthermore, compared to an older scheme with the same generality, our scheme significantly reduces the amount of processor communication required and increases the overlap among dependent iterations. We evaluate our algorithm with an extensive set of loops running on the 32-processor Cedar shared-memory multiprocessor. The execution times show speedups over the serial case that reach up to 13 with the full overhead of run-time analysis and up to 26 if part of the work is reused across loop invocations. Moreover, our algorithm outperforms the older scheme with the same generality in nearly all cases, reaching a 37-fold speedup over the older scheme when the loop has many dependences.
  • Thumbnail Image
    Item
    Robust Synchronization and its Applications in 3D Computer Vision
    (2020-08) Shi, Yunpeng
    This dissertation includes five works of my Ph.D. research. It starts with an introduction to 3D reconstruction and its associated synchronization problems, followed by the robust synchronization algorithms and their theoretical guarantees. Common 3D reconstruction tasks rely on accurate estimation of camera rotations and locations. These estimation problems are often solved by using graph optimization methods and can be mathematically formulated as synchronization problems. The synchronization problems ask to find the absolute states (e.g. rotations, locations) of graph nodes from the given noisy and corrupted relative states among pairs of nodes. The most common synchronization problem is group synchronization, where the states of nodes are elements of certain mathematical group. It asks to find the underlying group elements (e.g. absolute rotations) for each node from the given noisy and corrupted group ratios (e.g. relative rotations) among pairs of nodes. HASH(0x40ca7b0) In order to solve this problem, we first propose cycle-edge message passing (CEMP) framework that estimates the corruption levels of group ratios for any compact group. We establish the exact recovery and linear convergence guarantees with adversarial corruption and its stability to sub-Gaussian noise. We further show that under a uniform corruption model, the recovery results are sharp in terms of an information-theoretic bound. HASH(0x40c9e18) We next extend the idea of CEMP and develop message passing least squares (MPLS) framework for directly solving group elements under both high corruption and noise. We carefully refine the framework for specific applications of rotation and permutation synchronization in 3D computer vision. Both applications demonstrate the superior performance of MPLS over the state-of-the-art methods. HASH(0x40cb050) Finally, we discuss camera location estimation problem which can be viewed as a variant of group synchronization problem on the noncompact group R^3. We present and prove an exact recovery theory for the state-of-the-art least unsquared deviations (LUD) solver under adversarial corruption. We then develop the all-about-that-base (AAB) preprocessing step for detecting corrupted edges. We demonstrate that the application of AAB significantly improves the performance of common camera location solvers on both synthetic and real data.