Entry Narlikar:1999:SES 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{Narlikar:1999:SES,
  author =       "Girija J. Narlikar and Guy E. Blelloch",
  title =        "Space-Efficient Scheduling of Nested Parallelism",
  journal =      j-TOPLAS,
  volume =       "21",
  number =       "1",
  pages =        "138--173",
  month =        jan,
  year =         "1999",
  CODEN =        "ATPSDT",
  ISSN =         "0164-0925 (print), 1558-4593 (electronic)",
  ISSN-L =       "0164-0925",
  bibdate =      "Tue Sep 26 10:12:58 MDT 2000",
  bibsource =    "http://www.acm.org/pubs/contents/journals/toplas/;
                 http://www.math.utah.edu/pub/tex/bib/toplas.bib",
  URL =          "http://www.acm.org/pubs/citations/journals/toplas/1999-21-1/p138-narlikar/",
  abstract =     "Many of today's high-level parallel languages support
                 dynamic, fine-grained parallelism. These languages
                 allow the user to expose all the parallelism in the
                 program, which is typically of a much higher degree
                 than the number of processors. Hence an efficient
                 scheduling algorithm is required to assign computations
                 to processors at runtime. Besides having low overheads
                 and good load balancing, it is important for the
                 scheduling algorithm to minimize the space usage of the
                 parallel program. This article presents an on-line
                 scheduling algorithm that is provably space efficient
                 and time efficient for nested-parallel languages. For a
                 computation with depth $D$ and serial space requirement
                 $S_1$, the algorithm generates a schedule that requires
                 at most $S_1 + O(K\cdot D\cdot p)$ space (including
                 scheduler space) on $p$ processors. Here, $K$ is a
                 user-adjustable runtime parameter specifying the net
                 amount of memory that a thread may allocate before it
                 is preempted by the scheduler. Adjusting the value of
                 $K$ provides a trade-off between the running time and
                 the memory requirement of a parallel computation. To
                 allow the scheduler to scale with the number of
                 processors we also parallelize the scheduler and
                 analyze the space and time bounds of the computation to
                 include scheduling costs. In addition to showing that
                 the scheduling algorithm is space and time efficient in
                 theory, we demonstrate that it is effective in
                 practice. We have implemented a runtime system that
                 uses our algorithm to schedule lightweight parallel
                 threads. The results of executing parallel programs on
                 this system show that our scheduling algorithm
                 significantly reduces memory usage compared to previous
                 techniques, without compromising performance.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Transactions on Programming Languages and
                 Systems",
  generalterms = "Algorithms; Languages; Performance",
  keywords =     "dynamic scheduling; multithreading; nested
                 parallelism; parallel language implementation; space
                 efficiency",
  subject =      "Software --- Programming Techniques --- Concurrent
                 Programming (D.1.3): {\bf Parallel programming};
                 Software --- Programming Languages --- Processors
                 (D.3.4): {\bf Run-time environments}; Theory of
                 Computation --- Analysis of Algorithms and Problem
                 Complexity --- General (F.2.0)",
}

Related entries