Publication detail

Prototyping Parallel Applications Based on Divide and Conquer Strategy

KUTÁLEK, V., DVOŘÁK, V.

Original Title

Prototyping Parallel Applications Based on Divide and Conquer Strategy

English Title

Prototyping Parallel Applications Based on Divide and Conquer Strategy

Type

conference paper

Language

en

Original Abstract

The paper addresses a problem of parallel implementation of divide-and-conquer algorithms, whose performance is not always satisfactory. Questions like depth of recursion, multiple processes per processor, communication architecture and overhead, etc., are analyzed and the template for prototyping D&C algorithms in Transim language is explained. Prototypes of parallel D&C programs can be executed and their performance estimated before developing the code in detail. The technique is useful for programs with message passing as well as with shared variables. As an example a prototype of a parallel 1D-FFT benchmark targeted both to a distributed memory machine and to a SMP have been developed and simulated. The experiments show that the template can be used for quick estimation of performance and suitability of D&C approach in any given application.

English abstract

The paper addresses a problem of parallel implementation of divide-and-conquer algorithms, whose performance is not always satisfactory. Questions like depth of recursion, multiple processes per processor, communication architecture and overhead, etc., are analyzed and the template for prototyping D&C algorithms in Transim language is explained. Prototypes of parallel D&C programs can be executed and their performance estimated before developing the code in detail. The technique is useful for programs with message passing as well as with shared variables. As an example a prototype of a parallel 1D-FFT benchmark targeted both to a distributed memory machine and to a SMP have been developed and simulated. The experiments show that the template can be used for quick estimation of performance and suitability of D&C approach in any given application.

Keywords

Divide and conquer algorithms, parallel performance, parallel recursive FFT

RIV year

2002

Released

25.04.2002

Location

Ostrava

ISBN

80-85988-71-2

Book

Proceedings of 36th International Conference MOSIS '02 Modelling and Simulation of Systems

Edition

Vol. I

Pages from

313

Pages to

320

Pages count

8

Documents

BibTex


@inproceedings{BUT9833,
  author="Vladimír {Kutálek} and Václav {Dvořák}",
  title="Prototyping Parallel Applications Based on Divide and Conquer Strategy",
  annote="The paper addresses a problem of parallel implementation of
divide-and-conquer algorithms, whose performance is not always
satisfactory. Questions like depth of recursion, multiple processes per
processor, communication architecture and overhead, etc., are analyzed
and the template for prototyping D&C algorithms in Transim language
is explained. Prototypes of parallel D&C programs can be executed
and their performance estimated before developing the code in detail.
The technique is useful for programs with message passing as well as
with shared variables. As an example a prototype of a parallel 1D-FFT
benchmark targeted both to a distributed memory machine and to a SMP
have been developed and simulated. The experiments show that the
template can be used for quick estimation of performance and
suitability of D&C approach in any given application.",
  booktitle="Proceedings of 36th International Conference MOSIS '02 Modelling and Simulation of Systems",
  chapter="9833",
  edition="Vol. I",
  year="2002",
  month="april",
  pages="313--320",
  type="conference paper"
}