20563509
A theoretical foundation for program transformations to reduce cache thrashing due to true data sharing
Cache thrashing due to true data sharing can degrade the performance of parallel programs significantly. Our previous work showed that parallel task alignment via program transformations can be quite effective for the reduction of such cache thrashing. In this paper, we present a theoretical foundation for such program transformations. Based on linear algebra and the theory of numbers, our work analyzes the data dependences among the tasks created by a fork-join parallel program and determines at compile time how these tasks should be assigned to processors in order to reduce cache thrashing due to true data sharing. Our analysis and program transformations can be easily performed by compilers for parallel computers.
21079011
Task allocation for distributed multimedia processing on wirelessly networked handheld devices
In this paper, we consider distributed multimedia processing on wirelessly networked handheld devices, where multimedia data are heavily processed when transferred between the server and the handheld. We show that, to minimize battery consumption on the handheld, a tradeoff often needs to be made between the energy consumed by computation versus that by data transfer. We develop an energy cost model and present a task partition and allocation scheme to divide the data-processing responsibility between the server and the handheld. Experiments are performed on a Compaq iPAQ device which is connected to a server via a WaveLan interface. Out of 17 programs from the Mediabench suite, our scheme is shown to save energy significantly in 13 of them over the default mode of processing data locally on the handheld.
15223856
Efficient collection of sensor data in remote fields using mobile collectors
This paper proposes using a mobile collector, such as an airplane or a vehicle, to collect sensor data from remote fields. We present three different schedules for the collector: round-robin, rate-based, and min movement. The data are not immediately transmitted to the base station after being sensed but buffered at a cluster head; hence, it is important to ensure the latency is within an acceptable range. We compare the latency and the energy expended of the three schedules. We use the ns-2 network simulator to study the scenarios and illustrate conditions under which rate-based outperforms round-robin in latency, and vice-versa. The benefit of min movement is in minimizing the energy expended
23434511
A Compiler-Assisted Scheme for Adaptive Cache Coherence Enforcement
6048187
Fast video shot retrieval by trace geometry matching in principal component space
Content-based video retrieval technology holds the key to the efficient management and sharing of video content from different sources, in different scales, across different platforms, and shared over different communication channels. In this work we present a fast retrieval algorithm based on matching the geometry of video sequence traces in the principal component space. Techniques to address scale (spatial and temporal) issues, as well as, noise and other possible distortions, such as frame dropping, are discussed. Experimental results demonstrate the effectiveness of the proposed approach.
1229745
Fast Video Shot Retrieval with Luminance Field Trace Indexing and Geometry Matching
Efficient indexing is a key in content-based video retrieval solutions. In this paper we represent video sequences as traces in an appropriate low dimensional space via luminance field scaling and PCA projection, and develop an efficient indexing scheme and trace geometry matching algorithms for fast and robust video retrieval. Simulation results demonstrate that the proposed solution is very fast and accurate in retrieval performance.
2459398
On increasing end-to-end throughput in wireless ad hoc networks
One of the main characteristics of wireless ad hoc networks is their node-centric broadcast nature of communication, leading to interferences and spatial contention between adjacent wireless links. Due to such interferences, pessimistic concerns have been recently raised with respect to the decreasing network capacity in wireless ad hoc networks when the number of nodes scales to several orders of magnitude higher. In this paper, we argue that in all cases of end-to-end data communications - including one-to-k unicast and multicast data dissemination as well as k-to-one data aggregation - the maximum achievable end-to-end data throughput (measured on the sources) heavily depends on the strategy of arranging the topology of transmission between sources and destinations, as well as possible per-node operations such as coding. An optimal strategy achieves better end-to-end throughput than an arbitrary one. We present theoretical studies and critical insights with respect to how these strategies may be designed so that end-to-end throughput may be increased
12665870
Robust statistical methods for securing wireless localization in sensor networks
Many sensor applications are being developed that require the location of wireless devices, and localization schemes have been developed to meet this need. However, as location-based services become more prevalent, the localization infrastructure will become the target of malicious attacks. These attacks will not be conventional security threats, but rather threats that adversely affect the ability of localization schemes to provide trustworthy location information. This paper identifies a list of attacks that are unique to localization algorithms. Since these attacks are diverse in nature, and there may be many unforeseen attacks that can bypass traditional security countermeasures, it is desirable to alter the underlying localization algorithms to be robust to intentionally corrupted measurements. In this paper, we develop robust statistical methods to make localization attack-tolerant. We examine two broad classes of localization: triangulation and RF-based fingerprinting methods. For triangulation-based localization, we propose an adaptive least squares and least median squares position estimator that has the computational advantages of least squares in the absence of attacks and is capable of switching to a robust mode when being attacked. We introduce robustness to fingerprinting localization through the use of a median-based distance metric. Finally, we evaluate our robust localization schemes under different threat conditions.
566308
Reducing Energy Consumption of Disk Storage Using Power-Aware Cache Management
Reducing energy consumption is an important issue for data centers. Among the various components of a data center, storage is one of the biggest consumers of energy. Previous studies have shown that the average idle period for a server disk in a data center is very small compared to the time taken to spin down and spin up. This significantly limits the effectiveness of disk power management schemes. This paper proposes several power-aware storage cache management algorithms that provide more opportunities for the underlying disk power management schemes to save energy. More specifically, we present an off-line power-aware greedy algorithm that is more energy-efficient than Belady’s off-line algorithm (which minimizes cache misses only). We also propose an online power-aware cache replacement algorithm. Our trace-driven simulations show that, compared to LRU, our algorithm saves 16% more disk energy and provides 50% better average response time for OLTP I/O workloads. We have also investigated the effects of four storage cache write policies on disk energy consumption.