Automatically assigned DDC number: 00435

Manually assigned DDC number: 00435

Number of references: 8

Title: A Cost Model For Asynchronous and Structured Message Passing (Extended Version)

Author:

Author:

Author:

Subject: Emmanuel Melin,Xavier Rebeuf,Bernard Virot A Cost Model For Asynchronous and Structured Message Passing (Extended Version)

Description: In this paper, we present a cost model taking into account properties of present time machines. This work relies on SCL-chan, an asynchronous parallel execution model allowing explicit message passing. We show that it is possible to dene a complexity function for SCL-chan programs. It yields a symbolic date for each communication event. These dates can be ordered to compute upper bounds for the network load. In contrast to other classical approaches this cost computation can handle asynchronism in message passing and communication/computation overlap. Keywords: Cost Model; Symbolic Date; Parallel Programming Languages; Asynchronous Execution; Structural Clock. 1 Introduction In parallel programming, the main diĘculty is to nd an algorithm solving a given problem with the best" possible speed up. To compare two algorithms, a natural method consists in comparing their execution times. Nevertheless, execution time is not a good criterion since it depends on the characteristics of the...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1970-01-01

Pubyear: 1999

Format: ps

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

Source: ftp://ftp-lifo.univ-orleans.fr/pub/RR/RR99/RR99-07.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

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

