Search

Although High Performance Embedded Computing(HPEC) has been effectively analyzed on different platforms, there is still room for an in-depth analysis of thread level speculation (TLS), especially at the procedure level. This paper explores the potential parallelism of HPEC from procedure and loop level TLS techniques, and designs the corresponding analysis mechanism and data structures. Our aim is to show the improved performance of various applications used in HPEC. Results from our experiments demonstrate that: 1) the performance of all applications was relatively good, the best tdfir application achieves 221.8x speedup in procedure level speculation whilst a ct application gets a 13x speedup in loop level speculation; 2) HPEC programs can be accelerated by effectively utilizing the computing resources of 16 to 32 cores; 3) Applications, that contain multiple non-severe data-dependency procedure calls, are more suitable for developing parallelism using procedure level TLS technology.

The effective utilization of the abundant computation resources provided by Chip Multi-Processor (CMP? to speedup serial programs, has been received with various methods by many researchers making it a major research hotspot. However, embedded applications have not yet been thoroughly examined in thread level speculation (TLS), as compared to how researchers have focused and addressed other areas. In this paper, we propose kernel data structures of loop and procedure level speculation to accelerate serial programs. To verify the hypothesis, we choose some applications from Mibench, discuss codes and the impact of TLS technology features on the speedup such as coverage parallelism, dependence features, threads size, and core numbers. The experiment results prove that firstly, speculative thread level parallelism is better than instruction level parallel technology. Secondly, the best dijkstra application has a result 13.3x speedup in loop level speculation and a 29.7x speedup in procedure level. Thirdly, in the field of embedded applications, the TLS technology can effectively utilize resources of 4 to 8 core computing and procedure level speculation is better than loop level speculation.

General purpose computing applications have not yet been thoroughly explored in procedure level speculation, especially in the light-weighted profiling way. This paper proposes a light-weighted profiling mechanism to analyze speculative parallelism characterization in several classic general purpose computing applications from SPEC CPU2000 benchmark. By comparing the key performance factors in loop and procedure-level speculation, it includes new findings on the behaviors of loop and procedure-level parallelism under these applications. The experimental results are as follows. The best gzip application can only achieve a 2.4X speedup in loop level speculation, while the best mcf application can achieve almost 3.5X speedup in procedure level. It proves that our light-weighted profiling method is also effective. It is found that between the loop-level and procedure-level TLS, the latter is better on several cases, which is against the conventional perception. It is especially shown in the applications where their ‘hot’ procedure body is concluded as ‘hot’ loops. Category: Embedded computing

Applications typically exhibit extremely different performance characteristics depending on the accelerator. Back propagation neural network (BPNN) has been parallelized into different platforms. However, it has not yet been explored on speculative multicore architecture thoroughly. This paper presents a study of parallelizing BPNN on a speculative multicore architecture, including its speculative execution model, hardware design and programming model. The implementation was analyzed with seven well-known benchmark data sets. Furthermore, it trades off several important design factors in coming speculative multicore architecture. The experimental results show that: (1) the BPNN performs well on speculative multicore platform. It can achieve similar speedup (17.7x to 57.4x) compared with graphics processors (GPU) while provides a more friendly programmability. (2) 64 cores' computing resources can be used efficiently and 4k is the proper speculative buffer capacity in the model.

Graphic Processing Unit (GPU) can achieve remarkable performance for dataset-oriented application such as Back Propagation Network (BPN) under reasonable task decomposition and memory optimization. However, advantages of GPU’s memory architecture are still not fully exploited to parallel BPN. In this paper, we develop and analyze a parallel implementation of a back propagation neural network using CUDA. It focuses on kernels optimization through the use of shared memory and suitable blocks dimensions. The implementation was tested with seven well-known benchmark data sets and the results show promising 33.8x to 64.3x speedups can be realized compared to a sequential implementation on a CPU.

How to make use of multicore computing resources to accelerate the block cryptography applications has become a common concern problem. And the block cryptography applications have not yet been explored in procedure level speculation thoroughly. This paper proposes a procedure level speculation mechanism for accelerating block cryptography applications, including execution model, synchronization strategy and analysis method, etc. It also takes RC5 and AES for examples to analyze their potential speedups and memory accessing characteristics. The experimental results show that: (1) in procedure level speculation, the block cryptography applications can get a nearly liner growth speedup under ECB mode, (2) the severe inter-thread data dependence violations is the key factor that badly affect the system performance under CBC, CFB and OFB modes.

Traditional parallel programming complexity and its constraints on performance facilitate the thread level speculation (TLS) and transactional memory (TM) technology. It's reasonable to combine the benefits of them for exploiting more thread-level parallelism from multi-core architecture. This paper proposes a novel scalable transactional memory architecture supporting speculative parallelization, including its special hardware, compiler and execution support. It's a unified model that supports both TLS and TM semantics with minimal hardware overhead that would help simplify hardware design and improve the system interoperability. PTT makes two additional contributions. First, it proposes a directory-based cache coherence protocol supporting priority determination to achieve the hardware distributed arbitrating mechanism. Second, PTT reduces the complication and complexity of parallel programming work, thus greatly improving parallel programming productivity. The evaluation shows that the new system performs well in most suitable benchmarks, resulting liner growth speedups with increasing cores.

Thread level speculation (TLS) and Transactional memory (TM) are both promising way to enhance the performance of chip multiprocessor (CMP). The complexity of providing efficient memory accesses buffering mechanism in TLS can be supported by TM logically. This paper proposes a speculative multi-threading model based on transactional memory, including its special hardware, compiler and execution support. It's a low-design-complexity approach to effective unified support for both TLS&TM. The experimental results show that our framework is competent to exploit the speculative thread-level parallelism with little parallel degree loss by the parallel & ordered transaction partition strategy.

GPUs have recently been used to accelerate data-parallel applications for they provide easier programmability and increased generality while maintaining the tremendous memory bandwidth and computational power. Most of those applications use CPU as a controller who decides when GPUs run the computing-intensive tasks. This CPU-control-GPU-compute pattern wastes much of CPU's computational power. In this paper, we present a new CPU-GPU cooperative pattern for bioinformatics applications which can use both of CPU and GPU to compute. This pattern includes two parts: 1) the load-balanced data structure which manages data to keep the computational efficiency of GPU high enough when the length distribution of sequences in a sequence database is very uneven; 2) multi-threaded code partition which schedules computing on CPU and GPU in a cooperative way. Using this pattern, we develop CuHMMer based on HMMER which is one of the most important algorithms in bioinformatics. The experimental result demonstrates that CuHMMer get 13x to 45x speed up over available CPU implementations and could also outperform the traditional CUDA implementations which use CPU-control-GPU-compute pattern.

Applications of different categories contain varying levels of data, instruction and thread-level parallelism inherently. It's important to explore the potential coarse-grain thread-level parallelism in different applications to guide the computing resources allocation problem in multicore chips. Up to now, lots of depth researches have been mainly concentrated in the desktop applications. In order to fully understand thread level parallel (TLP) technology's applicability, this paper proposes a criterion for selecting the region to be executed in parallel and analyzes applications' performance impacting factors (computation, coverage parallelism, thread size, inter-thread control dependence feature and inter-thread data dependence feature) by our dynamic profiling tool set. It explores the TLP potentials in desktop, multimedia and High Performance Computing (HPC) fields by demonstrating different speedup potentials that can be exploited using different core numbers. The experimental results show that the majority of desktop applications can only make an effective use of 2 cores' computing resources while most multimedia and HPC applications can use 8-16 cores' computing resources efficiently in the coarse-grain thread-level parallelism. Although TLP technology didn't perform well in the desktop applications that have serious data dependence problem, it's suitable for most multimedia and HPC applications that have large calculation, moderate thread size, and fuzzy dependence but easy to resolve.

The Cell Broadband Engine is a typical heterogeneous chip multiprocessor which provides potential high performance for computing-intensive applications. Our researches focus on how to use Cell to speed up block cryptography applications. In this paper, we propose a mapping framework for block cryptography working in ECB mode and corresponding optimizing strategy. We take four algorithms(RC5, 3DES, AES, and Twofish) as benchmark and implement these four algorithms using Cell programming language. In order to enhance the performance, we present an optimizing strategy and evaluate the effects of the optimizing methods including compiler optimization, dual buffering, vectorization, and loop unrolling. The experiments indicate that all these four algorithms can obtain 5-20 times speedup compared with traditional processors, which shows that our mapping framework and optimizing strategy are effective for the block cryptography algorithms.

Recently many studies have been made to map cryptography algorithms onto graphics processors (GPU), and gained great performances. This paper does not focus on the performance of a specific program exploited by using all kinds of optimization methods algorithmically, but the intrinsic reason which lies in GPU architectural features for this performance improvement. Thus we present a study of several block encryption algorithms(AES, TRI-DES, RC5, TWOFISH and the chained block cipher formed by their combinations) processing on GPU using CUDA. We introduce our CUDA implementations, and investigate the program behavioral characteristics and their impacts on the performance in four aspects. We find that the number of threads used by a CUDA program can affect the overall performance fundamentally. Many block encryption algorithms can benefit from the shared memory if the capacity is large enough to hold the lookup tables. The data stored in device memory should be organized purposely to avoid performance degradation. Besides, the communication between host and device may turn out to be the bottleneck of a program. Through these analyses we hope to find out an effective way to optimize a CUDA program, as well as to reveal some desirable architectural features to support block encryption applications better.

Thread-level speculative (TLS) execution can facilitate automatic parallelization of programs that exhibit complicated memory access patterns, which make complete compile-time dependence analysis either impossible or extremely complicated. The decision on where to speculate can make a large difference in the resulting performance. Up to now, we still lack of appropriate dynamic profiling tool used to find and effectively exploit TLS parallelism. In this paper, we proposed a criterion for selecting the region to be speculatively executed and introduce a dynamic profiling tool set "OpenPro" which can be used to explore TLS parallelism for various applications in depth. The OpenPro can be used to analyze the key factors on TLS parallelism, such as inter-thread data dependence, inter-thread control-flow misprediction and inter-thread load imbalance, and to show the potential speedup to evaluate whether a given application or parts of it are suitable for TLS technology. By profiling the SPEC CPU2000 integer benchmark suite, we found that the TLS technology is not suitable for the traditional desktop applications.

Dataflow predication provides a lightweight full support for predicated execution in dataflow-like architectures. One of its major overhead is the large amounts of fanout trees for distributing predicates to all dependant instructions. Conventional optimizations are predicating only the heads or tails of dataflow chains. Predicating tails offers more speculation but leads to resource contentions and power consumption increasing. Predicating heads is power efficient but reduces speculation and instruction level parallelism. This paper introduces a profile guided technique to combine these optimizations. It uses profiling feedback to guide the compiler in deciding to predicate at the head or tail. By predicating tails on hot paths and predicating heads on infrequent paths, this technique can get performance, power and resource efficiency. Performance evaluation result shows that profile guided optimization performs better in removing fanout trees. It has 10.6% speedup over always predicating heads and 2.5% speedup over always predicating tails in performance.

Thread level speculation (TLS) and transactional memory (TM) are both proposed to address the problem of productivity in multi-core era. Both of them require similar underlying support. In this paper, we propose a low-design-complexity approach to effective unified support for both TLS & TM, by extending a scalable TM model to support TLS. The baseline TM model chosen is LogTM. A distributed hardware arbitration mechanism is also proposed to intensify scalability. This method takes advantage of hardware resources introduced by TM, resulting simplified hardware design. Moreover, it provides rich semantics of both TLS and TM to programmers. Five representative benchmarks have been adopted to evaluate performance characteristics of our TLS model under different memory access patterns. Influence of design choices such as interconnection is also studied. The evaluation shows that the new system performs well in most of the benchmarks in spite of its simplicity, resulting average region speedups around 3.5 at four threads.

General-purpose computing is taking an irreversible step toward on-chip parallel architectures. One way to enhance the performance of chip multiprocessors is the use of thread-level speculation (TLS). Identifying the points where the speculative threads will be spawned becomes one of the critical issues of this kind of architectures. In this paper, a criterion for selecting the region to be speculatively executed is presented to identify potential sources of speculative parallelism in general-purpose programs. A dynamic profiling method has been provided to search a large space of TLS parallelization schemes and where parallelism was located within the application. We analyze key factors impacting speculative thread-level parallelism of SPEC CPU2000, evaluate whether a given application or parts of it are suitable for TLS technology, and study how to balance thread partition for efficiently exploiting speculative thread-level parallelism. It shows that the inter-thread data dependences are ubiquitous and the synchronization mechanism is necessary; Return value prediction and loop unrolling are important to improve performance. The information we got can be used to guide the thread partition of TLS.

How to make use of multicore computing resources to accelerate high performance computing HPC applications has become a common concern problem. However, HPC applications have not yet been explored in thread level speculation TLS thoroughly, especially in the procedure level. This paper proposes a procedure and loop level speculation architecture model for speeding up HPC applications, including its speculative mechanism, analysis method, etc. It also takes several applications from SPLASH2 to analyse their speculative parallel potential together with performance impacting factors. The experimental results show that: 1 the best Barnes application can get a 90.9× speedup in loop level speculation while Lu application can get 40.2× speedup in procedure level speculation; 2 limited parallelism coverage and severe inter-thread data dependence violations badly affect both loop and procedure level speculative parallelism in some HPC applications; 3 It is found that although loop structure is the main source of speculative parallelism, procedure structure can be treated as its important supplement. Especially in applications that their 'hot' iteration body concludes multiple procedure calls, higher speculative procedure level speedup can be achieved than that in loop level speculation.