The Experts below are selected from a list of 67938 Experts worldwide ranked by ideXlab platform

J J Choi - One of the best experts on this subject based on the ideXlab platform.

  • Parallel Algorithm for Finding the Smallest Enclosing Rectangle on SIMD Machines
    2007
    Co-Authors: J J Choi
    Abstract:

    In this thesis, we present a parallel algorithm for finding the smallest enclosing rectangle which encloses a set S of n points in the plane. This problem arises frequently in industrial fields such as packing and optimal layout problems. Using the property that the smallest enclosing rectangle of a convex hull for S has the same area as that of n points in S, we first compute a convex hull for S and then find the smallest enclosing rectangle directly from that convex hull. Therefore, our algorithm can be executed very fast with small constant factor. The proposed algorithm can be generally implemented on SIMD (Single Instruction stream and Multiple Data stream)-type parallel Computers such as MCC (Mesh Connected Computer) and CCC (Cube Connected Computer) . Our parallel algorithm can be executed with the time complexity O( p n) and O(log 2 n) on MCC and CCC respectively. Contents 1 Introduction 1 2 Models of Parallel Computations 5 2.1 Parallel Architecture : : : : : : : : : :..

  • AN OPTIMAL PARALLEL ALGORITHM FOR FINDING THE SMALLEST ENCLOSING TRIANGLE ON A MESH-Connected Computer∗
    Parallel Algorithms and Applications, 1993
    Co-Authors: J J Choi, Chang-sung Jeong, Myung-soo Kim
    Abstract:

    In this paper, we consider the problem of finding the smallest triangle circumscribing a convex polygon with n edges. We show that this can be done in O( √n)time by efficient data partition schemes and proper set mapping and comparison operations using the so-called √n-decomposition technique. Since the nontrivial operation on mesh-Connected Computers requires Ω(,√n), the time complexity is optimal within a constant time factor.

  • an optimal parallel algorithm for finding the smallest enclosing rectangle on a mesh Connected Computer for rectangle read triangle
    International Parallel Processing Symposium, 1992
    Co-Authors: C S Jeong, J J Choi
    Abstract:

    The authors consider the problem of finding the smallest triangle circumscribing a convex polygon with n edges. They show that this can be done in O( square root n) time by efficient data partition schemes and proper set mapping and comparison operations using a so called square root n-decomposition technique. Since the nontrivial operation on MCC requires Omega ( square root n), the time complexity is optimal within a constant time factor. >

  • IPPS - An optimal parallel algorithm for finding the smallest enclosing rectangle on a mesh-Connected Computer (for rectangle read triangle)
    Proceedings Sixth International Parallel Processing Symposium, 1
    Co-Authors: C S Jeong, J J Choi
    Abstract:

    The authors consider the problem of finding the smallest triangle circumscribing a convex polygon with n edges. They show that this can be done in O( square root n) time by efficient data partition schemes and proper set mapping and comparison operations using a so called square root n-decomposition technique. Since the nontrivial operation on MCC requires Omega ( square root n), the time complexity is optimal within a constant time factor. >

Z Rácz - One of the best experts on this subject based on the ideXlab platform.

  • Synchronization landscapes in small-world-Connected Computer networks.
    Physical review. E Statistical nonlinear and soft matter physics, 2006
    Co-Authors: Hasan Guclu, G Korniss, M A Novotny, Z Toroczkai, Z Rácz
    Abstract:

    Motivated by a synchronization problem in distributed computing we studied a simple growth model on regular and small-world networks, embedded in one and two dimensions. We find that the synchronization landscape (corresponding to the progress of the individual processors) exhibits Kardar-Parisi-Zhang-like kinetic roughening on regular networks with short-range communication links. Although the processors, on average, progress at a nonzero rate, their spread (the width of the synchronization landscape) diverges with the number of nodes (desynchronized state) hindering efficient data management. When random communication links are added on top of the one and two-dimensional regular networks (resulting in a small-world network), large fluctuations in the synchronization landscape are suppressed and the width approaches a finite value in the large system-size limit (synchronized state). In the resulting synchronization scheme, the processors make close-to-uniform progress with a nonzero rate without global intervention. We obtain our results by "simulating the simulations," based on the exact algorithmic rules, supported by coarse-grained arguments.

