Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines.

Saved in:

Bibliographic Details
Title:	Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines.
Authors:	Chung, Fan¹ fan@ucsd.edu, Graham, Ronald² graham@ucsd.edu, Mao, Jia² jiamao@cs.ucsd.edu, Varghese, George² varghese@cs.ucsd.edu
Source:	Theory of Computing Systems. Nov/Dec2006, Vol. 39 Issue 6, p829-849. 21p. 8 Diagrams.
Subjects:	Computer storage devices, Macro processors, Internet protocols, Packet switching, Data transmission systems, Computer networks
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 $\frac 32$ asymptotically. The proof utilizes a new bin packing model, which is interesting in its own right. Further, for important special cases that arise in practice a more sophisticated modification of this approximation algorithm is in fact optimal. We also discuss the online memory allocation problem and present fast online algorithms that provide good memory utilization while allowing fast updates. [ABSTRACT FROM AUTHOR]
	Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
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 $\frac 32$ asymptotically. The proof utilizes a new bin packing model, which is interesting in its own right. Further, for important special cases that arise in practice a more sophisticated modification of this approximation algorithm is in fact optimal. We also discuss the online memory allocation problem and present fast online algorithms that provide good memory utilization while allowing fast updates. [ABSTRACT FROM AUTHOR]
ISSN:	14324350
DOI:	10.1007/s00224-006-1249-3