Parallelism versus memory allocation in pipelined router forwarding engines

ABSTRACT

A crucial problem that needs to be solved is the allocation of memory to processors in a pipeline. Ideally, the processor memories should be totally separate (i.e., one port memories) in order to minimize contention; however, this minimizes memory sharing. Idealized sharing occurs by using a single shared memory for all processors but this maximizes contention. Instead, in this paper we show that perfect memory sharing of shared memory can be achieved with a collection of *two*-port memories, as long as the number of processors is less than the number of memories. We show that the problem of allocation is NP-complete in general, but has a fast approximation algorithm that comes within a factor of 3/2. The proof utilizes a new bin packing model, which is interesting in its own right. Further, for important special cases that arise in practice the approximation algorithm is indeed optimal. We also describe an incremental memory allocation algorithm that provides good memory utilization while allowing fast updates.

REFERENCES

• 1: A. Basu and G. Narlikar, Fast Incremental Updates for Pipeline Forwarding Engines, InfoCom 2003.
• 2: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 3: Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.943-958, September 1997 [doi>10.1109/71.615440]
• 4: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 5: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.3-14, September 14-18, 1997, Cannes, France
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: M. R. Garey and D. S. Johnson, Complexity results for multiprocessor scheduling under resource constraints, SIAM J. Comput., (1975), 397--411.
• 8: Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
• 9: B. Ramakrishna Rau, Pseudo-randomly interleaved memory, Proceedings of the 18th annual international symposium on Computer architecture, p.74-83, May 27-30, 1991, Toronto, Ontario, Canada
• 10: T. V. Lakshman , D. Stiliadis, High-speed policy-based packet forwarding using efficient multi-dimensional range matching, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.203-214, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 11: M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, Survey and Taxonomy of IP Address Lookup Algorithms, IEEE Network, March/April 2001.
• 12: Sandeep Sikka , George Varghese, Memory-efficient state lookups with fast updates, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.335-347, August 28-September 01, 2000, Stockholm, Sweden
• 13: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Performance, Theory

Keywords:
approximation algorithm, memory allocation