6837612
Group Management Schemes for Implementing MPI collective Communication over IP-Multicast
A new apricot tree cultivar producing early maturing fruit of very good dessert and canning qualities.
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.
18020602
Automatic validation of code-improving transformations on low-level program representations
This paper presents a general approach for automatically validating code-improving transformations on low-level program representations. The approach ensures the correctness of compiler and hand-specified optimizations at the machine instruction level. The method verifies the semantic equivalence of the program representation before and after a transformation to determine the validity of the transformation. To verify that the transformation is semantics preserving, the method derives semantic effects from the instructions that span the execution paths affected by the transformation. The semantics are preserved if the normalized semantic effects are unchanged. A validating compilation system was implemented that is able to validate traditional compiler transformations and more powerful transformations that modify the branch structure of a program.
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.
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.
33385860
An empirical study of reliable multicast protocols over Ethernet-connected networks
Recent advances in multicasting over the Internet present new opportunities for improving communication performance for clusters of workstations. Realizing collective communication over reliable multicast can achieve higher performance than over reliable unicast primitives. The standard IP multicast, however, only supports unreliable multicast, which is difficult to use for building high level message passing routines. Thus, reliable multicast primitives must be implemented over the standard IP multicast to facilitate the use of multicast for high-performance communication on clusters of workstations. Although many reliable multicast protocols have been proposed for the wide area Internet environment, the impact of special features of local area networks (LANs) on the performance of the reliable multicast protocols has not been thoroughly studied. Efficient reliable multicast protocols for LANs must exploit these features to achieve the best performance. In this paper, we present our implementation of four types of reliable multicast protocols: the ACK-based protocols, the NAK-based protocols with polling, the ring-based protocols and the tree-based protocols. The protocols are implemented over IP multicast using the standard UDP interface. We evaluate the performance of the protocols over Ethernet-connected networks, study the impact of some special features of the Ethernet on the performance of the protocols and investigate the methods to exploit these features to improve communication performance.
2000177
A distributed visual surveillance system
We present a distributed vision-based surveillance system. The system acquires and processes grey level images through one or multiple camera units monitoring certain area(s) via a local area network (LAN) and is capable of combining information from multiple camera units to obtain a consensus decision. It can be trained to detect certain type of intrusions, for example pedestrians, a group of pedestrians, vehicles, pets, etc., and minimizes false alerts due to other non-interested intrusions. As a case study, we aim to detect pedestrian/vehicle in an observation area. Our vision-based intrusion detection approach consists of two main steps: background subtraction based hypothesis generation (HG) and appearance-based hypothesis verification (HV). HG hypothesizes possible threats (intrusions), and HV verifies those hypotheses using a Gabor filter for feature extraction and support vector machines (SVMs) for classification. The system has been tested in an unconstrained outdoor environment, illustrating good performance.
33631313
Particle Swarm Optimization with Multiscale Searching Method
This paper presents a new method for effectively searching all global minima of a multimodal function. The method is based on particle swarm optimizer, particles are dynamically divided into serval subgroups of different size in order to explore variable space using various step size simultaneously. In each subgroup, a new scheme is proposed to update the the positions of particles, this scheme takes into consideration the effect of all subgroup seeds. Experimental results for one dimensional, two dimensional and thirty dimensional test suites demonstrated that this method can get overall promising performance over a wide range problems.
16773627
Illustrating surfaces in volume
This paper presents a novel framework for illustrating surfaces in a volume. Surfaces are illustrated by drawing only feature lines, such as silhouettes, valleys, ridges, and surface hatching strokes, and are embedded in volume renderings. This framework promises effective illustration of both surfaces and volumes without occluding or cluttering each other. A two-step approach has been taken: the first step depicts surfaces; the second step performs volume rendering, at the same time embedding surfaces from the first step.
 We introduce Procedurally Perturbed Image Processing (PIP), a new method for enhancing both feature detection and depiction of surfaces. We also present implementation strategies, especially those leveraging modern graphics hardware, for delivering an interactive rendering system. Our implementation results have shown that this mixed form of rendering improves volume visualization and is efficient.
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 .
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.