Quentin F. Stout - One of the best experts on this subject based on the ideXlab platform.

  • optimal algorithms for a mesh Connected Computer with limited additional global bandwidth
    International Parallel and Distributed Processing Symposium, 2017
    Co-Authors: Quentin F. Stout
    Abstract:

    We give efficient algorithms to solve fundamental data movement problems on mesh-Connected Computers augmented with limited global bandwidth. Adding a small amount of global bandwidth makes a practical design that combines aspects of mesh and fully Connected models to achieve the benefits of each. We give algorithms for sorting, finding the median, finding a spanning tree, and determining various graph properties to show that the small amount of global communication can significantly reduce the time, and that concurrent read helps even more. Most of these algorithms are optimal. We also extend our results to mesh-Connected Computers with row and column buses.

  • IPDPS - Optimal Algorithms for a Mesh-Connected Computer with Limited Additional Global Bandwidth
    2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2017
    Co-Authors: Quentin F. Stout
    Abstract:

    We give efficient algorithms to solve fundamental data movement problems on mesh-Connected Computers augmented with limited global bandwidth. Adding a small amount of global bandwidth makes a practical design that combines aspects of mesh and fully Connected models to achieve the benefits of each. We give algorithms for sorting, finding the median, finding a spanning tree, and determining various graph properties to show that the small amount of global communication can significantly reduce the time, and that concurrent read helps even more. Most of these algorithms are optimal. We also extend our results to mesh-Connected Computers with row and column buses.

  • an optimal time power tradeoff for sorting on a mesh Connected Computer with on chip optics
    International journal of networking and computing, 2014
    Co-Authors: Patrick Poon, Quentin F. Stout
    Abstract:

    Energy consumption has become a critical factor constraining the design of massively parallel Computers, necessitating the development of new models and energy-efficient algorithms. The primary component of on-chip energy consumption is data movement, and the mesh Computer is a natural model of this, explicitly taking distance into account. Unfortunately the dark silicon problem increasingly constrains the number of bits which can be moved simultaneously. For sorting, standard mesh algorithms minimize time and total data movement, and hence constraining the mesh to use only half its processors at any instant must double the time. It is anticipated that on-chip optics will be used to minimize the energy needed to move bits, but they have constraints on their layout. In an abstract model, we show that a pyramidal layout and a new power-aware algorithm allows one to sort with only a square root increase in time as the fraction of processors simultaneously powered decreases. Furthermore, this layout is shown to be optimal in terms of the time-power tradeoff required for sorting. Previous algorithms assumed fully powered systems, hence pyramid sorting was of no interest since when fully powered they are no faster than the base mesh. Our results show asymptotic theoretical limits of computation and energy usage on a model which takes physical constraints and developing interconnection technology into account.Â

  • time power tradeoffs for sorting on a mesh Connected Computer with optical connections
    IEEE International Symposium on Parallel & Distributed Processing Workshops and Phd Forum, 2013
    Co-Authors: Patrick Poon, Quentin F. Stout
    Abstract:

    Energy consumption has become a critical factor constraining the design of massively parallel Computers, necessitating the development of new models and energy-efficient algorithms. The primary component of on-chip energy consumption is data movement, and the mesh Computer is a natural model of this, explicitly taking distance into account. Unfortunately the dark silicon problem increasingly constrains the number of bits which can be moved simultaneously. For sorting, standard mesh algorithms minimize time and total data movement, and hence constraining the mesh to use only half its processors at any instant must double the time. It is anticipated that on-chip optics will be used to minimize the energy needed to move bits, but they have constraints on their layout. In an abstract model, we show that a pyramidal layout and a new power-aware algorithm allows one to sort with only a square root increase in time as the fraction of processors simultaneously powered decreases. Previous algorithms assumed fully powered systems, hence pyramid sorting was of no interest since when fully powered they are no faster than the base mesh. Our results show asymptotic theoretical limits of computation and energy usage on a model which takes physical constraints and developing interconnection technology into account.

