Microsoft Technology Licensing, LLC

Robert I Davidson

Nathan P Myhrvold

Gideon Andreas Yuval

Keith R Vogel

Richard M Shupak

Norman Eugene Apperson

David Earl Heckerman

John S Breese

David O Hovel

Russell P Blake

Andrew C Craze

Paul W Davis

The present invention provides a method and system for determining an optimal placement order for basic blocks within a computer program to improve locality of reference and reduce the working set of the computer program. By reducing the working set, the computer program requires less memory than it normally would require to execute on a computer system. The optimal placement order for basic blocks within a computer program reflects the concurrency of usage for basic blocks during execution of the computer program. The method for determining an optimal placement order includes analyzing the computer program to identify all of the basic blocks, determining how many times each basic block is executed, assigning a placement order to each basic block depending upon how many times each basic block was executed, and reordering the basic blocks according to their assigned placement orders to produce an optimized computer program. The method used to identify all of the basic blocks includes disassembling known instruction addresses to identify the beginning and end of basic blocks and processing jump tables to identify more instruction addresses. Processing jump tables includes processing the first entry of every jump table before processing the second entry of any jump table. The present invention further optimizes a computer program by replacing rarely executed instructions with other instructions that require a smaller amount of storage space.

Method and system for improving the locality of memory references during execution of a computer program

A system and method for determining a workload placed on a target computer system during execution of a specified computer program. The system receives a set of performance measurements representing the performance of the target computer system during execution of the specified computer program. The system then identifies a plurality of workloads and for each identified workload, uses a model of the target computer system to predict a set of performance measurements that would results when a computer program that places the identified workload on the target computer system is executed. The system selects the identified workload whose set of predicted performance measurements most closely matches the received set of performance measurements as the determined workload that was place on the target computer system during execution of the specified computer program. The system uses the selected workload to predict the performance of the specified computer program on the target computer system with various different configurations. The system also determines the resource that is a bottleneck for each of the different configurations.

Automatic bottleneck detection by means of workload reconstruction from

A method and system for swapping blocks of data between a main memory area and a secondary storage area of a computer system that uses absolute addresses as its native addressing format. A series of linked information structures is maintained in the main memory area of the computer system. Each information structure allocates storage for a near return address pointer, a previous information structure pointer, a reference number and an offset. A first and second data block are swapped into the main memory area of the computer system. When the first data block transfers control to the second data block, a memory location indicating an absolute address for this point of transfer is stored in an information structure associated with the first data block. Prior to swapping the first data block out of the main memory area, the absolute address is resolved into a reference number and an offset. This resolved address is then stored in an information structure associated with the first data block. When the first data block is swapped back into the main memory area, the resolved address is restored into a new absolute address which directs processing control to a proper return point in the first data block.

Apparatus and method for swapping blocks of memory between a main memory

Method and system for improving the locality of memory references during

A method and system for generating and auditing a signature for executable modules are provided. A signature is a means that uniquely identifies an authorized copy of the executable module. The signature of each authorized copy is encoded within the order of instructions of the executable module. Each executable module is made up of multiple blocks of instructions. To place a signature within the executable module, a group of blocks having a flow of execution is selected from the executable module. The group of blocks is then reordered to form a signature for the executable module. To ensure that the reordered group of blocks has the same flow of execution, the blocks within the reordered group of blocks are modified to maintain the flow of execution. The reordered group of modified blocks replaces the unmodified group of blocks within the authorized copy of the executable module. The modified copy of the executable module executes in a manner that is functionally equivalent to the unmodified executable module. However, the reordered blocks provide a signature that is unique to each authorized copy. By inspecting the order of the group of blocks in a copy of the executable module, the signature can be determined, and thus it can be determined from which authorized copy the executable module derives.

Method and system for generating and auditing a signature for a computer

Growing community of inventors

Bellevue, WA, United States of America

Robert I Davidson