Granted Patent B2

US 9,116,625 · App. 13/469,429 · Granted Aug 25, 2015

Inventor: David A. Palmer (Boise, ID)

Assignee: Micron Technology, Inc.

G06F3/0619G06F3/0659G06F3/0688

Abstract

Claims (56)

1. A method for write command overlap detection in a memory system, comprising:

creating a tree data structure comprising a first number of nodes, each of the first number of nodes being associated with a starting logical address and/or an ending logical address of a write command in a queue of write commands, wherein the tree data structure is created in response to the number of write commands in the queue reaching a first threshold number;

placing a second number of nodes associated with a starting logical address and/or an ending logical address of an incoming write command in the tree data structure;

comparing a node of the second number of nodes that is associated with a starting logical address of the incoming write command to an in-numerical-order predecessor node of the first number of nodes;

comparing the node of the second number of nodes that is associated with a starting logical address of the incoming write command to an in-numerical-order successor node of the first number of nodes;

comparing a node of the second number of nodes that is associated with an ending logical address of the incoming write command to an in-numerical-order successor node of the first number of nodes;

removing the placed second number of nodes associated with the starting logical address and/or the ending logical address of the incoming write command from the tree data structure in response to the logical address of the incoming write command overlapping with a logical address of a write command in the queue;

placing the incoming write command in the queue if the in-numerical-order predecessor node is an end node or a start/end node, the in-numerical-order successor node of the node associated with the starting logical address of the incoming write command is the node associated with the ending logical address of the incoming write command, and the in-numerical-order successor node of the node associated with the ending logical address is a start node or a start/end node;

executing a portion of the number of command in the queue; and

discontinuing use of the tree data structure and performing a linear comparison of the number of write commands in the queue in response to the number of write commands in the queue reaching a second threshold number.

2. The method of claim 1 , including placing the incoming write command in the queue if a logical address of the incoming write command does not overlap with a logical address of a write command in the queue.

3. The method of claim 1 , including aborting the incoming write command if a logical address of the incoming write command overlaps with a logical address of a write command in the queue.

4. The method of claim 1 , including delaying processing of the incoming write command if a logical address of the incoming write command overlaps with a logical address of a write command in the queue.

5. A method for write command overlap detection in a memory system, comprising:

creating a tree data structure comprising nodes associated with starting and/or ending logical addresses of each write command of a number of write commands in a queue in response to the number of commands in the queue reaching a first threshold number;

placing a node associated with a starting logical address of an incoming write command and a node associated with an ending logical address of an incoming write command in the tree data structure;

comparing the most recently placed node associated with the starting logical address of the incoming write command to an in-numerical-order predecessor node in the tree data structure;

comparing the most recently placed node associated with the starting logical address of the incoming write command to an in-numerical-order successor node in the tree data structure;

comparing the most recently placed node associated with the ending logical address of the incoming write command to an in-numerical-order successor node in the tree data structure;

removing the most recently placed node associated with the starting logical address of the incoming write command from the tree data structure if the in-numerical-order predecessor node of the node associated with the starting logical address of the incoming write command is a start node;

placing the incoming write command in the queue if the in-numerical-order predecessor node is an end node or a start/end node, the in-numerical-order successor node of the node associated with the starting logical address of the incoming write command is the node associated with the ending logical address of the incoming write command, and the in-numerical-order successor node of the node associated with the ending logical address is a start node or a start/end node;

executing write commands in the queue in an order in which the write commands were placed in the queue removing the executed commands from the queue; and

discontinuing use of the tree data structure and performing a linear comparison of the number of write commands in the queue in response to the number of write commands in the queue reaching a second threshold number.

6. The method of claim 5 , including aborting the incoming write command if the in-numerical-order predecessor node of the node associated with the starting logical address of the incoming write command is a start node, the in-numerical-order successor node of the node associated with the starting logical address of the incoming write command is not the node associated with the ending logical address of the incoming write command, and/or the in-numerical-order successor node of the node associated with the ending logical address of the incoming write command is an end node.

7. The method of claim 5 , including delaying processing of the incoming write command if the in-numerical-order predecessor node of the node associated with the starting logical address of the incoming write command is a start node, the in-numerical-order successor node of the node associated with the starting logical address of the incoming write command is not the node associated with the ending logical address of the incoming write command, and/or the in-numerical-order successor node of the node associated with the ending logical address of the incoming write command is an end node.

8. The method of claim 7 , including removing the node associated with the starting logical address of the incoming write command and the node associated with the ending logical address of the incoming write command from the tree data structure if processing of the incoming write command is delayed.

