International Business Machines Corporation

Barbara Bluestein Simons

Vivek Sarkar

Kalyan Muthukumar

Hovey Ramond Strong, Jr

Shankar Ramaswamy

Joseph Y Halpern

Dz Ching Ju

Mauricio J Serrano

Code restructuring or reordering based on profiling information and memory hierarchy is provided by constructing a Program Execution Graph (PEG) corresponding to a level of the memory hierarchy, partitioning this PEG to reduce estimated memory overhead costs below an upper bound, and constructing a PEG for a next level of the memory hierarchy from the partitioned PEG. The PEG is constructed from control flow and frequency information from a profile of the program to be restructured. The PEG is a weighted undirected graph comprising nodes representing basic blocks and edges representing transfer of control between pairs of basic blocks. The weight of a node is the size of the basic block it represents and the weight of an edge is the frequency of transition between the pair of basic blocs it connects.

Method of, system for, and computer program product for providing efficient utilization of memory hierarchy through code restructuring

An optimizing, compiler that performs retargetable object code generation for a specific processor by matching tree patterns in directed acyclic graphs derived from the source code.

Retargeting optimized code by matching tree patterns in directed acyclic graphs

Code restructuring or reordering based on profiling information and memory hierarchy is provided by constructing a Program Execution Graph (PEG) corresponding to a level of the memory hierarchy, partitioning this PEG to reduce estimated memory overhead costs below an upper bound, and constructing a PEG for a next level of the memory hierarchy from the partitioned PEG. The PEG is constructed from control flow and frequency information from a profile of the program to be restructured. The PEG is a weighted undirected graph comprising nodes representing basic blocks and edges representing transfer of control between pairs of basic blocks. The weight of a node is the size of the basic block it represents and the weight of an edge is the frequency of transition between the pair of basic blocks it connects. The nodes of the PEG are partitioned or clustered into clusters such that the sum of the weights of the nodes in any cluster is no greater than an upper bound. A next PEG is then constructed from the clusters of the partitioned PEG such that a node in the next PEG corresponds to a cluster in the partitioned PEG, and such that there is an edge between two nodes in the next PEG if there is an edge between the clusters represented by the two nodes. Weights are assigned to the nodes and edges of the next PEG to produce a PEG, and then the PEG partitioning, basic block reordering, and PEG construction steps may be repeated for each level of the memory hierarchy. After the clustering is completed, the basic blocks are reordered in memory by grouping all of the nodes of a cluster in an adjacent order beginning at a boundary for all the levels of the memory hierarchy. Because clusters must not cross boundaries of memory hierarchies, NOPs are added to fill out the portion of a memory hierarchy level that is not filled by the clusters.

Improved scheduling of instructions within a loop for execution by a computer system having hardware lookahead is provided. A dependence graph is constructed which contains all the nodes of a dependence graph corresponding to the loop, but which only contains loop-independent dependence edges. A start node simulating a previous iteration of the loop may be added to the dependence graph, and an end node simulating a next iteration of the loop may also added to the dependence graph. A loop-independent edge between a source node and the start node is added to the dependence graph, and a loop-independent edge between a sink node and the end node is added to the dependence graph. Loop-carried edges which satisfy a computed lower bound on the time required for a single loop iteration are eliminated from a dependence graph, and loop-carried edges which do not satisfy the computed lower bound are replaced by a pair of loop-independent edges. Instructions may be scheduled for execution based on the dependence graph.

System, method, and program product for loop instruction scheduling

Instructions are scheduled for execution by a processor having a lookahead buffer by identifying an idle slot in a first instruction schedule of a first basic block of instructions, and by rescheduling the idle slot later in the first instruction schedule. The idle slot is rescheduled by determining if the first basic block of instructions may be rescheduled into a second instruction schedule in which the identified idle slot is scheduled later than in the first instruction schedule. The first basic block of instructions is rescheduled by determining a completion deadline of the first instruction schedule, decreasing the completion deadline, and determining the second instruction schedule based on the decreased completion deadline. Deadlines are determined by computing a rank of each node of a DAG corresponding to the first basic block of instructions; constructing an ordered list of the DAG nodes in nondecreasing rank order; and applying a greedy scheduling heuristic to the ordered list. An instruction in a second subsequent basic block of instructions may be rescheduled to execute in the rescheduled idle slot. This process may be repeated for each idle slot.

System, method, and program product for instruction scheduling in the

A method for synchronizing clocks in a distributed computing system in the presence of faults. The condition to be renewed guarantees that all clocks of correct processors never deviate by more than some maximum amount. This condition is achieved by periodically resynchronizing the clocks so that the correct clocks do not deviate by more than some minimum deviation. In the process of resynchronization, a correct clock is never adjusted by more than a maximum amount during a period and it is never set back. The method requires ascertaining whether a valid time value message has been received within a specified period. A message is valid if it was received within an interval predetermined as a function of the number of signatures from other processors appending the message. If the valid message has not been received within the current period, then the local processor originates and broadcasts to all processors exactly one time value message and appends thereto its unforgeable signature. On the other hand if a valid message has been received, then the local processor appends its unforgeable signature to the message and passes exactly the one message on by broadcasting to all processors. As part of the protocol involving broadcasting of a message, each processor resets the time for expected resynchronization and updates its local clock.

Decentralized synchronization of clocks

A method for synchronizing clocks in a distributed computing system in the presence of faults. The condition to be renewed guarantees that all clocks of correct processors never deviate by more than some maximum amount. This condition is achieved by periodically resynchronizing the clocks so that the correct clocks do not deviate by more than some minimum deviation. In the process of resynchronization, a correct clock is never adjusted by more than a maximum amount during a period and it is never set back. The method requires that there is a previously agreed upon ordered list of all participants. At a specified time in the period, the first processor on the list attempts to synchronize all to its clock. The result of this is either a synchronization of all correct processors and their clocks to be within the desired tolerance or an agreement among all other correct processors that the first node on the list has failed. If the first fails, then the second tries and so on. Assuming at most f faulty components then one of the first f+1 attempts must succeed.

Growing community of inventors

Palo Alto, CA, United States of America

Barbara Bluestein Simons