14733597
Automatic Validation of Code-Improving Transformations
Programmers of embedded systems often develop software in assembly code due to critical speed and/or space constraints and inadequate support from compilers. Many embedded applications are being used as a component of an increasing number of critical systems. While achieving high performance for these systems is important, ensuring that these systems execute correctly is vital. One portion of this process is to ensure that code-improving transformations on a program will not change the program's semantic behavior. This paper describes a general approach for validation of many low-level code-improving transformations made either by a compiler or specified by hand.
7026270
Branch elimination by condition merging
Conditional branches are expensive. Branches require a significant percentage of execution cycles since they occur frequently and cause pipeline flushes when mispredicted. In addition, branches result in forks in the control flow, which can prevent other code-improving transformations from being applied. In this paper we describe profile-based techniques for replacing the execution of a set of two or more branches with a single branch on a conventional scalar processor. These sets of branches can include tests of multiple variables. For instance, the test if (p1 ! = 0 && p2 ! = 0), which is testing for NULL pointers, can be replaced with if (p1 & p2 ! = 0). Program profiling is performed to target condition merging along frequently executed paths. The results show that eliminating branches by merging conditions can significantly reduce the number of conditional branches executed in non-numerical applications.
58764317
Performance of Multi-hop Communications Using Logical Topologies on Optical Torus Networks
We consider multi-hop communication in optical networks with time-division multiplexing. By using time-division multiplexing, multiple communication channels are supported on each link. As a result, more sophisticated logical topologies can be realized on top of a simpler physical network to improve the communication performance. These logical topologies reduce the number of intermediate hops that a packet travels at the cost of a larger multiplexing degree. On the one hand, the large multiplexing degree increases the packet communication time between hops. On the other hand, reducing the number of intermediate hops reduces the time spent at intermediate nodes. We study the trade-off between the multiplexing degree and the number of intermediate hops needed to realize the logical topologies on top of physical torus networks. Specifically, we examine four logical topologies ranging from the most complex logical all-to-all connections to the simplest logical torus topology. We develop an analytical model that models the maximum throughput and the average packet delay, verify the analytical model through simulations, and study the performance and the impact of system parameters on the performance for these logical topologies.
3570050
Algorithms for Supporting Compiled Communication
We investigate the compiler algorithms to support compiled communication in multiprocessor environments and study the benefits of compiled communication, assuming that the underlying network is an all-optical time-division-multiplexing (TDM) network. We present an experimental compiler, E-SUIF, that supports compiled communication for High Performance Fortran (HPF) like programs on all-optical TDM networks, and describe and evaluate the compiler algorithms used in E-SUIF. We further demonstrate the effectiveness of compiled communication on all-optical TDM networks by comparing the performance of compiled communication with that of a traditional communication method using a number of application programs.
14857157
An MPI prototype for compiled communication on Ethernet switched clusters
Compiled communication has recently been proposed to improve communication performance for clusters of workstations. The idea of compiled communication is to apply more aggressive optimizations to communications whose information is known at compile time. Existing MPI libraries do not support compiled communication. In this paper, we present an MPI prototype, CC-MPI, that supports compiled communication on Ethernet switched clusters. The unique feature of CC-MPI is that it allows the user to manage network resources such as multicast groups directly and to optimize communications based on the availability of the communication information. CC-MPI optimizes one-to-all, one-to-many, all-to-all, and many-to-many collective communication routines using the compiled communication technique. We describe the techniques used in CC-MPI and report its performance.The results show that communication performance of Ethernet switched clusters can be significantly improved through compiled communication.
8426908
Branch Elimination via Multi-variable Condition Merging
Conditional branches are expensive. Branches require a significant percentage of execution cycles since they occur frequently and cause pipeline flushes when mispredicted. In addition, branches result in forks in the control flow, which can prevent other code-improving transformations from being applied. In this paper we describe profile-based techniques for replacing the execution of a set of two or more branches with a single branch on a conventional scalar processor. First, we gather profile information to detect the frequently executed paths in a program. Second, we detect sets of conditions in frequently executed paths that can be merged into a single condition. Third, we estimate the benefit of merging each set of conditions. Finally, we restructure the control flow to merge the sets that are deemed beneficial. The results show that eliminating branches by merging conditions can significantly reduce the number of conditional branches performed in non-numerical applications.
13005280
High dynamic range volume visualization
High resolution volumes require high precision compositing to preserve detailed structures. This is even more desirable for volumes with high dynamic range values. After the high precision intermediate image has been computed, simply rounding up pixel values to regular display scales loses the computed details. In this paper, we present a novel high dynamic range volume visualization method for rendering volume data with both high spatial and intensity resolutions. Our method performs high precision volume rendering followed by dynamic tone mapping to preserve details on regular display devices. By leveraging available high dynamic range image display algorithms, this dynamic tone mapping can be automatically adjusted to enhance selected features for the final display. We also present a novel transfer function design interface with nonlinear magnification of the density range and logarithmic scaling of the color/opacity range to facilitate high dynamic range volume visualization. By leveraging modern commodity graphics hardware and out-of-core acceleration, our system can produce an effective visualization of huge volume data.
27055322
A Fast Evolution Strategies Based Approach To Image Registration
An image registration approach based on Evolution Strategies is proposed. In image registration, an invariant reference needs to be established within each source image, which is unavailable in many cases. To solve this problem, feature configuration (which is defined as the cluster of feature vectors on an image representing homogeneous feature distribution,) is employed to describe the object inside the scene. Instead of finding the correspondence of the entire image, the spatial relationships of the feature configuration in every source image are discovered with Evolution Strategies (ES). While one approach, even this one, may not be suitable for every image domain, the ES approach has many advantages. Compared to some methods, it is computationally effective; compared to other, it is capable of discovering transformations of larger scope (e.g., greater rotation angles or translation distances etc.) The search structure we use is an ellipsoid. The results from various images prove it to be an efficient and effective method.
6386106
Procedural Image Processing for Visualization
We present a novel Procedural Image Processing (PIP) method and demonstrate its applications in visualization. PIP modulates the sampling positions of a conventional image processing kernel (e.g. edge detection filter) through a procedural perturbation function. When properly designed, PIP can produce a variety of styles for edge depiction, varying on width, solidity, and pattern, etc. In addition to producing artistic stylization, in this paper we demonstrate that PIP can be employed to achieve various visualization tasks, such as contour enhancement, focus+context visualization, importance driven visualization and uncertainty visualization. 
 
