Source: http://www.google.com/patents/US7603488?ie=ISO-8859-1&dq=7,117,286
Timestamp: 2015-04-28 01:54:35
Document Index: 585095584

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60']

Patent US7603488 - Systems and methods for efficient memory management - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsSystems and methods for providing efficient memory allocation, reduced processor intervention and power consumption, and increased memory access bandwidth. One embodiment comprises a system including a plurality of memory units which are accessible in parallel, a dynamic memory unit configured to dynamically...http://www.google.com/patents/US7603488?utm_source=gb-gplus-sharePatent US7603488 - Systems and methods for efficient memory managementAdvanced Patent SearchPublication numberUS7603488 B1Publication typeGrantApplication numberUS 10/892,538Publication dateOct 13, 2009Filing dateJul 15, 2004Priority dateJul 15, 2003Fee statusLapsedPublication number10892538, 892538, US 7603488 B1, US 7603488B1, US-B1-7603488, US7603488 B1, US7603488B1InventorsMartin Gravenstein, Nirmalendu B. Patra, Andrew Probst, Dave Ohmann, Clair A. HardestyOriginal AssigneeAlereon, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (8), Referenced by (5), Classifications (16), Legal Events (7) External Links: USPTO, USPTO Assignment, EspacenetSystems and methods for efficient memory management
This application claims priority to U.S. Provisional Patent Application No. 60/487,293, entitled �Wireless Mesh Networking Implemented over TDMA� by Gravenstein, filed Jul. 15, 2003; U.S. Provisional Patent Application No. 60/487,302, entitled �Wireless 1394 by Means of Wireless DMA� by Hardesty, et al., filed Jul. 15, 2003; U.S. Provisional Patent Application No. 60/487,348, entitled �Parallel Access Instruction Driven�Dynamic Memory Unit,� by Probst, et al., filed Jul. 15, 2003; U.S. Provisional Patent Application No. 60/487,563, entitled �Efficient Data Transfer Mechanism,� by Patra, et al., filed Jul. 15, 2003; and U.S. Provisional Patent Application No. 60/487,341, entitled �Packet Reordering for Hi-speed Networks,� by Patra, et al., filed Jul. 15, 2003; U.S. Provisional Patent Application No. 60/487,349, entitled �Building a Wireless PCI Bridge by Means of Wireless DMA,� Hardesty, et al., filed Jul. 15, 2003; each of which is fully incorporated by reference as if set forth herein in its entirety.
Conventional mechanisms for memory management (e.g., memory management units, or MMUs) are constrained by various limitations. For example, in conventional systems, memory is statically allocated prior to its use. In other words, a judgment is made as to the amount of memory that will be required for a particular program or process, and this amount of memory is allocated for use by the program/process. If insufficient memory is allocated, the program/process may not have enough memory to store all of the data that it needs to store, and some of the data may be lost. This may be referred to as a data overflow. In order to avoid a data overflow condition, it may be desirable to over-allocate (i.e., to allocate more memory than is expected to be used.) If less than all of the memory is actually used, however, the unused portion of the memory is wasted�it is not used by the program/process, yet could not be allocated to a different program/process. Whether the memory space is under-allocated or over-allocated, the usage of the memory space is inefficient.
As noted above, each of ports 211-213 of MMU micro engine 210 includes an instruction decoder, as well as allocate, deallocate and access (read/write) state machines. This is because, in the embodiment of FIG. 2, accesses to packet memory 140 are instruction-driven. This design allows packet memory-related functions to be completed more quickly. For example, memory is conventionally allocated in two steps. First, there is a write to a control register indicating that it is desired to allocate a block of memory. Then, it is necessary to perform a read to get the pointer to the allocated memory. In the present, instruction-driven design, the same thing can be accomplished in one step�an �allocate� instruction is issued, where this instruction returns a pointer to the allocated memory. The design of the embodiment shown in FIG. 2 also includes an instruction bus to support this instruction-driven access to the packet memory.
As explained above, the DMA relaxation FIFOs serve as a sort of �resting place� for data that is being moved through MAC engine 130 from the system to the wireless link, or vice versa. The FIG. 3 illustrates an example of data movement in each direction�from the system to the wireless link, and from the wireless link to the system. Data movement in each direction is considered a separate DMA channel, and each of these DMA channels has its own relaxation buffer within packet memory 140. While only two DMA channels are illustrated in the figure, there may actually be many more, each having its own FIFO.
As explained above, the operation of TDMA micro engine 220 and FIFO micro engine 230 are slightly different with respect to the manner in which they move data. As the name (�time division multiple access�) implies, TDMA micro engine 220 divides its available time between the various transmit channels that require its attention. Thus, if there are multiple FIFOs that hold data to be transmitted over the wireless link, TDMA micro engine 220 may, for example, divide a certain period of time by the number of transmit channels (which can be determined from the context table described below.) The resulting interval is the portion of the period that is allocated to each channel. Alternatively, the interval may be specified by the MAC protocol.
In one embodiment, the first byte of the first block (411) of linked list 410, includes a �0� bit 420 and a length 421. The �0� bit indicates that the blocks form a normal, un-fragmented packet. Length 421 indicates the number of data bytes in the packet. This length may span several linked blocks of memory (in this case, three.) The last byte (422) of memory block 411 is a pointer to the block of memory storing the next byte of the packet. As many memory blocks as are needed to store the packet may be allocated and linked together. If the packet does not completely fill the last memory block (413,) the unused bytes in the block are left empty. It should be noted that the particular formatting of the packet, including the specific structure of the packet indicator (420), length indicator (421), next-block pointer (422), and so on, may vary in other embodiments.
Referring to FIG. 4B, the structure of a fragmented packet stored as a linked list 430 is shown. Linked list 430 includes three smaller linked lists, 431-433, each of which is linked to the next (i.e., 431 is linked to 432 and 432 is linked to 433.) Each of linked lists 431-433 is similar in structure to linked list 410. One of the primary differences is that, rather than storing a complete packet, each of lists 431-433 stores a packet fragment rather than a complete packet. Accordingly, the length identified in each of lists 431-433 is the length of the corresponding fragment, rather than the length of a packet. Another of the primary differences is that, in the first block of memory, the first data bit, 441 is a �1,� indicating that the memory blocks form a fragmented packet, and the remainder (442) of the first data byte indicates the number of fragments in the packet. (In one embodiment, this indicator can be set to 1, indicating that it is a complete packet, rather than a packet fragment.) Then, the second byte of the block contains a �0� bit (443,) followed by the length (444) of the fragment. The third and subsequent bytes of the data block contain the data of the packet fragment, with next-block pointers and empty bytes as explained above in connection with storage of the unfragmented packet.
It should be noted that, for the purposes of clarity in the following discussion, �packet fragments� or �fragments� will be used to refer to both fragments of packets and complete packets.
This situation becomes even more complicated in another acknowledgment/re-ordering scheme which is referred to herein as �delayed acknowledgment.� In this scheme, the transmitter transmits multiple packets to the receiver and, at some point, transmits a request for delayed acknowledgment of the received packets. There is no set time for requesting this acknowledgment, however. The receiver is therefore responsible for indefinitely maintaining a list of received packet fragments that can be returned in response to a delayed acknowledgment request, and also maintaining all of the received packet fragments that cannot be delivered because earlier packets have not been successfully received.
The linked list packet storage scheme employed by the dynamic memory unit is useful to provide support for delayed acknowledgment because this scheme facilitates the handling of the packet fragments when they cannot be delivered to the destination device. In conventional systems, these packets typically have to be stored twice�first, when they are stored and awaiting missing packets, and second, when the missing packets are received and the packets need to be recopied into the correct order before being delivered to their destination. Using the linked list scheme, the packet fragments can simply be copied into the packet memory once, and when the missing packet fragments are received, they are simply joined or �stitched� into the chain of packets, which can then be delivered to the destination device.
The dynamic memory unit keeps track of the different pieces of the linked list by retaining the portion of the list between breaks as complete chains of data. As packet fragments which fall within the breaks are received, these packets are �stitched� onto the end of the preceding chain if possible. If there remains a missing packet fragment between the newly received packet fragment and the preceding chain, the nearly received packet fragment is viewed as the beginning of the succeeding chain. Whenever a packet or fragment immediately preceding the top of an existing chain is received, the existing chain is stitched on to the newly received packet fragment.
As used herein, �stitching� packet fragments together consists simply of joining the packet fragments by setting the pointer at the end of the preceding packet fragment to point to the beginning of the succeeding packet fragment. The data packet fragments are thereby incorporated into the chain in the same manner as if they had originally been received in the order in which they were transmitted. (Remember that, in either case, the space for the packet fragment is randomly allocated among the memory units, so there is no need to find contiguous memory space for the new data.) Further, because the two parts of the linked list can be connected simply by setting a pointer, there is no need to recopy completed packets to a different memory location sent that they can then be moved (via DMA) to the destination device. The dynamic memory unit thereby saves the cost associated with the recopying of the data.
The chains (linked lists) formed by the received portions of the linked list of FIFO 550 are represented in FIG. 6. There are three chains�the first includes only packet fragment 561, the second includes packet fragment 563 and packet 552, and the third includes packet 553. When missing packet fragment 562 is received, it will be stored in memory, and the pointer at the end of packet fragment 561 will be set to point to the beginning of packet fragment 562. The first chain will then consist of a linked list having these two packet fragments. Then, because there are no longer any missing packet fragments between fragments 562 and 563, these two fragments can be stitched together by setting the pointer at the end of fragment 562 to point to the beginning of fragment 563. At this point, there will be only two chains�the first including packets 551 and 552, and the second including only packet 554. Because packets 551 and 552 are now complete, and because they are the next packets to be read from the FIFO, FIFO micro engine 230 can be notified that they are ready to be delivered. FIFO micro engine 230 can then read these packets from the linked lists, copy them to the destination memory and deallocate the memory space that had been used to store packets 551 and 552. Later, when packet 553 is received, it can be stitched together with packet 554, and these packets can be delivered as well.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5930827 *Dec 2, 1996Jul 27, 1999Intel CorporationMethod and apparatus for dynamic memory management by association of free memory blocks using a binary tree organized in an address and size dependent mannerUS6026464 *Jun 24, 1997Feb 15, 2000Cisco Technology, Inc.Memory control system and method utilizing distributed memory controllers for multibank memoryUS6154793 *Apr 30, 1997Nov 28, 2000Zilog, Inc.DMA with dynamically assigned channels, flexible block boundary notification and recording, type code checking and updating, commands, and status reportingUS6654819 *Jun 26, 2000Nov 25, 2003Texas Instruments IncorporatedExternal direct memory access processor interface to centralized transaction processorUS6820142 *Dec 14, 2000Nov 16, 2004International Business Machines CorporationToken based DMAUS20020097594 *Mar 27, 2001Jul 25, 2002Bruce Ricardo H.Parallel erase operations in memory systemsUS20030012223 *Jul 10, 2001Jan 16, 2003Chappell Christopher L.System and method for processing bandwidth allocation messagesUS20030123392 *Dec 31, 2001Jul 3, 2003Jussi RuutuPacket flow control method and device* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8601182 *Mar 23, 2009Dec 3, 2013Fujitsu LimitedData communication control deviceUS8701095Jul 25, 2005Apr 15, 2014Microsoft CorporationAdd/remove memory pressure per objectUS8713524 *Apr 6, 2005Apr 29, 2014Microsoft CorporationMemory management configurationUS20060230387 *Apr 6, 2005Oct 12, 2006Microsoft CorporationMemory management configurationWO2011091690A1 *Dec 9, 2010Aug 4, 2011Zte CorporationData processing method and apparatus* Cited by examinerClassifications U.S. Classification710/22, 710/20, 711/120, 710/21, 712/9, 710/56International ClassificationG06F13/28, G06F3/00Cooperative ClassificationY02B60/1225, G06F12/0223, G06F2212/171, G06F12/023, H04L1/1874, H04L1/1835European ClassificationG06F12/02D, G06F12/02D2Legal EventsDateCodeEventDescriptionJan 9, 2014ASAssignmentOwner name: ALEREON, INC., TEXASFree format text: RELEASE BY SECURED PARTY;ASSIGNORS:ENHANCED CAPITAL TEXAS FUND II, LLC;ENHANCED JOBS FOR TEXAS FUND, LLC;REEL/FRAME:031948/0065Effective date: 20131227Dec 3, 2013FPExpired due to failure to pay maintenance feeEffective date: 20131013Oct 13, 2013LAPSLapse for failure to pay maintenance feesMay 24, 2013REMIMaintenance fee reminder mailedApr 13, 2012ASAssignmentEffective date: 20120412Free format text: SECURITY AGREEMENT;ASSIGNOR:ALEREON, INC.;REEL/FRAME:028039/0323Owner name: ENHANCED JOBS FOR TEXAS FUND, LLC, NEW YORKEffective date: 20120412Owner name: ENHANCED CAPITAL TEXAS FUND II, LLC, NEW YORKFree format text: SECURITY AGREEMENT;ASSIGNOR:ALEREON, INC.;REEL/FRAME:028039/0323Apr 3, 2012ASAssignmentFree format text: RELEASE BY SECURED PARTY;ASSIGNOR:VENTURE LENDING & LEASING IV, INC.;REEL/FRAME:027982/0814Effective date: 20120330Owner name: ALEREON, INC., TEXASFree format text: RELEASE BY SECURED PARTY;ASSIGNOR:VENTURE LENDING & LEASING V, INC.;REEL/FRAME:027982/0868Effective date: 20120330Owner name: ALEREON, INC., TEXASNov 15, 2004ASAssignmentOwner name: ALEREON, INC., TEXASFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:GRAVENSTEIN, MARTIN;PATRA, NIRMALENDU B.;PROBST, ANDREW;AND OTHERS;REEL/FRAME:015995/0527;SIGNING DATES FROM 20041104 TO 20041105RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services