Method and apparatus for merging critical sections

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.

RELATED APPLICATION

This application is related to commonly assigned U.S. application Ser. No. 10/582,204, filed by Xiaofeng Guo, Jinquan Dai, and Long Li with an effective filing date of Jan. 26, 2006 and entitled “Scheduling Multithreaded Programming Instructions Based on Dependency Graph,” and is related to commonly assigned U.S. application Ser. No. 10/582,427, filed by Xiaofeng Guo, Jinquan Dai, Long Li, and Zhiyuan Lv with an effective filing date of Nov. 17, 2005 and entitled “Latency Hiding of Traces Using Block Coloring,” and is related to commonly assigned U.S. application Ser. No. 11/662,217, filed by Xiaofeng Guo, Jinquan Dai, and Long Li with an effective filing date of Dec. 24, 2005 (the PCT application designating the U.S. was filed on this date) and entitled “Automatic Critical Section Ordering for Parallel Program.”

BACKGROUND

This disclosure relates generally to compiling technologies in a computing system, and more specifically but not exclusively, to method and apparatus for merging critical sections when compiling a computer program.

Multithreading and multiprocessing are common programming techniques often used to maximize the efficiency of computer programs by providing a tool to permit concurrency or multitasking. Threads are ways for a computer program to be divided into multiple and distinct sequences of programming instructions where each sequence is treated as a single task and to be processed simultaneously. An application that may use the multithreaded programming technique is a packet-switched network application that processes network packets in a high speed packet-switched system concurrently.

To maintain and organize the different packets, a new thread may be created for each incoming packet. In a single processor environment, the processor may divide its time between different threads. In a multiprocessor environment, different threads may be processed on different processors. For example, the Intel® IXA™ network processors (IXPs) have multiple microengines (MEs) processing network packets in parallel where each ME supports multiple threads.

In such a parallel programming paradigm, accesses to shared resources, including shared memory, global variables, shared pipes, and so on, are typically be protected by critical sections to ensure mutual exclusiveness and synchronizations between threads. Normally, critical sections are created by using a signal mechanism in a multiprocessor system. A signal may be used to permit the entering or to indicate the exiting of a critical section. For instance, in an Intel® IXP™, packets are distributed to a chain of threads in order (i.e., an earlier thread in the chain processes an earlier packet). Each thread waits for a signal from the previous thread before entering the critical section. After the signal is received, the thread executes the critical section code exclusively. Once this thread is done, it sends the signal to the next thread after leaving the critical section.

Due to hardware cost, the number of signals is limited by the scale of processing element. For example, each thread only has 16 signals in Intel® IXP™ MEs. Excessive use of critical sections may adversely impact the performance of a program. Therefore, it is desirable to efficiently use critical sections.

DETAILED DESCRIPTION

According to embodiments of the subject matter disclosed in this application, critical sections used for multiple threads in a program to access shared resource may be minimized. A trace-based instruction level dependence graph may be constructed based on the result of the critical section minimization. The dependence graph so constructed may be summarized. Additionally, critical sections in the program may be selected to merge with each other based on the summarized dependence graph to reduce the number of signals/tokens used to create critical sections. Furthermore, latency-sensitive optimizations may be applied to hide resource access latency.

Reference in the specification to “one embodiment” or “an embodiment” of the disclosed subject matter means that a particular feature, structure or characteristic described in connection with the embodiment is included in at least one embodiment of the disclosed subject matter. Thus, the appearances of the phrase “in one embodiment” appearing in various places throughout the specification are not necessarily all referring to the same embodiment.

FIG. 1is a block diagram of an exemplary computing system100in which an example embodiment of the present invention may be implemented. The computing system100includes a processor101that processes data and a memory113. The processor101may have multiple or many processing cores (for brevity of description, term “multiple cores” will be used hereinafter to include both multiple processing cores and many processing cores). The processor101may be a complex instruction set microprocessor, a reduced instruction set computing microprocessor, a very long instruction word computer microprocessor, a processor implementing a combination of instruction sets, or other processor device.FIG. 1shows the computing system100with a single processor. However, it is understood that the computing system100may operate with multiple processors. Additionally, each of the one or more processors may support one or more hardware threads. The processor101is coupled to a CPU (Central Processing Unit) bus110that transmits data signals between processor101and other components in the computing system100.