Hasan Guclu - One of the best experts on this subject based on the ideXlab platform.

  • Synchronization landscapes in small-world-Connected Computer networks.
    Physical review. E Statistical nonlinear and soft matter physics, 2006
    Co-Authors: Hasan Guclu, G Korniss, M A Novotny, Z Toroczkai, Z Rácz
    Abstract:

    Motivated by a synchronization problem in distributed computing we studied a simple growth model on regular and small-world networks, embedded in one and two dimensions. We find that the synchronization landscape (corresponding to the progress of the individual processors) exhibits Kardar-Parisi-Zhang-like kinetic roughening on regular networks with short-range communication links. Although the processors, on average, progress at a nonzero rate, their spread (the width of the synchronization landscape) diverges with the number of nodes (desynchronized state) hindering efficient data management. When random communication links are added on top of the one and two-dimensional regular networks (resulting in a small-world network), large fluctuations in the synchronization landscape are suppressed and the width approaches a finite value in the large system-size limit (synchronized state). In the resulting synchronization scheme, the processors make close-to-uniform progress with a nonzero rate without global intervention. We obtain our results by "simulating the simulations," based on the exact algorithmic rules, supported by coarse-grained arguments.

  • Synchronization in Small-World-Connected Computer Networks
    arXiv: Statistical Mechanics, 2006
    Co-Authors: Hasan Guclu
    Abstract:

    In this thesis we study synchronization phenomena in natural and artificial coupled multi-component systems, applicable to the scalability of parallel discrete-event simulation for systems with asynchronous dynamics. We analyze the properties of the virtual time horizon or synchronization landscape (corresponding to the progress of the processing elements) of these networks by using the framework of non-equilibrium surface growth. When the communication topology mimics that of the short-range interacting underlying system, the virtual time horizon exhibits Kardar-Parisi-Zhang-like kinetic roughening. Although the virtual times, on average, progress at a nonzero rate, their statistical spread diverges with the number of processing elements, hindering efficient data collection. We show that when the synchronization topology is extended to include quenched random communication links (small-world links) between the processing elements, they make a close-to-uniform progress with a nonzero rate, without global synchronization. We also provide a coarse-grained description for the small-world-synchronized virtual-time horizon and compare the findings to those obtained by simulating the simulations based on the exact algorithmic rules. We also present numerical results for the evolution of the virtual-time horizon on scale-free Barabasi-Albert networks serving as communication topology among the processing elements. Finally, we investigate to what extent small-world couplings (extending the original local relaxational dynamics through the random links) lead to the suppression of extreme fluctuations in the synchronization landscape.

C S Jeong - One of the best experts on this subject based on the ideXlab platform.

  • an optimal parallel algorithm for finding the smallest enclosing rectangle on a mesh Connected Computer for rectangle read triangle
    International Parallel Processing Symposium, 1992
    Co-Authors: C S Jeong, J J Choi
    Abstract:

    The authors consider the problem of finding the smallest triangle circumscribing a convex polygon with n edges. They show that this can be done in O( square root n) time by efficient data partition schemes and proper set mapping and comparison operations using a so called square root n-decomposition technique. Since the nontrivial operation on MCC requires Omega ( square root n), the time complexity is optimal within a constant time factor. >

  • IPPS - An optimal parallel algorithm for finding the smallest enclosing rectangle on a mesh-Connected Computer (for rectangle read triangle)
    Proceedings Sixth International Parallel Processing Symposium, 1
    Co-Authors: C S Jeong, J J Choi
    Abstract:

    The authors consider the problem of finding the smallest triangle circumscribing a convex polygon with n edges. They show that this can be done in O( square root n) time by efficient data partition schemes and proper set mapping and comparison operations using a so called square root n-decomposition technique. Since the nontrivial operation on MCC requires Omega ( square root n), the time complexity is optimal within a constant time factor. >

  • SPDP - An improved parallel algorithm for construction Voronoi diagram on a mesh-Connected Computer
    Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing 1990, 1
    Co-Authors: C S Jeong
    Abstract:

    While constructing a Voronoi diagram V/sub p/ for a set P of n points on a mesh-Connected Computer(MCC), it is necessary to find a set B of edges which are intersected by the dividing chain C during the merge process of two Voronoi diagrams V/sub L/ and V/sub A/, where L and R contain the leftmost (n/2) points and the rightmost (n/2) points of P respectively. The computation of B requires two operations: First decide for each edge e in V/sub L/ and V/sub R/ whether its end vertices are closer to L or R, and then from that information, determine, whether e is intersected by C. The paper shows that the latter operation can be done in O(1) time without executing planar point location and the former operation can be executed without the computation of convex hulls. Therefore, the computation of B is reduced to only one planar point location. >