PIP produces unique effects that often either cannot be easily achieved through conventional filters or would require multiple pass filtering. PIP perturbation functions are either defined by analytical expressions or encoded in pre-generated images. We leverage the programmable fragment shader of the current graphics hardware for achieving the operations in real-time.
40043182
Vertices of degree k in a minimally k-edge-connected digraph
Abstract Let k be a positive integer and D=(V,E) be a minimally k -edge-connected simple digraph. For a vertex x∈V(D) , its outdegree δ + (x) (indegree δ − (x) ) is the number of edges leaving (entering) x . Let u + (D) (resp. u ± (D) and u − (D) ) denote the number of vertices x in D such that δ + (x)=k − (x) (resp. δ + (x)=δ − (x)=k and δ + (x)>k=δ − (x) ). In this paper we prove that u + (D)+2u ± (D)+u − (D)⩾2k+2, which was conjectured by Mader (Combinatorics 2 (1996) 423–449). We also present a lower bound on u + (D)+u ± (D)+u − (D) when |D|⩾4k−1 .
18808395
Stippling and silhouettes rendering in geometry-image space
We present a novel non-photorealistic rendering method that performs all operations in a geometry-image domain. We first apply global conformal parameterization to the input geometry model and generate corresponding geometry images. Strokes and silhouettes are then computed in the geometry-image domain. The geometry-image space provides combined benefits of the existing image space and object space approaches. It allows us to take advantage of the regularity of 2D images and yet still have full access to the object geometry information. A wide range of image processing tools can be leveraged to assist various operations involved in achieving non-photorealistic rendering with coherence.