Automatically assigned DDC number: 00435

Manually assigned DDC number: 519233

Number of references: 4

Title: On The Space-Time Mapping Of A Class Of Divide-And-Conquer Recursions

Author:

Author:

Subject: Christoph Herrmann,Christian Lengauer On The Space-Time Mapping Of A Class Of Divide-And-Conquer Recursions

Description: We propose a functional program skeleton for balanced fixed-degree divide-and-conquer and a method for its parallel implementation on message-passing multiprocessors. In the method, the operations of the skeleton are first mapped to a geometric computational model which is then mapped to space-time in order to expose the inherent parallelism. This approach is inspired by the method of parallelizing nested loops in the polytope model. Keywords: divide-and-conquer, functional program, parallelization, skeleton, space-time mapping. 1. Introduction The divide-and-conquer (DC) paradigm is a special case of cascading recursion which enables efficient solutions to many practical problems like the multiplication of matrices or large integers, Fast Fourier Transform, sorting, etc. We are interested in the parallelization of DC recursions with the goal of sublinear execution times on a mesh. Sublinearity can only be achieved if the input is read in parallel. We choose a mesh because it is a w...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1997-03-20

Pubyear: 1996

Format: ps

Identifier: http://citeseer.ist.psu.edu/147307.html

Source: ftp://ftp.uni-passau.de/pub/local/parallel/papers/HerLe96.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/359221.html"   Type="inproceedings"   CiteSeer_Book="Mathematics   of   Program   Construction"   CiteSeer_Volume=""   Title="Architecture   Independent   Massive   Parallelization   of   Divide-and-Conquer   Algorithms,">

            <identifier   Org="ISBN:3540601171"   Paper_ID="/359221.html"   Extracted="3540601171"   DDC="004.2/0151"   Normalized_DDC="00420151"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:3540616276"   Paper_ID="/359221.html"   Extracted="3540616276"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:3540633987"   Paper_ID="/359221.html"   Extracted="3540633987"   DDC="005.13/3"   Normalized_DDC="005133"   Normalized_Weight="0.3333333333333333"   />

            <identifier   Org="ISBN:3765719528"   Paper_ID="/359221.html"   Extracted="3765719528"   />

      </rec>

      <rec   ID="/355907.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Notes   on   the   space-time   mapping   of   divide-andconquer   recursions,"   />

      <rec   ID="/354729.html"   Type="inproceedings"   CiteSeer_Book="International   Conference   on   Concurrency   Theory"   CiteSeer_Volume=""   Title="Loop   Parallelization   in   the   Polytope   Model,">

            <identifier   Org="ISBN:0387476563"   Paper_ID="/354729.html"   Extracted="0387476563"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:0769501435"   Paper_ID="/354729.html"   Extracted="0769501435"   />

            <identifier   Org="ISBN:0824747119"   Paper_ID="/354729.html"   Extracted="0824747119"   DDC="004.16"   Normalized_DDC="00416"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:1581134096"   Paper_ID="/354729.html"   Extracted="1581134096"   />

            <identifier   Org="ISBN:1581135297"   Paper_ID="/354729.html"   Extracted="1581135297"   />

            <identifier   Org="ISBN:3540221190"   Paper_ID="/354729.html"   Extracted="3540221190"   DDC="005.13"   Normalized_DDC="00513"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540229248"   Paper_ID="/354729.html"   Extracted="3540229248"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540401903"   Paper_ID="/354729.html"   Extracted="3540401903"   DDC="005.13"   Normalized_DDC="00513"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540424954"   Paper_ID="/354729.html"   Extracted="3540424954"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540572082"   Paper_ID="/354729.html"   Extracted="3540572082"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540584307"   Paper_ID="/354729.html"   Extracted="3540584307"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540609733"   Paper_ID="/354729.html"   Extracted="3540609733"   DDC="005.1/01/5113"   Normalized_DDC="0051015113"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540615768"   Paper_ID="/354729.html"   Extracted="3540615768"   DDC="004/.01/5116"   Normalized_DDC="004015116"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540616268"   Paper_ID="/354729.html"   Extracted="3540616268"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540649522"   Paper_ID="/354729.html"   Extracted="3540649522"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540675531"   Paper_ID="/354729.html"   Extracted="3540675531"   DDC="004/.3"   Normalized_DDC="0043"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540678581"   Paper_ID="/354729.html"   Extracted="3540678581"   DDC="005.453"   Normalized_DDC="005453"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540679561"   Paper_ID="/354729.html"   Extracted="3540679561"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540787909"   Paper_ID="/354729.html"   Extracted="3540787909"   DDC="005.4/53"   Normalized_DDC="005453"   Normalized_Weight="0.0625"   />

      </rec>

      <rec   ID="/513680.html"   Type="article"   CiteSeer_Book="ACM   Transactions   on   Programming   Languages   and   Systems"   CiteSeer_Volume="16"   Title="Powerlist:   {A}   Structure   for   Parallel   Recursion,">

            <identifier   Org="ISBN:0818684275"   Paper_ID="/513680.html"   Extracted="0818684275"   DDC="005.2/75"   Normalized_DDC="005275"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:1581134150"   Paper_ID="/513680.html"   Extracted="1581134150"   />

            <identifier   Org="ISBN:1852330929"   Paper_ID="/513680.html"   Extracted="1852330929"   DDC="005.2/75"   Normalized_DDC="005275"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:1852335068"   Paper_ID="/513680.html"   Extracted="1852335068"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540223800"   Paper_ID="/513680.html"   Extracted="3540223800"   DDC="004.2/1/0151"   Normalized_DDC="004210151"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540255966"   Paper_ID="/513680.html"   Extracted="3540255966"   DDC="005.131"   Normalized_DDC="005131"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:354042525X"   Paper_ID="/513680.html"   Extracted="354042525X"   DDC="004/.01/51"   Normalized_DDC="0040151"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540425411"   Paper_ID="/513680.html"   Extracted="3540425411"   DDC="621.39/5"   Normalized_DDC="621395"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540425586"   Paper_ID="/513680.html"   Extracted="3540425586"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540440496"   Paper_ID="/513680.html"   Extracted="3540440496"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540600434"   Paper_ID="/513680.html"   Extracted="3540600434"   DDC="005.1/01/512"   Normalized_DDC="005101512"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540616276"   Paper_ID="/513680.html"   Extracted="3540616276"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540617566"   Paper_ID="/513680.html"   Extracted="3540617566"   DDC="005.13"   Normalized_DDC="00513"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540658319"   Paper_ID="/513680.html"   Extracted="3540658319"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540713891"   Paper_ID="/513680.html"   Extracted="3540713891"   DDC="005.12"   Normalized_DDC="00512"   Normalized_Weight="0.07142857142857142"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="On   The   Space-Time   Mapping   Of   A   Class   Of   Divide-And-Conquer   Recursions">

            <identifier   Org="ISBN:0387953914"   Paper_ID="SELF"   Extracted="0387953914"   DDC="005.13"   Normalized_DDC="00513"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540633987"   Paper_ID="SELF"   Extracted="3540633987"   DDC="005.13/3"   Normalized_DDC="005133"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540664432"   Paper_ID="SELF"   Extracted="3540664432"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.25"   />

            <identifier   Org="ISBN:3540678581"   Paper_ID="SELF"   Extracted="3540678581"   DDC="005.453"   Normalized_DDC="005453"   Normalized_Weight="0.25"   />

      </rec>

</references_metadata>