The memory113may be a dynamic random access memory (“DRAM”) device, a static random access memory (“SRAM”) device, read-only memory (“ROM”), a synchronous DRAM (“SDRAM”) device, a Double Data Rate (“DDR”) SDRAM device, and/or other memory device. The memory113may store instructions and code represented by data signals that may be executed by the processor101. According to an embodiment of the computing system100, a compiler may be stored in the memory113and implemented by the processor101in the computing system100. The compiler may construct an instruction-level dependence graph and summarize the dependence graph so constructed. According to an embodiment of the subject matter disclosed in this application, the summarized dependence graph may be used to merge critical sections to save signals needed for critical section creations and to reduce the number of overall instructions in an execution path of a program.

A cache102may reside inside processor101to store data stored in memory113. The cache102speeds access to memory by the processor101by taking advantage of its locality of access. In an alternative embodiment of the computing system100, the cache102may reside external to the processor101. In another embodiment, the cache102may include multiple levels, such as level 1 cache (L1 cache), level 2 cache (L2 cache), level 3 cache, and so on, with one or more levels (e.g., L1 cache) residing inside the processor101and others residing outside the processor101. A bridge memory controller111directs data signals between the processor101, the memory113, and other components in the computing system100and bridges the data signals between the CPU bus110, the memory113, and a first IO (Input/Output) bus120.

The first IO bus120may be a single bus or a combination of multiple buses. The first IO bus120provides communication links between components in the computer system100. A network controller121may be coupled to the first IO bus120. The network controller121may link the computing system100to a network of computers (not shown) and support communication among the computers. A display device controller122may be coupled to the first IO bus120. The display device controller122allows coupling of a display device (not shown) to the computing system100and acts as an interface between the display device and the computing system100.

A second IO bus130may be a single bus or a combination of multiple buses. The second IO bus130may provide communication links between components in the computing system100. A data storage device131is coupled to the second IO bus130. The data storage device131may be hard disk drive, a floppy disk drive, a compact disc (“CD”) ROM device, a flash memory device or other mass storage device. An input interface132may be coupled to the second IO bus130. The input interface132may be, for example, a keyboard and/or mouse controller to other input interface. The input interface132may be a dedicated device or can reside in another device such as a bus controller or other controller. The input interface132allows coupling of an input device to the computing system100and transmits data signals from an input device to the computing system100. An audio controller133may be coupled to the second IO bus130. The audio controller133operates to coordinate the recording and playing of sounds by a device such as an audio codec which is also coupled to the IO bus130. A bus bridge123couples the first IO bus120and the second IO bus130. The bus bridge123operates to buffer and bridge data signals between the first IO bus120and the second IO bus130.

When a program is executed in the computing system100, it may be executed in multiple threads. In one embodiment, all of the threads may be running on processor101. In another embodiment, threads may be distributed and run on multiple processor or processing cores. Threads communicate to other threads through shared resources such as global memory, registers, or signals. In many instances, the shared resource may only be accessed by one thread. Such an exclusive access of the shared resource by one thread at a time may be implemented by using a critical section. A conventional method to implement a critical section is to use a signal mechanism. A thread may enter a critical section after receiving a signal and exiting the critical section by notifying the next thread that it is done and by passing a signal to the next thread.

FIG. 2illustrates an example of signal-based critical sections. A thread202waits for a token or signal204from a previous thread201. After accessing its critical section, the thread202then passes a token or signal205to a thread203. Before the thread203receives the token or signal205, the thread202has exclusive access to a shared resource210.

Typically it takes time to access the shared resource. This time is referred to as resource access latency, which is measured between the instant when resource access (e.g., memory access) is initiated and the instant when the accessed data in the resource is effective. If resource access latency is included in a critical section, the processor or processing core executing the thread that has entered this critical section will be idle during this latency period. This results in inefficient use of computing power. One way to improve the efficiency of a computing system running multiple threads is to hide resource access latency or overlap resource access latency in one thread with resource access latency and/or other computations in other threads.

FIGS. 3A and 3Billustrate an example of moving instructions outside of a critical section to shorten the critical section according to an example embodiment of the present invention. In a token or signal based critical section described inFIG. 2, thread302may wait until thread301exits a critical section311before thread302may begin to execute its instructions in a critical section312. A shaded block350represents the instructions blocked by a wait instruction351. Since the wait instruction351already blocks all the subsequent instructions in350, the instructions in350may be moved outside of the critical section311and not affecting the sequence in which the instructions may be executed.

