We present a language and compilation framework for productively generating high-performance systolic arrays for dense tensor kernels on spatial architectures, including FPGAs and CGRAs. It decouples a functional specification from a spatial mapping, allowing programmers to quickly explore various spatial optimizations for the same function. The actual implementation of these optimizations is left to a compiler. Thus, productivity and performance are achieved at the same time. We used this framework to implement several important dense tensor kernels. We implemented dense matrix multiply for an Arria-10 FPGA and a research CGRA, achieving 88% and 92% of the performance of manually written, and highly optimized expert (ninja") implementations in just 3% of their engineering time. Three other tensor kernels, including MTTKRP, TTM and TTMc, were also implemented with high performance and low design effort, and for the first time on spatial architectures."

Exploiting Thread-Level Parallelism (TLP) is a promising way to improve the performance of applications with the advent of general-purpose cost effective uni-processor and shared-memory multiprocessor systems. In this paper, we describe the OpenMP* implementation in the Intel/spl reg/ C++ and Fortran compilers for Intel platforms. We present our major design consideration and decisions in the Intel compiler for generating efficient multithreaded codes guided by OpenMP directives and pragmas. We describe several transformation phases in the compiler for the OpenMP* parallelization. In addition to compiler support, the OpenMP runtime library is a critical part of the Intel compiler. We present runtime techniques developed in the Intel OpenMP runtime library for exploiting thread-level parallelism as well as integrating the OpenMP support with other forms of threading termed as sibling parallelism. The performance results of a set of benchmarks show good speedups over the well-optimized serial code performance on Intel/spl reg/ Pentium- and Itanium-processor based systems.

When comparing OpenMP to other parallel programming models, it is easier to choose between OpenMP and MPI than between OpenMP and POSIX Threads (Pthreads). With languages like C and C++, developers have frequently chosen Pthreads to incorporate parallelism in applications. Few developers are currently using OpenMP C/C++, but they should. We show that converting Genehunter, a hand-threaded C program, to OpenMP increases robustness without sacrificing performance. It is also a good case study as it highlights several issues that are important in understanding how OpenMP uses threads. Genehunter is a genetics program which analyzes DNA assays from members of a family tree where a disease is present in certain members and not in others. This analysis is done in an attempt to identify the gene most likely to cause the disease. This problem is called linkage analysis. The same sections of Genehunter were parallelized first by hand-threading and then with OpenMP on Compaq Alpha Tru64 systems. We present examples using both methods and illustrate the tools that proved useful in the process. Our basic conclusion is that, although we could express the parallelism using either Pthreads or OpenMP, it was easier to express the parallelism at a higher level of abstraction. OpenMP allowed enough control to express the parallelism without exposing the implementation details. Also, due to the higher level specification of parallelism with OpenMP, the tools available to assist in the construction of correct and efficient programs provide more useful information than the equivalent tools available for hand-threaded programs. The following concepts are presented: differences between coding styles for OpenMP and Pthreads; data scoping specification for correct parallel programming; adapting a signal based exception mechanism to a parallel program; OpenMP tools: Debuggers—Ladebug, TotalView and Assure; Profilers—Hiprof and GuideView; performance tuning with memory allocation, synchronization, and scheduling. Genehunter does not cover a few important topics in C/C++ programming style, which will be discussed separately. These are: interfacing a GUI team of threads with an OpenMP compute team; coordinating data structure with scheduling. Copyright © 2000 John Wiley & Sons, Ltd.

OpenMP cannot handle some very common programming idioms like recursive control and list or tree data structures. We present the workqueuing model and show it as a natural, flexible, and easy to use extension of OpenMP that is available as a commercial product. A detailed description of workqueuing is presented, together with performance results and pointers to the source code used. Copyright © 2000 John Wiley & Sons, Ltd.

Data dependence analysis techniques are the main component of today's trategies for automatic detection of parallelism. Parallelism detection strategies are being incorporated in commercial compilers with increasing frequency because of the widespread use of processors capable of exploiting instruction-level parallelism and the growing importance of multiprocessors. An assessment of the accuracy of data dependence tests is therefore of great importance for compiler writers and researchers. The tests evaluated in this study include the generalized greatest common divisor test, three variants of Banerjee's test, and the Omega test. Their effectiveness was measured with respect to the Perfect Benchmarks and the linear algebra libraries, EISPACK and LAPACK. Two methods were applied, one using only compile-time information for the analysis, and the second using information gathered during program execution. The results indicate that Banerjee's test is for all practical purposes as accurate as the more complex Omega test in detecting parallelism. However, the Omega test is quite effective in proving the existence of dependences, in contrast with Banerjee's test, which can only disprove, or break dependences. The capability of the Omega test of proving dependences could have a significant impact on several compiler algorithms not considered in this study.

This paper discusses the effectiveness of several dependence tests in Perfect Benchmarks. The tests analyzed include the generalized greatest common divisor test, Banerjee's test and the Omega test. Two methods are applied. One uses only compile-time information for the analysis. The other uses information gathered during program execution. It is shown that, for the codes considered, the Omega test improved the accuracy of the analysis by only 1% when codes are analyzed statically. Furthermore, the dynamic analysis shows that the Omega test does not improve the detected inherent parallelism.