Search

Although technology advancement can pack more and more physical registers in processors, the numbers of architectural registers defined by the instruction set architectures (ISAs) remain relatively small on most modern processors. Exposing more architectural registers to compilers and programmers can improve the effectiveness of compiler optimization and the quality of code. However, increasing the number of architectural registers by simply adding extra bits to the register fields of instructions will expand the code size. Therefore, a better way of exposing more ISA registers without significantly expanding the code size is needed. This paper presents a new ISA called Floating Accumulator Architecture ( FAA ) that can expand the number of ISA registers without increasing the instruction length. Unlike the accumulator architecture whose accumulator is a fixed, special register, FAA dynamically chooses a register from the general-purpose register file as the accumulator. In other words, the accumulator in FAA is an alias to some register in the register file at any instruction, and the alias relation can be dynamically updated by FAA at any program points. Since the accumulator implicitly stores the result, the destination register field can be omitted from FAA instructions, resulting in a saving of 3 to 5 bits for each instruction. This new free instruction bit space can be utilized in two possible ways: doubling the number of ISA registers of modern 32-bit RISC processors or maintaining the number of ISA registers for 16-bit instructions on embedded processors. This paper presents the result of utilizing the free bit space to double the number of ISA registers from 16 to 32 on ARM processors, and experimental results show that performance can be improved by 7.6% on average for MediaBench benchmarks. [ABSTRACT FROM AUTHOR]

Abstract: Effective address calculations for load and store instructions need to compete for ALU with other instructions and hence extra latencies might be incurred to data cache accesses. Fast address generation is an approach proposed to reduce cache access latencies. This paper presents a fast address generator that can eliminate most of the effective address computations by storing computed effective addresses of previous load/store instructions in a dummy register file. Experimental results show that this fast address generator can reduce effective address computations of load and store instructions by about 74% on average for SPECint2000 benchmarks and cut the execution times by 8.5%. Furthermore, when multiple dummy register files are deployed, this fast address generator eliminates over 90% of effective address computations of load and store instructions and improves the average execution times by 9.3%. [Copyright &y& Elsevier]

This paper proposes a simple yet efficient algorithm to distribute loads evenly on multiprocessor computers with hypercube interconnection networks. This algorithm was developed based upon the well-known dimension exchange method. However, the error accumulation suffered by other algorithms based on the dimension exchange method is avoided by exploiting the notion of regular distributions, which are commonly deployed for data distributions in parallel programming. This algorithm achieves a perfect load balance over P processors with an error of 1 and the worst-case time complexity of O(M log2P), where M is the maximum number of tasks initially assigned to each processor. Furthermore, perfect load balance is achieved over subcubes as well—once a hypercube is balanced, if the cube is decomposed into two subcubes by the lowest bit of node addresses, then the difference between the numbers of the total tasks of these subcubes is at most 1. [ABSTRACT FROM AUTHOR]

Dependence analysis algorithms have been proposed to identify parallelism in programs with tree-like data structures. However, they cannot analyze the dependence of statements if recursive data structures of programs are cyclic. This paper presents a technique to identify parallelism in programs with cyclic graphs. The technique consists of three steps: (1) traversal patterns that loops or recursive procedures traverse graphs are identified, and the statements that construct the links of traversal patterns will be located by definition–use chains of recursive data structures; (2) traversal-pattern-sensitive shape analysis is performed to estimate possible shapes of traversal patterns; (3) dependence analysis is performed to identify parallelism using the result of shape analysis. This approach can identify parallelism in programs with cyclic data structures due to the facts that many programs follow acyclic structures (i.e. traversal patterns) to access all nodes on the cyclic data structures. Once the traversal patterns are isolated from the overall data structures, dependence analysis can be applied to identify parallelism. [Copyright &y& Elsevier]

This paper presents a flow-sensitive algorithm to compute interprocedural definition-use chains of dynamic pointer-linked data structures. The goal is to relate the statements that construct links of dynamic pointer-linked data structures (i.e. definitions) to the statements that might traverse the structures through the links (i.e. uses). Specifically, for each statement S that defines links of pointer-linked data structures, the algorithm finds the set of statements that traverse the links which are defined by S. This algorithm solves the definition-use chaining problem by performing backward iterative data flow analysis to compute the set of upward exposed uses at each statement. The results of this algorithm can be used to identify parallelism in programs even with cyclic pointer-linked data structures. [ABSTRACT FROM AUTHOR]

