Segmentation management using a rolling window technique

• US 7,441,093 B2
• Filed: 06/30/2005
• Issued: 10/21/2008
• Est. Priority Date: 06/30/2005
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Conley, Christopher N., Ganjoo, Afshin
• Primary Examiner(s): Shah; Sanjiv
• Assistant Examiner(s): TSUI, DANIEL D
• Application Number:
  US11/174,072
• Publication Number:
  US 20070005921A1
• Time in Patent Office: 1,209 Days
• Field of Search: 711/103, 711/165, 711/171
• US Class Current: 711/165
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory

Abstract

A method, device, and system are disclosed. In one embodiment, the method comprises receiving a code segment to be inserted into a flash memory storing code segments, selecting one or more contiguous code segments in flash memory with a total size equal to or larger than the received code segment, calculating the amount of data movement necessary for the one or more selected contiguous code segments, and if the amount is minimum, moving the one or more selected contiguous code segments and replacing them with the received code segment.

Claims

1. A method, comprising:

receiving a code segment to be inserted into a flash memory storing code segments;

selecting one or more contiguous code segments in flash memory with a total size equal to or larger than the received code segment;

calculating the amount of contiguous code segment data to be removed to insert the received code segment and the cost to relocate the removed code segments to alternate locations in the flash memory; and

if the amount is minimum,

moving the one or more selected contiguous code segments and replacing them with the received code segments;

removing the one or more selected contiguous code segments from a table of code segments;

placing the one or more selected contiguous code segments in a list of segments to be added to the table;

placing the received code segment in the table at the location of the one or more removed contiguous code segments; and

sorting the list by decreasing size of code segments.

2. The method of claim 1, further comprising recursively calculating the amount of code segment data movement required to allow all current code segments to remain in flash memory and the insertion of the received code segment in flash memory.

3. The method of claim 1, wherein the minimum amount of data movement further comprises the least amount of total data to be moved in flash memory required to insert the received code segment and move all of the one or more selected contiguous code segments to other location in flash memory.

4. A device, comprising:

a memory to store a table of code segments and a list of segments to be added to the table;

a segment receiving unit to receive a code segment and place the code segment in the list of segments to be added to the table;

a segment selection unit to select one or more contiguous code segments in the table with a total size greater than or equal to the received code segment;

a data movement calculation unit to calculate the necessary amount of contiguous code segment data to be removed to insert the received code segment and the cost to relocate the removed code segments to alternate locations in a flash memory; and

if the calculated amount of data movement is minimum, a segment rearranging unit to

move the one or more selected contiguous code segments to one or more different locations in flash memory and replace them with the received code segments;

remove the one or more selected contiguous code segments from the table;

place the one or more selected contiguous code segments in the list;

place the received code segment in the table at the location of the one or more removed contiguous code segments; and

sort the list by decreasing size of code segments.

5. The device of claim 4, wherein the segment selection unit is further operable to select one or more contiguous code segments in the table with a total size greater than or equal to the code segment at the top of the list.

6. The device of claim 4, wherein the data movement calculation unit is further operable to recursively calculate the cost of moving the code segments that require rearrangement to allow all current code segments to remain in flash memory when the received code segment is inserted.

7. The device of claim 4, wherein the minimum amount of data movement further comprises the least amount of total data to be moved in flash memory required to insert the received code segment and move all of the one or more selected contiguous code segments to one or more other locations in flash memory.

8. A system, comprising:

an interconnect;

a processor coupled to the interconnect;

a flash memory device coupled to the interconnect;

a memory, coupled to the interconnect, to store

a table of code segments representing code segments stored in the flash memory device; and

a list of segments to be added to the table; and

a segmentation management device, coupled to the interconnect, further comprising;

a segment receiving unit, operable to

receive a code segment for storage in the flash memory; and

place the code segment in the list of segments to be added to the table;

a segment selection unit, operable to select one or more contiguous code segments in the table with a total size greater than or equal to the received code segment;

a data movement calculation unit, operable to calculate the amount of calculating the amount of contiguous code segment data to be removed to insert the received code segment and the cost to relocate the removed code segments to alternate locations in the flash memory; and

if the calculated amount of data movement is minimum, a segment rearranging unit operable to

move the selected contiguous code segment and replace with the received code segment in the flash memory;

remove the one or more selected contiguous code segments from the table;

place the one or more selected contiguous code segments in the list;

place the received code segment in the table at the location of the one or more removed contiguous code segments; and

sort the list by decreasing size of code segments.

9. The system of claim 8, wherein the segment selection unit is further operable to select one or more contiguous code segments in the table with a total size greater than or equal to the code segment at the top of the list.

10. The system of claim 8, wherein the cost calculation is further operable to recursively calculate the cost of moving the code segments that require rearrangement to allow all current code segments to remain in flash memory when the received code segment is inserted in flash memory.

11. The system of claim 8, wherein the minimum amount of data movement further comprises the least amount of total data to be moved in flash memory required to insert the received code segment and move all of the one or more selected contiguous code segments to one or more other locations in flash memory.

12. The system of claim 8, wherein the system farther comprises one or more additional processors coupled to the interconnect.