Reducing memory access latency in scatter/gather operations

An information processing system for executing a program with improved cache efficiency:

• a memory;
• and
• a processor communicatively coupled to the memory, the processor configured to perform a method comprising:
• receiving a program for processing a plurality of objects stored in one or more data structures;
• prior to and executing the program,
• partitioning the program comprising a plurality of operations into a first partition and at least a second partition, wherein the first partition is configured to comprise a first subset of operations from the plurality of operations having regular access patterns and further configured to comprise a first set of computations that utilize the regular access patterns, wherein the second partition is configured to comprise at least a second subset of operations from the plurality of operations initially having irregular access patterns prior to the partitioning that is subsequently regularized by configuring each of the irregular access patterns to access one of a set of limited regions of memory represented by a plurality of queues, and wherein the second partition is further configured to comprise a second set of computations that utilize the irregular access patterns and results from the first set computations of the first partition,
• reordering an original programmed execution sequence of operations from the first subset of operations independent of the second subset of operations,
• reordering an original programmed execution sequence of operations from the second subset of operations independent of the first subset of operations,
• transforming the program by adding code that configures the program to maintain a plurality of queues, where each queue in the plurality of queues is associated with a different cacheable region of a memory, wherein when the program is received the program is absent code configuring the program to maintain the plurality of queues when executed;
• and
• executing the program, wherein executing the program comprises
• performing a first set of one or more operations from the first subset operations on the plurality of objects stored in the one or more data structures, the first set of one or more operations having a regular memory access pattern,
• storing, after each operation of the first set of one or more operations from the first subset of operations has been performed, results of the operation in one of the plurality of queues,
• performing, for at least one queue in the plurality of queues, a second set of one or more operations of the second subset of operations, the second set of one or more operations utilizing results of the operations of the first set of one or more operations stored in the queue as input, where irregular access patterns of the second set of one or more operations are regularized by localizing memory locations accessed by the second set of one or more operations to the cacheable region of memory associated with the at least one queue, and
• storing results of each operation performed in the second set of one or more operations in memory.

A computer program product for executing a program with improved cache efficiency, the computer program product comprising a storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method, the method comprising:

• receiving a program for processing a plurality of objects stored in one or more data structures;
• prior to executing the program,
• partitioning the program comprising a plurality of operations into a first partition and at least a second partition, wherein the first partition is configured to comprise a first subset-of operations from the plurality of operations having regular access patterns and further configured to comprise a first set of computations that utilize the regular access patterns, wherein the second partition is configured to comprise at least a second subset of operations from the plurality of operations initially having irregular access patterns prior to the partitioning that are subsequently regularized by configuring each of the irregular access patterns to access one of a set of limited regions of memory represented by a plurality of queues, and wherein the second partition is further configured to comprise a second set of computations that utilize the irregular access patterns and results from the first set of computations of the first partition,
• reordering an original programmed execution sequence of operations from the first subset of operations independent of the second subset of operations,
• reordering an original programmed execution sequence of operations from the second subset of operations independent of the first subset of operations,
• transforming the program by adding code that configures the program to maintain a plurality of queues, where each queue in the plurality of queues is associated with a different cacheable region of a memory, wherein when the program is received the program is absent code configuring the program to maintain the plurality of queues when executed;
• and
• executing the program, wherein executing the program comprises
• performing a first set of one or more operations from the first subset of operations on the plurality of objects stored in the one or more data structures, the first set of one or more operations having a regular memory access pattern,
• storing, after each operation of the first set of one or more operations from the first subset of operations has been performed, results of the operation in one of the plurality of queues,
• performing for at least one queue in the plurality of queues, a second set of one or more operations of the second subset of operations, the second set of one or more operations utilizing results of the operations of the first set of one or more operations stored in the queue as input, where irregular access patterns of the second set of one or more operations are regularized by localizing memory locations accessed by the second set of one or more operations to the cacheable region of memory associated with the at least one queue, and
• storing results of each operation performed in the second set of one or more operations in memory.