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

Carla Guerrini - One of the best experts on this subject based on the ideXlab platform.

  • Paper: A domain decomposition method for scattered data approximation on a Distributed Memory Multiprocessor
    1991
    Co-Authors: L. Bacchelli Montefusco, Carla Guerrini
    Abstract:

    The problem of reconstructing a function f(x, y) from N experimental evaluations (x"i, y"i, f"i), i = 1,..., N irregularly Distributed in the plane, has been considered for very large values of N. In this case the known local methods give the best sequential algorithms, but are not well suited for parallel implementation due to their excessively large arithmetic overhead. In this work we present a domain decomposition parallel method, especially studied for Distributed Memory Multiprocessors which also achieves high efficiency as a sequential algorithm. In fact, it is based on the decomposition strategy already used in the local methods, but a particular decomposition in slightly overlapping regions and appropriate choice of the limited support weight functions has been realized in order to reduce arithmetic, communication and synchronization overheads. A good performance of the coarse grained parallel algorithm is then achieved by means of a dynamic arithmetic load-balance. Timings and efficiency results from a large experimentation carried out on a Hypercube iPSC/2 are given.

  • a domain decomposition method for scattered data approximation on a Distributed Memory Multiprocessor
    EDMCC2 Proceedings of the 2nd European conference on Distributed memory computing, 1991
    Co-Authors: Bacchelli L Montefusco, Carla Guerrini
    Abstract:

    lThe problem of reconstructing a function f(x, y) from N experimental evaluations (xi, yi, fi), i=1, ..., N irregularly Distributed in the plane, has been considered for very large values of N. In this case the known local methods give the best sequential algorithms, but are not well suited for parallel implementation due to their excessively large arithmetic overhead. In this work we present a domain decomposition parallel method, especially studied for Distributed Memory Multiprocessors which also achieves high efficiency as a sequential algorithm. In fact, it is based on the decomposition strategy already used in the local methods, but a particular decomposition in slightly overlapping regions and appropriate choice of the limited support weight functions has been realized in order to reduce arithmetic, communication and synchronization overheads. A good performance of the coarse grained parallel algorithm is then achieved by means of a dynamic arithmetic load- balance. Timings and efficiency results from a large experimentation carried out on a Hypercube iPSC/2 are given.

  • EDMCC - A Domain Decomposition Method for Scattered Data Approximation on a Distributed Memory Multiprocessor
    Lecture Notes in Computer Science, 1
    Co-Authors: L. Bacchelli Montefusco, Carla Guerrini
    Abstract:

    lThe problem of reconstructing a function f(x, y) from N experimental evaluations (xi, yi, fi), i=1, ..., N irregularly Distributed in the plane, has been considered for very large values of N. In this case the known local methods give the best sequential algorithms, but are not well suited for parallel implementation due to their excessively large arithmetic overhead. In this work we present a domain decomposition parallel method, especially studied for Distributed Memory Multiprocessors which also achieves high efficiency as a sequential algorithm. In fact, it is based on the decomposition strategy already used in the local methods, but a particular decomposition in slightly overlapping regions and appropriate choice of the limited support weight functions has been realized in order to reduce arithmetic, communication and synchronization overheads. A good performance of the coarse grained parallel algorithm is then achieved by means of a dynamic arithmetic load- balance. Timings and efficiency results from a large experimentation carried out on a Hypercube iPSC/2 are given.

Ophir Frieder - One of the best experts on this subject based on the ideXlab platform.

  • Dynamic adaptive surface rendering within a Distributed Memory Multiprocessor
    Journal of Systems and Software, 1992
    Co-Authors: M. R. Stytz, Ophir Frieder
    Abstract:

    Abstract We describe a software-based approach to computing surface renderings from three-dimensional volume primitives using a general purpose Distributed Memory multiple-instruction, multiple-data Multiprocessor architecture. The system reduces total elapsed image rendering time by exploiting Distributed computing and using dynamic algorithm selection to reduce individual processor rendering time. We briefly describe the system pipeline architecture, the operation of the pipeline, and the computational bottleneck our research addresses. We then describe two adaptively terminating surface rendering algorithms. Our new approach to reducing surface rendering time uses the two algorithms and a procedure for predicting individual processor workload from the image-rendering parameters. The technique we describe locally and dynamically selects the optimum surface-rendering algorithm at each processor in the Multiprocessor machine, thereby substantially reducing the total elapsed image-rendering time.

Gyungleen Park - One of the best experts on this subject based on the ideXlab platform.

  • performance evaluation of a list scheduling algorithm in Distributed Memory Multiprocessor systems
    Future Generation Computer Systems, 2004
    Co-Authors: Gyungleen Park
    Abstract:

    Since it has been shown that the Multiprocessor scheduling problem is NP-complete, research efforts have resulted in numerous scheduling algorithms based on heuristics. The need for measuring the effectiveness of the various task scheduling algorithms leads to a great demand on modeling and evaluation tools. This paper proposes to use the stochastic Petri net (SPN) model and its equivalent continuous time Markov chain (CTMC) as the tool for modeling and evaluation of task scheduling algorithms. The proposed approach is applied to DPS (decisive path scheduling) algorithm to investigate its effectiveness. The proposed approach is verified by comparing the result obtained using the SPN model with that obtained by actually running DPS algorithm. The performance comparison reveals that the proposed approach provides very accurate performance evaluation for the scheduling algorithm when the CCR (communication to computation ratio) value is small.

  • dfrn a new approach for duplication based scheduling for Distributed Memory Multiprocessor systems
    International Parallel Processing Symposium, 1997
    Co-Authors: Gyungleen Park, B Shirazi, Jeff Marquis
    Abstract:

    Duplication based scheduling (DBS) is a relatively new approach for solving Multiprocessor scheduling problems. The problem is defined as finding an optimal schedule which minimizes the parallel execution time of an application on a target system. We classify DBS algorithms into two categories according to the task duplication method used. We then present our new DBS algorithm that extracts the strong features of the two categories of DBS algorithms. Our simulation study shows that the proposed algorithm achieves considerable performance improvement over existing DBS algorithms with equal or less time complexity. We analytically obtain the boundary condition for the worst case behavior of the proposed algorithm and also prove that the algorithm generates an optimal schedule for a tree structured input directed acyclic graph.

Tao Yang - One of the best experts on this subject based on the ideXlab platform.

  • CAIP - Static Global Scheduling for Optimal Computer Vision and Image Processing Operations on Distributed-Memory Multiprocessor
    Computer Analysis of Images and Patterns, 1995
    Co-Authors: Cheolwhan Lee, Yuanfang Wang, Tao Yang
    Abstract:

    In this paper, we develop a static global scheduling scheme for mapping computer vision and image processing (CVIP) operations on Distributed-Memory Multiprocessors. Unlike most current parallel image processing research which focuses on parallelizing individual processing algorithms on a particular parallel architecture, our scheduler is for optimizing processor assignment and data partition for an entire image processing pipeline. The scheduler operates on task graphs specified by conventional visual languages such as Khoros and Explorer. A task graph is assumed to be a linear chain of operations with any number of nested loops. The task chain is first decomposed into simpler subchains; each a linear sequence of tasks without loops. The communication and computation costs of the component tasks in the subchains are determined by a taxonomy of CVIP operations. Data redistribution overheads in between tasks can also be tabulated in advance for many popular data partitioning schemes. The scheduler then employs a shortest path algorithm to optimize the parallel time, taking into consideration possible variation in the task and resource parameters (such as the image size and number of processors used), and both the intra-operation and the inter-operation computation and communication times. In this paper, we present the scheduling scheme, and provide analyses and experimental results to verify our approach.

  • static global scheduling for optimal computer vision and image processing operations on Distributed Memory Multiprocessor
    Computer Analysis of Images and Patterns, 1994
    Co-Authors: Cheolwhan Lee, Yuanfang Wang, Tao Yang
    Abstract:

    In this paper, we develop a static global scheduling scheme for mapping computer vision and image processing (CVIP) operations on Distributed-Memory Multiprocessors. Unlike most current parallel image processing research which focuses on parallelizing individual processing algorithms on a particular parallel architecture, our scheduler is for optimizing processor assignment and data partition for an entire image processing pipeline. The scheduler operates on task graphs specified by conventional visual languages such as Khoros and Explorer. A task graph is assumed to be a linear chain of operations with any number of nested loops. The task chain is first decomposed into simpler subchains; each a linear sequence of tasks without loops. The communication and computation costs of the component tasks in the subchains are determined by a taxonomy of CVIP operations. Data redistribution overheads in between tasks can also be tabulated in advance for many popular data partitioning schemes. The scheduler then employs a shortest path algorithm to optimize the parallel time, taking into consideration possible variation in the task and resource parameters (such as the image size and number of processors used), and both the intra-operation and the inter-operation computation and communication times. In this paper, we present the scheduling scheme, and provide analyses and experimental results to verify our approach.

Jon Mauney - One of the best experts on this subject based on the ideXlab platform.

  • a scalable scheduling scheme for functional parallelism on Distributed Memory Multiprocessor systems
    IEEE Transactions on Parallel and Distributed Systems, 1995
    Co-Authors: Santosh Pande, Dharma P Agrawal, Jon Mauney
    Abstract:

    We attempt a new variant of the scheduling problem by investigating the scalability of the schedule length with the required number of processors, by performing scheduling partially at compile time and partially at run time. Assuming infinite number of processors, the compile time schedule is found using a new concept of the threshold of a task that quantifies a trade-off between the schedule-length and the degree of parallelism. The schedule is found to minimize either the schedule length or the number of required processors and it satisfies: A feasibility condition which guarantees that the schedule delay of a task from its earliest start time is below the threshold, and an optimality condition which uses a merit function to decide the best task-processor match for a set of tasks competing for a given processor. At run time, the tasks are merged producing a schedule for a smaller number of available processors. This allows the program to be scaled down to the processors actually available at run time. Usefulness of this scheduling heuristic has been demonstrated by incorporating the scheduler in the compiler backend for targeting Sisal (Streams and Iterations in a Single Assignment Language) on iPSC/860. >