Automatically assigned DDC number: 00435

Manually assigned DDC number: 00435

Title: Determining the Idle Time of a Tiling




Subject: Karin Hogstedt,Larry Carter,Jeanne Ferrante Determining the Idle Time of a Tiling

Description: This paper investigates the idle time associated with a parallel computation, that is, the time that processors are idle because they are either waiting for data from other processors or waiting to synchronize with other processors. We study doubly-nested loops corresponding to parallelogram- or trapezoidal-shaped iteration spaces that have been parallelized by the wellknown tiling transformation. We introduce the notion of rise r, which relates the shape of the iteration space to that of the tiles. For parallelogram- shaped iteration spaces, we show that when r Gamma2, the idle time is linear in P , the number of processors, but when r Gamma1, it is quadratic in P . In the context of hierarchical tiling, where multiple levels of tiling are used, a good choice of rise can lead to less idle time and better performance. While idle time is not the only cost that should be considered in evaluating a tiling strategy, current architectural trends (of deeper memory hierarchies and multipl...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1997-08-22

Pubyear: 1997

Format: ps



Language: en

Rights: unrestricted


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


      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Determining   the   Idle   Time   of   a   Tiling">

            <identifier   Org="ISBN:0306477432"   Paper_ID="SELF"   Extracted="0306477432"   DDC="005.2/75"   Normalized_DDC="005275"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:0769505740"   Paper_ID="SELF"   Extracted="0769505740"   />

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

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

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

            <identifier   Org="ISBN:142004382X"   Paper_ID="SELF"   Extracted="142004382X"   DDC="005.4/53"   Normalized_DDC="005453"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:1581131240"   Paper_ID="SELF"   Extracted="1581131240"   />

            <identifier   Org="ISBN:1581134096"   Paper_ID="SELF"   Extracted="1581134096"   />

            <identifier   Org="ISBN:1581135297"   Paper_ID="SELF"   Extracted="1581135297"   />

            <identifier   Org="ISBN:3540660682"   Paper_ID="SELF"   Extracted="3540660682"   DDC="573/.8"   Normalized_DDC="5738"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:9810249519"   Paper_ID="SELF"   Extracted="9810249519"   />