Entry Kennedy:1998:ADL from toplas.bib

Last update: Tue May 1 02:05:46 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Kennedy:1998:ADL,
  author =       "Ken Kennedy and Ulrich Kremer",
  title =        "Automatic Data Layout for Distributed-Memory
                 Machines",
  journal =      j-TOPLAS,
  volume =       "20",
  number =       "4",
  pages =        "869--916",
  month =        jul,
  year =         "1998",
  CODEN =        "ATPSDT",
  ISSN =         "0164-0925 (print), 1558-4593 (electronic)",
  ISSN-L =       "0164-0925",
  bibdate =      "Mon Mar 1 10:04:11 MST 1999",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/toplas.bib",
  URL =          "http://www.acm.org:80/pubs/citations/journals/toplas/1998-20-4/p869-kennedy/",
  abstract =     "The goal of languages like Fortran D or High
                 Performance Fortran (HPF) is to provide a simple yet
                 efficient machine-independent parallel programming
                 model. After the algorithm selection, the data layout
                 choice is the key intellectual challenge in writing an
                 efficient program in such languages. The performance of
                 a data layout depends on the target compilation system,
                 the target machine, the problem size, and the number of
                 available processors. This makes the choice of a good
                 layout extremely difficult for most users of such
                 languages. If languages such as HPF are to find general
                 acceptance, the need for data layout selection support
                 has to be addressed. We believe that the appropriate
                 way to provide the needed support is through a tool
                 that generates data layout specifications
                 automatically. This article discusses the design and
                 implementation of a data layout selection tool that
                 generates HPF-style data layout specifications
                 automatically. Because layout is done in a tool that is
                 not embedded in the target compiler and hence will be
                 run only a few times during the tuning phase of an
                 application, it can use techniques such as integer
                 programming that may be considered too computationally
                 expensive for inclusion in production compilers. The
                 proposed framework for automatic data layout selection
                 builds and examines search spaces of candidate data
                 layouts. A candidate layout is an efficient layout for
                 some part of the program. After the generation of
                 search spaces, a single candidate layout is selected
                 for each program part, resulting in a data layout for
                 the entire program. A good overall data layout may
                 require the remapping of arrays between program parts.
                 A performance estimator based on a compiler model, an
                 execution model, and a machine model are needed to
                 predict the execution time of each candidate layout and
                 the costs of possible remappings between candidate data
                 layouts. In the proposed framework, instances of
                 NP-complete problems are solved during the construction
                 of candidate layout search spaces and the final
                 selection of candidate layouts from each search space.
                 Rather than resorting to heuristics, the framework
                 capitalizes on state-of-the-art 0-1 integer programming
                 technology to compute optimal solutions of these
                 NP-complete problems. A prototype data layout assistant
                 tool based on our framework has been implemented as
                 part of the D system currently under development at
                 Rice University. The article reports preliminary
                 experimental results. The results indicate that the
                 framework is efficient and allows the generation of
                 data layouts of high quality.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Transactions on Programming Languages and
                 Systems",
  keywords =     "algorithms; languages; theory",
  subject =      "{\bf D.3.4} Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf C.1.2} Computer Systems
                 Organization, PROCESSOR ARCHITECTURES, Multiple Data
                 Stream Architectures (Multiprocessors). {\bf D.3.4}
                 Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization. {\bf E.1} Data, DATA STRUCTURES, Arrays.
                 {\bf G.1.6} Mathematics of Computing, NUMERICAL
                 ANALYSIS, Optimization, Integer programming. {\bf
                 D.3.4} Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization.",
}

Related entries