Pointer analysis has been an active research field in recent years. Combining pointer analysis and dependence analysis can identify parallelism in programs with pointers or graphs, which are in turn represented by dynamic pointer-linked data structures. After parallelism is identified, programs can be parallelized and then executed on parallel multiprocessor systems to achieve high performance. The compiler analysis techniques that have been proposed so far can only recognize parallelism in the traversal references of programs with cyclic graphs by analyzing the traversal patterns on graphs. Consequently, only the graph traversal operations will be parallelized while the graph construction operations will be left to be executed in sequential. Although this approach can usually parallelize the most time-consuming part of these programs (the graph traversal operations account for over 90% of total execution times in most programs), the rest of programs that accounts for less than 10% will dominate the execution on multiprocessor systems according to Amdahl''s law. This paper presents a technique that can identify parallelism in the construction operations of programs even with cyclic graphs. This technique is designed to facilitate automatic parallelization of scientific computational applications that construct cyclic graphs to represent adjacent lists, which in turn describe the interactions of simulated objects. Experimental results show this approach can parallelize the construction phase of such programs and achieve good speedup on multiprocessor systems. [Copyright &y& Elsevier]

Probabilistic pointer analysis (PPA) is a compile-time analysis method that estimates the probability that a points-to relationship will hold at a particular program point. The results are useful for optimizing and parallelizing compilers, which need to quantitatively assess the profitability of transformations when performing aggressive optimizations and parallelization. This paper presents a PPA technique using the static single assignment (SSA) form. When computing the probabilistic points-to relationships of a specific pointer, a pointer relation graph (PRG) is first built to represent all of the possible points-to relationships of the pointer. The PRG is transformed by a sequence of reduction operations into a compact graph, from which the probabilistic points-to relationships of the pointer can be determined. In addition, PPA is further extended to interprocedural cases by considering function related statements. We have implemented our proposed scheme including static and profiling versions in the Open64 compiler, and performed experiments to obtain the accuracy and scalability. The static version estimates branch probabilities by assuming that every conditional is equally likely to be true or false, and that every loop executes 10 times before terminating. The profiling version measures branch probabilities dynamically from past program executions using a default workload provided with the benchmark. The average errors for selected benchmarks were 3.80 percent in the profiling version and 9.13 percent in the static version. Finally, SPEC CPU2006 is used to evaluate the scalability, and the result indicates that our scheme is sufficiently efficient in practical use. The average analysis time was 35.59 seconds for an average of 98,696 lines of code. [ABSTRACT FROM PUBLISHER]

The heterogeneous system architecture (HSA), announced by the HSA Foundation, is an approach to integrate central processing unit (CPU) and graphics processing unit (GPU) architectures. The open computing language (OpenCL) is a programming framework that can help utilize heterogeneous architectures. The well-known OpenCL framework, currently in version 1.2, provides programming models for heterogeneous computing. The proposed specifications of OpenCL 2.0 can help utilize HSA features, such as shared virtual memory (SVM). In previous work, we helped enable Portable Computing Language (PoCL)-based OpenCL 1.2 runtime frameworks on the HSA. In this paper, we further extend the PoCL-based runtime on the HSA to support OpenCL 2.0 features. In addition, this is the first work, to our best knowledge, to support PoCL-based OpenCL 2.0 features on HSA. Compared with the widely used OpenCL 1.2, OpenCL 2.0 will support SVM, nested parallelism, pipes, and atomic operations. It can further support parallel design patterns such as tree searches, pointer-based programming and nested parallelism models. Note that PoCL is a widely used open source implementation of OpenCL. Our design flow can help academics to enable OpenCL 2.0 flow on the HSA and benefit further from advanced academic research. The experimental results indicate that our framework provides adequate features to support advanced research. [ABSTRACT FROM AUTHOR]

In recent years, the parallel computing performance on GPUs (graphics processing units) has grown rapidly. As a result, GPUs have been widely applied in computationally intensive applications such as image processing, deep learning, and artificial intelligence. Because these applications can be modeled by multiple GPU kernels, some of which might even be dependent, it is essential to identify an efficient method for scheduling dependent kernels on GPU cores. Simply observing kernel dependencies by executing them in sequence results in performance degradation. Furthermore, dependent kernels generally need to share data. Consequently, without properly scheduling dependent kernels, unnecessary memory accesses and copies will be generated. Neural network model environments include many operators that are suitable for both parallel and dependent kernels. This paper proposes an efficient and clear method for creating a framework to analyze the ONNX (open neural network exchange) model and find the pattern of dependent kernels, which can then be used for scheduling with the GPU architecture. The preliminary experimental results show that this technique improves the overall performance by 8% and reduces the cache miss rate by 14% on average by combining neural network operators and appropriate memory policies. [ABSTRACT FROM AUTHOR]