Result: Parallelization with tree skeletons

Title:
Parallelization with tree skeletons
Authors:
MATSUZAKI, Kiminori, ZHENJIANG HU, TAKEICHI, Masato
Source:
Euro-Par 2003 parallel processing (Klagenfurt, 26-29 August 2003)Lecture notes in computer science. :789-798
Publisher Information:
Berlin: Springer, 2003.
Publication Year:
2003
Physical Description:
print, 14 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Génie logiciel, Software engineering, Conception programme, Program design, Concepción programa, Parallélisation, Parallelization, Paralelisacíon, Programmation parallèle, Parallel programming, Programación paralela, Programme parallèle, Parallel program, Programa paralelo, Préservation, Preservation, Preservación, Squelette, Skeleton, Esqueleto, Structure donnée arborescente, Tree data structures, Transformation programme, Program transformation, Transformación programa
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Graduate School of Information Science and Technology, University of Tokyo, Japan
PRESTO21, Japan Science and Technology Corporation, Japan
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=15530758
Rights:
Copyright 2004 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.15530758
Database:
PASCAL Archive

Further Information

Trees are useful data structures, but to design efficient parallel programs over trees is known to be more difficult than to do over lists. Although several important tree skeletons have been proposed to simplify parallel programming on trees, few studies have been reported on how to systematically use them in solving practical problems; it is neither clear how to make a good combination of skeletons to solve a given problem, nor obvious even how to find suitable operators used in a single skeleton. In this paper, we report our first attempt to resolve these problems, proposing two important transformations, the tree diffusion transformation and the tree context preservation transformation. The tree diffusion transformation allows one to use familiar recursive definitions to develop his parallel programs, while the tree context preservation transformation shows how to derive associative operators that are required when using tree skeletons. We illustrate our approach by deriving an efficient parallel program for solving a nontrivial problem called the party planning problem, the tree version of the famous maximum-weight-sum problem.