Entry vonHanxleden:1992:RSC from sigplan1990.bib

Last update: Thu Apr 12 03:37:15 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | 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{vonHanxleden:1992:RSC,
  author =       "Reinhard {von Hanxleden} and Ken Kennedy",
  title =        "Relaxing {SIMD} control flow constraints using loop
                 transformations",
  journal =      j-SIGPLAN,
  volume =       "27",
  number =       "7",
  pages =        "188--199",
  month =        jul,
  year =         "1992",
  CODEN =        "SINODQ",
  ISBN =         "0-89791-475-9",
  ISBN-13 =      "978-0-89791-475-8",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  LCCN =         "QA76.7.S53 1992",
  bibdate =      "Thu May 13 12:37:27 MDT 1999",
  bibsource =    "Compendex database;
                 http://www.acm.org/pubs/contents/proceedings/pldi/143095/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/143095/p188-v__hanxleden/",
  abstract =     "Many loop nests in scientific codes contain a
                 parallelizable outer loop but have an inner loop for
                 which the number of iterations varies between different
                 iterations of the outer loop. When running this kind of
                 loop nest on a SIMD machine, the SIMD-inherent
                 restriction to single program counter common to all
                 processors will cause a performance degradation
                 relative to comparable MIMD implementations. This
                 problem is not due to limited parallelism or bad load
                 balance, it is merely a problem of control flow. This
                 paper presents a loop transformation, which we call
                 {\em loop flattening\/}, that overcomes this limitation
                 by letting each processor advance to the next loop
                 iteration containing useful computation, if there is
                 such an iteration for the given processor. We study a
                 concrete example derived from a molecular dynamics code
                 and compare performance results for flattened and
                 unflattened versions of this kernel on two SIMD
                 machines, the CM-2 and the DECmpp 12000. We then
                 evaluate loop flattening from the compiler's
                 perspective in terms of applicability, cost,
                 profitability, and safety. We conclude with arguing
                 that loop flattening, whether performed by the
                 programmer or by the compiler, introduces negligible
                 overhead and can significantly improve the performance
                 of scientific codes for solving irregular problems.",
  acknowledgement = ack-nhfb,
  affiliation =  "Rice Univ",
  affiliationaddress = "Houston, TX, USA",
  annote =       "Published as part of the Proceedings of PLDI'92.",
  classification = "723.1",
  conference =   "Proceedings of the ACM SIGPLAN '92 Conference on
                 Programming Language Design and Implementation",
  conferenceyear = "1992",
  journalabr =   "SIGPLAN Not",
  keywords =     "algorithms; Computer architecture; Computer
                 programming; design; languages; Loop flattening; Loop
                 transformations; Parallel processing systems",
  meetingaddress = "San Francisco, CA, USA",
  meetingdate =  "Jun 17--19 1992",
  meetingdate2 = "06/17--19/92",
  sponsor =      "ACM",
  subject =      "{\bf D.3.4} Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf D.3.2} Software,
                 PROGRAMMING LANGUAGES, Language Classifications,
                 FORTRAN. {\bf C.1.2} Computer Systems Organization,
                 PROCESSOR ARCHITECTURES, Multiple Data Stream
                 Architectures (Multiprocessors),
                 Single-instruction-stream, multiple-data-stream
                 processors (SIMD). {\bf F.3.3} Theory of Computation,
                 LOGICS AND MEANINGS OF PROGRAMS, Studies of Program
                 Constructs. {\bf D.3.3} Software, PROGRAMMING
                 LANGUAGES, Language Constructs and Features, Control
                 structures. {\bf D.3.4} Software, PROGRAMMING
                 LANGUAGES, Processors, Optimization.",
}

Related entries