When the wait instruction351is moved outside of the critical section311, the critical section311may be shortened. As depicted inFIG. 3B, a critical section361is shorter than the critical section311depicted inFIG. 3A. As a result, thread371may release the critical section361to thread372sooner than thread301releases the critical section311to thread302. In this embodiment of the invention, the wait instruction351is moved to a location indicated by381and the instructions blocked by the wait instructions,350, are moved to a location indicated by380. When critical sections are shortened as much as they may be shortened, a multithreaded program may be executed efficiently.

When resource access latency and other unnecessary instructions are removed out of critical sections, it may become more effective to merge shortened critical sections to reduce the number of signals used by critical sections than merge un-shortened critical sections.

FIG. 4is a block diagram that illustrates a compiler400that may include a critical section merging apparatus, according to an example embodiment of the present invention. The compiler400may include a compiler manager410. The compiler manager410receives source code to compile. The compiler manager410interfaces with and transmits information between other components in the compiler400.

The compiler400may include a front end unit420. According to an embodiment of the compiler400, the front end unit420operates to parse source code and convert it to an abstract syntax tree. The compiler400may also include an intermediate language (“IL”) unit430. The IL unit430transforms the abstract syntax tree into a common intermediate form such as an intermediate representation. It should be appreciated that the IL unit430may transform the abstract syntax tree into one or more common intermediate forms.

The complier may include an optimizer unit440. The optimizer unit440may utilize one or more optimization procedures to optimize the intermediate representation of the code. According to an embodiment of the compiler440, the optimizer unit440may perform peephole, local, loop, global, interprocedural and/or other optimizations. According to an embodiment of the compiler440, the optimizer unit440includes a critical section merging apparatus441. The critical section merging apparatus441may minimize critical sections and construct a trace-based instruction level dependence graph based on the result of the critical section minimization. Additionally, the critical section merging apparatus441may summarize the dependence graph so constructed. Moreover, the critical section merging apparatus441may merge critical sections based on the summarized dependence graph. Moreover, the critical section merging apparatus441may apply latency-sensitive optimizations to hide resource access latency.

The compiler400may include a register allocator unit450. The register allocator unit450identifies data in the intermediate representation that may be stored in registers in the processor rather than in memory. Additionally, the compiler400may include a code generator460. The code generator460converts the intermediate representation into machine or assembly code.

FIG. 5is a block diagram of an exemplary critical section merging apparatus500according to an example embodiment of the present invention. The critical section merging apparatus500may be used to implement the critical section merging apparatus441shown inFIG. 4. The critical section merging apparatus500includes a critical section merging manager510. The critical section merging manager510interfaces with and transmits information between other components in the critical section merging apparatus500.

The critical section merging apparatus500may include a minimization unit520. The minimization unit520may perform critical section minimization. The minimization unit520may employ any method or a combination of a variety of methods to minimize each critical section by identifying a portion of instructions that could be executed outside of the critical section and by removing such a portion of instructions out of the critical section. The commonly assigned U.S. patent application Ser. No. 10/582,204 entitled “Scheduling Multithreaded Programming Instructions Based on Dependency Graph,” filed by Xiaofeng Guo, Jinquan Dai, and Long Li with an effective filing date of Jan. 26, 2006, and the commonly assigned U.S. patent application Ser. No. 10/582,427 entitled “Latency Hiding of Traces Using Block Coloring,” filed by Xiaofeng Guo, Jinquan Dai, Long Li, and Zhiyuan Lv with an effective filing date of Nov. 17, 2005 describe some methods for shortening critical sections and thus minimizing the length of critical sections. These two U.S. patent applications are incorporated by reference herein.

As mentioned above, using multi-threading technology is one approach to shorten critical sections. It is estimated that if all memory accesses latency can be hided and the computations out of critical section can be used on hiding the memory accesses latency by using a multi-threading technology in a single processor, the execution speed of the program may be sped up by:

Speed⁢-⁢up⁢⁢1=Cc+∑i=1Cm⁢⁢LiCc+Cm,(1)
where Ccdenotes cycles for computation; Cmdenotes times of memory accesses; and Lidenotes the ithmemory access latency. When multiple processors or processing cores are used for the multiple threads, the execution speed of the program may be sped up by:

