Microsoft Technology Licensing, LLC

Erik S Ruf

Ray Bittner

Brian Kevin Guenter

Todd B Knoblock

A system may include a Graphics Processing Unit (GPU) and a Field Programmable Gate Array (FPGA). The system may further include a bus interface that is external to the FPGA, and that is configured to transfer data directly between the GPU and the FPGA without storing the data in a memory of a central processing unit (CPU) as an intermediary operation.

Direct communication between GPU and FPGA components

A framework is set forth herein that uses a composition mechanism to produce function data that describes a kernel. The composition mechanism may then send the function data to an execution mechanism. The execution mechanism uses the function data to dynamically execute pre-compiled code modules, which are identified by the function data. According to another aspect, the framework provides different mechanisms for implementing the kernel, depending on the native capabilities of the execution mechanism.

Implementing functional kernels using compiled code modules

A schedule can be generated for physically transposing an array such that when the array is transferred from a first memory type to a second memory type, the number of block transfers performed is minimized. The array can be rearranged to ensure that most or all data elements in any block read into internal memory are used before that block's internal storage is reused. The algorithm can compute an offline schedule and then execute that schedule. The method can assemble the schedule during one or more passes with an algorithm. Scheduling passes can apply a permutation to a representation of the array's structure and then tile the representation to ensure efficient use of internal memory. Tiling may alter the permutation, so the algorithm can be reinvoked and run on the tiled representation. The algorithm can be run on successively retiled representations until no additional tiling is required. Optimizations for schedule generation and/or execution include: simplification of the data structure representing the array; alteration of the order in which tiles are accessed; inversion of permutations; processing non-canonical input; and the production of stream output. The method can also be modified for specialized architectures, including: block I/O architecture; fully associative caches; set-associative caches; and multi-level memory hierarchies.

Memory efficient array transposition via multi pass tiling

Indirect method invocation of methods that only return constant values is optimized using fetching operations and return constant tables. Such method calls can be optimized if all possible method calls via the call site instruction return a constant value and have no side effects. Each constant return value is loaded from a return constant table, and method invocation is eliminated. If all possible target methods in a program result in a constant return value and have no side effects, an associated virtual function dispatch table (vtable) may be used as the return constant table. Furthermore, control operation optimization may be applied to identify type constraints, based on one or more possible type-dependent constant return values from an indirect method invocation. An optimizer identifies and maps between a restricted set of values and an associated restricted set of types on which execution code may operate relative to a given control operation. The type constraints are used to optimize the associated execution code by filtering propagation of runtime type approximations for optimization.

Constant return optimization transforming indirect calls to data fetches

Synchronization optimization for statically compiled Java programs is performed in three phases: Thread closure analysis, Alias analysis, and Specialization and transformation. Thread closure analysis bounds the number of thread instances constructed at each thread allocation site, and determines the set of methods potentially executed by each thread instance. Alias analysis generates equivalence class representation based alias signatures for each method. These signatures describe the aliasing and synchronization behavior of each method. The specialization and transformation phase traverses a call graph in a top-down manner starting from the program entry point, and creates specialized copies of methods when they can be individually optimized. A synchronization operation is removed from the code whenever it can be proven that all objects reaching the operation at runtime can be synchronized by at most one thread instance.

Equivalence class based synchronization optimization

Type partitioned dataflow analyses perform a dataflow analysis of a program by partitioning the dataflow analysis into phases using types to help reduce costs attendant to the dataflow analysis of the entire program. Each phase models only a subset of the relevant program quantities and may be analyzed separately. Type partitioned dataflow analyses extend quantity-based partitioning to non-separable dataflow analyses by determining analysis-time dependencies connoting potential run-time interactions between relevant program quantities and scheduling the dataflow analysis of each program quantity after the dataflow analysis of all other program quantities upon which it depends. Because each phase may be analyzed separately, type partitioned dataflow analyses may enable the use of suitable efficient dataflow techniques, such as suitable sparse representation methods for example, that otherwise could not have been used for an entire non-separable program and may also enable the performance of dataflow analyses in parallel for more than one separate phase of such a non-separable program.

Type partitioned dataflow analyses

A computer-implemented shading system includes a geometric renderer which renders a computer generated image to produce geometric image information for an object in a scene, and a user interface which permits a user to selectively vary a designated parameter(s) to affect how that object is shaded. The system also includes a specialized shader to shade the object in the scene according to the designated parameter(s) and other shading parameters. The specialized shader is created from the user's original shader. The specialized shader has a cache loader which contains all of the terms of the user's original shader, plus load operations to load values from computations that do not depend from the designated parameter(s). The specialized shader also has a cache reader which contains a reduced set of terms from the original shader that depend on the designated parameter(s), plus read operations to read the values of the non-variant terms from the cache. When the user designates a parameter(s), the cache loader is executed once to compute the values that will not change when the user varies the designated parameter(s). The cache reader is then executed each time the user alters the value of the designated parameter(s). In this manner, only the computations that are dependent on the designated parameter(s) are recomputed for each alteration, thereby streamlining operation of the entire shading process.

Growing community of inventors

Kirkland, WA, United States of America

Erik S Ruf