The plane sweep algorithm, although widely used in computational geometry, does not parallelize efficiently, rendering it incapable of benefiting from recent trends of multi-core CPUs and general-purpose GPUs. Instead of the plane sweep, some researchers have proposed the uniform grid as a foundation for parallel algorithms of computational geometry, but long-standing robustness and performance issues have deterred its wider adoption, at least in the case of overlay analysis. To remedy that, we have developed previously missing methods to perform snap rounding and compute efficiently the winding number of overlay faces on the uniform grid, and we have implemented them as part of an extensible geometry engine to perform polygon overlay with OpenMP on CPUs and CUDA on GPUs. The overall algorithm works on any polygon configuration, either degenerate, overlapping, self-overlapping, disjoint, or with holes. On typical data, it features time and space complexities of O(N + K) where N is the number of edges and K the number of intersections. Its single-threaded performance not only rivals the plane sweep, it achieves a parallel efficiency of 0.9 on our quad-core CPU, with an additional speedup of over 4 on our GPU, a result that should extrapolate to distributed computing and other geometric operations.

Overlapping computations and communication is a key to accelerating stencil applications on parallel computers, especially for GPU clusters. However, such programming is a time-consuming part of the stencil application development. To address this problem, we developed an automatic code generation tool to produce a parallel stencil application with latency hiding automatically from its dataflow model. With this tool, users visually construct the workflows of stencil applications in a dataflow programming model. Our dataflow compiler determines a data decomposition policy for each application, and generates source code that overlaps the stencil computations and communication (MPI and PCIe). We demonstrate two types of overlapping models, a CPU-GPU hybrid execution model and a GPU-only model. We use a CFD benchmark computing 19-point 3D stencils to evaluate our scheduling performance, which results in 1.45 TFLOPS in single precision on a cluster with 64 Tesla C1060 GPUs.

A Trusted Computing Base (TCB) such as a Trusted Platform Module (TPM) or a Mobile Trusted Module plays anessential role for security and privacy applications in embedded systems such as cell phones, smart sensors, and actuators. However, existing hardware-based TCBs lack flexibility for function updates, bug fixes, and feature updates. In this paper, we present a dependable TCB on a Cell Broadband Engine TM processor by providing a hardware and software hybrid TPM. Unlike prior approaches, we provide three new features: (1) TPM functions are implemented in software running in memory isolated by hardware, (2) our software TPM is launched and establishes a chain of trust from the hardware using a secure boot method, and (3) anew TPM command provides dynamic patching to the running software TPM and secure code overlays for the efficient use of the limited resources. We show the feasibility of this hybrid implementation of the TPM by assessing its performance and security properties.

This paper presents the design and implementation of the Cell Broadband Engine TM(Cell/B.E.) isolation loader which is a part of the IBM Software Development Kit for Multicore Acceleration [14]. Our isolation loader is a key component in realizing secure application boot and encrypted application execution. During the application load process, the isolation loader fetches, validates, and decrypts a Synergistic Processor Element (SPE) executable, establishing a chain of trust from the hardware to the application. Since not all applications are SPE executables, we also introduce a general solution. This is a verification service framework in which all applications including system functions can be verified by the isolation loader immediately before execution.We have applied several novel implementation techniques to the isolation loader. The countermeasure implemented in our isolation loader against the substituted-ciphertext attack is given and our staging technique to allocate contiguous working areas for applications is also introduced. The load overhead of this loader including application fetch, validation (RSA-2048/SHA-1), and decryption (RSA-2048 and AES) is less than 50 milliseconds on the 2.8 GHz IBM PowerXCell 8i processor. This overhead is reasonable compared with the 500-millisecond 2048-bit RSA signing needed by the Trusted Platform Module chips [3].