Intel Corporation

Jinquan Dai

Long Li

Bo Huang

Xiaofeng Guo

Cotton Seed

Luddy Harrison

Zhiyuan Lv

Xiaodan Jiang

Jiangang Zhuang

Li Long

An embodiment of the present invention is a technique to hide latency in program traces. Blocks of instructions between start and end of a critical section are associated with color information. The blocks correspond to a program trace and containing a wait instruction. The wait instruction is sunk down the blocks globally to the end of the critical section using the color information and a dependence constraint on the wait instruction.

Latency hiding of traces using block coloring

Critical sections in a programming code may be ordered based at least in part on code motions. A flow graph of the code including the critical section may be generated. Two initiative motions may be performed based on the flow graph to identify possible positions of critical codes in the flow graph. Dependence relationship of critical sections may be determined based on the positions of critical sections. Using the dependence relationship information, the order of critical sections may be determined. The determined order of critical sections may be further used by a compiler to perform optimizations for the code.

Critical section ordering for multiple trace applications

A computer implemented method for scheduling multithreaded programming instructions based on the dependency graph wherein the dependency graph organizes the programming instruction logically based on blocks, nodes, and super blocks and wherein the programming instructions could be executed outside of a critical section may be executed outside of the critical section by inserting dependency relationship in the dependency graph.

Scheduling multithreaded programming instructions based on dependency graph

A method of compiling code that includes partitioning instructions in the code among a plurality of processors based on memory access latency associated with the instructions is disclosed. According to one aspect of the invention, partitioning instructions includes partitioning memory access dependence chains. Other embodiments are described and claimed.

Method and apparatus for partitioning programs to balance memory latency

A method of compiling code includes ordering instructions that protect and release critical sections in the code to improve parallel execution of the code according to an intrinsic order of the critical sections. According to one embodiment, the intrinsic order of the critical sections in the code is determined from data dependence and control dependence of instructions in the critical sections, and additional dependencies are generated to enforce the intrinsic order of the critical sections. Other embodiments are described and claimed.

Method and apparatus for ordering code based on critical sections

In some embodiments, a method and apparatus for automatically parallelizing a sequential network application through pipeline transformation are described. In one embodiment, the method includes the configuration of a network processor into a D-stage processor pipeline. Once configured, a sequential network application program is transformed into D-pipeline stages. Once transformed, the D-pipeline stages are executed in parallel within the D-stage processor pipeline. In one embodiment, transformation of a sequential application program is performed by modeling the sequential network program as a flow network model and selecting from the flow network model into a plurality of preliminary pipeline stages. Other embodiments are described and claimed.

Apparatus and method for automatically parallelizing network applications through pipelining transformation

Critical sections used for multiple threads in a parallel program to access shared resource may be selected to merge with each other to reduce the number of signals/tokens used to create critical sections. Critical section merge may be based on a summarized dependence graph which is obtained from an instruction level dependence graph constructed based on a result of critical section minimization.

Method and apparatus for merging critical sections

Instructions that have no dependence constraint between them and other instructions in a loop of a critical section may be moved out of the critical section so that the size of the critical section may be reduced. A flow graph of a program including the critical section may be generated, which includes loops. The flow graph may be transformed based on which any unnecessary instructions in loops may be moved out of the critical section. Subsequently, the original flow graph of the critical section may be recovered from the transformed flow graph.

Code optimization based on loop structures

In one embodiment, the present invention includes a method for partitioning a program segment into at least a first stage and a second stage, determining a live set of variables and control flow information alive at a boundary between the first and second stages, and controlling the first stage to transmit a trace-specific portion of the live set for a first trace to the second stage via a communication channel. In such manner, reduced transmission of data between the stages is effected. Other embodiments are described and claimed.

Transmitting trace-specific information in a transformed application

Various embodiments that may be used in performing speculative code motion for memory latency hiding are disclosed. One embodiment comprises extracting an asynchronous signal from a memory access instruction in a program to represent a latency of the memory access instruction, and generating a wait instruction to wait the asynchronous signal.

Speculative code motion for memory latency hiding

A method is presented including assigning a first register class to at least one symbolic register in at least one instruction, determining and assigning a second register class to the at least one register, reducing register class fixups and renaming the at least one symbolic register. Also presented is a system including a processor having at least one register and a compiler executing in the processor that inputs a source program having many operation blocks. The compiler assigns a first register class in at least one instruction to at least one symbolic register, determines and assigns a second register class to the at least one symbolic register, reduces register class fixups, and renames the at least one symbolic register.

Method and system for assigning register class through efficient dataflow analysis

A processing device includes an optimizer to migrate objects from an external memory of a network processing to local memory device to registers connected to a processor. The optimizer further aligns and eliminates redundant unitialization code of the objects.

Optimizing memory accesses for network applications using indexed register files

Automatic software controlled caching generations in network applications are described herein. In one embodiment, a candidate representing a plurality of instructions of a plurality of threads that perform one or more external memory accesses is identified, where the external memory accesses have a substantially identical base address. One or more directives and/or instructions are inserted into an instruction stream corresponding to the identified candidate to maintain contents of at least one of a content addressable memory (CAM) and local memory (LM) of a processor, and to modify at least one of the external memory access to access at least one of the CAM and LM of the processor without having to perform the respective external memory access. Other methods and apparatuses are also described.

Automatic caching generation in network applications

A program may be partitioned into at least two stages, where at least one of the stages comprises more than one parallel thread. Data required by each of the stages, which data is defined in a previous stage may be identified. Transmission of the required data between consecutive stages may then be provided for.

Growing community of inventors

Shanghai, China

Jinquan Dai