Prefetch system applicable to complex memory access schemes

A computer processor comprising:

• a central processing unit, said central processing unit executing load instructions for loading of data from an external memory device;
• interface means for coupling said central processing unit with the external memory device;
• a cache memory coupled with said interface and said central processing unit, said cache memory having an access time which is less than an access time for the external memory device;
• recurrence recognition means for monitoring said load instructions and calculating linear and indirect memory strides based upon consecutive executions of said load instructions from said central processing unit, said recurrence recognition means producing an enable signal indicating one of a linear and indirect armed state upon recognition of one of a respectively recurring linear and indirect load operand address memory traversal pattern, wherein said linear armed state is entered in response to at least two consecutive equal linear strides in load operand addresses, and said linear stride is .alpha.i.sub.k =Ai.sub.k -Ai.sub.k-1, where a current load operand address is Ai.sub.k, a last prior load operand address is Ai.sub.k-1, and said indirect armed state is entered in response to at least two consecutive equal indirect strides, and the indirect stride is .beta.i.sub.k =Ai.sub.k -mem(Ai.sub.k-1), where mem(Ai.sub.k-1) are the contents of the memory location addressed by Ai.sub.k-1 ;
• and
• prefetch address generation means for speculatively calculating prefetch addresses for said load instructions based upon one of said linear and indirect strides by using the linear address stride to calculate linear prefetch addresses according to Ai.sub.k+1 =Ai.sub.k +.alpha.i.sub.k, where a next prefetch address is Ai.sub.k+1, and by using the indirect address stride to calculate indirect prefetch addresses according to Ai.sub.k+1 =mem(Ai.sub.k)+.beta.i.sub.k.