Search

The power of data dependence testing techniques of a parallelizing compiler is its essence to transform and optimize programs. Numerous techniques were proposed in the past, and it is, however, still a challenging problem to evaluate the relative power of these techniques to better understand the data dependence testing problem. In the past, either empirical studies or experimental evaluation results are published to compare these data dependence testing techniques, being not able to convince the research community completely. In this paper, we show a theoretical study on this issue, comparing the power on disproving dependences of existing techniques by proving theorems in a proposed formal system K-DT. Besides, we also present the upper bounds of these techniques and introduce their minimum complete sets. To the best of our knowledge, K-DT is the first formal system used to compare the power of data dependence testing techniques, and this paper is the first work to show the upper bounds and minimum complete sets of data dependence testing techniques. [ABSTRACT FROM AUTHOR]

To further parallelize large-scale nonlinear scientific computing applications, some data dependence techniques for nonlinear subscripts, especially for quadratic subscripts, were proposed in the past. The quadratic programming (QP) test and polynomial variable interval (PVI) test are two representative techniques. The QP test, which serves as an exact but time-consuming technique, always gives conservative results when the coefficient matrix of the quadratic terms is not positive semi-definite, while the PVI test will lose efficiency when there exist mixed polynomials in the dependence equation. Focusing on the dependences caused by quadratic subscripts in nonlinear and irregular programs, we propose an improved nonlinear data dependence test in this paper. We first normalize a quadratic equation which is written in a general form, and determine whether the canonical equation is integer solvable in the region of interest based on the interval equation theory. Experimental results show that, compared with the QP test, our method maintains a much lower time complexity. Furthermore, it can detect more general dependences than other dependence testing methods like the PVI test in terms of quadratic subscripts. [ABSTRACT FROM AUTHOR]

Traditional dependence tests detect dependences with linear array subscripts, but only give passive results to those with non‐linear expressions. It may result in a multitude of pseudo‐dependences. To maximise the parallelism of applications and improve an optimising compiler's ability of detecting dependences between program statements, it is necessary to develop a non‐linear dependence test to eliminate these pseudo‐dependences. This study presents a new non‐linear dependence test by analysing the optimal solution of the quadratic subscripts with the index bounds constraints. The authors prove that the non‐linear dependences caused by subscripts, which can be written in the form of quadratic programming model, are able to be detected, and introduce a non‐linear dependence testing algorithm based on quadratic programming. The effectiveness of this algorithm is verified. The authors developed a prototype implementation of the test with the Open64 compiler and evaluated it using some real world applications from Perfect Club benchmarks and Spec2006 benchmark suites. The experimental results indicate that, compared to existing testing methods, the quadratic programming (QP) test is more efficient for quadratic cases. [ABSTRACT FROM AUTHOR]

Vectorization of programs is crucial for achieving high performance on modern processors with SIMD (Single Instruction Multiple Data) extensions. Programs with IF-statements suffer from control flow divergence that seriously complicates automatic vectorization. Therefore, contemporary compilers employ the IF-conversion approach to convert control flow to data flow, which relies on using predicated execution techniques (i.e., masked or select SIMD instructions). In this paper, we enhance the compiler's capabilities to generate efficiently vectorized code for processors without masked instructions. We improve the state of the art in program vectorization by developing a novel approach—IF-select transformation—which is applicable to arbitrarily nested IF-statements. We implement our approach in the open-source Open64 compiler and evaluate its performance on the SW26010 processor used in the Sunway TaihuLight supercomputer (currently #3 in the TOP500 list) that does not support masked instructions. We extend our vectorization approach by providing an additional LLVM optimization pass to reduce the amount of masked memory accesses on processors without masked instructions, e.g., IBM Power8 and ARMCortex-A8. Experimental results demonstrate the performance advantages of the suggested vectorization techniques. [ABSTRACT FROM AUTHOR]

Feature extraction is very important for steganalysis of content-adaptive JPEG steganography. The scale co-occurrence matrix feature based on a two-dimensional (2-D) Gabor filter is proposed, and diverse quantization for filter residuals is utilized to improve the detection performance. First, the definition of scale co-occurrence matrix based on a 2-D Gabor filter is given and the rules for feature merge are analyzed. Then, the influence of the scale parameter and quantization step on the detection performance of the scale co-occurrence matrix feature is discussed and verified. Next, the effect of diverse quantization strategy is presented. Last, the detailed extraction process of the proposed steganalysis feature is described. The experimental results show that the proposed steganalysis feature can achieve a performance that is competitive with the state-of-the-art steganalysis features when used for the detection of the latest content-adaptive JPEG steganography algorithms. © 2018 SPIE and IS&T [DOI: 10.1117/1.JEI.27.6.063004] [ABSTRACT FROM AUTHOR]