9. The method of claim 5 , wherein a number of the nodes associated with starting and/or ending logical addresses comprise a node that is associated with a logical address of a write command in the queue having a single logical address.

10. An apparatus, comprising:

an array of memory cells; and

a controller operably coupled to the array and configured to:

create a tree data structure comprising a first number of nodes associated with a starting logical address and/or an ending logical address of each write command in a queue of write commands, and a second number of nodes associated with a starting logical address and/or an ending logical address of an incoming write command, wherein the tree data structure is created only in response to a number of write commands in the queue reaching a first threshold number;

compare a node of the second number of nodes that is associated with a starting logical address of the incoming write command to an in-numerical-order predecessor node of the first number of nodes;

compare the node of the second number of nodes that is associated with a starting logical address of the incoming write command to an in-numerical-order successor node of the first number of nodes;

compare a node of the second number of nodes that is associated with an ending logical address of the incoming write command to an in-numerical-order successor node of the first number of nodes;

remove the second number of nodes from the tree data structure and delay processing of the incoming write command or abort the incoming write command if the logical address of the incoming write command overlaps with a logical address of a write command in the queue, and

place the incoming write command in the queue if the in-numerical-order predecessor node is an end node or a start/end node, the in-numerical-order successor node of the node associated with the starting logical address of the incoming write command is the node associated with the ending logical address of the incoming write command, and the in-numerical-order successor node of the node associated with the ending logical address is a start node or a start/end node, wherein the use of the tree data structure is discontinued and a linear comparison of the number of write commands in the queue is performed in response to the number of write commands in the queue reaching a second threshold number.

11. The apparatus of claim 10 , wherein the array of memory cells comprises a number of memory devices.

12. The apparatus of claim 10 , wherein the controller is configured to delay processing of the incoming write command if the logical address of the incoming write command overlaps with the logical address of the write command in the queue, and wherein the controller is configured to place the incoming write command in the queue responsive to executing a number of the write commands in the queue.

13. The apparatus of claim 12 , wherein the controller is configured to place the incoming write command in the queue if a logical address of the incoming write command no longer overlaps with a logical address of a write command in the queue.

14. An apparatus, comprising:

an array of memory cells; and

a controller operably coupled to the array and configured to:

create a tree data structure comprising a number of nodes in response to a number of write commands in a queue reaching a first threshold number;

place a node associated with a starting logical address of an incoming write command in the tree data structure;

compare the most recently placed node associated with a starting logical address of the incoming write command to an in-numerical-order predecessor node in the tree data structure;

compare the most recently placed node associated with the starting logical address of the incoming write command to an in-numerical-order successor node in the tree data structure; and

compare the most recently placed node associated with an ending logical address of the incoming write command to an in-numerical-order successor node in the tree data structure, wherein the predecessor and successor nodes are among the number of nodes associated with starting and/or ending logical addresses of the number of write commands in the queue and wherein the controller is configured to abort the incoming write command and remove the most recently placed node associated with the starting logical address of the incoming write command from the tree data structure if the in-numerical-order predecessor node is a start node; and place the incoming write command in the queue if the in-numerical-order predecessor node is an end node or a start/end node, the in-numerical-order successor node of the node associated with the starting logical address of the incoming write command is the node associated with the ending logical address of the incoming write command, and the in-numerical-order successor node of the node associated with the ending logical address is a start node or a start/end node;

execute a portion of the number of commands in the queue; and

discontinue use of the tree data structure and perform a linear comparison of the number of write commands in the queue in response to the number of write of commands in the queue reaching a second threshold number.

15. The apparatus of claim 14 , wherein the controller is configured to abort the incoming write command if the in-numerical-order predecessor node is a start node, the in-numerical-order successor node of the node associated with to the starting logical address of the incoming write command is not the node associated with to the ending logical address of the incoming write command, and/or the in-numerical-order successor node of the node associated with the ending logical address of the incoming write command is an end node.

16. The apparatus of claim 14 , wherein the controller is configured to delay processing of the incoming write command if the in-numerical-order predecessor of the node associated with the starting logical address of the incoming write command node is a start node, the in-numerical-order successor node of the node associated with the starting logical address of the incoming write command is not the node associated with the ending logical address of the incoming write command, and/or the in-numerical-order successor node of the node associated with the ending logical address of the incoming write command is an end node.

17. The apparatus of claim 16 , wherein the controller is configured to:

execute a number of the write commands in the queue in an order in which the write commands were placed in the queue; and

place the incoming write command in the queue responsive to executing the number of write commands.

18. The apparatus of claim 14 , wherein the apparatus is a computing system.

19. The apparatus of claim 14 , wherein the apparatus is a memory system.

Assignments (8)

Continuity (1)