14353884
Post-pass binary adaptation for software-based speculative precomputation
Recently, a number of thread-based prefetching techniques have been proposed. These techniques aim at improving the latency of single-threaded applications by leveraging multithreading resources to perform memory prefetching via speculative prefetch threads. Software-based speculative precomputation (SSP) is one such technique, proposed for multithreaded Itanium models. SSP does not require expensive hardware support-instead it relies on the compiler to adapt binaries to perform prefetching on otherwise idle hardware thread contexts at run time. This paper presents a post-pass compilation tool for generating SSP-enhanced binaries. The tool is able to: (1) analyze a single-threaded application to generate prefetch threads; (2) identify and embed trigger points in the original binary; and (3) produce a new binary that has the prefetch threads attached. The execution of the new binary spawns the speculative prefetch threads, which are executed concurrently with the main thread. Our results indicate that for a set of pointer-intensive benchmarks, the prefetching performed by the speculative threads achieves an average of 87% speedup on an in-order processor and 5% speedup on an out-of-order processor.
15405424
Intel nehalem processor core made FPGA synthesizable
We present a FPGA-synthesizable version of the Intel Nehalem processor core, synthesized, partitioned and mapped to a multi-FPGA emulation system consisting of Xilinx Virtex-4 and Virtex-5 FPGAs. To our knowledge, this is the first time a modern state-of-the-art x86 design with the out-of-order micro-architecture is made FPGA synthesizable and capable of high-speed cycle-accurate emulation. Unlike the Intel Atom core which was made FPGA synthesizable on a single Xilinx Virtex-5 in a previous endeavor, the Nehalem core is a more complex design with aggressive clock-gating, double phase latch RAMs, and RTL constructs that have no true equivalent in FPGA architectures. Despite these challenges, we are successful in making the RTL synthesizable with only 5% RTL code modifications, partitioning the design across five FPGAs, and emulating the core at 520 KHz. The synthesizable Nehalem core is able to boot Linux and execute standard x86 workloads with all architectural features enabled.
45664762
On Fault-Tolerant Computation of Orthogonal Transforms on Hypercube Computers
40482370
Quantitative evaluation of the register stack engine and optimizations for future Itanium processors
This paper examines the efficiency of the register stack engine (RSE) in the canonical Itanium architecture, and introduces novel optimization techniques to enhance the RSE performance. To minimize spills and fills of the physical register file, optimizations are applied to reduce internal fragmentation in statically allocated register stack frames. Through the use of dynamic register usage (DRU) and dead register value information (DVI), the processor can dynamically guide allocation and deallocation of register frames. Consequently, a speculatively allocated register frame with a dynamically determined frame size can be much smaller than the statically determined frame size, thus achieving minimum spills and fills. Using the register stack engine (RSE) in the canonical Itanium architecture as the baseline reference, we thoroughly study and gauge the tradeoffs of the RSE and the proposed optimizations using a set of SPEC CPU2000 benchmarks built with different compiler optimizations. A combination of frame allocation policies using the most frequent frame size and deallocation policies using dead register information proves to be highly effective. On average, a 71% reduction in aggregate spills and fills can be achieved over the baseline reference.
13981080
Pangaea: A tightly-coupled IA32 heterogeneous chip multiprocessor
Moore's Law and the drive towards performance efficiency have led to the on-chip integration of general-purpose cores with special-purpose accelerators. Pangaea is a heterogeneous CMP design for non-rendering workloads that integrates IA32 CPU cores with non-IA32 GPU-class multi-cores, extending the current state-of-the-art CPU-GPU integration that physically “fuses” existing CPU and GPU designs. Pangaea introduces (1) a resource repartitioning of the GPU, where the hardware budget dedicated for 3D-specific graphics processing is used to build more general-purpose GPU cores, and (2) a 3-instruction extension to the IA32 ISA that supports tighter architectural integration and fine-grain shared memory collaborative multithreading between the IA32 CPU cores and the non-IA32 GPU cores. We implement Pangaea and the current CPU-GPU designs in fully-functional synthesizable RTL based on the production quality RTL of an IA32 CPU and an Intel GMA X4500 GPU. On a 65 nm ASIC process technology, the legacy graphics-specific fixed-function hardware has the area of 9 GPU cores and total power consumption of 5 GPU cores. With the ISA extensions, the latency from the time an IA32 core spawns a GPU thread to the time the thread begins execution is reduced from thousands of cycles to fewer than 30 cycles. Pangaea is synthesized on a FPGA-based prototype and runs off-the-shelf IA32 OSes. A set of general-purpose non-graphics workloads demonstrate speedups of up to 8.8×.
14739906
Helper threads via virtual multithreading
Memory latency dominates the performance of many applications on modern processors, despite advances in caches and prefetching techniques. Numerous prefetching techniques, both in hardware and software, try to alleviate the memory bottleneck. One such technique, known as helper threading improves single-thread performance on a simultaneous multithreaded architecture (SMT), which shares processor resources, including caches, among logical threads. It uses otherwise idle hardware thread contexts to execute speculative threads on behalf of the main thread. Helper threading accelerates a program by exploiting a processor's multithreading capability to run assist threads. Based on the helper threading usage model, virtual multithreading (VMT), a form of switch-on-event user-level multithreading, can improve performance for real-world workloads with a wall-clock speedup of 5.0 to 38.5 percent
206077177
Pentagons and cycle coverings
Let G be a graph of order n ≥ 5k + 2, where k is a positive integer. Suppose that the minimum degree of G is at least (n + k)/2 . We show that G contains k pentagons and a path such that they are vertexdisjoint and cover all the vertices of G. Moreover, if n ≥ 5k + 7, then G contains k + 1 vertex-disjoint cycles covering all the vertices of G such that k of them are pentagons. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 194–208, 2007
9557765
An ILC-Based Adaptive Control for General Stochastic Systems With Strictly Decreasing Entropy
In this paper, a new method for adaptive control of general nonlinear and non-Gaussian unknown stochastic systems has been proposed. The method applies the minimum entropy control scheme to decrease the closed-loop randomness of the output under an iterative learning control (ILC) basis. Both modeling and control of the plant are performed using dynamic neural networks. For this purpose, the whole control horizon is divided into a certain number of time domain subintervals called batches and a pseudo-D-type ILC law is employed to train the plant model and controller parameters so that the entropy of the closed-loop tracking error is made to decrease batch by batch. The method has the advantage of decreasing the output uncertainty versus the advances of batches along the time horizon. The analysis on the proposed ILC convergence is made and a set of demonstrable experiment results is also provided to show the effectiveness of the obtained control algorithm, where encouraging results have been obtained.
206733269
A Fast and Robust Ellipse Detection Algorithm Based on Pseudo-random Sample Consensus
Ellipse is one of the most common features that appears in images. Over years in research, real-timing and robustness have been two very challenging problems aspects of ellipse detection. Aiming to tackle them both, we propose an ellipse detection algorithm based on pseudo-random sample consensus (PRANSAC). In PRANSAC we improve a contour-based ellipse detection algorithm (CBED), which was presented in our previous work. In addition, the parallel thinning algorithm is employed to eliminate useless feature points, which increases the time efficiency of our detection algorithm. In order to further speed up, a 3-point ellipse fitting method is introduced. In terms of robustness, a "robust candidate sequence" is proposed to improve the robustness performance of our detection algorithm. Compared with the state-of-the-art ellipse detection algorithms, experimental results based on real application images show that significant improvements in time efficiency and performance robustness of the proposed algorithm have been achieved.
22789583
Disjoint directed quadrilaterals in a directed graph
Let D be a directed graph of order 4k, where k is a positive integer. Suppose that the minimum degree of D is at least 6k 2. We show that D contains k disjoint directed quadrilaterals with only one exception. 2005 Wiley Periodicals, Inc. J Graph Theory 50: 91–104, 2005
7096747
A Performance Study of Secure Data Mining on the Cell Processor
This paper examines the potential of the Cell processor as a platform for secure data mining on the future volunteer computing systems. Volunteer computing platforms have the potential to provide massive computing power. However, privacy and security concerns prevent using volunteer computing for data mining of sensitive data. The Cell processor comes with a hardware security feature. The secure volunteer data mining can be achieved by using this hardware security feature. In this paper, we present a general security scheme for the volunteer computing, and a secure parallelized K-Means clustering algorithm for the Cell processor. We also evaluate the performance of the algorithm on the Cell secure system simulator. Evaluation results indicate that the proposed secure data clustering outperforms a non-secure clustering algorithm on the general purpose CPU, but incurs a huge performance overhead introduced by the decryption process of the Cell security features.