Skip to main content
SpringerLink
Log in
Book cover

Algorithm Engineering and Experimentation

International Workshop ALENEX'99 Baltimore, MD, USA, January 15-16, 1999, Selected Papers

  • Book
  • © 1999

Overview

Editors:
  1. Michael T. Goodrich

    1. Department of Computer Science, John Hopkins University, Baltimore, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Catherine C. McGeoch

    1. Department of Mathematics and Computer Science, Amherst University, Amherst, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1619)

Included in the following conference series:

Conference proceedings info: ALENEX 1999.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (20 chapters)

  1. Front Matter

    Pages I-VII
    Download chapter PDF

  2. Combinatorial Algorithms

    1. Efficient Implementation of the WARM-UP Algorithm for the Construction of Length-Restricted Prefix Codes

      • Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany Laber
      Pages 1-17

    2. Implementing Weighted b-Matching Algorithms: Insights from a Computational Study

      • Matthias Müller-Hannemann, Alexander Schwartz
      Pages 18-36

    3. Designing Practical Efficient Algorithms for Symmetric Multiprocessors

      • David R. Helman, Joseph JáJá
      Pages 37-56

    4. Circular Drawings of Biconnected Graphs

      • Janet M. Six, Ioannis G. Tollis
      Pages 57-73

    5. Heuristics and Experimental Design for Bigraph Crossing Number Minimization

      • Matthias Stallmann, Franc Brglez, Debabrata Ghosh
      Pages 74-93

    6. Binary Space Parititions in Plücker Space

      • David M. Mount, Fan-Tao Pu
      Pages 94-113

    7. Practical Point-in-Polygon Tests Using CSG Representations of Polygons

      • Robert J. Walker, Jack Snoeyink
      Pages 114-128

  3. Software and Applications

    1. Accessing the Internal Organization of Data Structures in the JDSL Library

      • Michael T. Goodrich, Mark Handy, Benoît Hudson, Roberto Tamassia
      Pages 129-144

    2. Object-Oriented Design of Graph Oriented Data Structures

      • Maurizio Pizzonia, Giuseppe Di Battista
      Pages 145-160

    3. A Case Study on the Cost of Geometric Computing

      • Stefan Schirra
      Pages 161-181

    4. Design and Implementation of the Fiduccia-Mattheyses Heuristic for VLSI Netlist Partitioning

      • Andrew E. Caldwell, Andrew B. Kahng, Igor L. Markov
      Pages 182-198

    5. Algorithms for Restoration Planning in a Telecommunications Network

      • S. Cwilich, M. Deng, D. F. Lynch, S. J. Phillipsy, J. R. Westbrooky
      Pages 199-214

    6. Computing the n × m Shortest Paths Efficiently

      • Tetsuo Shibuya
      Pages 215-229

    7. Image Watermarking for Copyright Protection

      • Gregory L. Heileman, Carlos E. Pizano, Chaouki T. Abdallah
      Pages 230-249

  4. Algorithms for NP-Hard Problems

    1. A Self Organizing Bin Packing Heuristic

      • Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, Richard R. Weber
      Pages 250-269

    2. Finding the Right Cutting Planes for the TSP

      • Matthew S. Levine
      Pages 270-285

    3. Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An Exact Algorithm

      • Martin Zachariasen, Pawel Winter
      Pages 286-299

  5. Data Structures

    1. Adaptive Algorithms for Cache-efficient Trie Search

      • Anurag Acharya, Huican Zhu, Kai Shen
      Pages 300-315

    2. Fast Priority Queues for Cached Memory

      • Peter Sanders
      Pages 316-321
Back to top

Keywords

About this book

Symmetric multiprocessors (SMPs) dominate the high-end server market and are currently the primary candidate for constructing large scale multiprocessor systems. Yet, the design of e cient parallel algorithms for this platform c- rently poses several challenges. The reason for this is that the rapid progress in microprocessor speed has left main memory access as the primary limitation to SMP performance. Since memory is the bottleneck, simply increasing the n- ber of processors will not necessarily yield better performance. Indeed, memory bus limitations typically limit the size of SMPs to 16 processors. This has at least twoimplicationsfor the algorithmdesigner. First, since there are relatively few processors availableon an SMP, any parallel algorithm must be competitive with its sequential counterpart with as little as one processor in order to be r- evant. Second, for the parallel algorithm to scale with the number of processors, it must be designed with careful attention to minimizing the number and type of main memory accesses. In this paper, we present a computational model for designing e cient al- rithms for symmetric multiprocessors. We then use this model to create e cient solutions to two widely di erent types of problems - linked list pre x com- tations and generalized sorting. Both problems are memory intensive, but in die rent ways. Whereas generalized sorting algorithms typically require a large numberofmemoryaccesses, they areusuallytocontiguousmemorylocations. By contrast, prex computation algorithms typically require a more modest qu- tity of memory accesses, but they are are usually to non-contiguous memory locations.

Editors and Affiliations

  • Department of Computer Science, John Hopkins University, Baltimore, USA

    Michael T. Goodrich

  • Department of Mathematics and Computer Science, Amherst University, Amherst, USA

    Catherine C. McGeoch

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation