Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Assembly level interprocedual pointer analysis method based on speculative multithreading

A pointer analysis and inter-procedural technology, applied in the computer field, which can solve the problems of ignoring the influence of pointer variables and data dependencies, and limiting the parallelism of thread aggressive speculation.

Active Publication Date: 2018-12-04
XIAN AERONAUTICAL UNIV
View PDF4 Cites 5 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

Second, the traditional inter-process analysis technology mostly uses conservative pointing analysis, without combining the characteristics of the speculative framework, it always analyzes the pointing relationships on all possible paths, and obtains a large number of pointing relationship sets, which limits the aggressive conjecture parallelism of threads
Third, the data flow analysis library functions in the currently used compilation framework can only analyze and extract data dependencies on scalar variables within the process, ignoring the impact of data dependencies between pointer variables and processes

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Assembly level interprocedual pointer analysis method based on speculative multithreading
  • Assembly level interprocedual pointer analysis method based on speculative multithreading
  • Assembly level interprocedual pointer analysis method based on speculative multithreading

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0059] The following is a further detailed description of the present invention, which is an explanation rather than a limitation of the present invention.

[0060] The present invention provides a method for analyzing pointers between assembly-level processes based on speculative multi-threading. First, at the assembly level, probability-based path analysis cost evaluation is performed for all execution paths, and the candidate speculative paths to be analyzed are constructed, and then the selected All memory operation instructions on the path with the largest cost are subjected to radical point analysis (embodied in claim step 2 and step 3, compared with the traditional process, only the pointing relationship on the path with the largest cost is considered at this time, so used here Radical pointing analysis to explain the difference), on the one hand, use the abstract position set and predicate representation to carry out the pointing analysis in the process, get the accurat...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention discloses an assembly level interprocedual pointer analysis method based on speculative multithreading. Through assembly level interprocedual points-to analysis, a procedure call graph of all processes is established in a source program before the interprocedual points-to analysis is carried out, and after establishment, points-to analysis is carried out in two stages. The method comprises: in the first stage, firstly, establishing a path profiling cost model based on probability, extracting speculative paths selected by all process nodes in the procedure call graph, and then performing points-to analysis in a process; in the second stage, performing interprocedual points-to analysis and interprocedual side-effect calculation, on each process calling point, performing mappingand inverse mapping on points-to relations using a points-to analysis result in a process, to obtain an interprocedual side-effect calculation result, and realize context points-to relation update ofa calling procedure. On this basis, the method guides a whole procedure to perform interprocedual data flow analysis, evaluates data dependence degree among pointer variable memory points-to relations, and obtains a more accurate thread partitioning result.

Description

technical field [0001] The invention belongs to the field of computers, relates to thread-level parallelism and thread-level speculation technology, in particular to an assembly-level inter-procedural pointer analysis method based on speculative multithreading. Background technique [0002] Speculative Multithreading (SpMT), also known as Thread-Level Speculation (TLS), as a mainstream thread-level parallel technology, can identify and extract multiple Threads of underlying control and data dependencies. Under the action of the execution model, these threads are stimulated, executed, verified and submitted according to the correct serial semantics, and are used to realize the automatic speculative parallelism of the entire program. During the speculation process, once a data dependency violation occurs, the current offending thread and all the subsequent threads triggered by it need to be revoked in time, and re-speculation is performed again. Frequent data dependency viola...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06F9/38G06F9/30
CPCG06F9/30145G06F9/3842
Inventor 李美蓉赵银亮程传旭张少应陈庆荣许雯
Owner XIAN AERONAUTICAL UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products