Computer system implementing a multi-threaded stride prediction read ahead algorithm

A computer system comprising:

• a microprocessor;
• a memory coupled to the microprocessor, the memory including program instructions executable to implement the method of:
• storing a first run value indicative of a first sequential run size of a first plurality of read requests;
• storing a first skip value indicative of an extent of a non-sequential skip associated with a subsequent read request;
• determining whether a second run value indicative of a second sequential run size of a second plurality of read requests equals the first run value;
• determining whether a second skip value indicative of an extent of another nonsequential skip associated with an additional read request equals the first skip value;
• and
• performing a stride based prefetch operation in response to determining that the second run value equals the first run value and that the second skin value equals the first skip value;
• wherein the stride based prefetch operation further includes scheduling a prefetch of one or more blocks of data having a sequential run that is equal to the first and second run values, followed by a skip corresponding to the first skip value to additional blocks.

A memory medium comprising program instructions executable to implement the method of:

• storing a first run value indicative of a first sequential run size of a first plurality of read requests;
• storing a first skip value indicative of an extent of a non-sequential skip associated with a subsequent read request;
• determining whether a second run value indicative of a second sequential run size of a second plurality of read requests equals the first run value;
• determining whether a second skip value indicative of an extent of another non-sequential skip associated with an additional read request equals the first skip value;
• and
• performing a stride based prefetch operation in response to determining that the second run value equals the first run value and that the second skip value equals the first skip value;
• wherein the stride based prefetch operation includes scheduling a prefetch of one or more blocks of data having a sequential run that is equal to the first and second run values, followed by a skip corresponding to the first skip value to additional blocks.

A computer system comprising:

• a memory;
• and
• a read ahead engine coupled to the memory, wherein the read ahead engine is configured to store a first run value indicative of a first sequential run size of a first plurality of read requests, store a first skip value indicative of an extent of a non-sequential skip associated with a subsequent read request, determine whether a second run value indicative of a second sequential run size of a second plurality of read requests equals the first run value, determine whether a second skip value indicative of an extent of another non-sequential skip associated with an additional read request equals the first skip value, and perform a stride based prefetch operation in response to determining that the second run value equals the first run value and that the second skip value equals the first skip value;
• wherein the stride based prefetch operation includes scheduling a prefetch of one or more blocks of data having a sequential run that is equal to the first and second run values followed by a skip corresponding to the first skip value to additional blocks.

A method comprising:

• receiving a first plurality of sequential read requests;
• storing a first sequential run value indicative of a length of the first plurality of sequential read requests;
• receiving a first non-sequential read request;
• storing a first skip value indicative of a difference between a location of the first nonsequential read request and a location that is sequential to the first plurality of sequential read requests;
• receiving a second plurality of sequential read requests;
• storing a second sequential run value indicative of a length of the second plurality of sequential read requests;
• receiving a second non-sequential read request;
• storing a second skip value indicative of a difference between a location of the second non-sequential read request and a location that is sequential to the second plurality of sequential read requests;
• detecting that a stride pattern exists in response to comparing the first sequential run value with the second sequential run value and comparing the first skip value with the second skip value;
• and
• prefetching one or more blocks of data according to the stride pattern after determining that the stride pattern exists.

A computer system comprising:

• a microprocessor;
• and
• a memory coupled to the microprocessor, the memory including program instructions executable to implement the method of:
• receiving a first plurality of sequential read requests;
• storing a first sequential run value indicative of a length of the first plurality of sequential read requests;
• receiving a first non-sequential read request;
• storing a first skip value indicative of a difference between a location of the first non-sequential read request and a location that is sequential to the first plurality of sequential read requests;
• receiving a second plurality of sequential read requests;
• storing a second sequential run value indicative of a length of the second plurality of sequential read requests;
• receiving a second non-sequential read request;
• storing a second skip value indicative of a difference between a location of the second non-sequential read request and a location that is sequential to the second plurality of sequential read requests;
• detecting that a stride pattern exists in response to comparing the first sequential run value with the second sequential run value and comparing the first skip value with the second skip value;
• and
• prefetching one or more blocks of data according to the stride pattern after determining that the stride pattern exists.

A system comprising:

• means for storing a first run value indicative of a first sequential run size of a first plurality of read requests;
• means for storing a first skip value indicative of an extent of a non-sequential skip associated with a subsequent read request;
• means for determining whether a second run value indicative of a second sequential run size of a second plurality of read requests equals the first run value;
• means for determining whether a second skip value indicative of an extent of another non-sequential skip associated with an additional read request equals the first skip value;
• and
• means for performing a stride based prefetch operation in response to determining that the second run value equals the first run value and that the second skin value equals the first skip value;
• wherein the stride based prefetch operation includes scheduling a prefetch of one or more blocks of data having a sequential run that is equal to the first and second run values, followed by a skip corresponding to the first skip value to additional blocks.