Virginia Tech - Wake Forest University School of Biomedical Engineering & Sciences
Computer Science Technical Reports @Virginia TechNot a member yet
997 research outputs found
Sort by
On the discrete adjoints of adaptive time stepping algorithms
Get PDFWe investigate the behavior of adaptive time stepping numerical algorithms under the reverse mode of automatic differentiation (AD). By differentiating the time step controller and the error estimator of the original algorithm, reverse mode AD generates spurious adjoint derivatives of the time steps. The resulting discrete adjoint models become inconsistent with the adjoint ODE, and yield incorrect derivatives. To regain consistency, one has to cancel out the contributions of the non-physical derivatives in the discrete adjoint model. We demonstrate that the discrete adjoint models of one-step, explicit adaptive algorithms, such as the Runge--Kutta schemes, can be made consistent with their continuous analogs using simple code modifications. Furthermore, we extend the analysis to cover second order adjoint models derived through an extra forward-mode differentiation of the discrete adjoint code. Two numerical examples support the mathematical derivations
An Adaptive Noise Filtering Algorithm for AVIRIS Data with Implications for Classiï¬cation Accuracy
Get PDFThis paper describes a new algorithm used to adaptively ï¬lter a remote sensing dataset based on signal-to-noise ratios (SNRs) once the maximum noise fraction (MNF) has been applied. This algorithm uses Hermite splines to calculate the approximate area underneath the SNR curve as a function of band number, and that area is used to place bands into “bins†with other bands having similar SNRs. A median ï¬lter with a variable sized kernel is then applied to each band, with the same size kernel used for each band in a particular bin. The proposed adaptive ï¬lters are applied to a hyperspectral image generated by the AVIRIS sensor, and results are given for the identiï¬cation of three different pine species located within the study area. The adaptive ï¬ltering scheme improves image quality as shown by estimated SNRs, and classiï¬cation accuracies improved by more than 10% on the sample study area, indicating that the proposed methods improve the image quality, thereby aiding in species discrimination
On Locally Linear Classification by Pairwise Coupling
Get PDFLocally linear classification by pairwise coupling addresses a nonlinear classification problem by three basic phases: decompose the classes of complex concepts into linearly separable subclasses, learn a linear classifier for each pair, and combine pairwise classifiers into a single classifier. A number of methods have been proposed in this framework. However, these methods have several deficiencies: 1) lack of a systematic evaluation of the framework, 2) naive application of general clustering algorithms to generate subclasses, and 3) no valid method to estimate and optimal number of subclasses. This paper proves the equivalence between three popular combination schemas under general settings, defines several global criterion functions for measuring the goodness of subclasses, and presents a supervised greedy clustering algorithm to minimize the proposed criterion functions. Extensive experiments has also been conducted on a set of benchmark data to validate the effectiveness of the proposed techniques
Revisiting the Speed-versus-Sensitivity Tradeoff in Pairwise Sequence Search
Get PDFThe Smith-Waterman algorithm is a dynamic programming method for determining optimal local alignments between nucleotide or protein sequences. However, it suffers from quadratic time and space complexity. As a result, many algorithmic and architectural enhancements have been proposed to solve this problem, but at the cost of reduced sensitivity in the algorithms or signiï¬cant expense in hardware, respectively. Hence, there exists a need to evaluate the tradeoffs between the different solutions. This motivation, coupled with the lack of an evaluation metric to quantify these tradeoffs leads us to formally deï¬ne and quantify the sensitivity of homology search methods so that tradeoffs between sequence-search solutions can be evaluated in a quantitative manner. As an example, though the BLAST algorithm executes signiï¬cantly faster than Smith-Waterman, we ï¬nd that BLAST misses 80% of the signiï¬cant sequence alignments. This paper then presents a highly efï¬cient parallelization of the Smith-Waterman algorithm on the Cell Broadband Engine, a novel hybrid multicore architecture that drives the PlayStation 3 (PS3) game consoles, and emulates BLAST by repeatedly executing the parallelized Smith-Waterman algorithm to search for a query in a given sequence database. Through an innovative mapping of the optimal Smith-Waterman algorithm onto a cluster of PlayStation 3 nodes, our implementation delivers a 10-fold speed-up over a high-end multicore architecture and an 88-fold speed-up over a non-accelerated PS3. Finally, we compare the performance of our implementation of the Smith-Waterman algorithm to that of BLAST and the canonical Smith-Waterman implementation, based on a combination of three factors — execution time (speed), sensitivity, and the actual cost of de-ploying each solution. In the end, our parallelized Smith-Waterman algorithm approaches the speed of BLAST while maintaining ideal sensitivity and achieving low cost through the use of PlayStation 3 game consoles
A Workload-Aware, Eco-Friendly Daemon for Cluster Computing
Get PDFThis paper presents an eco-friendly daemon that reduces power consumption while better maintaining high performance via a novel behavioral quantification of workload. Specifically, our behavioral quantification achieves a more accurate workload characterization than previous approaches by inferring "processor stall cycles due to off-chip activities." This quantification, in turn, provides a foundation upon which we construct an interval-based, power-aware, run-time algorithm that is implemented within a system-wide daemon. We then evaluate our power-aware daemon in a cluster-computing environment with the NAS Parallel Benchmarks. The results indicate that our novel behavioral quantification of workload allows our power-aware daemon to more tightly control performance while delivering substantial energy savings
CPU MISER: A Performance-Directed Run-Time System for Power Aware Cluster
No full textPerformance and power are two primary design constraints in today’s high-end computing systems. Because of
the inherent dependency between performance and power, reducing power consumption without impacting system
performance is a challenge for the HPC community. In this paper, we present a run-time system as well as its
underlying performance model for performance-directed, power-aware cluster computing. Experimental results
based on physical measurements show that NPB benchmarks benefit up to 36% energy saving and 21% performance
gain. On average, our run-time system leads to 10.7% energy saving with 1.2% performance loss over 9
NPB benchmarks, and is 1.59X improvement in ED2P than CPUSPEED. We also show that our system is performance
directed in the sense that the performance loss for most application is within the user specified limit. We
attribute the promising results to the accurate performance modeling and prediction, and effective performance
control techniques
An Analysis of 10-Gigabit Ethernet Protocol Stacks in Multicore Environments
Get PDFThis paper analyzes the interactions between the protocol stack (TCP/IP or iWARP over 10-Gigabit Ethernet) and its multicore environment. Specifically, for host-based protocols such as TCP/IP, we notice that a significant amount of processing is statically assigned to a single core, resulting in an imbalance of load on the different cores of the system and adversely impacting the performance of many applications. For host-offloaded protocols such as iWARP, on the other hand, the portions of the communication stack that are performed on the host, such as buffering of messages and memory copies, are closely tied with the associated process, and hence do not create such load imbalances. Thus, in this paper, we demonstrate that by intelligently mapping different processes of an application to specific cores, the imbalance created by the TCP/IP protocol stack can be largely countered and application performance significantly improved. At the same time, since the load is a better balanced in host-offloaded protocols such as iWARP, such mapping does not adversely affect their performance, thus keeping the mapping generic enough to be used
with multiple protocol stacks
On Utilization of Contributory Storage in Desktop Grids
Get PDFThe availability of desktop grids and shared computing platforms has popularized the use of contributory resources,
such as desktops, as computing substrates for a variety of applications. However, addressing the exponentially growing
storage demands of applications, especially in a contributory environment, remains a challenging research problem. In
this report, we propose a transparent distributed storage system that harnesses the storage contributed by grid participants
arranged in a peer-to-peer network to yield a scalable, robust, and self-organizing system. The novelty of our work
lies in (i) design simplicity to facilitate actual use; (ii) support for easy integration with grid platforms; (iii) ingenious
use of striping and error coding techniques to support very large data files; and (iv) the use of multicast techniques
for data replication. Experimental results through simulations and an actual implementation show that our system can
provide reliable and efficient storage with large file support for desktop grid applications
Modeling the Goodput of TCP NewReno in Cellular Environments
Get PDFIn this paper, we present an analytical model that characterizes TCP NewReno's goodput as a function of round-trip time, average time duration between handoffs, average number of packets reordered during a handoff, and the congestion window threshold. In cellular networks, the effective packet-loss probability for a flow experiencing handoffs is not exactly equal to the physical-layer packet-loss probability; it also depends on the frequency of handoffs and the number of packets that may arrive out of order at the receiver due to handoffs.
With the emergence of technologies such as WiMax and Ultra Mobile Broadband (UMB), understanding the effect of handoffs and packet reordering on the goodput of TCP becomes very important for the designers of next generation cellular networks. Existing TCP throughput models cannot be used to understand the precise effect of handoffs and the resultant packed reordering on TCP's goodput. In this paper, we present a model of TCP NewReno goodput that captures the effect of handoffs. We validate the model by performing actual file transfers between different hosts that are connected by a router which emulates the wireless environment with handoff events and packet reordering
Study and Redesign of a Semi-public Display: Online Enlightenment
Get PDFSemi-public displays are systems designed to strengthen awareness and collaboration among small co-located group environments. Placed in a semi-public space, Online Enlightenment is a physical device associated with MSN® Messenger to provide information regarding the online status of peers. The raison d'être of the system is to leverage group members’ awareness of their peers’ availability through changes of their online status in order to facilitate meeting scheduling, promote opportunistic collaboration, and foster project teamwork without introducing distraction. At an early stage of the development process, this paper presents the results of a usability study of the system and proposes a redesigned mock-up to address the identified deficiencies