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.
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.
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.
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.
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.
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.
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.
6706494
Real-Time Sensor Fusion Framework for Distributed Intelligent Sensors
Multi-sensor data fusion has found widespread applications in industrial and research sectors. The purpose of real time multi-sensor data fusion is to dynamically estimate an improved system model from a set of different data sources, i.e., sensors. This paper presented a systematic and unified real time sensor fusion framework (RTSFF) based on distributed intelligent sensor network. The RTSFF is an open architecture which consists of four layers – the transaction layer, the process fusion layer, the control layer, and the planning layer. This paradigm facilitates distribution of intelligence to the sensor level and sharing of information among sensors, controllers, and other devices in the system. The transducer layer is populated with intelligent sensors. The learning ability of the intelligent sensor model enables it to extract characteristics of monitored signal. The representation issue is managed at this level. After describing the RTSFF, the paper then focuses on the fundamental units of the framework, the highly autonomous transducers.
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.
38619191
Function Granularity Estimation for Multimodal Optimization
In this article, we study the subspace function granularity and present a method to estimate the sharing distance and the optimal population size. To achieve multimodal function optimization, niching techniques diversify the population of Evolutionary Algorithms (EA) and encourage heterogeneous convergence to multiple optima. The key to a successful diversification is effective resource sharing. Without knowing the fitness landscape, resource sharing is usually determined by uninformative assumptions on the number of peaks. Using the Probably Approximately Correct (PAC) learning theory and the ∊-cover concept, a PAC neighborhood for a set of samples is derived. Within this neighborhood, we sample the fitness landscape and compute the subspace Fitness Distance Correlation (FDC) coefficients. Using the estimated granularity feature of the fitness landscape, the sharing distance and the population size are determined. Experiments demonstrate that by using the estimated population size and sharing distance an Evolutionary Algorithm successfully identifies multiple optima.
223678
Automatic classification of digestive organs in wireless capsule endoscopy videos
Wireless Capsule Endoscopy (WCE) allows a physician to examine the entire small intestine without any surgical operation. With the miniaturization of wireless and camera technologies the ability comes to view the entire gestational track with little effort. Although WCE is a technical break-through that allows us to access the entire intestine without surgery, it is reported that a medical clinician spends one or two hours to assess a WCE video, It limits the number of examinations possible, and incur considerable amount of costs. To reduce the assessment time, it is critical to develop a technique to automatically discriminate digestive organs such as esophagus, stomach, small intestinal (i.e., duodenum, jejunum, and ileum) and colon. In this paper, we propose a novel technique to segment a WCE video into these anatomic parts based on color change pattern analysis. The basic idea is that the each digestive organ has different patterns of intestinal contractions that are quantified as the features. We present the experimental results that demonstrate the effectiveness of the proposed method.