Speed⁢-⁢up⁢⁢2=Cc+∑i=1Cm⁢⁢LiCcs,(2)
where Ccsdenotes computations in the largest critical section. It may be noted from Equation (2) that the critical section size acts as one of the most important parameter in evaluating the performance of a multi-processor system.

The critical section merging apparatus500may include a dependence unit530. The dependence unit530generates an instruction dependence graph of instructions in the code. According to an embodiment of the critical section merging apparatus500, the dependence unit530generates the instruction dependence graph by constructing a control flow graph of the code, computing flow dependence and output dependence of instructions by using a forward and disjunctive data flow, computing anti-dependence of the instructions by using a backward and disjunctive data flow, and adding the flow dependence and output dependence of instructions with the anti-dependence of the instructions. It should be appreciated that other techniques may be used to generate the instruction dependence graph.

The critical section merging apparatus500may include a graph summary unit540. The graph summary unit540generates a summarized graph reflecting only instructions that protect and release the critical sections. According to an embodiment of the critical section merging apparatus500, the graph summary unit540generates the summarized graph by building a transitive closure of the instruction dependence graph generated by the dependence unit530, and adding an edge from a node n to a node m if there is a path from the node n to the node m in the instruction dependence graph, where n and m represent instructions that start or release a critical section or instructions of resource accesses. It should be appreciated that other techniques may be used to generate the summarized dependence graph.

The critical section merging apparatus500includes a merger unit550. The merger unit550merges critical sections based on the summarized dependence graph generated by the graph summary unit540. After the summarized dependence graph is created, the merger unit550may select certain critical sections to merge based on rules below:

[Rule] Merge CS1 and CS2 if and only if:(1) CS1 is conjoint with CS2 on any trace; or(2) For any resource access (“RA”), neither (CS1Begin→RA→CS2End) nor (CS2Beigin→RA→CS1End) is in the summarized dependence graph.
CS1 and CS2 above represent critical section 1 and critical section 2, respectively. CSxBegin is the beginning instruction of critical section x; and CSxEnd is the ending instruction of critical section x.

The critical section merging apparatus500may include a general optimization unit560. The general optimization unit560applies general optimization methods such as code motion, code scheduling, copy optimizations to hide resource access latency. The commonly assigned U.S. patent application Ser. No. 10/582,427 entitled “Latency Hiding of Traces Using Block Coloring,” filed by Xiaofeng Guo, Jinquan Dai, Long Li, and Zhiyuan Lv with an effective filing date of Nov. 17, 2005 describes several approaches to optimize code so that resource access latencies may be hid. This patent application is incorporated by reference herein.

FIG. 6is a flowchart of one example process600for merging critical sections according to an example embodiment of the present invention. At block610, the size of critical sections may be minimized by using any critical section minimization approach or a combination of several approaches, for example, using computations outside a critical section to hide resource access latency. At block620, an instruction-level dependence graph may be constructed. In construction an instruction-level dependence graph, later optimizations for hiding resource access latency may need to be considered in adding control dependence to improve the overall performance for critical section merge. At block630, a summarized dependence graph may be created for beginning instructions and ending instructions of critical sections and resource accesses based on the instruction-level dependence graph constructed at block620. Only beginning instructions (“CSBegin”) and ending instructions (“CSEnd”) of critical sections and resource accesses may be reserved in the summarized dependence graph. The summarized dependence graph may be created by building a transitive closure based on the instruction deperidence graph constructed at block620, and adding an edge from a node n to a node m if there is a path from the node n to the node m in the instruction dependence graph, where n and m represent CSBegin, CSEnd, and resource access instructions. Resource accesses that are protected by critical sections will be eliminated from the summarized graph, e.g., for any resource access in the summarized dependence graph, if CSiBegin→RA→CSiEnd, RA will be removed from the summarized dependence graph.

It should be appreciated that any other techniques used for constructing an instruction-level dependence graph and summarizing the dependence graph so constructed may be used at block620and block630. The commonly assigned PCT patent application No. PCT/CN2005/002307 entitled “Automatic Critical Section Ordering for Parallel Program,” filed by Jinquan Dai, Long Li, and Xiaofeng Guo on Dec. 24, 2005 describes approaches to constructing an instruction dependence graph and summarizing the graph so constructed. This patent application is incorporated by reference herein.

