Prefetch list management in a computer system
View Patent ↗Method and apparatus for tracking a prefetch list of a list prefetcher associated with a computer program in the event the list prefetcher cannot track the computer program. During a first execution of a computer program, the computer program outputs checkpoint indications. Also during the first execution of the computer program, a list prefetcher builds a prefetch list for subsequent executions of the computer program. As the computer program executes for the first time, the list prefetcher associates each checkpoint indication with a location in the building prefetch list. Upon subsequent executions of the computer program, if the list prefetcher cannot track the prefetch list to the computer program, the list prefetcher waits until the computer program outputs the next checkpoint indication. The list prefetcher is then able to jump to the location of the prefetch list associated with the checkpoint indication.
1. A method comprising:
performing a first execution of a computer program, wherein the computer program outputs checkpoint indications, wherein each checkpoint indication corresponds to a different execution point of the computer program;
generating a prefetch list, wherein each item in the prefetch list corresponds to a cache miss during the first execution of the computer program, and, upon output of a checkpoint indication by the computer program, creating an association between a location in the prefetch list and the output checkpoint indication;
upon a subsequent execution of the computer program:
loading a first portion of the prefetch list into a cache; and
upon determining that the prefetch list is not tracking the subsequent execution of the computer program:
receiving a checkpoint indication from the computer program;
tracking a location in the prefetch list associated with the received checkpoint indication; and
loading into the cache a second portion of the prefetch list that includes the tracked location.
2. The method of claim 1 , wherein the location in the prefetch list associated with the output checkpoint indication is a location in the prefetch list immediately following a location in the prefetch list corresponding to the last cache miss prior to the output of the checkpoint indication by the computer program.
3. The method of claim 1 , wherein each output checkpoint indication comprises an ordering indication, wherein the location in the prefetch list comprises a memory address of a portion of the prefetch list, and wherein creating the association between the location in the prefetch list and the output checkpoint indication comprises storing the memory address of the portion of the prefetch list in a position in a tracking array corresponding to the ordering indication.
4. The method of claim 1 , wherein each output checkpoint indication comprises a pointer to a memory location, wherein the location in the prefetch list comprises a memory address of a portion of the prefetch list, and wherein creating the association between the location in the prefetch list and the output checkpoint indication comprises storing the memory address of the portion of the prefetch list into the memory location associated with the pointer.
5. The method of claim 1 , wherein each checkpoint association comprises a memory address request by the computer program that will generate a cache miss such that the requested memory address is added to the prefetch list being generated, and wherein creating the association between the location in the prefetch list and the output checkpoint indication comprises writing to the requested memory address the location of the cache miss in the prefetch list generated by the memory request.
6. The method of claim 5 , further comprising:
upon the subsequent execution of the computer program and upon determining that the prefetch list is not tracking the subsequent execution of the computer program:
receiving the memory address request by the computer program; and
tracking to the location of the prefetch list stored in the requested memory address.