Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines.
Saved in:
| Title: | Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines. |
|---|---|
| Authors: | Chung, Fan1 fan@ucsd.edu, Graham, Ronald2 graham@ucsd.edu, Mao, Jia2 jiamao@cs.ucsd.edu, Varghese, George2 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 23302488 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Chung%2C+Fan%22">Chung, Fan</searchLink><relatesTo>1</relatesTo><i> fan@ucsd.edu</i><br /><searchLink fieldCode="AR" term="%22Graham%2C+Ronald%22">Graham, Ronald</searchLink><relatesTo>2</relatesTo><i> graham@ucsd.edu</i><br /><searchLink fieldCode="AR" term="%22Mao%2C+Jia%22">Mao, Jia</searchLink><relatesTo>2</relatesTo><i> jiamao@cs.ucsd.edu</i><br /><searchLink fieldCode="AR" term="%22Varghese%2C+George%22">Varghese, George</searchLink><relatesTo>2</relatesTo><i> varghese@cs.ucsd.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Nov/Dec2006, Vol. 39 Issue 6, p829-849. 21p. 8 Diagrams. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Computer+storage+devices%22">Computer storage devices</searchLink><br /><searchLink fieldCode="DE" term="%22Macro+processors%22">Macro processors</searchLink><br /><searchLink fieldCode="DE" term="%22Internet+protocols%22">Internet protocols</searchLink><br /><searchLink fieldCode="DE" term="%22Packet+switching%22">Packet switching</searchLink><br /><searchLink fieldCode="DE" term="%22Data+transmission+systems%22">Data transmission systems</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+networks%22">Computer networks</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=23302488 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00224-006-1249-3 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 21 StartPage: 829 Subjects: – SubjectFull: Computer storage devices Type: general – SubjectFull: Macro processors Type: general – SubjectFull: Internet protocols Type: general – SubjectFull: Packet switching Type: general – SubjectFull: Data transmission systems Type: general – SubjectFull: Computer networks Type: general Titles: – TitleFull: Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Chung, Fan – PersonEntity: Name: NameFull: Graham, Ronald – PersonEntity: Name: NameFull: Mao, Jia – PersonEntity: Name: NameFull: Varghese, George IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 11 Text: Nov/Dec2006 Type: published Y: 2006 Identifiers: – Type: issn-print Value: 14324350 Numbering: – Type: volume Value: 39 – Type: issue Value: 6 Titles: – TitleFull: Theory of Computing Systems Type: main |
| ResultId | 1 |