<references_metadata>

      <rec   ID="/31084.html"   Type="inproceedings"   CiteSeer_Book="Principles   Practice   of   Parallel   Programming"   CiteSeer_Volume=""   Title="{LogP}:   Towards   a   Realistic   Model   of   Parallel   Computation,">

            <identifier   Org="ISBN:0070730202"   Paper_ID="/31084.html"   Extracted="0070730202"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0387986804"   Paper_ID="/31084.html"   Extracted="0387986804"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:158488360X"   Paper_ID="/31084.html"   Extracted="158488360X"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540254242"   Paper_ID="/31084.html"   Extracted="3540254242"   DDC="004.1/1"   Normalized_DDC="00411"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540305106"   Paper_ID="/31084.html"   Extracted="3540305106"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540309993"   Paper_ID="/31084.html"   Extracted="3540309993"   DDC="004.36"   Normalized_DDC="00436"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:354040788X"   Paper_ID="/31084.html"   Extracted="354040788X"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.05263157894736842"   />

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

            <identifier   Org="ISBN:3540428623"   Paper_ID="/31084.html"   Extracted="3540428623"   DDC="005.453"   Normalized_DDC="005453"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540437924"   Paper_ID="/31084.html"   Extracted="3540437924"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.05263157894736842"   />

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

            <identifier   Org="ISBN:3540620486"   Paper_ID="/31084.html"   Extracted="3540620486"   DDC="001.64"   Normalized_DDC="00164"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540631666"   Paper_ID="/31084.html"   Extracted="3540631666"   DDC="004.24015113"   Normalized_DDC="00424015113"   Normalized_Weight="0.05263157894736842"   />

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

            <identifier   Org="ISBN:3540659692"   Paper_ID="/31084.html"   Extracted="3540659692"   DDC="004/.3"   Normalized_DDC="0043"   Normalized_Weight="0.05263157894736842"   />

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

            <identifier   Org="ISBN:3540754431"   Paper_ID="/31084.html"   Extracted="3540754431"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540775595"   Paper_ID="/31084.html"   Extracted="3540775595"   DDC="004.2/2"   Normalized_DDC="00422"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540874747"   Paper_ID="/31084.html"   Extracted="3540874747"   />

            <identifier   Org="ISBN:905199267X"   Paper_ID="/31084.html"   Extracted="905199267X"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.05263157894736842"   />

      </rec>

      <rec   ID="/313774.html"   Type="inproceedings"   CiteSeer_Book="Symposium   on   Computational   Geometry"   CiteSeer_Volume=""   Title="Scalable   Parallel   Geometric   Algorithms   for   Coarse   Grained   Multicomputers,">

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

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

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

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

            <identifier   Org="ISBN:0818671955"   Paper_ID="/313774.html"   Extracted="0818671955"   />

            <identifier   Org="ISBN:0818677929"   Paper_ID="/313774.html"   Extracted="0818677929"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.07142857142857142"   />

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

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

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

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

            <identifier   Org="ISBN:3540290311"   Paper_ID="/313774.html"   Extracted="3540290311"   DDC="004.1/1"   Normalized_DDC="00411"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:354040161X"   Paper_ID="/313774.html"   Extracted="354040161X"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540411836"   Paper_ID="/313774.html"   Extracted="3540411836"   DDC="004.015115"   Normalized_DDC="004015115"   Normalized_Weight="0.07142857142857142"   />

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

            <identifier   Org="ISBN:3540571558"   Paper_ID="/313774.html"   Extracted="3540571558"   DDC="005.7/3"   Normalized_DDC="00573"   Normalized_Weight="0.07142857142857142"   />

            <identifier   Org="ISBN:3540620311"   Paper_ID="/313774.html"   Extracted="3540620311"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.07142857142857142"   />

      </rec>

      <rec   ID="/148936.html"   Type="inproceedings"   CiteSeer_Book="The   Data   Parallel   Programming   Model"   CiteSeer_Volume=""   Title="Automatic   Parallelization   in   the   Polytope   Model,">

            <identifier   Org="ISBN:0387953914"   Paper_ID="/148936.html"   Extracted="0387953914"   DDC="005.13"   Normalized_DDC="00513"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:0387986804"   Paper_ID="/148936.html"   Extracted="0387986804"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.058823529411764705"   />

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

            <identifier   Org="ISBN:0792376897"   Paper_ID="/148936.html"   Extracted="0792376897"   DDC="005.4/3573"   Normalized_DDC="00543573"   Normalized_Weight="0.058823529411764705"   />

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

            <identifier   Org="ISBN:084931240X"   Paper_ID="/148936.html"   Extracted="084931240X"   DDC="005.4/53"   Normalized_DDC="005453"   Normalized_Weight="0.058823529411764705"   />

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

            <identifier   Org="ISBN:3540212973"   Paper_ID="/148936.html"   Extracted="3540212973"   DDC="005.4/53"   Normalized_DDC="005453"   Normalized_Weight="0.058823529411764705"   />

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

            <identifier   Org="ISBN:354026969X"   Paper_ID="/148936.html"   Extracted="354026969X"   DDC="004.2/2"   Normalized_DDC="00422"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540307818"   Paper_ID="/148936.html"   Extracted="3540307818"   DDC="001.64"   Normalized_DDC="00164"   Normalized_Weight="0.058823529411764705"   />

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

            <identifier   Org="ISBN:3540582010"   Paper_ID="/148936.html"   Extracted="3540582010"   DDC="001.64"   Normalized_DDC="00164"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3540617361"   Paper_ID="/148936.html"   Extracted="3540617361"   DDC="005.2"   Normalized_DDC="0052"   Normalized_Weight="0.058823529411764705"   />

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

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

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

            <identifier   Org="ISBN:3540739394"   Paper_ID="/148936.html"   Extracted="3540739394"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.058823529411764705"   />

            <identifier   Org="ISBN:3833426691"   Paper_ID="/148936.html"   Extracted="3833426691"   DDC="830"   Normalized_DDC="83"   Normalized_Weight="0.058823529411764705"   />

      </rec>

      <rec   ID="/360589.html"   Type="misc"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="Structural   Clocks   for   a   Loosely   Synchronized   Data-Parallel   Language,">

            <identifier   Org="ISBN:0818678828"   Paper_ID="/360589.html"   Extracted="0818678828"   DDC="005.2/75"   Normalized_DDC="005275"   Normalized_Weight="0.5"   />

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

      </rec>

      <rec   ID="/69791.html"   Type="inproceedings"   CiteSeer_Book="Lectures   on   Parallel   Computation   Proc   1991   ALCOM   Spring   School   on   Parallel   Computation"   CiteSeer_Volume=""   Title="{G}eneral   {P}urpose   {P}arallel   {C}omputing,"   />

      <rec   ID="/4966.html"   Type="inproceedings"   CiteSeer_Book="5th   EUROMICRO   Workshop   on   Parallel   and   Distributed   Processing   London   United   Kingdom"   CiteSeer_Volume=""   Title="A   General   but   Simple   Technique   to   Handle   Asynchronous   Data-Parallel   Control   Structures,">

            <identifier   Org="ISBN:0818678828"   Paper_ID="/4966.html"   Extracted="0818678828"   DDC="005.2/75"   Normalized_DDC="005275"   Normalized_Weight="1.0"   />

      </rec>

      <rec   ID="/26937.html"   Type="article"   CiteSeer_Book="Journal   of   Parallel   and   Distributed   Computing"   CiteSeer_Volume="50"   Title="A   Structured   Synchronization   and   Communication   Model   Fitting   Irregular   Data   Accesses,">

            <identifier   Org="ISBN:3540664432"   Paper_ID="/26937.html"   Extracted="3540664432"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.5"   />

            <identifier   Org="ISBN:3540681051"   Paper_ID="/26937.html"   Extracted="3540681051"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.5"   />

      </rec>

      <rec   ID="/117752.html"   Type="unpublished"   CiteSeer_Book=""   CiteSeer_Volume=""   Title="mini{BSP}:   {A}   {{BSP}}   {L}anguage   and   {T}ransformation   {S}ystem,"   />

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="A   Cost   Model   For   Asynchronous   and   Structured   Message   Passing   (Extended   Version)">

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

      </rec>

</references_metadata>

www.000webhost.com