At block640, critical sections may be selected to merge based on the rule described above along with theFIG. 5description. Pseudo code for merging critical sections is also shown below:

/* DG is the summarized dependence graph. */For (cp in trace-set) /* cp stands for “critical path”. */{For (CS1 on cp){CS2 = cp.next[CS1]; /* CS2 is a critical section next toCS1 on cp */For (RA in resource-assess-set){If (((CS1.Begin→RA) in DG) && ((RA→CS2.End)in DG)))return false;If (((CS2.Begin→RA) in DG) && ((RA→CS1.End)in DG)))return false;}}}
At block650, optimizations may be applied to hide resource access latency. Any optimization approach may be applied, for example, those mentioned above along with theFIG. 5description.

Although an example embodiment of the disclosed subject matter is described with reference to block and flow diagrams inFIGS. 1-6, persons of ordinary skill in the art will readily appreciate that many other methods of implementing the disclosed subject matter may alternatively be used. For example, the order of execution of the blocks in flow diagrams may be changed, and/or some of the blocks in block/flow diagrams described may be changed, eliminated, or combined.

In the preceding description, various aspects of the disclosed subject matter have been described. For purposes of explanation, specific numbers, systems and configurations were set forth in order to provide a thorough understanding of the subject matter. However, it is apparent to one skilled in the art having the benefit of this disclosure that the subject matter may be practiced without the specific details. In other instances, well-known features, components, or modules were omitted, simplified, combined, or split in order not to obscure the disclosed subject matter.

Various embodiments of the disclosed subject matter may be implemented in hardware, firmware, software, or combination thereof, and may be described by reference to or in conjunction with program code, such as instructions, functions, procedures, data structures, logic, application programs, design representations or formats for simulation, emulation, and fabrication of a design, which when accessed by a machine results in the machine performing tasks, defining abstract data types or low-level hardware contexts, or producing a result.

For simulations, program code may represent hardware using a hardware description language or another functional description language which essentially provides a model of how designed hardware is expected to perform. Program code may be assembly or machine language, or data that may be compiled and/or interpreted. Furthermore, it is common in the art to speak of software, in one form or another as taking an action or causing a result. Such expressions are merely a shorthand way of stating execution of program code by a processing system which causes a processor to perform an action or produce a result.

Program code may be stored in, for example, volatile and/or non-volatile memory, such as storage devices and/or an associated machine readable or machine accessible medium including solid-state memory, hard-drives, floppy-disks, optical storage, tapes, flash memory, memory sticks, digital video disks, digital versatile discs (DVDs), etc., as well as more exotic mediums such as machine-accessible biological state preserving storage. A machine readable medium may include any mechanism for storing, transmitting, or receiving information in a form readable by a machine. Program code may be transmitted in the form of packets, serial data, parallel data, propagated signals, etc., and may be used in a compressed or encrypted format.

Program code may be implemented in programs executing on programmable machines such as mobile or stationary computers, personal digital assistants, set top boxes, cellular telephones and pagers, and other electronic devices, each including a processor, volatile and/or non-volatile memory readable by the processor, at least one input device and/or one or more output devices. Program code may be applied to the data entered using the input device to perform the described embodiments and to generate output information. The output information may be applied to one or more output devices. One of ordinary skill in the art may appreciate that embodiments of the disclosed subject matter can be practiced with various computer system configurations, including multiprocessor or multiple-core processor systems, minicomputers, mainframe computers, as well as pervasive or miniature computers or processors that may be embedded into virtually any device. Embodiments of the disclosed subject matter can also be practiced in distributed computing environments where tasks may be performed by remote processing devices that are linked through a communications network.

Although operations may be described as a sequential process, some of the operations may in fact be performed in parallel, concurrently, and/or in a distributed environment, and with program code stored locally and/or remotely for access by single or multi-processor machines. In addition, in some embodiments the order of operations may be rearranged without departing from the spirit of the disclosed subject matter. Program code may be used by or in conjunction with embedded controllers.

While the disclosed subject matter has been described with reference to illustrative embodiments, this description is not intended to be construed in a limiting sense. Various modifications of the illustrative embodiments, as well as other embodiments of the subject matter, which are apparent to persons skilled in the art to which the disclosed subject matter pertains are deemed to lie within the scope of the disclosed subject matter.