Entry Amarasinghe:1993:COC 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{Amarasinghe:1993:COC,
  author =       "Saman P. Amarasinghe and Monica S. Lam",
  title =        "Communication optimization and code generation for
                 distributed memory machines",
  journal =      j-SIGPLAN,
  volume =       "28",
  number =       "6",
  pages =        "126--138",
  month =        jun,
  year =         "1993",
  CODEN =        "SINODQ",
  ISBN =         "0-89791-598-4",
  ISBN-13 =      "978-0-89791-598-4",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  bibdate =      "Sun Dec 14 09:16:37 MST 2003",
  bibsource =    "http://portal.acm.org/;
                 http://www.acm.org/pubs/contents/proceedings/pldi/155090/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/155090/p126-amarasinghe/",
  abstract =     "This paper presents several algorithms to solve code
                 generation and optimization problems specific to
                 machines with distributed address spaces. Given a
                 description of how the computation is to be partitioned
                 across the processors in a machine, our algorithms
                 produce an SPMD (single program multiple data) program
                 to be run on each processor. Our compiler generated the
                 necessary receive and send instructions, optimizes the
                 communication by eliminating redundant communication
                 and aggregating small messages into large messages,
                 allocates space locally on each processor, and
                 translates global data addresses to local addresses.
                 Our techniques are based on an exact data-flow analysis
                 on individual array element accesses. Unlike data
                 dependence analysis, this analysis determines if two
                 dynamic instances refer to the same value, and not just
                 to the same location. Using this information, our
                 compiler can handle more flexible data decompositions
                 and find more opportunities for communication
                 optimization than systems based on data dependence
                 analysis. Our technique is based on a uniform
                 framework, where data decompositions, computation
                 decompositions and the data flow information are all
                 represented as systems of linear inequalities. We show
                 that the problems of communication code generation,
                 local memory management, message aggregation and
                 redundant data communication elimination can all be
                 solved by projecting polyhedra represented by sets of
                 inequalities onto lower dimensional spaces.",
  acknowledgement = ack-nhfb,
  affiliation =  "Comput. Syst. Lab., Stanford Univ., CA, USA",
  annote =       "Published as part of the Proceedings of PLDI'93.",
  classification = "C6110P (Parallel programming); C6120 (File
                 organisation); C6150C (Compilers, interpreters and
                 other processors)",
  confdate =     "23-25 June 1993",
  conflocation = "Albuquerque, NM, USA",
  confsponsor =  "ACM",
  keywords =     "algorithms; Code generation; Communication code
                 generation; Compiler; Computation decompositions; Data
                 flow information; Distributed address spaces; Exact
                 data-flow analysis; Global data addresses; Individual
                 array element accesses; Linear inequalities; Local
                 addresses; Local memory management; Message
                 aggregation; Optimization problems; performance;
                 Polyhedra; Redundant communication; Redundant data
                 communication elimination; Send instructions; Single
                 program multiple data; SPMD; theory; Uniform
                 framework",
  subject =      "{\bf D.3.4} Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf D.3.4} Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers. {\bf
                 D.3.4} Software, PROGRAMMING LANGUAGES, Processors,
                 Code generation. {\bf F.3.3} Theory of Computation,
                 LOGICS AND MEANINGS OF PROGRAMS, Studies of Program
                 Constructs. {\bf G.2.2} Mathematics of Computing,
                 DISCRETE MATHEMATICS, Graph Theory, Trees.",
  thesaurus =    "Distributed memory systems; Parallel programming;
                 Program compilers; Storage management",
}

Related entries